Quantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise

Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.

Figure 1

(a) and (b) Energy levels and (c) and (d) gap for (a) and (c) a hypercube of size $n=9$ and (b) and (d) a complete graph. Both the true gap (blue solid line) and the approximate, analytical, gap (red dashed line) are shown for the hypercube in (c). The analytical gap is only accurate near the true minimum gap, however it is here that transitions to higher-energy levels are most rapid, so the resulting analytical schedule still yields optimal quantum speedup. Energy units are defined by Eq. (14).

Figure 2

Comparison of annealing schedules from Sec. 3 for AQC searching over a hypercube of (a) $n=20$ qubits and (b) $n=5$ qubits for a two-level approximation analytically calculated $s^{\left(c\right)}$ (dashed line) and numerically calculated $s^{\left(n\right)}$ (solid line). Note the different scale for $s$ in (a).

Figure 3

Difference in success probabilities ${\mathsf{P}}_c-{\mathsf{P}}_n$ between the annealing schedule calculated analytically $s^{\left(c\right)}$ and the numerically calculated schedule $s^{\left(n\right)}$ for a single run over a time $\pi /g_{\text{min}}$. The lower inset shows the offset plot of the success probabilities $\mathsf{P}$ versus $t_f{g}_{\text{min}}/\pi$ for $s^{\left(c\right)}$ [red (gray) line] and $s^{\left(n\right)}$ (black line) for $n=5$–20. The upper inset shows the sum of the overlaps of $|E_1\rangle$ with $|m\rangle$ and $|{\psi }_{\text{init}}\rangle$ (${\mathsf{P}}_{\mathrm{FE}}=|\langle E_1|m\rangle {|}^2+|\langle E_1|{\psi }_{\text{init}}\rangle {|}^2$) against $s$ for 20 qubits. Since the relevant avoided crossing is in the space spanned by $|m\rangle$ and $|{\psi }_{\text{init}}\rangle$, a vanishing value ${\mathsf{P}}_{\mathrm{FE}}$ is indicative of very little rotation of the ground state. The vertical dashed line is the position of $g_{\text{min}}$.

Figure 4

Interpolated schedule functions $A(\alpha ,\beta ,\tau )$ (dashed lines) and $B(\alpha ,\beta ,\tau )$ (solid lines) as defined by Eq. (30) for hybrid QW-AQC quantum searching on an (a) ($n=5$)- and (b) ($n=8$)-dimensional hypercube graph for $\alpha =0$ (QW), blue (dark gray) line; $\alpha =0.1$, black line; $\alpha =0.5$, green (medium gray) line; and $\alpha =1$ (AQC), red (light gray) line, calculated numerically following the method in Appendix pp2.

Figure 5

Numerically calculated hybrid schedules $A$ and $B$ against runtime $\tau$ for a quantum search on a five-qubit hypercube graph for (a) $\alpha =0$ (QW) (black line), (b) $\alpha =0.5$ [red (medium gray) line], and (c) $\alpha =1$ (AQC) [cyan (light gray) line]. (d) Success probability of the corresponding searches [indicated by matching color (shade of gray)] against total search time $t_f$, in units given by Eq. (25). Note that this does not show the time evolution against $t$ or $\tau$.

Figure 6

Success probabilities $\mathsf{P}$ of a hybrid QW-AQC quantum search on a five-qubit hypercube graph plotted against the interpolation parameter $\alpha$ and total runtime $t_f$ using optimal schedules (a) $s^{\left(c\right)}$ from analytical solution and (b) $s^{\left(n\right)}$ from numerical solution. Dashed lines with black points indicate the optimal protocol at a given runtime $t_f$. (c) Probability corresponds to the optimal protocol for analytical [blue (dark gray) line] and numerical [green (medium gray) line] solutions. Time units are given by Eq. (25).

Figure 7

Success probabilities $\mathsf{P}$ of a hybrid QW-AQC quantum search on an eight-qubit hypercube graph plotted against the interpolation parameter $\alpha$ and total runtime $t_f$ using optimal schedules (a) $s^{\left(c\right)}$ from analytical solution and (b) $s^{\left(n\right)}$ from numerical solution. Dashed lines with black points indicate the optimal protocol at a given runtime $t_f$. (c) Probability corresponds to the optimal protocol for analytical [blue (dark gray) line] and numerical [green (medium gray) line] solutions. Time units are given by Eq. (25).

Figure 8

Optimal schedule $s\left(\tau \right)$ scaled by $1+1/n$ against the number of qubits $n$ for $90\%$ [blue (dark gray) lines], $93\%$ [red (light gray) lines], $95\%$ [green (medium gray) lines] overlap of $\left|\psi \right(t)\rangle$ with $|m\rangle$ (solid lines) and with $|{\psi }_{\text{init}}\rangle$ (dot-dashed lines). Magenta stars are the transition point, the value of $s\left(\tau \right)$ when the minimum gap $g_{\text{min}}$ occurs. The left inset shows $g_{\text{min}}=min(E_1-E_0)$ (lower black stars) and $min(E_2-E_0)$ [upper red (light gray) stars]. Energy units are given by Eq. (25). The right inset shows the width of the transition $w\left(n\right)=\mathrm{\Delta }s\left(\tau \right)$, the difference between solid and dot-dashed curves of the same color in the main figure. The data were calculated using the AQC search hypercube Hamiltonian mapped to the line (see Appendix pp2).

Figure 9

Search success probability $\mathsf{P}$ at the first peak for a quantum-walk search against qubit number $n$ up to $n=50$. The inset shows the rescaled offset plot of $\mathsf{P}$ against $t$ starting at the bottom with $n=5$ qubits and going to $n=20$. The data were calculated using the hypercube QW search mapped to the line.

