Sbo-QAOA Achieves Fair Sampling of Degenerate States with Four Variational Parameters

Scientists are tackling a critical challenge in quantum optimisation: ensuring fair sampling when multiple optimal solutions exist. Tetsuro Abe and Shu Tanaka, both from the Graduate School of Science and Technology at Keio University, alongside Shu Tanaka et al, present a novel approach to the Quantum Approximate Optimisation Algorithm (QAOA) that addresses biases arising in standard implementations as computational complexity increases. Their research introduces a temperature-targeted QAOA , dubbed SBO-QAOA , grounded in classical correspondence theory, which demonstrably yields uniform probabilities across degenerate ground states, even with limited variational parameters. This breakthrough is significant because it moves us closer to reliable quantum solutions for complex combinatorial problems, paving the way for more robust and unbiased optimisation processes.

This new study, published in the Journal of the Physical Society of Japan LETTERS, introduces a method for achieving fairer sampling by fundamentally altering the target Hamiltonian within the QAOA framework. The team achieved this breakthrough by leveraging quantum, classical correspondence theory, a theoretical framework linking classical statistical mechanics to quantum systems. Experiments show that SBO-QAOA maintains these fairness and temperature-targeting properties while utilizing only four variational parameters under a linear schedule, a significant reduction in computational overhead.

The researchers meticulously constructed the target Hamiltonian, ensuring it accurately represents the classical Gibbs distribution at a specified temperature. The resulting Hamiltonian, termed the SBO Hamiltonian, is then integrated into the QAOA cost function, replacing the traditional target Hamiltonian. This research establishes a pathway towards more reliable quantum optimization algorithms, particularly in scenarios where identifying a single optimal solution is insufficient and a diverse set of equivalent solutions is required. The ability to target specific temperatures and achieve fair sampling opens doors for applications in fields like logistics, finance, drug discovery, and machine learning, where exploring multiple optimal solutions can lead to more robust and effective outcomes. Furthermore, the simplified parameterization of SBO-QAOA, reducing the number of optimization variables to just four, suggests a promising route for implementation on near-term quantum devices.

SBO-QAOA and Temperature-Dependent Hamiltonian Design offer promising avenues

Scientists developed SBO-QAOA, a novel quantum approximate optimization algorithm designed to address biases in sampling degenerate ground states prevalent in standard QAOA implementations. This work centres on achieving fair sampling in combinatorial optimization, particularly when dealing with systems possessing multiple equivalent lowest-energy configurations. To achieve this, the team engineered a cost Hamiltonian, HS(T), defined as −e−α/T Σi σx i −eHi/T, where α is determined by the maximum norm of local Hamiltonian terms Hi, and T represents the target temperature. This innovative approach directly addresses the limitations of standard QAOA by focusing on the design of the target Hamiltonian rather than modifying the mixer.

Experiments employed an Ising model, H0 = −Σ1≤i<j≤N Jij σzi σzj − Σi hi σzi, to represent the target problem, with the classical energy H0(σ) calculated for each computational basis state |σ⟩. The quantum state at circuit depth p was generated using |ψp⟩ = ∏k=1 e−iβk HXe−iγk HC|+⟩⊗N, where βk and γk are variational parameters optimised using the Powell method. Crucially, the researchers implemented two parameterization schemes: a full-parameter approach with 2p independent variables, and a linearized scheme reducing the parameters to just four (γslope, γintcp, βslope, βintcp) via γk = γslope k / p + γintcp and βk = βslope k / p + βintcp. Numerical results confirm that the probability distribution over degenerate ground states becomes uniform, overcoming the fundamental limitations of biased sampling observed in standard QAOA and paving the way for more reliable quantum optimization.

SBO-QAOA resolves bias in degenerate ground states

Experiments revealed that with full-parameter QAOA, the total ground-state probability, PGS, rapidly exceeded 0.9 within a few depths and approached unity at p ∼10. However, the distribution within the degenerate subspace exhibited clear bias, with probabilities P1, P2, and P3 failing to coincide even at high-p regimes. Linearized QAOA mirrored this biased behaviour, demonstrating that even with only four variational parameters, the probability distribution remained non-uniform as p increased. Linearized SBO-QAOA achieved comparable results, with PGS converging to 0.83 and the distribution becoming increasingly uniform, though with slightly more noticeable differences at smaller values of p.

Data shows that for both full-parameter and linearized SBO-QAOA, the total variation distance, DTVD, between the final distribution Pp(σ) and the Gibbs distribution PGibbs(σ) decreased with increasing p, converging to values close to zero. Specifically, at a temperature of T = 1.0, DTVD approached zero as p increased for both full-parameter and linearized SBO-QAOA, indicating convergence towards reproducing the entire state distribution corresponding to the specified temperature. This behaviour demonstrates that SBO-QAOA not only concentrates probability on the degenerate ground states but also accurately replicates the entire thermal distribution.

SBO-QAOA resolves biased sampling in optimisation

Furthermore, the researchers successfully implemented a four-parameter linearization scheme, maintaining fair sampling despite significantly reducing the number of variational parameters from 2p to four, suggesting that complexity of the mixer isn’t necessarily linked to achieving fairness. The authors acknowledge a limitation regarding scalability, as exact evaluation of the matrix exponential becomes challenging for larger systems due to the many-body interactions induced by the temperature-dependent Hamiltonian. Future research will focus on developing efficient Pauli-string expansions and circuit decompositions to enable direct implementation of SBO-QAOA on gate-based quantum devices, alongside exploring low-order approximations suitable for implementable interaction orders.