Optimization via Quantum Preconditioning
arXiv:2502.18570 · doi:10.1103/9prw-684p
Abstract
State-of-the-art classical optimization solvers set a high bar for quantum computers to deliver utility in this domain. Here, we introduce a quantum preconditioning approach based on the quantum approximate optimization algorithm. It transforms the input problem into a more suitable form for a solver with the level of preconditioning determined by the depth of the quantum circuit. We demonstrate that best-in-class classical heuristics such as simulated annealing and the Burer-Monteiro algorithm can converge more rapidly when given quantum preconditioned input for various problems, including Sherrington-Kirkpatrick spin glasses, random 3-regular graph maximum-cut problems, and a real-world grid energy problem. Accounting for the additional time taken for preconditioning, the benefit offered by shallow circuits translates into a practical quantum-inspired advantage for random 3-regular graph maximum-cut problems through quantum circuit emulations. We investigate why quantum preconditioning makes the problem easier and test an experimental implementation on a superconducting device. We identify challenges and discuss the prospects for a hardware-based quantum advantage in optimization via quantum preconditioning.
26 pages, 18 figures
References in corpus (70)
- Quantum Computing
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Logical quantum processor based on reconfigurable atom arrays
- Randomized Benchmarking of Quantum Gates
- Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum error correction below the surface code threshold
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Annealing and Analog Quantum Computation
- Quantum Error Mitigation
- Noise tailoring for scalable quantum computation via randomized compiling
- Perspectives of quantum annealing: Methods and implementations
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Spin-Glass Theory for Pedestrians
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Training variational quantum algorithms is NP-hard
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Mitigating measurement errors in multi-qubit experiments
- A Race Track Trapped-Ion Quantum Processor
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
- Barren Plateaus in Variational Quantum Computing
- Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography
- Quantum Optimization of Fully-Connected Spin Glasses
- Combinatorial Optimization with Physics-Inspired Graph Neural Networks
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Challenges and Opportunities in Quantum Optimization
- Model-free readout-error mitigation for quantum expectation values
- Extremal Optimization for Graph Partitioning
- Detector Tomography on IBM 5-qubit Quantum Computers and Mitigation of Imperfect Measurement
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- MAXCUT QAOA performance guarantees for p >1
- Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
- A quantum-classical cloud platform optimized for variational hybrid algorithms
- Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
- Chemistry Beyond the Scale of Exact Diagonalization on a Quantum-Centric Supercomputer
- On the representation of Boolean and real functions as Hamiltonians for quantum computing
- A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
- Efficient correction of multiqubit measurement errors
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Constrained mixers for the quantum approximate optimization algorithm
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Towards large-scale quantum optimization solvers with few qubits
- Parameter Setting in Quantum Approximate Optimization of Weighted Problems
- Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
- Quantum-Enhanced Greedy Combinatorial Optimization Solver
- Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
- Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
- Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
- Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
- Extending relax-and-round combinatorial optimization solvers with quantum correlations
- A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates
- Conditionally rigorous mitigation of multiqubit measurement errors
- Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
- Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
- QAOA with
- Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
- Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
- Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
- MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
- Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set