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:2411.05294 · Physical review. E

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

Elijah Pelofske

Published May 1, 2025• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.111.054103

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

Depth One Quantum Alternating Operator Ansatz as an Approximate Gibbs Distribution Sampler

Elijah Pelofske

This study numerically investigates the thermal sampling properties of QAOA, the Quantum Alternating Operator Ansatz which was generalized from the original Quantum Approximate Optimization Algorithm. Specifically, the ability of QAOA to sample from the Gibbs distribution, equivalently the Boltzmann distribution, defined by a classical Ising model, specifically a fully connected disordered spin glass (Sherrington-Kirkpatrick) model. We focus on two different QAOA mixers; the standard transverse field X mixer, and the Grover mixer. At a QAOA depth of one we examine, for a single full QAOA parameter search space period, the energy landscape, the Shannon entropy landscape of the QAOA probability distribution, and the tradeoff between Boltzmann distribution sampling temperature and error rate (how close to the true Boltzmann distribution is the QAOA distribution). We find that at very high temperatures one-round Grover mixer QAOA can sample from the Boltzmann distribution more accurately than the standard X mixer QAOA at one round. Both X mixer and Grover mixer depth one QAOA can serve as approximate Boltzmann distribution samplers, and how good this approximation is depends heavily on the QAOA angle choice.

arXiv:2510.10345•Oct 11, 2025•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

Performance upper bound of a Grover-mixer quantum alternating operator ansatz

Ningyi Xie, Jiahua Xu, Tiejin Chen +4 more

The quantum alternating operator ansatz (QAOA) represents a branch of quantum algorithms for solving combinatorial optimization problems. A specific variant, the Grover-mixer (GM) QAOA, ensures uniform amplitude across states that share equivalent objective values. This property makes the algorithm independent of the problem structure, focusing instead on the distribution of objective values within the problem. In this work we provide an alternative proof for the upper bound on the probability of measuring a computational basis state from a GM QAOA circuit with a given depth, which is a critical factor in QAOA cost. Using this, we derive the upper bounds for the probability of sampling an optimal solution and for the approximation ratio of maximum optimization problems, both dependent on the objective value distribution. Through numerical analysis, we link the distribution to the problem size and build the regression models that relate the problem size, QAOA depth, and performance upper bound. Our results suggest that the GM QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.

Physical Review A•Jan 2, 2025•5 citations

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

Salvatore Mandrà, Zheng Zhu, Helmut G. Katzgraber

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.

arXiv:1606.07146•Physical Review Letters•Feb 17, 2017•72 citations

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

Yuichiro Nakano, Keisuke Fujii

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.

quant-pharXiv:2512.14552•Dec 17, 2025•0 citations
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 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.
This study numerically investigates the thermal sampling properties of QAOA, the Quantum Alternating Operator Ansatz which was generalized from the original Quantum Approximate Optimization Algorithm. Specifically, the ability of QAOA to sample from the Gibbs distribution, equivalently the Boltzmann distribution, defined by a classical Ising model, specifically a fully connected disordered spin glass (Sherrington-Kirkpatrick) model. We focus on two different QAOA mixers; the standard transverse field X mixer, and the Grover mixer. At a QAOA depth of one we examine, for a single full QAOA parameter search space period, the energy landscape, the Shannon entropy landscape of the QAOA probability distribution, and the tradeoff between Boltzmann distribution sampling temperature and error rate (how close to the true Boltzmann distribution is the QAOA distribution). We find that at very high temperatures one-round Grover mixer QAOA can sample from the Boltzmann distribution more accurately than the standard X mixer QAOA at one round. Both X mixer and Grover mixer depth one QAOA can serve as approximate Boltzmann distribution samplers, and how good this approximation is depends heavily on the QAOA angle choice.
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.
The quantum alternating operator ansatz (QAOA) represents a branch of quantum algorithms for solving combinatorial optimization problems. A specific variant, the Grover-mixer (GM) QAOA, ensures uniform amplitude across states that share equivalent objective values. This property makes the algorithm independent of the problem structure, focusing instead on the distribution of objective values within the problem. In this work we provide an alternative proof for the upper bound on the probability of measuring a computational basis state from a GM QAOA circuit with a given depth, which is a critical factor in QAOA cost. Using this, we derive the upper bounds for the probability of sampling an optimal solution and for the approximation ratio of maximum optimization problems, both dependent on the objective value distribution. Through numerical analysis, we link the distribution to the problem size and build the regression models that relate the problem size, QAOA depth, and performance upper bound. Our results suggest that the GM QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
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.
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.