Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs

1 Introduction

• Minor embedding can substantially affect experimental results because mappings differ and may increase problem size or alter the represented instance.Applications are rarely defined directly on Chimera graphs, so the hardware requires a classical front end and embedding step.Source: §1 · p. 1
• The D-Wave machine returns heuristic Ising solutions quickly but does not guarantee true optima; repeated runs can increase the chance of finding them.Source: §1 · p. 1
• The study is motivated by whether 2048 qubits would make exact classical optimization difficult enough to assess current D-Wave 2000Q solution quality.Earlier empirical comparisons found that tested annealers lacked enough qubits for large problems, while Parekh et al. [42] predicted a change at 2048 qubits.Source: §1 · p. 2

Our Contribution

• Exact branch-and-cut, semidefinite, and dynamic-programming methods solve transformed Chimera-graph instances to optimality for comparison with D-Wave 2000Q.The Ising instances are transformed into maximum-cut instances, and the exact methods are tailored to Chimera graphs.Source: §1 · p. 2
• The comparison targets the quality of solutions produced by D-Wave hardware at its native task rather than a compound classical-and-oracle pipeline.The authors use their codes as simulators of the hardware and compare universal approaches on both sides.Source: §1 · p. 2

2 Previous work

• Reported speedups varied sharply with the classical formulation: McGeoch and Wang prompted a 3600-times claim, whereas Dash and Puget observed only 17 using a stronger linearized approach.Source: §2 · p. 2
• Prior D-Wave comparisons often used specialized classical algorithms, with classical methods frequently dominating quantum annealing.Source: §2 · p. 2
• Benchmarking proposals recommend comparing mapped instances because the best algorithm may depend on each combinatorial optimization instance [42].Using a tailored algorithm against a universal one can make a conclusion that quantum annealing is worse unfair [42].Source: §2 · pp. 2–3
• Related graph-specific methods include Saket's PTAS and Selby's exact dynamic program, which exploits the relatively low treewidth of Chimera graphs [47] [50].Source: §2 · p. 3
• Classical foundations include exact integer-linear-programming methods, grid-graph algorithms, cut-polytope lifting and separation, and semidefinite branch-and-bound approaches.Source: §2 · p. 3

3 Ground States of Ising Spin Glasses

• The model represents graph nodes as spins, graph edges as pairwise interactions Jij, and node weights as external-field effects hi.Source: §3 · p. 3
• An Ising ground state is a spin configuration s* of minimum energy H(s) over configurations whose spins take values +1 or −1.Source: §3 · p. 3
• An Ising instance has zero field when every node weight satisfies hi = 0.Source: §3 · p. 3
• Ising models apply to chemistry, neuroscience, and electronic-circuit layout, while the general problem and Chimera-graph variants are NP-complete.Source: §3 · p. 3

4 D-Wave Quantum Annealing

• D-Wave maps qubits and allowed interactions to a Chimera graph and searches for low-energy spin configurations using individual fields hi.Source: §4 · p. 4
• The C16 Chimera graph used by D-Wave 2000Q has 2048 nodes and 6016 edges, or 2049 nodes and 8064 edges when external fields are represented.Source: §4 · p. 4
• A Chimera graph Ck is a k × k grid of K4,4 cells, with horizontal and vertical inter-cell connections defining its structured topology.Source: §4 · p. 4
• Minor embedding increases qubit requirements and can require strongly coupled chains; broken chains may require postprocessing that dramatically reduces success probability.Source: §4 · p. 4
• The hardware's limited coefficient precision forces coupling and field values onto a discrete set Γ, so preprocessing may round the intended instance to an approximation [42].The paper states that γ is approximately 30 and that rounding is often neglected in computational studies.Source: §4 · p. 4

• MaxCut is represented by a cut’s characteristic vector, with edge weights accumulated over the cut edges.A cut is defined by a vertex subset W and its crossing edge set δ(W).Source: §5 · p. 5
• The authors transform Chimera Ising instances into MaxCut instances and solve them with exact optimization methods to compare against D-Wave.The formulation also relates Ising models to QUBO problems, preserving optimal solutions and objective values through explicit transformations.Source: §5 · p. 5
• An Ising instance is converted to MaxCut by adding a special node connected to every qubit, assigning Chimera-edge weights Jij and special-edge weights hi.An optimal MaxCut solution then yields an optimal Ising configuration.Source: §5 · p. 5
• For zero-field Ising models with nonnegative interactions, Chimera bipartiteness makes the maximum cut equal to the sum of all edge weights.The corresponding ground-state energy is the negative sum of those edge weights.Source: §5 · p. 5
• QUBO instances are mapped to Ising coefficients by setting Jij from quadratic terms and hi from the associated linear and quadratic coefficients.The resulting Ising solution is converted back to a QUBO solution with a corresponding transformed objective value.Source: §5 · p. 5
• The experiments restrict coefficients to Γ = {−1.0, −0.9, . . . , 1.0} with γ = 10 so quantum and classical optimization solve exactly the same instances.Without this restriction, QUBO-to-Ising transformations can produce field values outside the allowed coefficient granularity Γ.Source: §5 · p. 5

