Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting
quant-ph
Submitted: 2026-07-10
Updated: 2026-09-23
Comments: 8+13 pages; 3+4 figures; v2: minor implementation details corrections, fixed typos, corrected run selection in Fig. 2c; comments and suggestions are welcome!; accompanying repo: https://github.com/usra-riacs/quantum-approximate-optimization
Code: https://github.com/usra-riacs/quantum-approximateoptimization
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: Progress towards a quantum advantage using known heuristic methods for combinatorial optimization is impeded by hardware noise and limited qubit count.
Terminology
Abstract
Progress towards a quantum advantage using known heuristic methods for combinatorial optimization is impeded by hardware noise and limited qubit count. Here, we propose a noise-aware adaptive approach to quantum approximate optimization, Noise-Directed Adaptive Warm-Starting (ND-AWS), that builds on recent concepts such as Warm-Start QAOA and Noise-Directed Adaptive Remapping. By leveraging bitflip gauge transformations, our algorithm exploits amplitude-damping-like noise components. We experimentally implement high-performance quantum optimization ansätze on 100-qubit Ising Hamiltonians, showing that ND-AWS generally improves the performance over a non-gauge-transformed iterative Warm-Starting variant, at no additional circuit cost. This places our results among the highest-quality demonstrations of quantum optimization with similar ansätze at this scale. Crucially, the simplicity of the framework opens the door for future enhancements such as adaptive bias schedules, and integration with classical solvers.
Sources
- A Quantum Approximate Optimization Algorithm
- Quantum Optimization Benchmarking Library - The Intractable Decathlon
- Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms
- Quantum-Enhanced Optimization by Warm Starts
- The QAOA gets stuck starting from a good classical string
- Strategies for running the QAOA at hundreds of qubits
- Solving General QUBOs with Warm-Start QAOA via a Reduction to Max-Cut
- Iterative quantum optimisation with a warm-started quantum state
- A Non-Variational Quantum Approach to the Job Shop Scheduling Problem
- Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization
- Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
- Iterative warm-start optimization with quantum imaginary time evolution
- Enhancing NDAR with Delay-Gate-Induced Amplitude Damping
- LightSABRE: A Lightweight and Enhanced SABRE Algorithm
- A Depth-Independent Linear Chain Ansatz for Large-Scale Quantum Approximate Optimization
- Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem
- Evaluating the performance of quantum processing units at large width and depth
- Benchmarking neutral atom-based quantum processors at scale
- Warm-Starting QAOA with XY Mixers: A Novel Approach for Quantum-Enhanced Vehicle Routing Optimization
- Warm-Starting PCE for Traveling Salesman Problem
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity