Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
arXiv:2404.01412 · doi:10.22331/q-2025-11-06-1906
Abstract
We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios - for random, fully connected graphs on qubits, using only depth QAOA with NDAR. This compares to - for standard QAOA with the same number of function calls.
8+10 pages; 3+2 figures; comments and suggestions are welcome!; v2: updated references, fixed typos, improved narration; v3: updated references, fixed typos, improved narration, added confidence intervals to Fig. 2; accompanying repo: https://github.com/usra-riacs/quantum-approximate-optimization
References in corpus (51)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Ising formulations of many NP problems
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Defining and detecting quantum speedup
- Quantum Error Mitigation
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Dissipative preparation of entanglement in optical cavities
- Quantum Error Correction: An Introductory Guide
- Experimental signature of programmable quantum annealing
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Warm-starting quantum optimization
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Digital zero noise extrapolation for quantum error mitigation
- Challenges and Opportunities in Quantum Optimization
- Autonomous Quantum Error Correction and Application to Quantum Sensing with Trapped Ions
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Counterdiabaticity and the quantum approximate optimization algorithm
- Hybrid quantum-classical algorithms for approximate graph coloring
- Stable Quantum-Correlated Many Body States through Engineered Dissipation
- On the representation of Boolean and real functions as Hamiltonians for quantum computing
- Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
- Feedback-based quantum optimization
- Classical symmetries and the Quantum Approximate Optimization Algorithm
- Single-ancilla ground state preparation via Lindbladians
- Multilevel Combinatorial Optimization Across Quantum Architectures
- Characterizing local noise in QAOA circuits
- Noise-Assisted Quantum Autoencoder
- Quantum simulation of Ising spins on Platonic graphs
- Towards large-scale quantum optimization solvers with few qubits
- Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
- Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
- Quantum-Enhanced Greedy Combinatorial Optimization Solver
- An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
- Engineered dissipation to mitigate barren plateaus
- Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
- A quantum algorithm for solving open system dynamics on quantum computers using noise
- Optimally Stopped Optimization
- Extending relax-and-round combinatorial optimization solvers with quantum correlations
- Numerical Gate Synthesis for Quantum Heuristics on Bosonic Quantum Processors
- A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates
- Ferromagnetically shifting the power of pausing
- Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
- Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
- Verifying the output of quantum optimizers with ground-state energy lower bounds
- Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
- MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
- Quantum approximate optimization algorithm with random and subgraph phase operators
- Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
- Optimization via Quantum Preconditioning