General error estimate for adiabatic quantum computing

Most investigations devoted to the conditions for adiabatic quantum computing are based on the first-order correction $⟨{\Psi }_{\mathrm{ground}}\left(t\right)\mid \dot{H}\left(t\right)\mid {\Psi }_{\mathrm{excited}}\left(t\right)⟩∕\mathrm{\Delta }{E}^2\left(t\right)⪡1$. However, it is demonstrated that this first-order correction does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections as well, and shows that the computational error can be made exponentially small—which facilitates significantly shorter evolution times than the above first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time $T$ of order of the inverse minimum energy gap $\mathrm{\Delta }{E}_{\min }$ is sufficient and necessary, i.e., $T=O\left(\mathrm{\Delta }{E}_{\min }^{-1}\right)$. For some examples, these analytical investigations are confirmed by numerical simulations.

Figure 1

(Color online) The original integration contour (black line along real axis) of Eq. (10) is shifted to the complex plane (curved line). The gap structure $\mathrm{\Delta }E\left(s\right)$ leads to singularities near the real axis [green hollow circles, here displayed for $2a=4$ in Eq. (17)], which limit the deformation of the integration contour. The integral in the exponent (dashed line) in Eq. (10) ranges from $0$ to $s^{\prime }$, which gives rise to a real contribution to the exponent off the real axis only.

Figure 2

(Color online) Runtime scaling of the adiabatic Grover search for different interpolation functions $s\left(t\right)$ and a target fidelity of $3∕4$. Solid lines represent fits to full symbol data for $N⩾100$ and shaded regions correspond to fit uncertainties (99% confidence level). These uncertainties arise from the finite resolution when determining the necessary runtime. Hollow circles represent calculations with smoothed $C^{\infty }$-interpolations (compare dotted lines in Fig. 4 and Sec. 5), whereas hollow boxes correspond to the nonlinear interpolation example in Sec. 5.

Figure 3

(Color online) Final error probability $\mid a_1(T{)}^2\mid$ as a function of run-time $T$ for Grover’s algorithm with $N=100$ and $h=\mathrm{const}$. The oscillations stem from the time dependence of $a_0$ in Eq. (10). The solid (blue) line represents the second-order perturbative solution of Eq. (10).

Figure 4

(Color online) Evolution of the interpolation function $s\left(t\right)$ (bottom panel), the spectrum $\sigma \left[s\right(t\left)\right]$ (middle panel), and the occupation of the instantaneous ground state (top panel) versus the rescaled time $\tau =t∕T$ for an adiabatic Grover search problem with $N=100$ states. For each interpolation (different line styles), $T$ was adapted to reach 99% of final fidelity. Thin dotted lines represent $C^{\infty }$-interpolations smoothed with a test function.

Figure 5

(Color online) Evolution of the final and the maximum intermediate (red line) excitations with the run-time $T$ for the example (20). The exponential falloff in the final excitations is only visible, if a smooth $C^{\infty }$-interpolation (black circles) is used, whereas the scaling of the intermediary excitations (red line) is always polynomial. The suppression of the final error for $C^0$ or $C^1$-interpolations (blue squares and green crosses) is also merely polynomial.

Figure 6

(Color online) Occupation of the instantaneous ground state and some selected computational basis states for the Hamiltonian in (20) for an $M=8$ qubit system. Temporarily, the system leaves the instantaneous ground state, but the run-time $T$ has been adjusted such that the final fidelity is 99%.