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.
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.
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.
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.
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.
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 , … , 𝛾 𝑝 .