Optimization versus fair sampling in quantum annealing: An exactly characterized frustrated Ising benchmark

AI summary

Overview

Research area: Quantum annealing and quantum–classical benchmarking — specifically, the distinction between optimization (reaching a degenerate ground-state manifold) and fair sampling (sampling that manifold uniformly) on D-Wave hardware.

Technical level: Intermediate. The physics is Ising-model based and the exact solution is derived with elementary combinatorics, but familiarity with quantum annealing, minor embedding, and total-variation distance helps.

Scope: The paper introduces a frustrated Ising-ring benchmark whose complete zero-field ground-state manifold is known in closed form for every system size, embeds it on a D-Wave Advantage processor with up to 162 logical spins, and shows that high ground-state hit probability does not imply uniform sampling within the ground-state manifold.

What This Paper Is About

When a quantum annealer solves a problem with many exactly degenerate ground states, hitting the ground-state energy and sampling all of those ground states equally are two different achievements. In generic problems the full set of ground states is unknown, so a nonuniform output cannot be attributed to device bias rather than to the problem's own solution-space structure. The authors build a benchmark where the entire ground-state manifold — including its degeneracy and its decomposition into defect sectors — is known analytically at arbitrary size, so that every measured sample can be classed as a ground state or an excited state without any heuristic, and the two questions can be scored separately.

Key Contributions

1. An exactly solvable frustrated Ising benchmark. An Ising ring with additional couplings between maximally separated sites, whose ground-state energy, degeneracy, and defect structure are classified in closed form for each congruence class of the system size N modulo four (derived in Appendix A via bond variables, a global parity constraint, and a window rule).

2. A separation of optimization from sampling. Because the exact ground-state manifold is known, the ground-state hit probability P_G (optimization) is decoupled from the conditional distribution within the manifold, measured by the state-level and defect-sector total-variation distances d_TV^st and d_TV^sec.

3. A hardware study with controlled embedding. Manual embeddings on a D-Wave Advantage processor (system4) using length-two chains for every logical spin, compared against simulated annealing run both on the embedded physical problem and directly on the logical problem, across fast and standard annealing schedules.

4. Pause-annealing diagnostics. A 100 μs pause scanned across the anneal identifies a relaxation window where ground-state probability roughly doubles, while the sampling bias within the manifold is left intact — evidence for a thermally assisted picture of open-system quantum annealing.

Main Findings

• The interaction graph depends on parity, and the ground state on N mod 4. For even N each spin has a unique antipodal partner and the graph is a Möbius ladder; for odd N each spin has two maximally separated neighbours and the graph is the circulant graph C_N(1,(N−1)/2), relabelable as C_N(1,2).

• Closed-form ground-state classification (antiferromagnetic couplings, J₁ = −1, J* = −1 for even N and −1/2 for odd N, no longitudinal field). For N ≡ 0 mod 4 the ground states are two-defect frustrated states with E₀ = −3N/2 + 4 and |G| = N. For N ≡ 2 mod 4 they are the Néel pair with E₀ = −3N/2 and |G| = 2. For N ≡ 1 mod 4 there are one-defect odd-cycle states with E₀ = −N + 5/2 and |G| = 2N; for N ≡ 3 mod 4, E₀ = −N + 3/2 and |G| = 2N. In the odd case the 2N ground states group into N defect sectors related pairwise by global spin reversal.

• The frustrated N = 83 instance is characterized exactly: |G| = 166, |S| = 83 defect sectors, E₀ = −81.5, embedded with 83 logical spins and 166 physical qubits.

• Annealing time matters strongly for larger instances. With fast anneals (t_a = 0.005, 0.05, 0.1 μs) the ground-state hit probability of larger instances stays small; with the standard 20 μs anneal the N = 83 instance reaches P_G = 0.394, while the even instances reach P_G = 0.869 for N = 160 and P_G = 0.496 for N = 162.

