Tunneling and Speedup in Quantum Optimization for Permutation-Symmetric Problems

Tunneling is often claimed to be the key mechanism underlying possible speedups in quantum optimization via quantum annealing (QA), especially for problems featuring a cost function with tall and thin barriers. We present and analyze several counterexamples from the class of perturbed Hamming weight optimization problems with qubit permutation symmetry. We first show that, for these problems, the adiabatic dynamics that make tunneling possible should be understood not in terms of the cost function but rather the semiclassical potential arising from the spin-coherent path-integral formalism. We then provide an example where the shape of the barrier in the final cost function is short and wide, which might suggest no quantum advantage for QA, yet where tunneling renders QA superior to simulated annealing in the adiabatic regime. However, the adiabatic dynamics turn out not be optimal. Instead, an evolution involving a sequence of diabatic transitions through many avoided-level crossings, involving no tunneling, is optimal and outperforms adiabatic QA. We show that this phenomenon of speedup by diabatic transitions is not unique to this example, and we provide an example where it provides an exponential speedup over adiabatic QA. In yet another twist, we show that a classical algorithm, spin-vector dynamics, is at least as efficient as diabatic QA. Finally, in a different example with a convex cost function, the diabatic transitions result in a speedup relative to both adiabatic QA with tunneling and classical spin-vector dynamics.

Popular Summary

Quantum annealing, a quantum computing heuristic that has been realized in commercial hardware, is heralded as a technology that might realize speedups in unstructured, real-world optimization problems. Quantum tunneling through tall and thin barriers in the optimization cost function is often assumed to be the mechanism underlying potential quantum annealing speedups because these kinds of barriers are easier to tunnel through than thermally traverse ones. Here, we provide counterexamples to this assumption by first demonstrating quantum speedup via tunneling relative to a popular classical optimization heuristic—simulated annealing—on a cost function with short and wide barriers. We additionally demonstrate that even when quantum tunneling is possible, it is not necessarily the most efficient quantum speedup mechanism.

Our theoretical work focuses on perturbed Hamming weight oracle problems: We specifically select problems for which the cost function is invariant under permutations of the input bit string because they are analytically and numerically tractable. We find that speedups can occur via a novel and intricate mechanism that we call a diabatic cascade, whereby at intermediate stages, high-energy levels are populated and then depopulated via a sequence of avoided level crossings. This mechanism offers the optimal way to solve several of the problems we study even when they allow for tunneling. We specifically select problems for which the cost function is invariant under permutations of the input bit string; they are furthermore analytically and numerically tractable. Moreover, in the quantum annealing context, these problems can be characterized by a potential energy function that exposes the presence of tunneling during the quantum anneal. Our findings sometimes show that spin-vector dynamics can outperform the speedup of diabatic quantum annealing, although this trend does not hold true in all cases.

We expect that our findings will clarify the mechanisms by which quantum annealing might offer a speedup in information processing.

Figure 1

Fixed plateau cost function with $l=3$, $u=8$.

Figure 2

Results for the fixed plateau problem with $l=0$ and $n=512$. (a) The semiclassical potential with $u=6$ exhibits a double-well degeneracy at the position $s\approx 0.89$ (solid line), but is nondegenerate before and after this point (dotted and dashed lines), thus leading to a discontinuity in the position of its global minimum. The same is observed for the other PHWO problems we study (not shown). (b) The trace-norm distance $\sqrt{1-{|⟨{\psi }_{\text{GS}}|{\psi }_{\text{SC}\text{GS}}⟩|}^2}$ between the quantum ground state $|{\psi }_{\text{GS}}⟩$ (obtained by numerical diagonalization) and the spin-coherent state $|{\psi }_{\text{SC}\text{GS}}⟩$ corresponding to the instantaneous global minimum in $V_{\mathrm{SC}}$, as a function of $t/t_f$. The peak corresponds to the location of the tunneling event, at which point the semiclassical approximation breaks down. (c) $⟨\mathrm{HW}⟩$ in the instantaneous quantum ground state (GS) and the instantaneous ground state as predicted by the semiclassical (SC GS) potential, as a function of $t/t_f$. The sharp drop in the GS and SC GS curves is due to a tunneling event wherein $\sim u$ qubits are flipped, which occurs at the degeneracy point observed in the spin-coherent potential.