6 Solution of MaxCut to Optimality

• The section’s solution framework combines branch-and-cut, semidefinite programming, and Chimera-specific dynamic programming, while also evaluating Selby’s exact and heuristic approaches.These methods target provable optimality where feasible and exploit Chimera structure through cuts, relaxations, tree decompositions, and bounded-treewidth subgraphs.Source: §6 · p. 5, §6.1 · p. 6, §6.2 · p. 6

6.1 Polyhedral Approach

• Odd-cycle inequalities define the polyhedral relaxation, and cutting planes iteratively add violated inequalities until the relaxation is solved or embedded in branch-and-bound.For Chimera graphs, odd-cycle inequalities on 3- and 4-cycles can be enumerated efficiently; additional K4,4-subgraph inequalities strengthen the model.Source: §6.1 · p. 6

6.2 Semidefinite Programming Approach

• The semidefinite approach expresses MaxCut through spin variables and solves a positive-semidefinite relaxation over matrix variables.Triangle, 5-clique, and 7-clique hypermetric inequalities are added iteratively to tighten the relaxation.Source: §6.2 · pp. 6–7

6.3 Exact and Heuristic Approaches by Selby

• Dynamic programming solves MaxCut in O(2^wn) time for treewidth w, and Chimera graphs have treewidth 4k, making exact solution practical mainly for small k.Selby’s implementation regularly solved instances with k ≤ 8 but became impractical for larger k because of time and memory requirements.Source: §6.3 · p. 7
• The C8 experiments found Selby’s exact algorithm comparable to other exact methods and sometimes best, but its implementation computes only ground-state energy.The related randomized subgraph-sampling heuristic extends the low-treewidth strategy to larger Chimera graphs.Source: §6.3 · p. 7
• Selby’s inner algorithm optimizes spins on a bounded-treewidth subset while treating the remaining fixed spins as an external magnetic field.The outer algorithm repeatedly applies this optimization to subsets generated from the current configuration.Source: §6.3 · p. 7
• The heuristic repeatedly updates random or partially perturbed spin configurations, using randomly selected Chimera subgraphs covering the graph.In the default setting, 20% of the K4,4 subgraphs are randomly perturbed between runs, and execution stops after a prescribed wall-clock duration.Source: §6.3 · p. 8
• The induced Selby subgraphs are connected and have treewidth 4w, with their structure determined by alternating horizontal and vertical Chimera-node removals.The construction yields 2w subsets and supports the bounded-treewidth optimization used by the heuristic.Source: §6.3 · p. 8

7.1 McGeoch-Wang Instances

• Only 5 of 100 additional D-Wave 2000Q C8 instances differed from optimum, with a maximum relative deviation of 0.254%.These instances randomly selected faulty qubits and ±1 edge weights because the original faulty-qubit set was unavailable.Source: §7.1 · p. 9
• For 507-qubit C8 instances, chimeramaxcut averaged 195 seconds versus 4.6 hours for qubostdlin, while D-Wave found true ground states in all 20 cases.The tailored branch-and-cut implementation therefore outperformed the standard linearization method in these experiments.Source: §7.1 · p. 10
• On 2031-qubit C16 instances, with computation limited to 10 hours per instance, chimeramaxcut produced better solutions than D-Wave in 16 of 20 runs.The best D-Wave energies deviated from the best chimeramaxcut energies by at most 0.201% and 0.082% on average.Source: §7.1 · p. 10
• 95% of 439-qubit C8 instances reached optimality, whereas 80% of C16 runs were definitely not at the ground state, with gaps at most 0.201%.These results verify the smaller-instance behavior reported in but not its extension to larger instances.Source: §7.1 · p. 10

7.2 Random Instances with Full Range within Granularity

• For full-range random C16 instances, D-Wave missed every proven ground state, with relative deviations from 0.059% to 0.258% and an average of 0.137%.The corresponding chimeramaxcut computations averaged about 2.5 minutes.Source: §7.2 · p. 11, Figure 4 · p. 11

