What is the Computational Value of Finite-Range Tunneling?

Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite-range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to simulated annealing (SA). For instances with 945 variables, this results in a time-to-99%-success-probability that is $\sim 10^8$ times faster than SA running on a single processor core. We also compare physical QA with the quantum Monte Carlo algorithm, an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X again runs up to $\sim 10^8$ times faster than an optimized implementation of the quantum Monte Carlo algorithm on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a time scale comparable to the D-Wave 2X. However, it is well known that such solvers will become ineffective for sufficiently dense connectivity graphs. To investigate whether finite-range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that algorithms designed to simulate QA scale better than SA. We discuss the implications of these findings for the design of next-generation quantum annealers.

Popular Summary

A better understanding of the physics governing quantum annealers has long been a goal of the scientific community. Here, we apply new insights to construct proof-of-principle optimization problems and program them into the D-Wave 2X quantum annealer. These problems are designed to demonstrate quantum runtime advantages for hard-optimization problems characterized by rugged energy landscapes. For instances involving nearly 1000 binary variables, we find that quantum annealing outperforms single-core simulated annealing by a factor of $10^8$. While simulated annealing requires that energy barriers be climbed over, quantum annealing allows barriers to be tunneled through. We also compare the D-Wave 2X quantum annealer with quantum Monte Carlo, which emulates the behavior of quantum systems on classical processors. While the scaling with size is similar to that of D-Wave, the runtimes are differentiated again by large factors (i.e., up to $10^8$) because of the overhead of simulating quantum tunneling classically.

We note that there are algorithms—such as techniques based on cluster finding—that can exploit the almost-planar connectivity in the current generation of D-Wave processors and still solve problems faster than D-Wave. However, with sufficiently denser connectivity of next-generation annealers, we expect that those methods will become ineffective. Even though our results are encouraging, turning quantum-enhanced optimization into a practical technology requires more work. Next-generation annealers should increase the coherence, density, and control precision of qubits and make it possible to embed higher-order problems of practical relevance. Such problems stand to benefit from quantum optimization because quantum tunneling facilitates traversing tall and narrow barriers in the energy landscape.

We are optimistic that the significant runtime gains we have recovered will carry over to commercially relevant problems that occur in tasks relevant to machine intelligence.

Figure 1

Top: Quantum annealer dynamics are dominated by paths through the mean-field energy landscape that have the highest transition probabilities. Shown is a path that connects local minimum A to local minimum D. Bottom: Mean-field energy $V\mathbf{(}q(\tau )\mathbf{)}$ along the path from A to D, as defined by Eqs. (12) and (16). Finite-range, thermally assisted tunneling can be thought of as a transition consisting of three steps: (i) the system picks up thermal energy from the bath (red arrow up), (ii) the system performs a tunneling transition between the entry and exit points (blue arrow), and (iii) the system relaxes to a local minimum by dissipating energy back into the thermal bath (red arrow down). In transitions $\mathrm{A}\to \mathrm{B}$ or $\mathrm{B}\to \mathrm{C}$, finite-range tunneling considerably reduces the thermal activation energy needed to overcome the barrier. For long distance transitions in the lower part of the energy spectrum, such as $\mathrm{C}\to \mathrm{D}$, the transition rate is still dominated by the thermal activation energy, and the increase in transition rate brought about by tunneling is negligible.

Figure 2

A pair of weak-strong clusters, consisting of 16 qubits in two unit cells of the Chimera graph. All qubits are ferromagnetically coupled and evolve as part of two distinct qubit clusters. At the end of the annealing evolution, the right cluster is strongly pinned downwards due to strong local fields acting on all qubits in that cell. However, the local magnetic field $h_1$ in the left cluster is weaker and serves as a bifurcation parameter. For $h_1<1/2$, the left cluster will reverse its orientation during the annealing sweep and eventually align itself with the right cluster.

Figure 3

