Sbo-QAOA uses four variational parameters to achieve fair sampling of degenerate states

Scientists are tackling a key challenge in quantum optimization: ensuring fair sampling when multiple optimal solutions exist. Tetsuro Abe and Shu Tanaka of the Keio University Graduate School of Science and Engineering, along with Shu Tanaka and colleagues, will introduce a new approach to quantum approximation optimization algorithms (QAOA) that addresses biases that arise in standard implementations due to increased computational complexity. Their work introduces a temperature-targeted QAOA called SBO-QAOA based on classical correspondence theory and demonstrates that uniform probabilities can be obtained across degenerate ground states even when variational parameters are limited. This breakthrough is important because it brings us closer to reliable quantum solutions to complex combinatorial problems and paves the way for more robust and unbiased optimization processes.

This new research Journal of the Physical Society of Japan LETTERSintroduces a method to achieve fairer sampling by fundamentally changing the target Hamiltonian within the QAOA framework. The research team achieved this breakthrough by leveraging quantum-classical correspondence theory, a theoretical framework that connects classical statistical mechanics to quantum systems. Experiments show that SBO-QAOA maintains these fairness and temperature target properties while utilizing only four variational parameters under a linear schedule and significantly reduces computational overhead.

The researchers meticulously constructed the target Hamiltonian so that it could accurately represent the classical Gibbs distribution at a given temperature. The resulting Hamiltonian, called the SBO Hamiltonian, is integrated into the QAOA cost function and replaces the traditional target Hamiltonian. This work establishes a path towards more reliable quantum optimization algorithms, especially in scenarios where identifying a single optimal solution is not enough and a diverse set of equivalent solutions is required. The ability to target specific temperatures and achieve unbiased sampling opens the door to applications in areas such as logistics, finance, drug discovery, and machine learning, where exploring multiple optimal solutions yields more robust and effective outcomes. Moreover, the simplified parameterization of SBO-QAOA and reduction of the number of optimization variables to only four suggests a promising path for implementation in quantum devices in the near future.

SBO-QAOA and temperature-dependent Hamiltonian design offer a promising path

Scientists developed SBO-QAOA, a new quantum approximation optimization algorithm designed to address biases in sampling degenerate ground states common in standard QAOA implementations. This work focuses on achieving fair sampling in combinatorial optimization, especially when dealing with systems with multiple equivalent minimum energy configurations. To achieve this, the team designed a cost Hamiltonian HS(T) defined as −e−α/T Σi σx i −eHi/T. where α is determined by the maximum norm of the local Hamiltonian term 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.

The experiment used the Ising model, H0 = −Σ1≤i.

SBO-QAOA resolves degenerate ground state bias

Experiments reveal that for full-parameter QAOA, the total ground state probability PGS rapidly exceeds 0.9 within several depths and approaches 1 at p ~10. However, the distribution within the degenerate subspace showed a clear bias, and the probabilities P1, P2, and P3 did not match even in the high p region. The linearized QAOA reflects this biased behavior, showing that even with only four variational parameters, the probability distribution remains inhomogeneous as p increases. Linearized SBO-QAOA achieved comparable results, with PGS converging to 0.83 and an increasingly uniform distribution, although smaller values ​​of p led to slightly more noticeable differences.

The data show that for both full parameters and linearized SBO-QAOA, the total variation distance DTVD between the final distribution Pp(σ) and the Gibbs distribution PGibbs(σ) decreases with increasing p and converges to a value close to zero. Specifically, at temperature T = 1.0, DTVD approaches zero as p increases for both full parameters and linearized SBO-QAOA, indicating convergence towards reproduction of the entire state distribution corresponding to a given temperature. This behavior shows that SBO-QAOA not only concentrates the probabilities on the degenerate ground state but also accurately reproduces the entire thermal distribution.

SBO-QAOA solves sampling bias in optimization

Furthermore, the researchers successfully implemented a four-parameter linearization scheme, significantly reducing the number of variational parameters from 2p to 4, yet maintaining unbiased sampling. This suggests that mixer complexity is not necessarily tied to achieving fairness. The authors acknowledge limitations regarding scalability, as many-body interactions caused by the temperature-dependent Hamiltonian make accurate evaluation of the matrix index difficult in large systems. Future research will focus on developing efficient Pauli string extensions and circuit decompositions that enable direct implementation of SBO-QAOA on gate-based quantum devices, in parallel with the search for low-order approximations suitable for implementable interaction orders.