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:2512.14552

Fair sampling of ground-state configurations using hybrid quantum-classical MCMC algorithms

Yuichiro Nakano, Keisuke Fujii

quant-phSubmitted Dec 16, 2025• Announced Dec 17, 2025• 0 citations
arXivHTMLPDF

Abstract

We study the fair sampling properties of hybrid quantum-classical Markov chain Monte Carlo (MCMC) algorithms for combinatorial optimization problems with degenerate ground states. While quantum optimization heuristics such as quantum annealing and the quantum approximate optimization algorithm (QAOA) are known to induce biased sampling, hybrid quantum-classical MCMC incorporates quantum dynamics only as a proposal transition and enforces detailed balance through classical acceptance steps. Using small Ising models, we show that MCMC post-processing corrects the sampling bias of quantum dynamics and restores near-uniform sampling over degenerate ground states. We then apply the method to random $k$-SAT problems near the satisfiability threshold. For random 2-SAT, a hybrid MCMC combining QAOA-assisted neural proposals with single spin-flip updates achieves fairness comparable to that of PT-ICM. For random 3-SAT, where such classical methods are no longer applicable, the hybrid MCMC still attains approximately uniform sampling. We also examine solution counting and find that the required number of transitions is comparable to that of WalkSAT. These results indicate that hybrid quantum-classical MCMC provides a viable framework for fair sampling and solution enumeration.

Comments
12 pages, 7 figures

Related papers

Fair sampling with temperature-targeted QAOA based on quantum-classical correspondence theory

Tetsuro Abe, Shu Tanaka

In combinatorial optimization problems with degenerate ground states, fair sampling of degenerate solutions is essential. However, the quantum approximate optimization algorithm (QAOA) with a standard transverse-field mixer induces biases among degenerate states as circuit depth increases. Based on quantum-classical correspondence theory, we propose SBO-QAOA, which employs a temperature-dependent Hamiltonian encoding a Gibbs distribution as its ground state. Numerical simulations show that, unlike standard QAOA, SBO-QAOA yields ground-state probabilities converging to finite-temperature values with uniform distribution among degenerate states. These fairness and temperature-targeting properties are preserved even with only four variational parameters under a linear schedule.

quant-pharXiv:2601.16144•Jan 23, 2026•0 citations

Fair Sampling with Temperature-Targeted QAOA Based on Quantum–Classical Correspondence Theory

Tetsuro Abe, Shu Tanaka

In combinatorial optimization problems with degenerate ground states, fair sampling of degenerate solutions is essential. However, the quantum approximate optimization algorithm (QAOA) with a standard transverse-field mixer induces biases among degenerate states as circuit depth increases. Based on quantum–classical correspondence theory, we propose SBO-QAOA, which employs a temperature-dependent Hamiltonian encoding a Gibbs distribution as its ground state. Numerical simulations show that, unlike standard QAOA, SBO-QAOA yields ground-state probabilities converging to finite-temperature values with uniform distribution among degenerate states. These fairness and temperature-targeting properties are preserved even with only four variational parameters under a linear schedule.

Journal of the Physical Society of Japan•Jul 2, 2026•0 citations

Irreversibility Enhances Quantum-Enhanced Markov-Chain Monte Carlo

Kefan Cao, Zidong Cui, Lei Wang +1 more

Detailed balance underlies conventional Markov-chain Monte Carlo (MCMC) algorithms. Yet in classical systems, breaking detailed balance generates irreversible probability currents and can accelerate sampling. Whether irreversibility can similarly enhance quantum MCMC remains an intriguing question. Here we show that irreversibility provides a new route to improving the recent quantum-enhanced MCMC (QEMC), which combines quantum proposals with classical acceptance. By introducing state-dependent proposals that break detailed balance while preserving the target stationary distribution, we develop an irreversible quantum-enhanced Monte Carlo (IQEMC). Guided by Landau-Zener transitions, IQEMC promotes large energy descents from high-energy states while maintaining stable transitions near low-energy states. On spin-glass benchmarks, IQEMC outperforms QEMC without increasing computational complexity and, unlike the annealing baseline, exhibits a spectral gap that increases with system size and annealing speed. These results establish irreversibility as a physically grounded mechanism for enhancing quantum MCMC.

cond-mat.stat-mechCross-listedarXiv:2606.23350•Jun 23, 2026•0 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

Uniformity Bias in Ground-State Sampling Induced by Replica Alignment in Quantum Monte Carlo for Quantum Annealing

Naoki Maruyama, Masayuki Ohzeki, Kazuyuki Tanaka

