Verifying the output of quantum optimizers with ground-state energy lower bounds

Solving optimization problems encoded in the ground state of classical-spin systems is a focus area for quantum computing devices, providing upper bounds to the unknown solution. To certify these bounds, they are compared to those obtained by classical methods. However, even if the quantum bound beats them, this says little about how close it is to the unknown solution. We consider the use of relaxations to the ground-state problem as a benchmark for the output of quantum optimizers. These relaxations are radically more informative because they provide lower bounds to the ground-state energy. The chordal branch and bound algorithm we present provides a series of systematically improving confidence regions where the ground-state energy provably lies. Interestingly, each step in the process requires only an effort polynomial in the system size. Additionally, the algorithm exploits the locality and sparsity of relevant Ising spin models in a systematic way. This yields certified solutions for many of the problems that are currently addressed by heuristic optimization algorithms more efficiently and for larger system sizes. We apply the method to verify the output of a D-Wave 2000Q device and identify instances where the annealer does not reach the ground-state energy and, more importantly, instances where it does, something impossible to do by means of standard variational approaches. Our work provides a flexible and scalable method for the verification of the outputs produced by quantum optimization devices.

Figure 1

Example of sequences of upper and lower bounds obtained during the branching procedure with the CBB method, for a 2D Ising model of lattice size $15\times 15$. The convergence is met, yielding a certified value for the ground-state energy and configuration, after less than 20 steps, instead of having to explore all of the $2^{225}$ configurations.

Figure 2

(a) An example of graph $G$ that is not chordal, together with an option of edges to add (shown in red) in order to make it chordal, obtaining a chordal extension $G_C$. The new edges are chosen to “break” the larger cycles, such as the cycle $\{1,5,9,8\}$. (b) The graph $G_C$ and its corresponding maximal cliques $C_l$, shown with the different colors. In this example, the graph has $n_c=6$ cliques, out of them two are composed of four vertices, while the remaining ones consist of three vertices each.

Figure 3

Time comparison for a square lattice of $N$ sites between a standard SDP-based branch and bound (BB) algorithm and the one augmented with the chordal extension (CBB), as a function of the linear lattice size $L=\sqrt{N}$. The problem is finding the ground-state energy for a 2D Ising ferromagnetic model with random Gaussian magnetic field, close to the phase transition at $\sigma =1.5$, i.e., where the ground state is already partially disordered. The time estimation was averaged over 100 disorder realizations, except for the largest system size, where the averaging was reduced to 10 samples. Due to the large amount of disorder averaging, we limit ourselves to system sizes $L\le 15$, far below the maximum sizes we can tackle on our hardware. The comparison is shown in a linear scale and double logarithmic in the inset. The dashed lines in the inset are power laws of the form $L^{10}$ and $L^6$, demonstrating the claimed polynomial scaling of the runtime $N^5$ for BB vs $N^3$ for CBB.

Figure 4

Left: Comparison of the lowest energy value for a disordered phase at $\sigma =1.5$ on a triangular lattice on a 2040-qubit D-Wave quantum annealer and the CBB algorithm. Notice that in all the instances considered here the confidence region provided by CBB converged in few steps and the algorithm returned the exact ground-state energy. Right: Comparison of the corresponding ground-state spin configuration both for a case where D-Wave achieves the lowest energy and for two cases where it does not. Yellow spins are $+1$ and black one $-1$. It can be seen clearly that, even when the energies provided by the two methods are close, the corresponding spin configurations can be very different. This shows that the excited state that the D-Wave quantum annealer returns does not necessarily resemble the globally optimal solution.

Figure 5

Average magnetization $m$ of the ground state of the ferromagnetic Ising model with disordered magnetic field, as a function of the disorder strength $\sigma$, for a 2D triangular lattice of linear size $L$. The plot shows the cases $L=15$ (blue) and $L=20$ (red). The phase transition could be pinned down more precisely by means of a finite-size scaling analysis. For our purposes here it is sufficient to know that in the range $\sigma \in [1,3]$, the ground states has nontrivial spin patterns.