Why adiabatic quantum annealing is unlikely to yield speed-up

Abstract We study quantum annealing for combinatorial optimization with Hamiltonian <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi>H</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:mi>z</mml:mi> <mml:msub> <mml:mi>H</mml:mi> <mml:mi>f</mml:mi> </mml:msub> </mml:math> where H f is diagonal, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>=</mml:mo> <mml:mo>−</mml:mo> <mml:mo fence="false" stretchy="false">|</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo fence="false" stretchy="false">⟩</mml:mo> <mml:mo fence="false" stretchy="false">⟨</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo fence="false" stretchy="false">|</mml:mo> </mml:math> is the equal superposition state projector and z the annealing parameter. We analytically compute the minimal spectral gap, which is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mrow> <mml:mi class="MJX-tex-calligraphic">O</mml:mi> </mml:mrow> </mml:mrow> <mml:mfenced close=")" open="("> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>N</mml:mi> </mml:msqrt> </mml:mrow> </mml:mfenced> </mml:math> with N the total number of states, and its location <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msub> <mml:mi>z</mml:mi> <mml:mo>∗</mml:mo> </mml:msub> </mml:math> . We show that quantum speed-up requires an annealing schedule which demands a precise knowledge of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msub> <mml:mi>z</mml:mi> <mml:mo>∗</mml:mo> </mml:msub> </mml:math> , which can be computed only if the density of states of the optimization problem is known. However, in general the density of states is intractable to compute, making quadratic speed-up unfeasible for any practical combinatorial optimization problems. We conjecture that it is likely that this negative result also applies for any other instance independent transverse Hamiltonians such as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>=</mml:mo> <mml:mo>−</mml:mo> <mml:mrow> <mml:munderover> <mml:mo>∑</mml:mo> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi>n</mml:mi> </mml:munderover> </mml:mrow> <mml:msubsup> <mml:mi>σ</mml:mi> <mml:mi>i</mml:mi> <mml:mi>x</mml:mi> </mml:msubsup> </mml:math> .