Matthew B. Hastings

Abstract We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped sparse Hamiltonian with no sign problem. This is in sharp contrast with frustration-free stoquastic Hamiltonians, where no such speedup is possible as shown by Bravyi and Terhal (2008). 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 $\mathcal{O}(\mathrm{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^\delta)$ using at most $\exp(n^\delta)$ queries for $\delta= \frac15 - o(1)$. Our construction of the graph is somewhat similar to the ``welded-trees'' construction of Childs et al. (2003), but uses additional ideas for simultaneously achieving a spectral gap and a short adiabatic path.

One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P. There are four different additivity conjectures in quantum information theory, all of which were shown to be equivalent by Shor in 2004. These include the additivity of the Holevo capacity for sending classical information over a quantum channel, and the additivity of the minimum output entropy of a quantum channel. These conjectures relate to whether or not entanglement between different inputs to a quantum channel is useful to increase classical capacity or reduce output entropy. I will present a counter-example to the minimum output entropy conjecture, which implies that all of these additivity conjectures are false. The counter-example is based on a random construction of a channel with a large environment dimension and an even larger system dimension. I will relate this channel to recent work on quantum expanders, and I will propose a slightly weaker additivity conjecture which would give us a two-letter formula for capacity of channels invariant under complex conjugation.

One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P.