• Optimization and fair sampling do not improve together. For N = 83 at 20 μs the QPU has P_G = 0.394 and observes 164 of the 166 exact ground states, yet retains d_TV^st = 0.300 and d_TV^sec = 0.165. For N = 160, the QPU attains a larger ground-state probability than logical SA (0.869 against 0.519) but also a larger total-variation distance from uniformity (0.317 against 0.136).

• Simulated annealing on the hard odd instance is sample-starved. Physical SA produced 21 ground-state samples in 3000 reads (P_G = 0.007, 21/166 ground states observed) and logical SA gave P_G = 0.023 with 60/166 observed, so their large distances (0.873 and 0.639 at state level) partly reflect sparse support rather than a well-resolved bias — the authors state this caveat explicitly.

• A two-state manifold exposes device asymmetry directly. For N = 162 logical SA samples the two Néel states nearly uniformly (d_TV^st = 0.009), whereas the QPU at 20 μs gives observed probabilities of approximately 0.919 and 0.081, i.e. d_TV^st ≃ 0.419, with sector-level distance trivially zero once spin-flip partners are merged.

• Pause annealing locates a relaxation window without fixing the bias. On N = 83 with a 100 μs pause, the standard 20 μs baseline acquired with the pause data gives P_G = 0.422; the refined scan peaks at s_p = 0.40 with P_G = 0.862 and the mean decoded logical energy drops from −78.36 to −80.88, with enhancement broadly over 0.36 ≲ s_p ≲ 0.44. At s_p = 0.40 the state-level distance is 0.308 against a baseline 0.231, and the sector-level distance is 0.161 against 0.156; sector-resolved probabilities (uniform would be 1/83 ≃ 0.012, about 1.20 percent) stay persistently nonuniform.

• Supported interpretation. The combined time and pause dependence supports a thermally assisted quantum-annealing picture, in which transverse-field fluctuations and environmental relaxation cooperate in the intermediate part of the anneal, while freeze-out, analog biases, and embedding geometry can leave residual sampling bias; the data cannot uniquely identify which of these dominates.

Methodology in Plain English

The authors pick a simple, highly symmetric spin model: a ring of N Ising spins with antiferromagnetic nearest-neighbour couplings, plus antiferromagnetic couplings between sites that sit as far apart as possible on the ring. Because the rule for adding these long bonds is fixed, the resulting graph is a Möbius ladder for even N and a circulant graph for odd N. The frustration created by these long bonds is what makes the model interesting, and it depends only on N modulo four.

To solve it exactly they switch variables from spins to the products of neighbouring spins (bond variables). Each bond is either satisfied or is a "defect", and the ring geometry imposes exactly one constraint: the number of defects has the same parity as N. A long-range correlation can be written as a product of consecutive bond variables, which turns each maximally separated coupling into a rule about how many defects must lie in a window of a given length. Minimizing the resulting counting cost in each congruence class yields the energies and degeneracies in closed form.

For the experiments, each logical spin is mapped onto a chain of exactly two physical qubits (chain coupling J_chain = −2) in a hand-built embedding on a D-Wave Advantage processor, with decoded spins obtained by majority vote. All reported energies are recomputed after decoding using the original logical Hamiltonian. The working graph used contained 5627 active qubits and 40279 active couplers, with auto_scale=True.

Because the full ground-state set is known in advance, each decoded sample is unambiguously labelled as a ground state or an excited state. P_G measures how often the manifold is reached; conditioned on reaching it, the empirical distribution over ground states is compared with the uniform distribution using the total-variation distance, both at the level of individual states and at the level of defect sectors. Comparisons are made against simulated annealing applied to the embedded physical problem (with the same decoding) and to the logical problem directly, each with 3000 reads and 1000 sweeps per read, matching the 3000 reads per QPU data set. Pause experiments insert a 100 μs hold at annealing fraction s_p into a standard 20 μs schedule, first scanned over s_p = 0.2 to 0.9, then refined over 0.34 to 0.46.

Why This Matters

