Quantum Speedup by Quantum Annealing

We study the glued-trees problem from A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. Spielman, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (ACM, San Diego, CA, 2003), p. 59. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.

Figure 1

Two binary trees of depth $n=4$ glued randomly. The number of vertices is $N=2^{n+2}-2$. Each vertex is labeled with a randomly chosen $2n$-bit string. $j$ is the column number.

Figure 2

The three lowest eigenvalues of $H(s)$ in the subspace $\{|\mathrm{col}{⟩}_j{\}}_j$, for $\alpha =1/\sqrt{8}$ and $n=10$. ${\Delta }_{jk}={\lambda }_j-{\lambda }_k$ is the gap between the $j$th and $k$th eigenstates, respectively. We divide the evolution in five stages according to $s_1$, $s_2$, $s_3$, and $s_4$ [see text after Eq. (5)], with $s_1<s_{\times }=\alpha /\sqrt{2}=0.25<s_2$ and $s_3=1-s_2<1-s_{\times }<s_4=1-s_1$. Inside [$s_1$, $s_2$] and [$s_3$, $s_4$], the gap ${\Delta }_{10}$ becomes exponentially small in $n$. Elsewhere, ${\Delta }_{10}$ is only polynomially small in $n$. The small (brown) arrows $1\to 2$ and $3\to 4$ depict level transitions for an annealing rate in which $\dot{s}(t)\propto 1/\mathrm{\text{poly}}(n)$.

Figure 3

Overlap of the evolved state $U(t)|a(\mathrm{\text{ENTRANCE}})⟩$ with the instantaneous ground (blue line) and first-excited (red dashed line) states, $|{\varphi }_0\mathbf{(}s(t)\mathbf{)}⟩$ and $|{\varphi }_1\mathbf{(}s(t)\mathbf{)}⟩$, as a function of time. In this case, $n=40$, $\alpha =1/\sqrt{8}$, and $s(t)=t/10000$. We performed the simulation in the column subspace.