Embedding Overhead Scaling of Optimization Problems in Quantum Annealing

In order to treat all-to-all-connected quadratic binary optimization problems (QUBOs) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the topology of the hardware. The embedding of fully connected graphs—typically found in industrial applications—incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here, we investigate this embedding penalty of established planar embedding schemes such as square-lattice embedding, embedding on a chimera lattice, and the Lechner-Hauke-Zoller scheme, using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggests a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers, and could also serve as a benchmark for improvements of the standard quantum annealing protocol.

Popular Summary

Adiabatic quantum optimization has the potential to revolutionize several fields of research, as well as industrial optimization. However, many real-world optimization problems require an all-to-all graph topology. For example, any optimization problem with constraints that might be on a sparse graph becomes an all-to-all optimization problem when cast as a quadratic binary optimization problem for a quantum annealer. To accommodate an all-to-all topology, the problem has to be embedded into the hardwired topology of currently available quantum annealing hardware. A typical example is the traveling-salesperson problem: not only is there a quadratic overhead in the number of variables when enforcing a closed-loop topology but there is an additional quadratic overhead when embedding the tour in a sparse-graph quantum annealer. While this in itself can be discouraging, here we demonstrate that commonly used embedding schemes not only incur a space overhead but also a significant overhead in the time to solution.

Using large-scale quantum Monte Carlo simulations, we demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers that can easily accommodate an all-to-all topology. Our work highlights the need to develop new hardware paradigms that overcome the fundamental challenges found in current devices.

Figure 1

(a) Direct optimization. The fully connected problem with six binary variables (circles) labeled A–F. Couplers between the variables are represented as solid (red) lines. (b) Square Lattice Embedding. In a square embedding, the logical variable C is represented by a chain of $N-1$ logical qubits. Constraints are represented by black (dark) lines. These chains are laid out such that every variable chain can connect to every other variable chain, shown by the red (light) lines. (c) The LHZ Scheme. In the LHZ or PAQO embedding, a physical variable ${\alpha }_{i,j}$ is the product of two logical binary variables ${\sigma }_i{\sigma }_j$. The logical couplers correspond to physical local biases (red). Constraints are enforced with $4$-local interactions (black crosses) between neighboring spins. (d) The chimera lattice, $c=3$. A $K_{3,3}$ chimera lattice consisting of a square-embedding-like chain structure (black or dark lines) combined with bipartite graph cells. These cells contain the logical couplers (red or light lines).

Figure 2

(a) The ground-state hit probability (g.s.-Hit) for various annealing times $T$ using simulated quantum annealing. The slower we anneal, the more likely we are to find the ground state. The specific instance used in this example is a MaxCut instance of size $N=25$ and density $p=0.3$. For each annealing time, we repeat the algorithm $30$ times. The box plot shows the first to third quartile, while the whiskers represent 5% and 95% of the measured data. (b) The time to solution (with a probability of 90%) versus the annealing time $T$. Because the ground-state hit probability is not a linear function, it is faster to repeat short-annealing-time runs than to invest in one long run. Therefore, we measure the mean and not the median. Both panels have the same horizontal axis.

Figure 3

(a) All $s_{0.9}^{\mathrm{opt}}$ for a physical problem using simulated quantum annealing (SQA) [one highlighted in Fig. 2 with a green arrow] of all instances, with density $p=0.5$ sorted by size in a linear-log box plot. (b) The same as a) but for the problems embedded in the chimera lattice. Both panels have the same horizontal axis.

Figure 4

$s_L$ versus the logical system size $N$ for (a) MaxCut instances with $p=0.3$ and (b) Gaussian spin glasses. The data shown are for the three embedding schemes, as well as a direct simulation of the logical problem (bottom data set). The $s_L$ for each instance is determined by averaging over $30$ random starts of the algorithm. The reason for the absence of the largest system size for the PAQO scheme is the inability to find the ground state, likely due to insufficient constraint scaling. Both panels have the same vertical axis.

Figure 5

The same data as in Fig. 4 but divided by $s_L^{\mathrm{direct}}$. Both panels have the same vertical axis.

Figure 6

The same data as in Fig. 4 but displayed with $\log (s_L)$ embedded versus direct optimization of every independent instance as a scatter plot. The black crosses show the first to third quartiles for each logical size. The linear scaling in a log-log plot indicates a polynomial scaling. All panels share the same vertical and horizontal axes.

Figure 7

$s_L$ plotted versus $s_P$ for the three embedding schemes and MaxCut ($p=0.3$, left column) and Gaussian spin glasses (right column). A decoder can only make $s_L$ faster. If we run a trivial decoder that accepts no errors, then $s_L$ is equal to $s_P$—shown as the black circles. A trend to smaller benefits toward larger sizes (i.e., larger $s_P$) is visible, which leads to slightly worse scaling when fitting the data. Furthermore, it is visible that the decoder for the PAQO scheme is more efficient than majority voting for embedding on both the square and chimera lattices. While it reduces $s_L$ by orders of magnitude compared to $s_P$—which could be invaluable for any real-world applications—it does not improve the scaling.

Figure 8

A constraint-scaling example in the PAQO scheme. The logical system is not shown. (a) The logical couplers are set up in three equal groups for a logical system of large size $N$; hence we do not display the individual physical spins as in Fig. 1. All spins in A want to be parallel (light gray, $J=1$) to each other, as do the ones in B and C. Region I wants all A spins to be antiparallel (dark gray, $J=-1$) to all B spins. Region II is the same for all A and C spins and region III is the same for all B and C spins. (b) The physical ground state (blue down spin, orange up spin) if the $4$-local term constraint marked with the (red) circle is too weak. This broken ground state satisfies all problem couplings but does not correspond to a logical state. (c) If the constraints are strong enough, at least one of the regions is not satisfied [here, region II of area $(1/9)N^2$]. (d) Unsatisfied couplings from the solution in (c), where the red color marks physical spins that add energy. (e) Another possible physical ground state if constrained enough, with (f) showing the unsatisfied couplings thereof in region III, again of area $(1/9)N^2$.

Figure 9

The minimal $4$-local-term constraint strength required. Using the example from Fig. 8 and changing the number of spins in Groups A, B, and C (and therefore the size of the blocks I, II, and III) allows one to move the constraint position that breaks to any point and observe at which strength it breaks. This is mapped out in this contour plot in terms of $N^2$. It shows that the $4$-local-term constraint must be stronger in the middle of the PAQO embedding and can be weaker at toward the borders. This is, however, just one type of problem family and not a rigorous lower bound.

Figure 10

The spectrum, energy gap, and instantaneous ground state for a three-spin ferromagnetic chain with individual local fields [58]. (a) The spectrum of transverse field annealing, starting with the pure transverse field at $t=0$ and transforming to the pure problem Hamiltonian at $t=1$ in a linear manner. (b) An avoided level crossing between the two lowest states. (c) The first energy gap. (d) An enlargement of (c) on a log scale. The gap reaches $\mathrm{\Delta }\approx {10}^{-3}$ at its smallest position. (e) The instantaneous ground state is shown by the probabilities in the computational basis, of which we only label the three dominant parts and display the remaining five as black lines. (f) The sudden rise and fall of the ground-state components representing a flip in the first two spins and changing the third spin from a superposition to up.