Figure 3

(a) The difference in the position of the minimum gap from exact diagonalization and the position of the double-well degeneracy [as shown in Fig. 2 for the fixed plateau) from the semiclassical potential, as a function of $n$ for the fixed plateau, the spike, the 0.5-rectangle, the 0.33-rectangle, the precipice, and Grover problems (log-log scale). (b) The difference in the position of the sudden drop in Hamming weight [as seen in Fig. 2] and the position of the double-well degeneracy from the semiclassical potential [as seen in Fig. 2], as a function of the number of qubits $n$ for the fixed plateau, the spike, the 0.5-rectangle, the 0.33-rectangle, the precipice, and Grover problems (log-log scale).

Figure 4

(a) The height of the barrier between the two wells at the degeneracy point of the spin-coherent potential [as seen in Fig. 2], as a function of $n$ for the fixed plateau, the spike, the 0.5-rectangle, the 0.33-rectangle, the precipice, and Grover problems (log-log scale). (b) The inverse of the minimum gap as a function of $n$ for the fixed plateau, the spike, the 0.5-rectangle, the 0.33-rectangle, the precipice, and Grover problems (log-log scale). The important thing to note is that the order of scaling is preserved in both plots; that is, the steeper the scaling of the barrier height, the steeper the scaling of the inverse minimum gap.

Figure 5

Performance of different algorithms for the fixed plateau problem with $l=0$ and $u=6$. Shown is a log-log plot of the scaling of the time to reach a threshold success probability of 0.9, as a function of system size $n$ for AQA, SQA ($\beta =30$, $N_{\tau }=64$) and SA (${\beta }_f=20$). The time for SQA and SA is measured in single-spin updates (for SQA this is $N_{\tau }$ times the number of sweeps times the number of spins, whereas for SA this is the number of sweeps times the number of spins), where both are operated in “solver” mode as described in Appendix pp4. Also shown is the scaling of the numerator of the adiabatic condition as defined in Eq. (15). The scaling for AQA and the adiabatic condition extracted by a fit using $n\gtrsim 10^2$ is approximately $n^{0.44}$. However, the true asymptotic scaling is likely to be $\sim n^{0.5}$ since the scaling for the fixed plateau problem is clearly lower bounded by the plain Hamming weight problem, for which we have verified ${\tau }_0\sim n^{0.5}$ (see Appendix pp1), and we expect the effect of the plateau to become negligible in the large $n$ limit. SQA scales more favorably ($\sim n^{1.5}$) than SA ($\sim n^5$). We have checked that the scaling of SQA does not change even if we double the number of Trotter slices $N_{\tau }$ and keep the temperature $1/\beta$ fixed.

Figure 6

Diabatic QA verus SA and SVD for the fixed plateau problem with $l=0$. (a) Population $P_i$ in the $i$th energy eigenstate along the diabatic QA evolution at the optimal TTS for $n=512$ and $u=6$. Excited states are quickly populated at the expense of the ground state. By $t/t_f=0.5$ the entire population is outside the lowest nine eigenstates. In the second half of the evolution the energy eigenstates are repopulated in order. This kind of dynamics occurs due to a lining up of avoided-level crossings as seen in Fig. 7. (b) Scaling of the optimal TTS with $n$ for $u=6$, with an optimized number of single-spin updates for SA, and equal $(t_f{)}_{\mathrm{opt}}$ for DQA and SVD. SA scales as $\mathcal{O}(n)$, a consequence of performing sequential single-spin updates. DQA and SVD both approach $\mathcal{O}(1)$ scaling as $n$ increases. Here, we set $p_d=0.7$ in Eq. (14), in order to be able to observe the saturation of SVD’s TTS to the point where a single run suffices, i.e., ${\mathrm{TTS}}_{\mathrm{opt}}=(t_f{)}_{\mathrm{opt}}$. The conclusion is unchanged if we increase $p_d$: this moves the saturation point to larger $n$ for both SVD and DQA, and we have checked that SVD always saturates before DQA. Inset: Scaling as a function of $u$ for $n=1008$. SVD is again seen to exhibit the best scaling, while for this value of $n$ the scaling of DQA and SA is similar (DQA’s scaling with $n$ improves faster than SA’s as a function of $n$, at constant $u$). (c) $⟨\mathrm{HW}⟩$ of the QA wave function and the SVD state (defined as the product of identical spin-coherent states) for $n=512$ and $u=6$. The behavior of the two is identical up to $t/t_f\approx 0.8$, when they begin to differ significantly, but neither displays any of the sharp changes observed in Fig. 2 for the instantaneous ground state. Inset: The trace-norm distance between the DQA and SVD states, showing that they remain almost indistinguishable until $t/t_f\approx 0.8$.

