We introduce Quantum-Informed Surrogate Sampling (QISS), a post-processing framework that generates candidate solutions to combinatorial optimization problems from low-weight correlations of shallow quantum circuits. The quantum device estimates local observables, which are directly accessible by repeated measurements and for which a wide range of error-mitigation tools are available, while candidate solutions are generated classically without explicit dependence on the combinatorial optimization problem itself. We evaluate QISS on Maximum Cut and Maximum Independent Set problems on $N$ variables and show that only $O(N)$ low-order correlators from shallow circuits suffice to produce competitive solutions that surpass vanilla QAOA. For MaxCut on 3-regular graphs, QISS from $p=3$ QAOA correlators outperforms vanilla QAOA at $p=17$ on average, with further improvements possible by warm-starting QAOA. We validate the procedure on the 54-qubit IQM Emerald quantum device and demonstrate its noise resilience. Our results support a regime for near-term optimization in which shallow circuits serve not as direct samplers but as generators of informative statistics for scalable classical sampling.
We introduce Quantum-Informed Surrogate Sampling (QISS), a post-processing framework that generates candidate solutions to combinatorial optimization problems from low-weight correlations of shallow quantum circuits. The quantum device estimates local observables, which are directly accessible by repeated measurements and for which a wide range of error-mitigation tools are available, while candidate solutions are generated classically without explicit dependence on the combinatorial optimization problem itself. We evaluate QISS on Maximum Cut and Maximum Independent Set problems on N variables and show that only O(N) low-order correlators from shallow circuits suffice to produce competitive solutions that surpass vanilla QAOA. For MaxCut on 3-regular graphs, QISS from p=3 QAOA correlators outperforms vanilla QAOA at p=17 on average, with further improvements possible by warm-starting QAOA. We validate the procedure on the 54-qubit IQM Emerald quantum device and demonstrate its noise resilience. Our results support a regime for near-term optimization in which shallow circuits serve not as direct samplers but as generators of informative statistics for scalable classical sampling.
The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits.Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit's two-qubit marginals produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves a recovery ratio 1 − O [ ( 1 − p ) D ] , giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage.
The prospect of using quantum computers to solve combinatorial optimization problems via the quantum approximate optimization algorithm (QAOA) has attracted considerable interest in recent years. However, a key limitation associated with QAOA is the need to classically optimize over a set of quantum circuit parameters. This classical optimization can have significant associated costs and challenges. Here we provide an expanded description of Lyapunov control-inspired strategies for quantum optimization, as presented in [Magann et al., Phys. Rev. Lett. 129, 250502 (2022)], that do not require any classical optimization effort. Instead, these strategies utilize feedback from qubit measurements to assign values to the quantum circuit parameters in a deterministic manner, such that the combinatorial optimization problem solution improves monotonically with the quantum circuit depth. Numerical analyses are presented that investigate the utility of these strategies towards MaxCut on weighted and unweighted 3-regular graphs, both in ideal implementations and in the presence of measurement noise. We also discuss how how these strategies compare with QAOA and how they may be used to seed QAOA optimizations in order to improve performance for near-term applications, and we explore connections to quantum annealing.
Abstract We port the Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI) architecture from quantum chemistry to combinatorial graph optimization. Our framework, GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), follows the same principle: ML generates circuit programs, quantum samplers produce bitstrings, classical recovery repairs and expands them into a restricted subspace, and a classical solver finds the optimum within that subspace. We formalize the key quantity as the recovery-basin mass pr(qθ,G) = Prx∼qθ [x ∈ Ar(G)], where Ar(G) = {x : Er(R(x))∩X∗(G) ̸= ∅} is the preimage of the optimal set under repair R and r-flip expansion Er. Under B independent shots, success probability becomes Psuccess = 1 − (1 − pr)B. The quantum-benefit question reduces to: does pr(qquantum,G) > pr(qclassical,G)? We test this on MaximumWeighted Independent Set (MWIS) with a preregistered, frozen protocol. All 150 ground truths are certified with CBC + brute-force verification. Exact recovery-basin masks are enumerated for all n ≤ 20 instances. Nine samplers are compared on a held-out test set: uniform, greedy, simulated annealing, tabu search, multi-start local search, Metropolis, warm-start QAOA, oracle QAOA, and a matched learned classical policy. Key findings: 1. Tabu search dominates at all sizes (pr = 0.82–0.94), followed by simulated annealing. All quantum samplers and the learned classical policy lose to both at every problem size under the frozen test protocol. 2. Oracle QAOA loses to SA under fair evaluation: With random QAOA configurations (not per-instance optimized), oracle QAOA achieves pr = 0.014 at n = 28 vs SA’s 0.088. The earlier positive result (pr = 0.185 vs 0.130) required per-instance best-of-50 configuration selection—an oracle upper bound, not a deployable method. 3. Learned classical policy matches oracle QAOA: A matched 140K-parameter classical policy achieves pr = 0.005–0.101, comparable to oracle QAOA’s 0.014–0.113. The quantum circuit’s proposal distribution provides no structural advantage over a matched learned classical model in this setting. 4. Recovery-basin masks reveal the phase structure: At r = 2, uniform-sampling Precover drops from 0.975 (n = 16) to 0.775 (n = 20) at B = 200, identifying the regime where sampler quality matters. 5. Hardware robustness without advantage: 136 cores on Piast-Q show 93.4% recovery consistency between QPU and simulator, but no basin-mass advantage. This is a falsification study: Under rigorous, preregistered evaluation with matched learned baselines, shallow QAOA-derived proposal distributions do not outperform matched classical proposal models, and both lose to strong classical baselines (SA, tabu). The earlier positive oracle result was an artifact of per-instance configuration selection. We claim no quantum advantage.
Approximate combinatorial optimization is a promising use case for quantum computers. The quantum optimization algorithms often employ a fixed ansatz that evolves an unbiased initial state towards states with better values of the optimand, then samples the states to determine an approximately optimal solution. However, promising alternative approaches have considered ``warm-start" and sampling-based methods that instead begin from the best known solution, which can be directly optimized with the quantum computer and updated as new information becomes available, potentially outperforming the fixed ansätze. Here we use these ideas to design a nonvariational quantum algorithm for combinatorial optimization. At each step the algorithm begins with a state superposed around the best known solution, then drives it to lower energy using quantum imaginary time evolution. These nonvariational, initial-state-dependent circuits are determined using analytic equations that are evaluated using only a conventional computer. After implementing the circuits, the state is sampled, potentially obtaining a new best-known solution to use as the initial state at the next iteration. Using simulations of the algorithm solving MaxCut on 3-regular graphs with 30 or fewer vertices and a shot budget of 100 total shots, the approach obtains median solutions within 95\% of the global optimum and finds optimal solutions in 11\% or more of cases, significantly outperforming random and simplified classical search procedures. We discuss several future directions.
The Quantum Approximate Optimization Algorithm (QAOA) is widely regarded as a promising near-term quantum algorithm for addressing hard combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices; however, its real-world effectiveness is severely constrained by hardware noise, including gate infidelities, decoherence, and measurement errors. This work explores an error mitigation–driven approach to enhance the performance and robustness of QAOA without altering its algorithmic structure or requiring fault-tolerant quantum resources. Measurement error mitigation and zero-noise extrapolation are incorporated into the execution and post-processing stages of QAOA circuits and evaluated using the Minimum Vertex Cover problem as a representative benchmark. Performance is assessed through approximation ratios, solution stability, and noise sensitivity across multiple circuit depths. The results indicate that error mitigation not only improves approximation accuracy but also stabilizes output distributions and delays performance degradation at increased circuit depths. Additionally, the mitigated executions demonstrate better consistency across repeated runs, highlighting improved resilience to stochastic noise. These findings emphasize that lightweight and hardware-efficient error mitigation techniques can significantly extend the practical usability of QAOA on current NISQ hardware, providing a scalable and realistic pathway for executing quantum optimization algorithms more reliably in near-term quantum computing environments.
We study the Quantum Approximate Optimization Algorithm ( QAOA ) in the context of the Max-Cut problem. Noisy quantum devices are only able to accurately execute QAOA at low circuit depths, while classically-challenging problem instances may call for a relatively high circuit-depth. This is due to the need to build correlations between reachable pairs of vertices in potentially large graphs [ 16 ]. To enhance the solving power of low-depth QAOA, we introduce a classical pre-processing step that initializes QAOA with a biased superposition of possible cuts in the graph, referred to as a warm-start . In particular, we initialize QAOA with a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA , called QAOA-warm , is able to outperform standard QAOA on lower circuit depths in solution quality and training time. While this improvement is partly due to the classical warm-start, we find strong evidence of further improvement using QAOA circuit at small depth. We provide experimental evidence of improved performance as well as theoretical properties of the proposed framework.