7.3 Selby Instances

• On zero-field C8 Selby instances, D-Wave found true ground states in 13 of 20 cases, while its relative deviation from the best sdpmaxcut energies stayed below 0.165%.sdpmaxcut solved all but one instance to proven optimality within 5–15 minutes; the remaining ground state was verified by the exact Selby optimizer.Source: §7.3 · p. 11
• For zero-field C16 Selby instances, none of the exact approaches reached proven optima within reasonable time, and the reported gaps rose to 0.584%.The experiments therefore reported best solutions and lower bounds after limiting computation to 10 hours per instance.Source: §7.3 · p. 11

7.4 Maximum Independent Set Instances

• D-Wave found true ground states in only 4 of 20 maximum independent set instances, while exact solvers proved optimality within 1–3 seconds.For the remaining instances, D-Wave’s relative energy deviation ranged from 0.127% to 0.647%.Source: §7.4 · p. 12

7.5 Practical Instances from Gate Assignment in [53]

• D-Wave found true ground states for all practical gate-assignment instances, confirmed by generalmaxcut within 1.27 seconds.The average confirmation time was about 0.03 seconds.Source: §7.5 · p. 13

7.6 Large Gate-Assignment-like Instances

• For the 30 larger gate-assignment-like instances, D-Wave found only 2 true ground states, with relative deviations up to 0.347% and averaging 0.145%.sdpmaxcut succeeded on 24 instances and bounded the remaining six within at most 0.09% of the ground state energy.Source: §7.6 · p. 13

7.7 Embedded K64 Ising Instances

• D-Wave found true ground states for 48 of 80 embedded K64 Ising instances, with relative deviations capped at 0.134%.generalmaxcut confirmed the solutions within at most 2.18 seconds and 0.92 seconds on average.Source: §7.7 · p. 14

7.8 Embedded K64 MaxCut Instances

• D-Wave never found a true ground state on embedded K64 MaxCut instances, with deviations up to 0.499% and averaging 0.288%.generalmaxcut solved all instances to optimality, but the longest run took almost two CPU days.Source: §7.8 · p. 14

7.9 Performance of the Selby Exact Solver and the Selby Heuristic

• The Selby heuristic found every known optimum, but required 100 seconds for all but one difficult large gate-assignment-like instance.That remaining instance required six minutes to match its best known solution.Source: §7.9 · p. 15

7.10 Summary

• The tables report instance counts, transformed graph sizes, known optima, Selby success within 30 or 100 seconds, D-Wave best solutions, and maximum and average D-Wave gaps.Table 1 gives instance statistics, while Table 2 summarizes solver and D-Wave performance.Source: §7.10 · pp. 15–16, Table 1 · p. 16, Table 2 · p. 16
• Maximum independent set instances were easy for exact methods but among D-Wave’s hardest, whereas k64ising instances were easy for both despite 40% lacking a D-Wave ground state.The paper relates these differences to graph structure, fields, and weight distributions.Source: §7.10 · p. 16
• The hardest exact-solver sets were selby-c8, k64maxcut, lga, mgw-c16-2031, and selby-c16, with selby-c16 also producing D-Wave’s largest average gap.mgw-c16-2031 was beyond the current exact-solving capability described in the study.Source: §7.10 · pp. 16–17
• Proven ground states were computed for 1,401 of 1,445 instances; the remaining 44 had best solutions with reported high-quality bounds.Unknown-ground-state cases included 18 mgw-c16-2031, 20 selby-c16, and 6 lga instances.Source: §7.10 · p. 17

• The conjecture that solver running-time difficulty predicts quantum-annealer solution quality is not always true.Source: §8 · p. 17
• 0.647% is the maximum relative deviation from the ground state energy across all 1445 instances.The D-Wave computer is characterized as an extremely fast heuristic rather than a method expected to deliver true optima.Source: §8 · p. 17
• D-Wave solution quality deteriorates with increasing problem size for C8/C16 pairs such as mgw-c8/mgw-c16 and selby-c8/selby-c16, and for pga/lga.Source: §8 · p. 17
• Selby produces very good solutions in short computation time despite lacking an approximation-quality guarantee, making it a serious alternative.Source: §8 · p. 17
• General MaxCut solvers based on polyhedral combinatorics or semidefinite programming are the methods of choice for computing truly optimum solutions.Source: §8 · p. 17
• The exact approaches were tailored to Chimera graphs, but similar approaches are expected to be possible for future D-Wave architectures.Source: §8 · p. 17