Figure 7

The eigenenergy spectrum along the evolution for the fixed plateau with $n=512$, $l=0$, and $u=16$. Note the sequence of avoided-level crossings that unmistakably line up in the spectrum to reach the ground state. This is the pathway through which DQA is able to achieve a speedup over AQA.

Figure 8

(a)–(c) The optimal TTS for the spike, moving plateau, and 0.5-rectangle problems, respectively. Inset for (a) and (c): The optimal TTS for small problem sizes, where we observe SVD at first scaling poorly. However, as $n$ grows, this difficulty vanishes and it quickly outperforms DQA. (d)–(f) Population $P_i$ in the $i$th energy eigenstate along the diabatic QA evolution at the optimal TTS. We observe similar diabatic transitions for these problems (shown are the cases with $n=512$ and $t_f=9.85$ for the spike, $n=512$ and $t_f=10$ for the moving plateau, and $n=529$ and $t_f=9.8$ for the 0.5-rectangle problems) as we observed for the fixed plateau problem [Fig. 6].

Figure 9

The expectation value of the Hamming weight operator for the quantum ground state, SQA, and AQA for the fixed plateau problem with $n=512$, $l=0$, and $u=6$ and annealing time chosen so as to reach a success probability of 0.9. The expectation value for SQA ($\beta =30$, $N_{\tau }=64$) at a given $t/t_f$ is calculated by averaging over the Hamming weight of the $N_{\tau }$ imaginary-time states at that time and over $10^5$ independent trials. The case of 1500 sweeps is the minimum number of sweeps required for SQA (in “annealer” mode) to reach the threshold ground-state probability of $p_0=0.9$, and similarly for the annealing time value of $t_f=4931.16$ for AQA. While AQA is able to approximately follow the quantum ground state (i.e., the evolution is very close to being adiabatic), the optimal SQA evolution (i.e., that requires the fewest sweeps) for achieving the threshold criterion involves not following the ground state at the minimum gap point and instead thermally relaxing towards the ground state after this point. As shown using the higher $N_{\mathrm{sw}}$ values, only after increasing the number of sweeps by more than 2 orders of magnitude does SQA follow the instantaneous ground state closely.

Figure 10

The optimal TTS for the potential given in Eq. (27). QA outperforms SVD over the range of problem sizes we were able to check. The reason can be seen in the inset, which displays the ground-state probability for SVD and QA for different annealing times $t_f$, with $n=512$. The optimal annealing time for SVD occurs at the first peak in its ground-state probability ($t_f\approx 8.98$), whereas the optimal annealing time for QA occurs at the much larger second peak in its ground-state probability ($t_f\approx 10.91$).

Figure 11

Ground-state probability for a single qubit for different total time $t_f$, evolving under the plain Hamming weight Hamiltonian in Eq. (a5).

Figure 12

Scaling of the $p_{\mathrm{GS}}$ peak of QA for the fixed plateau problem with $l=0$ and $u=6$. (a) $p_{\mathrm{GS}}$ versus $t_f$ curves for several problem sizes $n$. The peak at $t_f\approx 10$ is the cause of the optimal annealing time. (b) For each $p_{\mathrm{GS}}$ versus $t_f$ curve, we fit a Gaussian to the peak. Plotted is the standard deviation of the fitted Gaussians as a function of $n$. An inverse polylogarithmic function provides an excellent fit to this data.