Impact on research. Benchmarking of annealers is usually reduced to a single number — the ground-state success probability, or the best energy found. This paper shows that this number is not sufficient for degenerate problems: a device can be excellent at reaching the right energy and poor at representing the solution set. Because the benchmark's ground-state manifold is known in closed form at arbitrary size, it provides a reference distribution that planted-solution benchmarks (unknown solution-set size), spin glasses (numerically estimated manifolds), and small frustrated units (only a few spins) cannot supply.

Real-world applications (relevance framed at the level of the problem class, not demonstrated in the paper):

• Diverse-solution optimization — logistics, scheduling, and portfolio-style problems where many equally good solutions exist and practitioners want a representative spread rather than one favoured answer.
• Sampling-based machine learning — Boltzmann-machine training and generative modelling depend on drawing samples in proportion to their probability, which is precisely a fair-sampling requirement.
• Materials and chemistry searches — degenerate ground-state manifolds correspond to competing orderings or configurations, where the population of each state carries physical meaning.
• Hardware procurement and calibration — a protocol-independent fairness metric gives buyers and operators a way to compare devices or schedules beyond headline success rates.

Industry relevance. Providers and users of annealing hardware currently report optimization metrics; this benchmark adds a cheap, exactly checkable fairness metric, and it can be embedded in a handful of two-qubit chains, so it is practical on present-day devices with modest qubit overhead.

Future Directions

• Decomposing the residual bias. The authors state that freeze-out in the late anneal, analog control errors, and embedding details cannot be separated with the present data; additional control over gauge choice, logical relabelling, and physical embedding would be needed. The 0.919/0.081 imbalance between two exactly degenerate Néel states for N ≡ 2 mod 4 is a concrete target for such a study.

• Connecting fairness to dynamics. The pause data show a window (approximately 0.36 ≲ s_p ≲ 0.44) where relaxation into the manifold is strongly enhanced while intra-manifold mixing is not. Understanding which relaxation channels populate the manifold but do not mix within it is left open.

• Scaling and other topologies. The classification holds for arbitrary N, but the demonstration reaches 162 logical spins with length-two chains; extending to longer chains, larger sizes, and other embedding strategies would test whether the observed bias persists or worsens.

• Turning the benchmark into a standard suite. Since the energies, degeneracies, and defect sectors are all available in closed form, the model can be packaged as a set of reference instances spanning all four congruence classes for systematic comparison of annealers, schedules, and classical samplers.

Target Audience

Researchers and engineers working on quantum annealing and adiabatic quantum computation, especially those interested in benchmarking, open-system dynamics, and sampling applications rather than pure optimization. It is also relevant to classical-optimization researchers who use simulated annealing and want a well-characterized test problem with a known solution-set structure, and to practitioners evaluating D-Wave hardware for sampling-based workloads. Graduate students with basic statistical-mechanics and Ising-model background will find the appendix derivation self-contained.

Authors’ abstract

Reaching a degenerate ground-state manifold and sampling it uniformly are distinct properties of a quantum annealer. We quantify this distinction using an Ising ring with additional couplings between maximally separated sites. For antiferromagnetic benchmark couplings and $N \geq 5$, we derive the exact ground-state energy, degeneracy, and defect structure for each congruence class of $N$ modulo four. This classification separates ground-state hit probability from conditional sampling bias. We embed instances with up to 162 logical spins on a D-Wave Advantage processor using length-two chains and compare its output with simulated annealing on the embedded and logical problems. For a frustrated $N=83$ instance, the processor visits 164 of the 166 exact ground states, yet the conditional distributions over states and defect sectors remain nonuniform. For $N=160$, the processor has a larger ground-state hit probability than logical simulated annealing (0.869 versus 0.519), but also a larger total-variation distance from uniformity (0.317 versus 0.136). A pause during the anneal raises the ground-state hit probability from 0.42 to 0.86 without restoring uniform sampling. These results identify a relaxation window and demonstrate that optimization success and sampling quality need not improve together, providing an exactly characterized benchmark for open-system quantum annealing.