Sensitivity of quantum speedup by quantum annealing to a noisy oracle

The glued-trees problem is the only example known to date for which quantum annealing provides an exponential speedup, albeit by partly using excited-state evolution, in an oracular setting. How robust is this speedup to noise on the oracle? To answer this, we construct phenomenological short-range and long-range noise models, and noise models that break or preserve the reflection symmetry of the spectrum. We show that under the long-range noise models an exponential quantum speedup is retained. However, we argue that a classical algorithm with an equivalent long-range noise model also exhibits an exponential speedup over the noiseless model. In the quantum setting, the long-range noise is able to lift the spectral gap of the problem so that the evolution changes from diabatic to adiabatic. In the classical setting, long-range noise creates a significant probability of the walker landing directly on the EXIT vertex. Under short-range noise the exponential speedup is lost, but a polynomial quantum speedup is retained for sufficiently weak noise. In contrast to noise range, we find that breaking of spectral symmetry by the noise has no significant impact on the performance of the noisy algorithms. Our results about the long-range models highlight that care must be taken in selecting phenomenological noise models so as not to change the nature of the computational problem. We conclude from the short-range noise model results that the exponential speedup in the glued-trees problem is not robust to noise, but a polynomial quantum speedup is still possible.

Figure 1

The graph structure of the glued-trees problem. $j=0,1,2,\cdots ,n,n+1,\cdots ,2n+1$ indexes the different columns of the graph starting from one vertex to another.

Figure 2

The smallest three eigenvalues of the Hamiltonian for the case of $n=6$ and $\alpha =1/\sqrt{8}$. We choose a small $n$ so that the exponentially small gaps are visible. (This image is from Ref. [6].)

Figure 3

The minimum time required to reach a success probability of $p_{\mathrm{Th}}=0.95$ as a function of size $n$ for the noiseless quantum annealing glued-trees algorithm. The solid line corresponds to a scaling of $n^{2.8613}$.

Figure 4

Probability of finding the ground state at the end of evolution as a function of $t_f$ for the noiseless glued-trees quantum anneal at problem size $n=10$. Strong oscillations are observed, indicating that the optimal time at which we should terminate the algorithm is subadiabatic.

Figure 5

Populations in the instantaneous ground state, first excited state, and second excited state as a function of the anneal parameter $s$ for the glued-trees problem without any added noise. (a) $n=4$, $t_f=268$; (b) $n=4$, $t_f=1000$; (c) $n=4$, $t_f=4000$; (d) $n=20$ at $t_f=t_f^{\mathrm{Th}}\left(20\right)=12125$ [see Eq. (9)].

Figure 6

The median success probability $p_{\mathrm{GS}}$ at the end of an evolution of duration $t_f^{\mathrm{Th}}\left(n\right)$ as a function of $n$ for $\epsilon =0$, ${10}^{-3}$, ${10}^{-2}$, $5\times {10}^{-2}$, ${10}^{-1}$, $5\times {10}^{-1}$. $\epsilon =0$ is the noiseless evolution ($\epsilon$ increases from top to bottom at $n=1$). $t_f^{\mathrm{Th}}\left(n\right)$ is chosen so that the success probability for the noiseless probability is just above 0.95. The error bars are obtained by bootstrap sampling over 300 realizations of the noise. (a) The long-range symmetric noise model. (b) The long-range asymmetric noise model. (c) The short-range symmetric noise model. (d) The short-range asymmetric noise model.

Figure 7

Median success probability vs the log (base 10) of the strength of the noise for the LS model for several larger values of the problem size $n$. There is a fall, then a rise, and then again a fall in this success probability as a function of $\epsilon$ for all values of $n$ displayed.

Figure 8

