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

This paper proposes SBO-QAOA, a temperature-targeted quantum algorithm based on quantum-classical correspondence theory that achieves fair sampling of degenerate ground states by converging to a uniform Gibbs distribution, overcoming the biases inherent in standard QAOA even with minimal variational parameters.

The Gist

The Big Problem: Finding the "Fair" Winner

Imagine you are running a contest to find the best solution to a complex puzzle. In many cases, there isn't just one perfect answer; there are several different answers that are all equally perfect. Let's call these "degenerate ground states."

In the real world, if you have five different teams that all tie for first place, you want to pick one of them at random so that no team feels cheated. This is called fair sampling. You want the computer to pick Team A, Team B, or Team C with equal probability, not favoring one just because of how the computer works.

The problem is that the current leading method for solving these puzzles on quantum computers (called QAOA) is a bit like a biased referee. As the computer gets deeper into the calculation (increasing the "circuit depth"), it starts to accidentally favor certain winning teams over others, even though they are all mathematically equal. It stops being fair.

The Old Way vs. The New Way

The researchers, Tetsuro Abe and Shu Tanaka, looked at how to fix this.

• The Old Way (Standard QAOA): Think of this as trying to find the bottom of a valley. The computer uses a standard "shaking" tool (a transverse-field mixer) to help the ball roll down. The problem is that this shaking tool pushes the ball toward specific spots at the bottom of the valley, ignoring the other equally deep spots. It's like a wind that only blows in one direction, pushing the ball to one side of the valley floor.
• The New Way (SBO-QAOA): Instead of changing the "shaking" tool, the researchers decided to change the shape of the valley itself. They used a clever mathematical trick based on "quantum-classical correspondence."

The Creative Analogy: The Temperature-Targeted Map

Imagine you want to simulate a crowd of people in a room.

• Standard QAOA is like trying to get everyone to sit in the single most comfortable chair. It works, but it forces everyone into one spot, or it gets stuck favoring one chair over another.
• SBO-QAOA is like setting the room's temperature.
  • If the room is very cold (low temperature), everyone wants to sit in the absolute best seats.
  • If the room is warm (higher temperature), people are more relaxed and spread out, sitting in various good seats with a probability that matches how comfortable they are.

The researchers designed a new "map" (called the SBO Hamiltonian) that encodes this temperature concept directly into the quantum computer's rules. Instead of just looking for the single lowest energy point, the computer is programmed to naturally settle into a distribution that looks like a warm room where everyone has an equal chance of sitting in any of the "best" seats.

What They Did (The Experiment)

To test this, they used a tiny "toy model" with just 5 spins (like 5 tiny magnets). This model was designed to have six different solutions that were all equally good (a six-fold tie).

They ran two types of simulations:

1. Standard QAOA: They cranked up the complexity (circuit depth) to see if it could find the winners.
2. SBO-QAOA: They used their new "temperature-targeted" map.

The Results

• Standard QAOA: As they made the calculation deeper, the computer found the winning solutions very often (almost 100% of the time). However, it was unfair. It kept picking two specific winning solutions and ignoring the other four. The "referee" was biased.
• SBO-QAOA: The computer found the winning solutions about 83% of the time (which is exactly what physics predicts for a room at that specific "temperature"). Crucially, when it did find a winner, it picked all six solutions with equal probability. It was perfectly fair.

Even better, they tested a "simplified" version of their new method where they reduced the number of settings the computer had to tune down to just four knobs. Even with this simple setup, the computer remained fair and temperature-targeted.

The Takeaway

The paper claims that you don't need to invent a complicated new "shaking" tool to get fair results. Instead, if you change the target the computer is aiming for (using the SBO Hamiltonian), the computer naturally learns to pick all the tied winners fairly, just like people spreading out in a room at a specific temperature.

This works even if you keep the settings simple (linear schedule), suggesting that fair sampling is possible without making the quantum computer's circuit overly complex. The authors note that while this works great on small simulations, the next step is figuring out how to build this efficiently on real, large-scale quantum machines, as the new "map" involves complex interactions that are hard to build physically.

Technical Summary

Technical Summary: Fair Sampling with Temperature-Targeted QAOA

Problem Statement
In combinatorial optimization problems characterized by degenerate ground states, the ability to perform "fair sampling"—obtaining a uniform distribution over all degenerate solutions without bias—is critical. While Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) are promising metaheuristics for these problems, standard implementations utilizing a transverse-field mixer often fail to achieve fair sampling. Theoretical and experimental evidence suggests that as circuit depth increases, standard QAOA induces biases among degenerate states, favoring specific solutions even when the approximation ratio converges to unity. Existing solutions, such as specialized mixers or hybrid post-processing, often increase circuit complexity or require additional classical computational steps.

