Practical engineering of hard spin-glass instances

Recent technological developments in the field of experimental quantum annealing have made prototypical annealing optimizers with hundreds of qubits commercially available. The experimental demonstration of a quantum speedup for optimization problems has since then become a coveted, albeit elusive goal. Recent studies have shown that the so far inconclusive results, regarding a quantum enhancement, may have been partly due to the benchmark problems used being unsuitable. In particular, these problems had inherently too simple a structure, allowing for both traditional resources and quantum annealers to solve them with no special efforts. The need therefore has arisen for the generation of harder benchmarks which would hopefully possess the discriminative power to separate classical scaling of performance with size from quantum. We introduce here a practical technique for the engineering of extremely hard spin-glass Ising-type problem instances that does not require “cherry picking” from large ensembles of randomly generated instances. We accomplish this by treating the generation of hard optimization problems itself as an optimization problem, for which we offer a heuristic algorithm that solves it. We demonstrate the genuine thermal hardness of our generated instances by examining them thermodynamically and analyzing their energy landscapes, as well as by testing the performance of various state-of-the-art algorithms on them. We argue that a proper characterization of the generated instances offers a practical, efficient way to properly benchmark experimental quantum annealers, as well as any other optimization algorithm.

Figure 1

Performance of the RAO algorithm for a single instance. A single run of the algorithm over 1000 steps, set up to maximize $t_{HFS}$ of a 512-bit Chimera instance with $J_{ij}=\pm 1$. Updates consist of flipping the value of randomly picked edges. Squares (red) show successful update attempts; crosses (blue) are rejected updates.

Figure 2

Histogram of the ratio of final to mean initial $t_{HFS}$ for 150 random signed instances (512 bit Chimera graph). As in Fig. 1 we adapted the instances by flipping random edge values, attempting to maximize $t_{HFS}$. This plot is a normalized histogram of the ratio final TTS, $t_{HFS}^{\left(f\right)}$, to mean initial TTS, $\langle t_{HFS}^{\left(i\right)}\rangle$, after 0 (blue), 500 (red), and 2500 (yellow, with red outline) algorithmic steps.

Figure 3

Mixing time $\tau$ vs ratio of typical GS-ES overlaps over GS-GS overlaps. For each instance for which PT computed $\tau$ successfully, we compute the median overlap (see text) between the ground and dominant first-excited states, normalizing by the median ground state to ground state overlap. Also plotted is the median data point for each group (filled black circle), where going from bottom right to upper left is in order from $k=1$ to $k=4$. Linear fit is on the median data point for $k=2,3,4$. $\tau$ is given in units of Metropolis sweeps.

Figure 4

PT hardness (mixing time) vs HFS hardness. The 400 instances generated as documented in the main text, examined on parallel tempering (PT). The linear fit of slope 1.40 is obtained from a least-squares fitting on the median data point (black squares) of each data group, ignoring the $k=1$ group. We also include, indicated by a green diamond marker, the hardest instance $\left(k_{max}\right)$ found using our adaptive algorithm, extrapolated using the linear fit to obtain the corresponding value for $\tau \approx 3.7\times {10}^7$. $\tau$ is given in units of Metropolis sweeps.

Figure 5

DW2 hardness vs HFS hardness. We plot the D-Wave TTS, $t_{DW}$, against $t_{HFS}$ for the 400 problem instances as explained in the main text. Note that there are fewer blue data points $\left(k=4\right)$, compared to the others. This is because many of these instances were not solved once by the D-Wave machine in $660000$ attempts and so are left off of this graph. The linear fit of slope 2.48 is obtained from a least squares fitting on the lower quartile data point (black squares) of each data group, excluding the $k=1$ group. We also include, indicated by a green diamond marker, the hardest instance $\left(k_{max}\right)$ found using our adaptive algorithm, extrapolated using the linear fit to obtain the corresponding value for $t_{DW}\approx {10}^3$ s, i.e., require $\sim {10}^8$ attempts.

Figure 6

Histogram of the ratio of final to mean initial $t_{HFS}$ for 100 planted-solution instances (504-bit Chimera graph). We compare the LAO algorithm after 2000 steps (red) to the 100 random initial (blue) planted-solution instances, each containing 350 random loops. Updates consisted of adding and removing random loops, where size 4 (6) loops have a probability of 0.1 (0.9) being chosen, with integer loop weight chosen randomly in range [1,5]. We plot the histogram of the ratio final HFS TTS, $t_{HFS}^{\left(f\right)}$, after 0 (blue) and 2000 (red) LAO steps, to the mean initial TTS, $\langle t_{HFS}^{\left(i\right)}\rangle$. The mean TTS ratio after the 2000 steps is $\approx 4.3$, and the maximum final TTS is $\approx 0.15$ s.

Figure 7

Annealing schedule of the DW2 device. The annealing curves $A\left(t\right)$ and $B\left(t\right)$ are calculated using rf-SQUID models with independently calibrated qubit parameters. Units of $\hslash =1$. The operating temperature of $17\mathrm{mK}$ is also shown.

Figure 8

$4\times 4$ patch of the full $8\times 8$ Chimera graph for the DW2 chip. Top left (red) shows a single $K_{4,4}$ bipartite graph. The qubits or spin variables occupy the vertices (circles) and the couplings $J_{ij}$ are along the edges. Of the 512 qubits, 504 were operative in our experiments.