Quasiadiabatic Grover search via the Wentzel-Kramers-Brillouin approximation

In various applications one is interested in quantum dynamics at intermediate evolution times, for which the adiabatic approximation is inadequate. Here we develop a quasiadiabatic approximation based on the WKB method, designed to work for such intermediate evolution times. We apply it to the problem of a single qubit in a time-varying magnetic field, and to the Hamiltonian Grover search problem, and show that already at first order the quasiadiabatic WKB captures subtle features of the dynamics that are missed by the adiabatic approximation. However, we also find that the method is sensitive to the type of interpolation schedule used in the Grover problem and can give rise to nonsensical results for the wrong schedule. Conversely, it reproduces the quadratic Grover speedup when the well-known optimal schedule is used.

Figure 1

Evolution of a single qubit ($n=1$) in a magnetic field, under the $g_0\left(r\right)=1$ schedule. (a) Population in the ground state $|m\rangle$ as a function of $r=s=t/t_f$ for $t_f=50$ according to the numerical solution ($|{\chi }_{\mathrm{Num}}\rangle$), the two lowest orders of the WKB approximation ($|{\chi }_{\mathrm{WKB}}^{\left(0\right)}\rangle$ and $|{\chi }_{\mathrm{WKB}}^{\left(1\right)}\rangle$), and the naive adiabatic evolution ($|{\chi }_{\mathrm{GS}}\rangle$). The WKB predictions and the numerical solution exhibit oscillations and are indistinguishable from each other on the scale shown. The adiabatic approximation does not exhibit oscillations. (b) The ground-state population difference between the WKB approximation and the numerical simulation for $t_f=50$. The higher-order WKB approximation provides a significantly better approximation.

Figure 2

Final ground-state population of a single qubit ($n=1$) in a magnetic field, under the $g_0\left(r\right)=1$ schedule. (a) Depopulation of the ground state (i.e., population in the excited state $|m^{\perp }\rangle$) at $r=1$ as a function of $t_f$, comparing the numerical solution ($|{\chi }_{\mathrm{Num}}\rangle$) and the two lowest orders of the WKB approximation ($|{\chi }_{\mathrm{WKB}}^{\left(0\right)}\rangle$ and $|{\chi }_{\mathrm{WKB}}^{\left(1\right)}\rangle$). The lowest order $|{\chi }_{\mathrm{WKB}}^{\left(0\right)}\rangle$ captures the asymptotic behavior of the exact solution, while $|{\chi }_{\mathrm{WKB}}^{\left(1\right)}\rangle$ becomes indistinguishable from the exact solution for $t_f\gtrsim 50$. (b) The difference between the true population in the state $|m^{\perp }\rangle$ at time $r=1$ and the asymptotic prediction of $\frac{1}{4t_f^2}$ obtained from the $1/t_f$ expansion of ${\left|\langle m^{\perp }|{\chi }_{\mathrm{WKB}}^{\left(0\right)}\left(1\right)\rangle \right|}^2$. The asymptotic approximation becomes more accurate as $t_f$ grows.

Figure 3

The time-averaged trace-norm distance [see Eq. (33)] vs $t_f$ for a single qubit ($n=1$) in a magnetic field under the $g_0\left(r\right)=1$ schedule. The distances plotted are between the numerical solution and the adiabatic approximation, and the two lowest-order WKB approximations. The adiabatic and the WKB distances decrease monotonically with $t_f$, with the former being a prediction of the adiabatic theorem in the large $t_f$ limit. The WKB approximations at both orders are consistently better than the adiabatic approximation and the first-order WKB approximation improves upon the zeroth-order WKB approximation.

Figure 4

The time required to achieve a final ground-state probability of 0.95 for the schedules defined in Eqs. (19) ($log$ scale). The straight lines represent exponential scaling fits of $\mathcal{O}\left(2^{1.01n}\right)$, $\mathcal{O}\left(2^{0.667n}\right)$, $\mathcal{O}\left(2^{0.508n}\right)$, and $\mathcal{O}\left(2^{0.463n}\right)$, respectively.

Figure 5

The scaling of $p_{\mathrm{GS}}\left(t_f\right)$ from the numerically exact solution under the $g_3$ schedule, for problem sizes larger than those in Fig. 4. The straight line represents an exponential scaling fit of $\mathcal{O}\left(2^{0.499n}\right)$. Thus, the scaling converges to the expected scaling of $\mathcal{O}\left(2^{n/2}\right)$ predicted by the query complexity bound [21].

Figure 6

