Low-Depth Mechanisms for Quantum Optimization

One of the major application areas of interest for both near-term and fault-tolerant quantum computers is the optimization of classical objective functions. In this work, we develop intuitive constructions for a large class of these algorithms based on connections to simple dynamics of quantum systems, quantum walks, and classical continuous relaxations. We focus on developing a language and tools connected with kinetic energy on a graph for understanding the physical mechanisms of success and failure to guide algorithmic improvement. This physical language, in combination with uniqueness results related to unitarity, allow us to identify some potential pitfalls from kinetic energy fundamentally opposing the goal of optimization. This is connected to effects from wavefunction confinement, phase randomization, and shadow defects lurking in the objective far away from the ideal solution. As an example, we explore the surprising deficiency of many quantum methods in solving uncoupled spin problems and how this is both predictive of performance on some more complex systems while immediately suggesting simple resolutions. Further examination of canonical problems like the Hamming ramp or bush of implications show that entanglement can be strictly detrimental to performance results from the underlying mechanism of solution in approaches like the quantum approximate optimization algorithm (QAOA). Kinetic energy and graph Laplacian perspectives provide new insights to common initialization and optimal solutions in QAOA as well as new methods for more effective layerwise training. Connections to classical methods of continuous extensions, homotopy methods, and iterated rounding suggest new directions for research in quantum optimization. Throughout, we unveil many pitfalls and mechanisms in quantum optimization using a physical perspective, which aim to spur the development of novel quantum optimization algorithms and refinements.

Popular Summary

From the scheduling of deliveries and computer resources to the design of new vehicles, improved optimization is an application with wide reaching impact. It is believed that quantum computers will eventually be able to accelerate some problems in this space; however, exactly which problems have been challenging to pin down. Rather than try to solve every possible problem, one might be interested in questions like what classical optimization problems quantum computers solve amazingly well, what characterizes such problems, and how quantum algorithms actually solve such problems from an intuitive perspective. Here we try to address some of these points by building physical intuition and insight for how common quantum algorithms for optimization solve problems.

For this work, we try to draw out common physical elements between the most ubiquitous quantum optimization algorithms, like the quantum approximate optimization algorithm, adiabatic quantum optimization, quantum walks, and quantum annealing. Examining these elements for some of the simplest possible problems yields new understanding and insights to shortcomings, simple improvements, and previously unnoted connections to classical optimization techniques. Tests of these insights on more advanced problems suggest that adoption may lead to general improvements in the application of quantum computers to optimization problems.

Figure 1

Sketches of mechanisms in low-depth optimization discussed here. On the left and right a particular wavefunction is depicted where the vertices are computational basis states, $|z⟩$, and colored regions represent wavefunction support, where colors depict relative phases between sites, i.e., the same color regions have the same associated phase. The transition from left to right depicts evolution under a low-depth optimization primitive like QAOA under a potential $f(z)$ and graph Laplacian $L_G$. The different processes depicted represent different mechanisms that may happen at once or at different times in an algorithm. As one progresses in an algorithm, the domain of support for possible solutions contracts and relative phase information accumulates inside domains of support. It is found that subsequent steps have dynamics generated by scattering from the boundary of the domain and randomized relative internal phases. These processes can detract from primary mechanisms of solution, such as concentrating density on a solution where most domain potential points agree, or a measure vote.

Figure 2

Comparison of the mean field and exact single step for the spike potential. As the prototypical example for the success of low-depth optimization strategies over quantum adiabatic optimization, this represents an important case that exemplifies the measure-vote mechanism. The number $p$ behind each method in the label represents the overlap with the exact solution found under a nonlocal search of the parameters $\gamma ,\beta$ (off chart). The distinction between the mean-field and exact cases implies that entanglement is involved in the mechanism, but is strictly detrimental to performance, due to the exact solution coinciding with the solution of the uncoupled spin problem at the foundation of the spike.

Figure 3

Comparison of the mean field and exact single step for the conflicted pair potential. Hyp. and $m$-hyp. refer to the hypercube graph Laplacian and a modified hypercube where the corresponding coefficient is shifted from 1 to 3. The number $p$ behind each method in the label represents the overlap with the exact solution found under a nonlocal search of the parameters $\gamma ,\beta$ (off chart). We see that the flexibility offered by individual modification of graph Laplacian terms allows dramatically improved solutions in this case, although entanglement is not seen to be overwhelmingly beneficial.

Figure 4

Sketches of extremes of improvement or information gain. The arrows follow a depiction of increasing information gain per unit step. The least information gain from the potential comes from any single bitstring of support or vastly separated single bitstrings. As one grows the domain of support, or the number of disjoint domains of support with randomized phases, the information gain increases. The existence of large coherent domains (solid colors) allows for that fraction of the space to effectively gain information, while checkered parts often scatter aimlessly. Finally, as phases within domains align and the domains of support become larger, the information gain per step is maximized. This caricature emphasizes the need for intermediate steps of optimization algorithms to consider phase alignment.