Quantum annealing (QA) with a transverse field often fails to sample degenerate ground states fairly, limiting applicability to problems requiring diverse optimal solutions. Although Quantum Monte Carlo (QMC) is widely used to simulate QA, its ability to reproduce such unfair ground-state sampling remains unclear because stochastic and coherent quantum dynamics differ fundamentally. We quantitatively evaluate how accurately QMC reproduces the sampling bias in QA by comparing the final ground-state distributions from the QMC master equation and the Schrödinger equation. We find QMC tends to produce uniform ground-state probabilities, unlike QA's biased distribution, and that this uniformity bias strengthens as annealing proceeds. Our analysis reveals that this bias originates from replica alignment -- the dominance of configurations in which all Trotter replicas coincide -- caused by the energetic suppression and entropic reduction of kink configurations (replica mismatches). These findings clarify a fundamental limitation of discrete-time QMC in faithfully simulating QA dynamics, highlighting the importance of replica correlations and transition rules in achieving realistic ground-state sampling.

arXiv:2510.10566•Journal of the Physical Society of Japan•Feb 6, 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
We study the fair sampling properties of hybrid quantum-classical Markov chain Monte Carlo (MCMC) algorithms for combinatorial optimization problems with degenerate ground states. While quantum optimization heuristics such as quantum annealing and the quantum approximate optimization algorithm (QAOA) are known to induce biased sampling, hybrid quantum-classical MCMC incorporates quantum dynamics only as a proposal transition and enforces detailed balance through classical acceptance steps. Using small Ising models, we show that MCMC post-processing corrects the sampling bias of quantum dynamics and restores near-uniform sampling over degenerate ground states. We then apply the method to random kkk-SAT problems near the satisfiability threshold. For random 2-SAT, a hybrid MCMC combining QAOA-assisted neural proposals with single spin-flip updates achieves fairness comparable to that of PT-ICM. For random 3-SAT, where such classical methods are no longer applicable, the hybrid MCMC still attains approximately uniform sampling. We also examine solution counting and find that the required number of transitions is comparable to that of WalkSAT. These results indicate that hybrid quantum-classical MCMC provides a viable framework for fair sampling and solution enumeration.
In combinatorial optimization problems with degenerate ground states, fair sampling of degenerate solutions is essential. However, the quantum approximate optimization algorithm (QAOA) with a standard transverse-field mixer induces biases among degenerate states as circuit depth increases. Based on quantum-classical correspondence theory, we propose SBO-QAOA, which employs a temperature-dependent Hamiltonian encoding a Gibbs distribution as its ground state. Numerical simulations show that, unlike standard QAOA, SBO-QAOA yields ground-state probabilities converging to finite-temperature values with uniform distribution among degenerate states. These fairness and temperature-targeting properties are preserved even with only four variational parameters under a linear schedule.
In combinatorial optimization problems with degenerate ground states, fair sampling of degenerate solutions is essential. However, the quantum approximate optimization algorithm (QAOA) with a standard transverse-field mixer induces biases among degenerate states as circuit depth increases. Based on quantum–classical correspondence theory, we propose SBO-QAOA, which employs a temperature-dependent Hamiltonian encoding a Gibbs distribution as its ground state. Numerical simulations show that, unlike standard QAOA, SBO-QAOA yields ground-state probabilities converging to finite-temperature values with uniform distribution among degenerate states. These fairness and temperature-targeting properties are preserved even with only four variational parameters under a linear schedule.
Detailed balance underlies conventional Markov-chain Monte Carlo (MCMC) algorithms. Yet in classical systems, breaking detailed balance generates irreversible probability currents and can accelerate sampling. Whether irreversibility can similarly enhance quantum MCMC remains an intriguing question. Here we show that irreversibility provides a new route to improving the recent quantum-enhanced MCMC (QEMC), which combines quantum proposals with classical acceptance. By introducing state-dependent proposals that break detailed balance while preserving the target stationary distribution, we develop an irreversible quantum-enhanced Monte Carlo (IQEMC). Guided by Landau-Zener transitions, IQEMC promotes large energy descents from high-energy states while maintaining stable transitions near low-energy states. On spin-glass benchmarks, IQEMC outperforms QEMC without increasing computational complexity and, unlike the annealing baseline, exhibits a spectral gap that increases with system size and annealing speed. These results establish irreversibility as a physically grounded mechanism for enhancing quantum MCMC.
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.
Quantum annealing (QA) with a transverse field often fails to sample degenerate ground states fairly, limiting applicability to problems requiring diverse optimal solutions. Although Quantum Monte Carlo (QMC) is widely used to simulate QA, its ability to reproduce such unfair ground-state sampling remains unclear because stochastic and coherent quantum dynamics differ fundamentally. We quantitatively evaluate how accurately QMC reproduces the sampling bias in QA by comparing the final ground-state distributions from the QMC master equation and the Schrödinger equation. We find QMC tends to produce uniform ground-state probabilities, unlike QA's biased distribution, and that this uniformity bias strengthens as annealing proceeds. Our analysis reveals that this bias originates from replica alignment -- the dominance of configurations in which all Trotter replicas coincide -- caused by the energetic suppression and entropic reduction of kink configurations (replica mismatches). These findings clarify a fundamental limitation of discrete-time QMC in faithfully simulating QA dynamics, highlighting the importance of replica correlations and transition rules in achieving realistic ground-state sampling.
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.