Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds

Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps $L$. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\gg 1$ is ${min}_s{\mathrm{\Delta }}_0\gtrsim {\pi }^2/\left[8{(L+1)}^2\right]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.

Figure 1

Solutions to the eigenvalue equation $H\left(s\right)\psi \left(s\right)=\lambda \left(s\right)\psi \left(s\right)$ are found as solutions to the trancendental equation $f\left(z\right)=s$, corresponding to intersections of the orange line $f\left(s\right)$ with the horizontal blue line $s$. The left figure is for $z=e^{\theta }$ [see Eq. (2)] and the right figure is for $z=e^{i\theta }$ [see Eq. (4)]. Plotted for $L=8$.

Figure 2

Approximate solutions to the trancendental equations (2) and (4) lead to approximate expressions for the eigenvalues and eigenvectors, plotted here with the blue and orange markers [see Eqs. (5), (6), and (8) for the corresponding expressions]. The approximations are close to the exact eigenvalues and eigenvectors (solid black lines) found by numerical diagonalization of the Hamiltonian $H\left(s\right)$, for $s=0.8$ and the small system size $L=32$.