- This event has passed.

# Prof. Andras Gilyen: Exponential advantage of adiabatic quantum computation with no sign problem

## 27 May 2021 @ 5:30 PM – 6:30 PM IDT

__Abstract:__

We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem.

This strengthens the superpolynomial separation recently proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected

graph, and we can view the adiabatic evolution as an efficient O(poly(n))-time quantum algorithm for finding a specific “EXIT” vertex in the graph given the “ENTRANCE” vertex.

On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the “EXIT” with probability greater than exp(−nδ) using at most exp(nδ) queries for δ=15−o(1).

Our construction of the graph is somewhat similar to the “welded-trees” construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.

### Technion – The Helen Diller Quantum Center (HDQC)

https://technion.zoom.us/j/97494700862