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

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

Tetsuro Abe, Shu Tanaka

quant-phcond-mat.stat-mechSubmitted Jan 22, 2026• Announced Jan 23, 2026• 2 citations
arXivHTMLPDF

Abstract

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.

Comments
4pages, 3figures

Related papers

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•7 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•4 citations

Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers

David Bucher, Maximilian Janetschek, Michael Poppel +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-$k$-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.

quant-pharXiv:2604.02083•New Journal of Physics•Apr 3, 2026•12 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•1 citation

A Brief Introduction to the QAOA

Andreas Bärtschi

The Quantum Approximate Optimization Algorithm (QAOA) is a heuristic for unconstrained combinatorial optimization.It prepares a statefrom which one would like to sample good solutions with high probability.QAOA is specified by • the initial state + 𝑛 , the uniform superposition over all basis states,• a Cost Hamiltonian 𝐻 𝐶 , used to phase basis states proportional to their cost 𝐶 𝑥 : 𝑥 ↦ 𝑒 -𝑖𝛾𝐶(𝑥) |𝑥⟩ and to evaluate the expectation value of the QAOA state, ⟨𝜷, 𝜸 𝐻 𝐶 𝜷, 𝜸⟩,• a Transverse Field Mixer ∑ 𝑖=1 𝑛 𝑋 𝑖 , used to interfere states in order to boost good solutions,• 𝑝 rounds with individual angle parameters 𝛽 1 , … , 𝛽 𝑝 , 𝛾 1 , … , 𝛾 𝑝 .

•Jun 17, 2024•0 citations

Shortcuts to the quantum approximate optimization algorithm

Yahui Chai, Yong‐Jian Han, Yu-Chun Wu +3 more

The quantum approximate optimization algorithm (QAOA) is a quantum-classical hybrid algorithm intending to find the ground state of a target Hamiltonian. Theoretically, QAOA can obtain the approximate solution if the quantum circuit is deep enough. Actually, the performance of QAOA decreases practically if the quantum circuit is deep since near-term devices are not noise free, and the errors caused by noise accumulate as the quantum circuit increases. In order to reduce the depth of quantum circuits, we propose an ansatz dubbed as ``Shortcuts to QAOA'' (S-QAOA), S-QAOA provides shortcuts to the ground state of the target Hamiltonian by including more two-body interactions and releasing the parameter freedoms. To be specific, besides the existing $ZZ$ interaction in the QAOA ansatz, other two-body interactions are introduced in the S-QAOA ansatz such that the approximate solutions could be obtained with smaller circuit depth. Considering the Max-Cut problem and the Sherrington-Kirkpatrick model, numerically computation shows the $YY$ interaction has the best performance. The reason for this might arise from the counterdiabatic effect generated by $YY$ interaction. On top of this, we release the freedom of parameters of two-body interactions, which a priori do not necessarily have to be fully identical, and numerical results show that it is worth paying the extra cost of having more parameter freedom since one has a greater improvement on success rate.

arXiv:2112.10943•Physical Review A•Apr 8, 2022•22 citations
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, 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.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-kkk-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a heuristic for unconstrained combinatorial optimization.It prepares a statefrom which one would like to sample good solutions with high probability.QAOA is specified by • the initial state + 𝑛 , the uniform superposition over all basis states,• a Cost Hamiltonian 𝐻 𝐶 , used to phase basis states proportional to their cost 𝐶 𝑥 : 𝑥 ↦ 𝑒 -𝑖𝛾𝐶(𝑥) |𝑥⟩ and to evaluate the expectation value of the QAOA state, ⟨𝜷, 𝜸 𝐻 𝐶 𝜷, 𝜸⟩,• a Transverse Field Mixer ∑ 𝑖=1 𝑛 𝑋 𝑖 , used to interfere states in order to boost good solutions,• 𝑝 rounds with individual angle parameters 𝛽 1 , … , 𝛽 𝑝 , 𝛾 1 , … , 𝛾 𝑝 .
The quantum approximate optimization algorithm (QAOA) is a quantum-classical hybrid algorithm intending to find the ground state of a target Hamiltonian. Theoretically, QAOA can obtain the approximate solution if the quantum circuit is deep enough. Actually, the performance of QAOA decreases practically if the quantum circuit is deep since near-term devices are not noise free, and the errors caused by noise accumulate as the quantum circuit increases. In order to reduce the depth of quantum circuits, we propose an ansatz dubbed as ``Shortcuts to QAOA'' (S-QAOA), S-QAOA provides shortcuts to the ground state of the target Hamiltonian by including more two-body interactions and releasing the parameter freedoms. To be specific, besides the existing ZZZZZZ interaction in the QAOA ansatz, other two-body interactions are introduced in the S-QAOA ansatz such that the approximate solutions could be obtained with smaller circuit depth. Considering the Max-Cut problem and the Sherrington-Kirkpatrick model, numerically computation shows the YYYYYY interaction has the best performance. The reason for this might arise from the counterdiabatic effect generated by YYYYYY interaction. On top of this, we release the freedom of parameters of two-body interactions, which a priori do not necessarily have to be fully identical, and numerical results show that it is worth paying the extra cost of having more parameter freedom since one has a greater improvement on success rate.