Layout of several instances of the weak-strong cluster network problem on the D-Wave 2X processor. Shown are three different sizes with 296, 489, and 945 qubits. Each cluster consists of an eight-qubit unit cell of the Chimera graph. Black dots depict qubits subject to a strong local field $h_R=-1$ while the gray dots represent qubits with the weak field $h_L=0.44$. Blue lines correspond to strong ferromagnetic couplings ($J=1$) and red lines to strong antiferromagnetic couplings ($J=-1$). Note that the graphs are somewhat irregular due to the fact that not all 1152 qubits are operational.

Figure 4

Time to find the optimal solution with 99% probability for different problem sizes. We compare simulated annealing (SA), the quantum Monte Carlo (QMC) method, and the D-Wave 2X. To assign a runtime for the classical algorithms we take the number of spin updates (for SA) or worldline updates (for QMC method) that are required to reach a 99% success probability and multiply that with the time to perform one update on a single state-of-the-art core. Shown are the 50th, 75th, and 85th percentiles over a set of 100 instances. The error bars represent 95% confidence intervals from bootstrapping. This experiment occupied millions of processor cores for several days to tune and run the classical algorithms for these benchmarks. The runtimes for the higher quantiles for the larger problem sizes for the QMC algorithm were not computed because the computational cost was too high. For a similar comparison with the QMC method with different parameters, please see Fig. 12.

Figure 5

Gap of the quantum Hamiltonian for $h_1=0.44$ as a function of the annealing parameter. The solid line is the energy difference between the ground state and the first excited state. The avoided crossing at $t/T_{\mathrm{QA}}=0.62$ corresponds to a minimum gap of 248 MHz. The next excited state is separated by a gap in excess of 2 GHz.

Figure 6

Success probability of QA $p_0$ versus $T$, given by theoretical modeling [Eq. (a2)]. Different colors correspond to different durations of the QA process $T_{\mathrm{QA}}$. Plots correspond to $h_1=0.44$.

Figure 7

Logarithmic plots of the theoretically modeled transition rate $W_{10}(s)$ versus $s$ after the avoided crossing for different temperatures. Red, green, mustard, and blue correspond to $T=12$, 8, 6, and 4 mK, respectively. All plots correspond to $h_1=0.44$ and $T_{\mathrm{QA}}=20\mu \mathrm{s}$.

Figure 8

Plots show the results of the solution of the time-dependent Schrödinger equation for the closed system QA. Probabilities of occupation of ground state and first excited state as a function of QA time are plotted with blue and red points, respectively. The QA time to reach probability of success 0.95 equals 70.9 ns. All plots correspond to $h_1=0.44$.

Figure 9

Probability of success versus $\beta$ for QMC with the D-Wave 2X schedule. Different colors correspond to different number of sweeps (see legend). The embedded plot shows the probability of success at saturation for different number of sweeps. We use periodic boundary conditions, which performed better than open boundary conditions in this case.

Figure 10

Schedule functions for D-Wave 2X chip. The annealing parameter is $s=t/T_{\mathrm{QA}}$ for time $t$ and total annealing time $T_{\mathrm{QA}}$.

Figure 11

Simulation of the probability of occupation of the ground state during the theoretically modeled QA process is shown with a solid black line. The red dashed line gives the equilibrium population of the ground state. Results are given at $T=12\mathrm{mK}$ and $h_1=0.44$. The dashed red line gives the equilibrium population of the ground state. The simulated quantum annealing time is $t_{\mathrm{QA}}=20\mu \mathrm{s}$.

Figure 12

Time to find the optimal solution with 99% probability for different problem sizes. We compare the QMC method with a linear schedule and the D-Wave 2X. To assign a runtime for the QMC code, we take the number of worldline updates that are required to reach a 99% success probability and multiply that with the time to perform one update on a single state-of-the-art core. Shown are the 50th, 75th, and 85th percentiles over a set of 100 instances. The error bars represent 95% confidence intervals from bootstrapping. The runtimes for the higher quantiles for the larger problem sizes for the QMC method were not computed because the computational cost was too high.