Figure 5

Empirically measured improvement or information gain on different states. Uniform refers to the standard $|+{⟩}^{\otimes n}$, while $L$ uniform refers to a localized Hamming ball of radius $n/2$. The label “rand” refers to randomized relative phases on the support region, and cut refers to coherent cutting applied to the graph Laplacian. Results agree with the developed intuition that phase scattering destroys the ability of a single step to meaningfully improve. Boundary scattering plays a smaller but significant role, and much of the effect of boundary scattering is improved by our coherent cutting procedure.

Figure 6

Sketch of the shadow defect from an exactly solvable potential. We examine the initial and final states of a low-depth optimization step started from the equal superposition of all bitstrings with Hamming distance $n/2$, shown as a blue histogram here. Even on the exactly solvable Hamming distance ramp, shown in light gray, the variational objective shown as a dotted line in the center is completely flat. Even though there is no barrier between the initial state and exact solution, this shadow defect cast over the exact solution makes improvement impossible without additional method refinements. We depict this shadow defect as an artist rendering in gray as with the ramp potential in gray on the left of the figure.

Figure 7

Avoiding spike shadow defects with coherent cuts. In this case, we initialize the wavefunction (yellow) with increased weight on the target state, confined to a Hamming distance of 5 for an eight-qubit system. The final wavefunction without Laplacian cutting (red) degrades in quality at the solution from 0.81 to 0.71 as compared to a case without the spike (gray indicates potential), despite having no support on the spike and a barrierless path to the solution. When the graph Laplacian is used to cut (cut indicated in cross-hatched blue, wavefunction in blue), the solution consistently has an overlap of 0.96.

Figure 8

Avoiding shadow defects with coherent cuts and variational objective modification. Here we show the results for the same initial state and potential that exhibited stalling due to shadow defects. In blue, we show the final state when using a coherent cutting, where the domain of cutting is depicted in the blue cross-hatched box. The orange result shows the uncut result when switching to the Gibbs variational objective. Notably this alleviates some of the problem, but suffers from a similar problem of symmetry in ultimate efficiency, suggesting that the more scalable solution to shadow defects is cutting the graph Laplacian.

Figure 9

QAOA dependence on scale and detuning. The 2D ferromagnetic Ising model and three-regular MaxCut problems are considered with two distinct couplings, and the dramatic performance changes are shown as the second coupling $J_2$ is altered. Separate lines label different values of repetitions ($p$) for the QAOA ansatz. (a) The configuration of couplings in the 2D ferromagnetic grid, where bold and nonbold links indicate the different couplings. (b) The probability of the exact ground state of a 2D ferromagnetic grid decreases as half of the couplings are detuned. Increasing the number of QAOA rounds, $p$, delays the onset of such problems of scale, but performance remains strongly dependent on the separation. (c) A MaxCut-like problem instance that shows nonmonotonic dependence on scale difference, with a curious dip at $J_2\sim 0.52$ where a particular scaling of the couplings apparently substantially decreases performance of the algorithm.

Figure 10

QAOA success probability against the classical continuous extension (CE) baseline in problems of scale. The same instances from Fig. 9 are used, with the horizontal lines indicating the performance of a classical continuous extension, and different lines for different detunings of the algorithm. (a) For $n=12$, 2D ferromagnetic grids, we see that one may need values of $p$ in excess of 10 to match the classical baselines. (b) For $n=14$, three-regular MaxCut problems ($J=1$), we see that, for a range of instances, one often needs a $p\ge 6$ to match the classical baseline.

Figure 11

Relative merit of QAOA relaxations in problems of scale for $p=1$. Here we examine the effect for the same 2D problems of scale in relaxing for QAOA in turn of the parameters $\gamma$ and $\beta$. As predicted from the noninteracting models, allowing free variation of $\gamma$ qualitatively restores the performance of QAOA across the variations in $J_2$, suggesting that this is a simple but powerful modification. Paradoxically, relaxation of only the $\beta$ terms leads to a decrease in performance under a probability of success metric, due to disagreement between the energy function and this objective under this constraint. However, we see that their combination gives a superadditive performance increase, at the cost of the greatest number of free parameters to optimize.

Figure 12

Performance of the iterated rounding technique for two settings of the 2D ferromagnetic. (a) For the challenging $J_2=0.2$ case, as the number of variables are fixed, we see an increase in the probability of success until a critical point around six frozen variables where the performance bifurcates. Even under bifurcation, the performance is strictly better than the unfrozen case. (b) For simpler cases like $J=1$, iterated rounding is wildly successful in improving the quality of the solution for a given value of $p$.