Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1606.07146 · Physical Review Letters

Exponentially Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians

Salvatore Mandrà, Zheng Zhu, Helmut G. Katzgraber

Published Feb 17, 2017• 72 citations
arXivHTMLPDF

Abstract

We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated with a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)NJOPFM1367-263010.1088/1367-2630/11/7/073021]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.

DOI
10.1103/physrevlett.118.070502

Related papers

Uncertain fate of fair sampling in quantum annealing

Mario S. Könz, Guglielmo Mazzola, Andrew J. Ochoa +2 more

Recently, it was demonstrated both theoretically and experimentally on the D-Wave quantum annealer that transverse-field quantum annealing does not find all ground states with equal probability. In particular, it was proposed that more complex driver Hamiltonians beyond transverse fields might mitigate this shortcoming. Here, we investigate the mechanisms of (un)fair sampling in quantum annealing. While higher-order terms can improve the sampling for selected small problems, we present multiple counterexamples where driver Hamiltonians that go beyond transverse fields do not remove the sampling bias. Using perturbation theory we explain why this is the case. In addition, we present large-scale quantum Monte Carlo simulations for spin glasses with known degeneracy in two space dimensions and demonstrate that the fair-sampling performance of quadratic driver terms is comparable to standard transverse-field drivers. Our results suggest that quantum annealing machines are not well suited for sampling applications, unless postprocessing techniques to improve the sampling are applied.

arXiv:1806.06081•Physical Review A•Sep 20, 2019•47 citations

Fair sampling of ground-state configurations of binary optimization problems

Zheng Zhu, Andrew J. Ochoa, Helmut G. Katzgraber

Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing-the heuristic employed in current commercially available quantum annealing machines-has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.

arXiv:1903.07600•Physical review. E•Jun 25, 2019•17 citations

Ground-state statistics from annealing algorithms: quantum versus classical approaches

Yoshiki Matsuda, Hidetoshi Nishimori, Helmut G. Katzgraber

We study the performance of quantum annealing for systems with ground-state degeneracy by directly solving the Schrödinger equation for small systems and quantum Monte Carlo simulations for larger systems. The results indicate that naive quantum annealing using a transverse field may not be well suited to identify all degenerate ground-state configurations, although the value of the ground-state energy is often efficiently estimated. An introduction of quantum transitions to all states with equal weights is shown to greatly improve the situation, but with a sacrifice in annealing time. We also clarify the relation between the spin configurations in degenerate ground states and the probabilities that those states are obtained by quantum annealing. The strengths and weaknesses of quantum annealing for problems with degenerate ground states are discussed in comparison with classical simulated annealing.

New Journal of Physics•Jul 9, 2009•74 citations

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

Masaru Hitomi, Masayuki Ohzeki

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.

quant-pharXiv:2610.29035•Oct 22, 2026•0 citations

Biased degenerate ground-state sampling of small Ising models with converged quantum approximate optimization algorithm

Elijah Pelofske

The quantum alternating operator ansatz, a generalization of the quantum approximate optimization algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the transverse field mixer as the driving Hamiltonian. One of the interesting properties of the transverse field driving Hamiltonian is that it results in nonuniform sampling of degenerate ground states of optimization problems. In this study, we numerically examine the fair sampling properties of the transverse field mixer QAOA, and Grover mixer QAOA (GM-QAOA), which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to a large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high-quality heuristically computed, but not necessarily optimal, QAOA angles, which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground states is quantified using the Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown, which exhibit exponential suppression of some degenerate ground states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step.

arXiv:2411.05294•Physical review. E•May 1, 2025•3 citations

Interpretation of Unfair Sampling in Quantum Annealing by Node Centrality

Naoki Maruyama, Masayuki Ohzeki