Methodology
The authors propose SBO-QAOA, a variant of QAOA that addresses sampling bias not by modifying the mixer, but by redesigning the target (cost) Hamiltonian based on quantum–classical correspondence theory.

• Theoretical Framework: Instead of targeting the ground state of the classical Ising Hamiltonian $\hat{H}_0$, SBO-QAOA targets the ground state of an effective Hamiltonian, $\hat{H}_S(T)$, derived by Somma et al. This Hamiltonian is constructed such that its unique ground state corresponds to a quantum state $|\psi_{Gibbs}(T)\rangle$, where the probability amplitudes are the square roots of the Boltzmann factors of the classical system at a specific temperature $T$.
• Hamiltonian Construction: The SBO Hamiltonian is defined as:
  $$\hat{H}_S(T) = -e^{-\alpha/T} \sum_{i=1}^N \left( \hat{\sigma}_i^x - e^{\hat{H}_i/T} \right)$$
  where $\hat{H}_i$ represents the local terms of $\hat{H}_0$ dependent on spin $i$, and $\alpha$ is a scaling factor preventing divergence as $T \to 0$. In SBO-QAOA, $\hat{H}_C$ is set to $\hat{H}_S(T)$, while the standard transverse-field mixer $\hat{H}_X$ is retained.
• Parameterization Schemes: The study evaluates two parameterization strategies for the variational angles $\{\gamma_k, \beta_k\}$:
  1. Full-parameter: $2p$ independent variables for circuit depth $p$.
  2. Linearized: A reduction scheme where angles are linear functions of the depth index, reducing the optimization variables to four ($\gamma_{slope}, \gamma_{intcp}, \beta_{slope}, \beta_{intcp}$) regardless of depth.
• Experimental Setup: Numerical simulations were performed on a 5-spin frustrated Ising toy model with six-fold ground-state degeneracy. The system was simulated exactly (full matrix evolution) to compare standard QAOA and SBO-QAOA across varying circuit depths ($p=1$ to $100$) and temperatures.

Key Results

• Standard QAOA Bias: In standard QAOA (targeting $\hat{H}_0$), increasing circuit depth $p$ drives the total ground-state probability ($P_{GS}$) toward unity. However, the distribution within the degenerate subspace remains biased; specific state pairs become dominant while others are suppressed, regardless of whether full or linearized parameters are used.
• SBO-QAOA Fairness: When targeting $\hat{H}_S(T)$, SBO-QAOA exhibits fundamentally different behavior:
  • Temperature Targeting: The total ground-state probability $P_{GS}$ does not approach unity but saturates at a value consistent with the Gibbs distribution probability at the specified temperature $T$ (e.g., $\approx 0.83$ for $T=1$).
  • Uniform Sampling: As $p$ increases, the probability distribution across the degenerate ground states becomes uniform. The probabilities of distinct state pairs converge to identical values, confirming fair sampling.
  • Total Variation Distance (TVD): The TVD between the output distribution and the target Gibbs distribution decreases with increasing $p$, converging near zero. This confirms that the algorithm reproduces the full finite-temperature distribution, not just the ground states.
• Robustness to Parameter Reduction: The fair sampling and temperature-targeting properties of SBO-QAOA are preserved even under the linearized scheme, where the number of variational parameters is reduced from $2p$ to just four.

Significance and Claims
The paper claims that fair sampling in QAOA can be achieved without increasing the complexity of the mixer or adding classical post-processing steps. By replacing the target Hamiltonian with the SBO Hamiltonian, the algorithm inherently encodes the Gibbs distribution as its ground state. The authors demonstrate that this approach allows for:

1. Fair Sampling: Achieving a uniform distribution over degenerate ground states.
2. Temperature Targeting: Controlling the sampling distribution via the parameter $T$.
3. Efficiency: Maintaining these properties with a minimal set of variational parameters (four), making the approach potentially scalable in terms of optimization complexity.

The authors note that while the current work validates these properties on a small system via exact diagonalization, future work must address scalability. Specifically, implementing $\hat{H}_S(T)$ on gate-based devices requires efficient Pauli-string expansions and circuit decompositions, as the Hamiltonian generally induces many-body interactions.