The time required to achieve a final ground-state probability of 0.95 for the interpolations defined in Eqs. (19) ($log$ scale), using the WKB approximation at the lowest order. The straight lines represent fits of $\mathcal{O}\left(2^n\right)$, $\mathcal{O}\left(2^{0.51n}\right)$, $\mathcal{O}\left(2^{3.5n^{0.2}}\right)$, and $\mathcal{O}\left(1\right)$, respectively. Thus, the lowest-order WKB approximation predicts the right scaling only for the optimized schedule $g_2\left(r\right)$.

Figure 7

(a) The trace-norm distance between the lowest-order WKB approximation and the numerically exact solution for the four different schedules [Eq. (19)] as a function of the evolution parameter $r$. Here $n=6$ and $t_f=60$. (b) The time-averaged trace-norm distance [Eq. (33)] between the lowest order WKB approximation and the numerically exact solution for the four different schedules [Eqs. (19)]. Here $n=6$. Both panels are consistent with Fig. 6 where $g_2$ recovers the correct scaling. Recall that $g_2$ represents the optimal schedule found in Ref. [7], which provides the best approximation to the numerical evolution.

Figure 8

Final ground-state probability $p_{\mathrm{GS}}$ as function of total evolution time $t_f$ for the Grover problem with $n=4$ for the four different schedules, $g_{\alpha }$ with $\alpha \in \{0,1,2,3\}$ as predicted by the WKB approximation at first order. (a) The $g_0$ and $g_1$ schedules. The rise in $p_{\mathrm{GS}}$ as a function of $t_f$ is very steep and quickly exceeds 1 for both schedules (the $g_0$ curve goes very slightly above 1). The $g_0$ curve rises faster than the $g_1$ curve for $p_{\mathrm{GS}}\le 1$. (b) The $g_2$ and $g_3$ schedules. The rise in the $p_{\mathrm{GS}}$ curve for $g_2$ is much steeper than the rise for the $g_3$ curve. In general, the smaller $\alpha$ is, the larger the steepness in the $p_{\mathrm{GS}}\left(t_f\right)$ curve is. This is consistent with the $t_f^{\mathrm{Th}}\left(n\right)$ scalings obtained in Fig. 6.

Figure 9

The Grover problem with the $g_2\left(r\right)$ schedule for $n\in \{1,\cdots ,5\}$. (a) The time-averaged trace-norm distance [Eq. (33)] between the numerical solution and the lowest-order WKB approximation (solid), i.e., $\overline{\mathcal{D}}(|{\chi }_{\mathrm{WKB}}^{\left(0\right)}\rangle ,|{\chi }_{\mathrm{Num}}\rangle )$, and the time-averaged trace-distance between the numerical solution and the adiabatic approximation (dashed), i.e., $\overline{\mathcal{D}}(|{\chi }_{\mathrm{GS}}\rangle ,|{\chi }_{\mathrm{Num}}\rangle )$. The lowest-order WKB approximation is always better than the adiabatic approximation for all $n$ values we have tested. (For both the solid and dashed lines, the lower the line on the plot is, the lower the value of $n$ is.)

Figure 10

The norm of the WKB approximation at the lowest order as a function of the evolution parameter $r$ for different schedules. $g_2$ represents the optimal schedule, but does not maintain normalization. Note that $g_3$ is significantly more subnormalized that than the rest and dips down to about 0.7 (not shown). Here $n=6$ and $t_f=60$.

Figure 11

The difference between the time-averaged trace-norm distances for the renormalized and unnormalized WKB approximants, for the four different schedules [Eqs. (19)]. Here $n=6$ and $t_f=60$. A negative value means that the unnormalized WKB approximation deviates more from the numerically exact solution than the renormalized WKB approximation.

Figure 12

The time required to achieve a final ground-state probability of 0.95 for the interpolations defined in Eqs. (19) ($log$ scale), using the renormalized WKB approximation at the lowest order. The straight lines represent fits of $\mathcal{O}\left(2^{n/2}\right)$, $\mathcal{O}\left(1\right)$, $\mathcal{O}\left(2^{-n/2}\right)$, and $\mathcal{O}\left(2^{-n/2}\right)$ respectively.

Figure 13

(a) The difference between the predictions of the naive adiabatic approximation ($|{\chi }_{\mathrm{GS}}\left(r\right)\rangle$) and the lowest-order HJ approximation ($|{\chi }_{\mathrm{HJ}}^{\left(0\right)}\rangle$) for the population in the state $|{\chi }_{\mathrm{GS}}\left(1\right)\rangle \equiv |0\rangle$, as a function of the rescaled time parameter $r$, for $t_f=20$. The difference is very small, of the order of ${10}^{-3}$. (b) The population in the state $|m\rangle$ as a function of time for the HJ expansion using the zeroth and first orders, the adiabatic solution, and the numerical solution. The adiabatic solution and the HJ method are indistinguishable on the scale of this plot. Clearly, they do not the capture the oscillations displayed by the numerical solution. Here $t_f=50$.