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:1912.10701 · Journal of the Physical Society of Japan

Fair Sampling by Simulated Annealing on Quantum Annealer

Masayuki Yamamoto, Masayuki Ohzeki, Kazuyuki Tanaka

Published Jan 28, 2020• 34 citations
arXivHTMLPDF

Abstract

Conventional quantum annealing does not sample all ground states fairly. We demonstrate that fair sampling can be achieved by performing simulated annealing on a quantum annealer. We discuss the problems that occur when implementing this method and propose an alternative way to overcome them. We numerically verify the fair sampling ability of our method in a small-scale toy model.

DOI
10.7566/jpsj.89.025002

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

Achieving fair sampling in quantum annealing

Vaibhaw Kumar, Casey Tomlin, C. Nehrkorn +2 more

Sampling all ground states of a Hamiltonian with equal probability is a desired feature of a sampling algorithm, but recent studies indicate that common variants of transverse field quantum annealing sample the ground state subspace unfairly. In this note, we present perturbation theory arguments suggesting that this deficiency can be corrected by employing reverse annealing-inspired paths. We confirm that this conclusion holds in simulations of previously studied small instances with degeneracy, as well as larger instances on quantum annealing hardware.

arXiv:2007.08487•Jul 16, 2020•12 citations

Advantages of Unfair Quantum Ground-State Sampling

Brian Hu Zhang, Gene Wagenbreth, Víctor Martín-Mayor +1 more

The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.

arXiv:1701.01524•Scientific Reports•Apr 13, 2017•26 citations

Optimization through quantum annealing: theory and some applications

Demian A. Battaglia, Lorenzo Stella

Quantum annealing is a promising tool for solving optimization problems, similar in some ways to the traditional (classical) simulated annealing of Kirkpatrick et al. Simulated annealing takes advantage of thermal fluctuations in order to explore the optimization landscape of the problem at hand, whereas quantum annealing employs quantum fluctuations. Intriguingly, quantum annealing has been proved to be more effective than its classical counterpart in many applications. We illustrate the theory and the practical implementation of both classical and quantum annealing – highlighting the crucial differences between these two methods – by means of results recently obtained in experiments, in simple toy-models, and more challenging combinatorial optimization problems (namely, Random Ising model and Travelling Salesman Problem). The techniques used to implement quantum and classical annealing are either deterministic evolutions, for the simplest models, or Monte Carlo approaches, for harder optimization tasks. We discuss the pro and cons of these approaches and their possible connections to the landscape of the problem addressed.

Contemporary Physics•Jul 1, 2006•8 citations

Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

Shunta Ide, Shu Tanaka

Quantum annealing (QA) is a promising approach for solving combinatorial optimization problems; however, it is known to exhibit unfair sampling, in which degenerate ground states are not sampled with equal probability even for sufficiently long annealing times. Fair sampling is important in applications such as solution diversity assessment and combinatorial counting, yet the mechanism of unfair sampling remains poorly understood, particularly in constrained combinatorial optimization problems. In this work, we investigate unfair sampling of QA in weighted graph bipartitioning problems (GBP), a representative constrained optimization problem. We study how the penalty coefficient in the penalty method affects sampling fairness. Through numerical simulations and experiments on the D-Wave Advantage2 system, we show that increasing the penalty coefficient reduces unfair sampling in a representative single instance, and that this qualitative behavior is also observed on actual hardware. A scaling analysis over randomly generated instances with up to 12 spins reveals that, while this trend does not hold universally, more than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases, even at the largest system size studied. These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability under practical annealing conditions, and call for a deeper theoretical understanding of unfair sampling in constrained optimization problems.

quant-pharXiv:2604.11449•Apr 14, 2026•0 citations

A Note on Enumeration by Fair Sampling

Yuta Mizuno, Tamiki Komatsuzaki

This note describes an algorithm for enumerating all the elements in a finite set based on uniformly random sampling from the set. This algorithm can be used for enumeration by fair sampling with quantum annealing. Our algorithm is based on a lemma of the coupon collector's problem and is an improved version of the algorithm described in arXiv:2007.08487 (2020). We provide a mathematical analysis and a numerical demonstration of our algorithm.

arXiv:2104.01941•Apr 5, 2021•0 citations
Conventional quantum annealing does not sample all ground states fairly. We demonstrate that fair sampling can be achieved by performing simulated annealing on a quantum annealer. We discuss the problems that occur when implementing this method and propose an alternative way to overcome them. We numerically verify the fair sampling ability of our method in a small-scale toy model.
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.
Sampling all ground states of a Hamiltonian with equal probability is a desired feature of a sampling algorithm, but recent studies indicate that common variants of transverse field quantum annealing sample the ground state subspace unfairly. In this note, we present perturbation theory arguments suggesting that this deficiency can be corrected by employing reverse annealing-inspired paths. We confirm that this conclusion holds in simulations of previously studied small instances with degeneracy, as well as larger instances on quantum annealing hardware.
The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.
Quantum annealing is a promising tool for solving optimization problems, similar in some ways to the traditional (classical) simulated annealing of Kirkpatrick et al. Simulated annealing takes advantage of thermal fluctuations in order to explore the optimization landscape of the problem at hand, whereas quantum annealing employs quantum fluctuations. Intriguingly, quantum annealing has been proved to be more effective than its classical counterpart in many applications. We illustrate the theory and the practical implementation of both classical and quantum annealing – highlighting the crucial differences between these two methods – by means of results recently obtained in experiments, in simple toy-models, and more challenging combinatorial optimization problems (namely, Random Ising model and Travelling Salesman Problem). The techniques used to implement quantum and classical annealing are either deterministic evolutions, for the simplest models, or Monte Carlo approaches, for harder optimization tasks. We discuss the pro and cons of these approaches and their possible connections to the landscape of the problem addressed.
Quantum annealing (QA) is a promising approach for solving combinatorial optimization problems; however, it is known to exhibit unfair sampling, in which degenerate ground states are not sampled with equal probability even for sufficiently long annealing times. Fair sampling is important in applications such as solution diversity assessment and combinatorial counting, yet the mechanism of unfair sampling remains poorly understood, particularly in constrained combinatorial optimization problems. In this work, we investigate unfair sampling of QA in weighted graph bipartitioning problems (GBP), a representative constrained optimization problem. We study how the penalty coefficient in the penalty method affects sampling fairness. Through numerical simulations and experiments on the D-Wave Advantage2 system, we show that increasing the penalty coefficient reduces unfair sampling in a representative single instance, and that this qualitative behavior is also observed on actual hardware. A scaling analysis over randomly generated instances with up to 12 spins reveals that, while this trend does not hold universally, more than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases, even at the largest system size studied. These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability under practical annealing conditions, and call for a deeper theoretical understanding of unfair sampling in constrained optimization problems.