Qubit-efficient quantum combinatorial optimization solver
arXiv:2407.15539 · doi:10.1103/s5jv-jh24
Abstract
Quantum optimization solvers typically rely on one-variable-to-one-qubit mapping. However, the low qubit count on current quantum computers is a major obstacle in competing against classical methods. Here, we develop a qubit-efficient algorithm that overcomes this limitation by mapping a candidate bit string solution to an entangled wave function of fewer qubits. We propose a variational quantum circuit generalizing the quantum approximate optimization ansatz (QAOA). Extremizing the ansatz for Sherrington-Kirkpatrick spin glass problems, we show valuable properties such as the concentration of ansatz parameters and derive performance guarantees. This approach could benefit near-term intermediate-scale and future fault-tolerant small-scale quantum devices.
16 pages, 15 figures; Added literature review, and adaptive ansatz variational algorithm with qubit-efficient encoding
References in corpus (41)
- Variational Quantum Algorithms
- Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms
- Ising formulations of many NP problems
- Suppressing quantum errors by scaling a surface code logical qubit
- Logical quantum processor based on reconfigurable atom arrays
- Quantum error correction below the surface code threshold
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Error Mitigation
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Training variational quantum algorithms is NP-hard
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum Error Correction: An Introductory Guide
- A Race Track Trapped-Ion Quantum Processor
- Trading classical and quantum computational resources
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Warm-starting quantum optimization
- Simulating Large Quantum Circuits on a Small Quantum Computer
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Barren Plateaus in Variational Quantum Computing
- CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations
- Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
- Optimal Protocols in Quantum Annealing and QAOA Problems
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- MAXCUT QAOA performance guarantees for p >1
- Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
- Qubit-efficient encoding schemes for binary optimisation problems
- Towards large-scale quantum optimization solvers with few qubits
- Quantum-Informed Recursive Optimization Algorithms
- Quantum-Enhanced Greedy Combinatorial Optimization Solver
- Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
- Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
- Calibrating the role of entanglement in variational quantum circuits
- Engineering generalized Gibbs ensembles with trapped ions
- Extending relax-and-round combinatorial optimization solvers with quantum correlations
- Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
- NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
- Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
- Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
- Dynamic quantum circuit compilation