Figure 10

Scaling of various quantities related to QW searching: (a) difference from one of the overlap of $|{\psi }_{\text{init}}\rangle$ with $|E_0\rangle$ and $|E_1\rangle$ against number of qubits $n$, (b) difference from one of the marked state with $|E_0\rangle$ and $|E_1\rangle$ (stars) and ${\mathsf{P}}_{max}^{\text{(}\text{QWS})}$ (squares) against $n$, and (c) ${\gamma }_o^{\left(h\right)}-1/n$ versus $n$. Red solid lines are numerical fits, summarized in Table 1. Data were calculated using the hypercube QW search mapped to the line.

Figure 11

Probability $\mathsf{P}$ of finding the marked state versus runtime $t_f$ and interpolation parameter $\alpha$ for the single-avoided-crossing model. White contours show success probability $\mathsf{P}=0.9$ (solid line), $\mathsf{P}=0.99$ (dashed line), and $\mathsf{P}=0.999$ (dotted line).

Figure 12

(a) Value of interpolation parameter $\alpha$ giving the shortest runtime for a fixed success probability $\mathsf{P}$ for a single search, using numerically calculated optimal schedules $s^{\left(n\right)}$ for hypercube dimensions (listed from the top line to the bottom line): $n=12$ (red), $n=14$ (green), $n=16$ (blue), $n=18$ (magenta), and $n=20$ (black). (b) Normalized runtime versus $\mathsf{P}$ for $\alpha$ and hypercube dimension corresponding to (a) (solid lines, same ordering). Dashed lines show the single-avoided-crossing model (large-$N$ limit) for $t_f=g_{\text{min}}/\pi$, the time at which a quantum walk reaches a success probability of one (red), the time for the quantum walk to reach $\mathsf{P}$ (blue), and the time for AQC to reach $\mathsf{P}$ (black).

Figure 13

(a) and (b) Optimal $\alpha$ and (c) and (d) optimal number of runs $r$ for the numerically optimized strategy $s^{\left(n\right)}$ with (a) and (c) $n=12$ and (b) and (d) $n=14$ qubits versus $t_{\text{init}}$ and search success probability $\mathsf{P}$. Here $t_{\text{init}}$ is in inverse energy units, the same as $t_f$ in other figures.

Figure 14

Shaded regions show the fastest protocol: QW (blue), AQC (red), hybrid advantage (yellow), and not achievable in a single run (black). The maximum success probability $\mathsf{P}$ is shown as dashed lines in matching colors versus decoherence rate $\kappa$ for $n=7$. The insets show, from left to right, $\mathsf{P}$ against reduced time $\tau$ for the QW (blue line), the AQC (red line), and the optimal hybrid strategy (thin black line) for $\kappa =0$, 0.0385 (vertical dotted line), and 0.075.

Figure 15

Quantum searching on the $n=7$ hypercube for the QW [red (medium gray)], the AQC [blue (dark gray)], and the hybrid search which yields the maximum $\mathsf{P}$ [orange (light gray)] given by ${\alpha }_o$. (a) Search time $t_o$, which maximizes $\mathsf{P}$ versus $\kappa$. The first data point (not shown) for the AQC and ${\alpha }_o$ series exceeds $t_f=200$, the upper limit of search times sampled. (b) Search probability $\mathsf{P}(t_f,\alpha ,\kappa )$ versus decoherence rate $\kappa$ maximized over search times $0\le t_f\le 200$ (left axis). The value of ${\alpha }_o$ changes as $\kappa$ varies (black, right axis label). The $\alpha$ values sampled are $0.0,0.1,\cdots ,1.0$. The analytic expression (21) is used for the AQC schedule. Time and rate units given are by Eq. (25).

Figure 16

Optimal hybrid search parameter ${\alpha }_o$ and number of runs $r_o$ for multiple-run searching on an $n=7$ hypercube. The optimal search is that which achieves the target success probability $\mathsf{P}$ in the shortest total time $r(t_{\text{init}}+t_f)$, where $t_{\text{init}}$ and $t_f$ are the initialization time and runtime, respectively. (a) and (b) Dependence on $t_{\text{init}}$ and decoherence rate $\kappa$ when $\mathsf{P}$ is set equal to 0.95. The black indicates the region of instantaneous measuring with $t_f=0$, where $r=382$. (c) and (d) Dependence on $\mathsf{P}$ and $\kappa$ when $t_{\text{init}}$ is set equal to 10. Plots (a) and (c) show ${\alpha }_o$ and (b) and (d) show $r_o$. The analytic expression (21) is used for the AQC schedule. Time and rate units are given by Eq. (25).

Figure 17

(a) Probability $\mathsf{P}$ of finding the marked state versus runtime and $\alpha$ for the single-avoided-crossing model, same as in Fig. 11. (b) Same as in (a) with a $30\%$ misspecification of the energy $\mathrm{\Delta }{g}_{\text{min}}$.

Figure 18

(a) Optimal value of $\alpha$ versus success probability $\mathsf{P}$ and $\mathrm{\Delta }{g}_{\text{min}}$ from Eq. (45). (b) Number of repeats $r$ in optimal strategy versus $\mathsf{P}$ and $\mathrm{\Delta }{g}_{\text{min}}$.

Figure 19

(a) Optimal value of $\alpha$ versus success probability $\mathsf{P}$ and $\mathrm{\Delta }q$ from Eq. (47). (b) Number of repeats $r$ in optimal strategy versus $\mathsf{P}$ and $\mathrm{\Delta }q$.