Base-2 logarithm of the median ground-state success probability, as a function of problem size $n$, or the logarithm of the problem size ${log}_{2}n$, at different noise levels $\epsilon$. Polynomial fits of the form $O\left(n^{\alpha }\right)$ are performed for the long-range models. Exponential fits of the form $O\left(2^{\alpha n}\right)$ are performed for the short-range models. This is done for $\epsilon \in \{{10}^{-3},{10}^{-2},5\times {10}^{-2},{10}^{-1},5\times {10}^{-1}\}$ for the short-range models ($\epsilon$ increases from top to bottom at $n=1$). For the long-range models, the set of values of $\epsilon$ is the same as for the short-range models, except that we omit the $\epsilon ={10}^{-2}$ case since it shows anomalous behavior (i.e., a rise and a fall) which does not fit a decay. The scaling coefficient $\alpha$ as a function of the noise $\epsilon$ is shown in Fig. 9. (a) The long-range symmetric noise model. (b) The long-range asymmetric noise model. (c) The short-range symmetric noise model. (d) The short-range asymmetric noise model.

Figure 9

The exponential scaling coefficient $\alpha$ as a function of the base-10 logarithm of the strength of the noise $\epsilon$ for the short-range noise models. (The long-range noise models do not show an exponential scaling.) The scaling coefficient $\alpha$ is obtained by performing an exponential fit of the form $O\left(2^{\alpha n}\right)$, to the median success probability, $p_{\mathrm{GS}}\left(t_f^{\mathrm{Th}}\right)$ vs $n$ curves [shown in Figs. 8 and 8]. The dashed horizontal line at $\alpha =-1/3$ represents the scaling coefficient below which the speedup, over the best possible classical algorithm to solve the glued-trees problem, is lost. Thus, the short-range models lose the speedup for $\epsilon \gtrsim {10}^{-1.75}$. The error bars are 95% confidence intervals. While some error bars are large due to the fits being performed on a small number of data points, the trend in the data is clear.

Figure 10

The scaling of the median minimum gap (log scale) as a function of problem size $n$ for the four noise models with $\epsilon \in \{{10}^{-4},{10}^{-3},{10}^{-2}\}$. The solid blue line represents the noiseless algorithm ($\epsilon =0$), which has an exponentially closing minimum gap. (a) Long-range symmetric. (b) Long-range asymmetric. (c) Short-range symmetric. (d) Short-range asymmetric. The long-range models display a constant gap with problem size, while the short-range models exhibit an exponentially decreasing gap with problem size. This is consistent with the perturbative argument given in Eq. (21).

Figure 11

Two random instances of the long-range symmetric noise for $n=20$ and $t_f=12125$, with $\epsilon ={10}^{-3}$ and $\epsilon ={10}^{-2}$. (a) The spectral gap between the ground state and the first excited state for the two noisy instances and the noiseless case ($\epsilon =0$), around $s=s^{*}$, i.e., near the location of the first exponentially closing gap in the noiseless problem. Both noisy instances increase the spectral gap from its value in the noiseless problem, with the increase being larger in the $\epsilon ={10}^{-2}$ case. (b) The populations in the lowest three eigenstates of the noisy Hamiltonian as a function of the anneal parameter $s$, for $\epsilon ={10}^{-3}$. The diabatic transitions do not happen as cleanly as in the noiseless case [shown in Fig. 5]. (c) As in (b), for $\epsilon ={10}^{-2}$. The dynamics are very close to adiabatic.

Figure 12

The median success probability $p_{\mathrm{GS}}$ for the normalized long-range asymmetric noise case at the end of an evolution of duration $t_f^{\mathrm{Th}}\left(n\right)$, with $\epsilon$ increasing from top to bottom at $n=1$. $t_f^{\mathrm{Th}}\left(n\right)$ is chosen so that the success probability for the noiseless probability is just above 0.95. Error bars were obtained by bootstrap sampling over 300 realizations of the noise.

Figure 13

The smallest instance of the glued-trees problem. The graph is labeled with three bits. The naming is chosen so as to minimize the Hamming distance between vertices joined by an edge.