Technical Summary: Quantum-Informed Surrogate Sampling (QISS) for Combinatorial Optimization

1. Problem Statement

Combinatorial optimization problems, such as Maximum Cut (MaxCut) and Maximum Independent Set (MIS), are computationally challenging at scale. While the Quantum Approximate Optimization Algorithm (QAOA) offers a promising hybrid quantum-classical approach, its performance on near-term hardware is constrained by noise and coherence limitations. These constraints typically restrict QAOA implementations to shallow circuits (low depth $p$).

A fundamental limitation of shallow QAOA is locality: for sparse graphs, the circuit's "light cone" is bounded by the depth $p$, not the problem size $N$. Consequently, fixed-$p$ QAOA often fails to exploit global problem structures and inherits limitations similar to local classical algorithms. Furthermore, the full output distribution of a quantum state is generally intractable to sample classically, and the quantum device itself cannot directly produce high-quality solutions when restricted to shallow depths.

The paper addresses the need for a method that leverages the specific strengths of near-term quantum devices—efficiently estimating low-order local statistics—while delegating the generation of candidate solutions to scalable classical post-processing.

2. Methodology: Quantum-Informed Surrogate Sampling (QISS)

The authors propose Quantum-Informed Surrogate Sampling (QISS), a post-processing framework that generates candidate solutions from low-weight quantum correlations without requiring explicit dependence on the combinatorial problem structure during the sampling phase.

Core Workflow

1. Quantum Estimation: A shallow QAOA circuit (depth $p$) is executed on a quantum device (or simulated) to estimate a selected set of low-weight expectation values (correlators) $\mu_{S_\alpha}$:
   $$\mu_{S_\alpha} = \langle \psi_p(\gamma, \beta) | \prod_{i \in S_\alpha} Z_i | \psi_p(\gamma, \beta) \rangle$$
   The paper focuses on weights $|S_\alpha| \in \{1, 2\}$. These values are accessible via repeated measurements and are amenable to error mitigation.

2. Surrogate Distribution Construction: A classical factor distribution $P(z)$ is constructed over the solution space $\{-1, +1\}^N$ using these measured correlators as parameters:
   $$P(z) \propto \prod_{S_\alpha \in \mathcal{S}} \left( 1 + \mu_{S_\alpha} \chi_{S_\alpha}(z) \right)$$
   where $\chi_{S_\alpha}(z) = \prod_{i \in S_\alpha} z_i$ is the parity function. This distribution is equivalent to a Gibbs distribution of an effective Ising Hamiltonian $H'$ with couplings $J_{S_\alpha} = -\text{arctanh}(\mu_{S_\alpha})$.

3. Classical Sampling: Candidate solutions are drawn from $P(z)$ using Markov-chain Monte Carlo (MCMC). The sampling utilizes single-site conditional updates, which are efficient because the conditional probability for a spin flip depends only on the local factors involving that spin. The normalization constant (partition function) is never required.

4. Correlator Selection: The paper distinguishes between two sets of correlators:

   • Edge Set ($\mathcal{S} = E \cup V$): Only direct edges of the problem graph. On locally tree-like graphs, this reproduces the QAOA moments without improvement.
   • Augmented Set ($\mathcal{S}' = E' \cup V$): Includes all pairs $(i, j)$ within the light cone distance $d_G(i, j) \le 2p$. This creates a dense, non-tree-like factor graph, allowing the surrogate to capture higher-order correlations implicitly and generate solutions superior to the raw QAOA output.

Key Features

• Training-Free: The method uses fixed, tree-optimal QAOA angles (from Ref. [61]), requiring no variational optimization of the surrogate.
• Modularity: The sampling step is cost-function agnostic; it only requires the correlators.
• Noise Resilience: The mapping from correlators to couplings ($\text{arctanh}$) is smooth, making the surrogate robust to noise in the measured statistics.

3. Key Contributions and Results

A. MaxCut on 3-Regular Graphs

• Performance vs. Vanilla QAOA: When using the augmented correlator set (all pairs within distance $2p$), QISS significantly outperforms vanilla QAOA. Specifically, QISS using correlators from a depth $p=3$ or $p=4$ QAOA circuit achieves average cut fractions that surpass vanilla QAOA at depth $p=17$ (the largest depth for which tree-optimal angles are known).
• Warm-Start Integration: The method was combined with Regularized Warm-Start QAOA (RWS-QAOA). Even at shallow depths ($p=1, 2$), QISS post-processing improved the solution quality of RWS-QAOA, pushing the approximation ratio close to the optimal bound.
• Hardware Validation: Experiments were conducted on the 54-qubit IQM Emerald QPU. The results demonstrated that QISS is highly noise-resilient. The approximation ratios obtained from raw, noisy QPU correlators were nearly indistinguishable from those obtained from noiseless simulations. The device noise was effectively "washed out" by the post-processing, rendering error mitigation largely irrelevant for the final solution quality in this regime.
• Scalability: The method maintained performance up to $N=140$ (limited by the number of available qubits after variable freezing), with approximation ratios remaining stable and well above standard SDP guarantees.

B. Maximum Independent Set (MIS)

• Constraint Handling: Unlike MaxCut, MIS is a constrained problem. QISS samples may contain conflicts (adjacent nodes both selected). The authors introduced a simple post-processing pruning routine to resolve conflicts and greedily add valid nodes.
• Performance: For MIS, using only edge correlators resulted in performance worse than vanilla QAOA due to the lack of $Z_2$ symmetry and overlapping factors. However, using the augmented set of correlators combined with the pruning routine allowed QISS to outperform standalone QAOA and compete with state-of-the-art classical heuristics (e.g., linear-prioritized search and quantum-enhanced greedy algorithms).

C. Comparison to Classical Solvers

QISS was benchmarked against Simulated Annealing (SA) and the Burer–Monteiro (BM) rank-two relaxation of the Goemans–Williamson SDP.

• QISS combined with RWS-QAOA produced results competitive with the BM solver.
• Unlike classical samplers whose performance degrades as system size increases under a fixed time budget, QISS leverages the locality of QAOA correlations, which remain stable with $N$.

4. Significance and Claims

The paper claims that QISS establishes a new regime for near-term optimization where shallow quantum circuits serve not as direct samplers, but as generators of informative statistics for scalable classical sampling.

• Division of Labor: The quantum device is utilized for its ability to efficiently estimate low-order, local observables (which are robust to noise and independent of system size in sample cost), while the classical computer handles the complex task of synthesizing these statistics into global solutions.
• Noise Resilience: A critical finding is that the surrogate distribution is so robust that it can recover near-optimal solutions from raw, unmitigated noisy hardware data. This suggests that for certain optimization tasks, the overhead of complex error mitigation may be unnecessary if a robust post-processing layer like QISS is employed.
• Scalability: The approach avoids the exponential scaling of classical contraction for deep circuits by relying on shallow circuits and classical MCMC, offering a path to solve larger problems than direct quantum sampling would allow on current hardware.

The authors conclude that while QISS relies on the specific structure of the measured correlations, it provides a practical, training-free, and hardware-efficient pathway to improve optimization performance on near-term quantum devices.