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.
Abstract In this work, we compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers such as Gurobi and MQLib to solve the combinatorial optimization problem MaxCut on 3-regular graphs. The goal is to identify under which conditions QAOA can achieve “quantum advantage” over classical algorithms, in terms of both solution quality and time to solution. One might be able to achieve quantum advantage on hundreds of qubits and moderate depth p by sampling the QAOA state at a frequency of order 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Otherwise, we demonstrate that the number of required samples grows exponentially with N, hindering the scalability of QAOA with p ≤ 11. These results put challenging bounds on achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
As quantum devices grow in size while remaining affected by noise, a key challenge is to determine when and how they can surpass classical computation on practical tasks. This requires the development of highly efficient classical simulation algorithms. Pauli backpropagation algorithms are among the most promising, having shown efficiency in simulating certain classes of parameterized quantum circuits, strong candidates for near‑term quantum advantage, under random circuit assumptions and depolarizing noise. However, their efficiency had not been demonstrated for more realistic nonunital noise models, such as amplitude damping, which better capture the behaviour of current hardware. We close this gap by adapting Pauli backpropagation to most single‑qubit noise channels, including nonunital noise, and proving that it remains efficient under these conditions. Our algorithm is parallelizable, memory‑efficient, and requires no assumptions on the locality of the observable, the geometry of the hardware, or the depth of the circuit. While hardware noise can strongly affect computational power in highly structured, fault‑tolerant circuits, our findings indicate little difference for most near‑term variational architectures. This establishes Pauli backpropagation as an efficient method for simulating noisy quantum devices under realistic noise assumptions.While these advances improve our ability to reproduce noisy expectation values of observables, many practical applications, including combinatorial optimization, require direct access to the bitstrings output by quantum circuits, as these encode candidate solutions. Classical replication of such noisy samples has so far been limited beyond the random circuit setting. To bridge this gap, we first focus on problems whose objective functions depend only on two‑body correlations, such as Max‑Cut, and apply Gaussian randomized rounding to the circuit's two‑qubit marginals. This produces classical samples whose expected cost is provably close to that of the noisy quantum device. Large‑scale simulations and experiments on IBMQ hardware confirm that the rounded samples reproduce the full energy distribution, with similar behaviour under various noise models. Coupled with Pauli backpropagation for efficiently estimating noisy marginals, this yields an end‑to‑end classical sampler operating in polynomial time for a broad class of variational circuits. Our results therefore show that sufficiently noisy quantum circuits for combinatorial optimization can be sampled from classically, clarifying where near‑term hardware may or may not outperform classical algorithms.Finally , we go beyond one and two‑body marginals and present an algorithm that samples valid bitstrings directly from a maximum‑entropy distribution matching the given expectation values of the quantum circuit. This method does not rely on the locality or sparsity of the problem's Hamiltonian and performs well across a variety of quantum circuits, including deep circuits on many qubits. When combined with Pauli propagation or error mitigation, it provides a practical pipeline for obtaining samples from quantum circuits in the near term, where full error correction might not yet be available.
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 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.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-k-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.