In applications where multiple optimal solutions are needed, transverse-field quantum annealing (QA) is known to sample degenerate ground states in a strongly biased manner. Despite extensive empirical observations, it remains unclear which features of degenerate ground states are preferentially sampled and why by QA. Here we analyze the final states using degenerate perturbation theory to characterize the preference among them. In this analysis, the adjacency matrix of the graph composed by the ground states naturally emerges, and we can predict the eigenvector centralities (one of the node centralities) are related to the probabilities of these states. We verify this prediction on toy models where degeneracy is lifted at first and second order, and we show that second-order weights encode local barrier information, relating sampling fairness to the flatness of the local energy landscape. Finally, this perspective suggests two practical routes toward fair sampling -- promoting connectivity of the graph and reducing heterogeneity of centralities -- and we illustrate consistency with higher-order drivers and minor-embedding transformations.

quant-pharXiv:2601.01920•Jan 6, 2026•0 citations
We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated with a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)NJOPFM1367-263010.1088/1367-2630/11/7/073021]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.
Recently, it was demonstrated both theoretically and experimentally on the D-Wave quantum annealer that transverse-field quantum annealing does not find all ground states with equal probability. In particular, it was proposed that more complex driver Hamiltonians beyond transverse fields might mitigate this shortcoming. Here, we investigate the mechanisms of (un)fair sampling in quantum annealing. While higher-order terms can improve the sampling for selected small problems, we present multiple counterexamples where driver Hamiltonians that go beyond transverse fields do not remove the sampling bias. Using perturbation theory we explain why this is the case. In addition, we present large-scale quantum Monte Carlo simulations for spin glasses with known degeneracy in two space dimensions and demonstrate that the fair-sampling performance of quadratic driver terms is comparable to standard transverse-field drivers. Our results suggest that quantum annealing machines are not well suited for sampling applications, unless postprocessing techniques to improve the sampling are applied.
Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing-the heuristic employed in current commercially available quantum annealing machines-has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.
We study the performance of quantum annealing for systems with ground-state degeneracy by directly solving the Schrödinger equation for small systems and quantum Monte Carlo simulations for larger systems. The results indicate that naive quantum annealing using a transverse field may not be well suited to identify all degenerate ground-state configurations, although the value of the ground-state energy is often efficiently estimated. An introduction of quantum transitions to all states with equal weights is shown to greatly improve the situation, but with a sacrifice in annealing time. We also clarify the relation between the spin configurations in degenerate ground states and the probabilities that those states are obtained by quantum annealing. The strengths and weaknesses of quantum annealing for problems with degenerate ground states are discussed in comparison with classical simulated annealing.
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≥5N \geq 5N≥5, we derive the exact ground-state energy, degeneracy, and defect structure for each congruence class of NNN 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=83N=83N=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=160N=160N=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.
The quantum alternating operator ansatz, a generalization of the quantum approximate optimization algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the transverse field mixer as the driving Hamiltonian. One of the interesting properties of the transverse field driving Hamiltonian is that it results in nonuniform sampling of degenerate ground states of optimization problems. In this study, we numerically examine the fair sampling properties of the transverse field mixer QAOA, and Grover mixer QAOA (GM-QAOA), which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to a large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high-quality heuristically computed, but not necessarily optimal, QAOA angles, which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground states is quantified using the Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown, which exhibit exponential suppression of some degenerate ground states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step.
In applications where multiple optimal solutions are needed, transverse-field quantum annealing (QA) is known to sample degenerate ground states in a strongly biased manner. Despite extensive empirical observations, it remains unclear which features of degenerate ground states are preferentially sampled and why by QA. Here we analyze the final states using degenerate perturbation theory to characterize the preference among them. In this analysis, the adjacency matrix of the graph composed by the ground states naturally emerges, and we can predict the eigenvector centralities (one of the node centralities) are related to the probabilities of these states. We verify this prediction on toy models where degeneracy is lifted at first and second order, and we show that second-order weights encode local barrier information, relating sampling fairness to the flatness of the local energy landscape. Finally, this perspective suggests two practical routes toward fair sampling -- promoting connectivity of the graph and reducing heterogeneity of centralities -- and we illustrate consistency with higher-order drivers and minor-embedding transformations.