Quantum-Enhanced Greedy Combinatorial Optimization Solver

Abstract

Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster their performance. Here, we introduce an iterative quantum heuristic optimization algorithm to solve combinatorial optimization problems. The quantum algorithm reduces to a classical greedy algorithm in the presence of strong noise. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement. Moreover, we observe an absolute performance comparable with a state-of-the-art semidefinite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics.

9 pages, 5 figures (+ 12 pages, 11 figures)

References in corpus (9)

• Randomized Benchmarking of Quantum Gates
• Quantum Error Mitigation
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• A Race Track Trapped-Ion Quantum Processor
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Constrained Optimization via Quantum Zeno Dynamics
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation

Cited by in corpus (15)

• Challenges and Opportunities in Quantum Optimization
• IBM Quantum Computers: Evolution, Performance, and Future Directions
• Quantum-Informed Recursive Optimization Algorithms
• Reinforcement Learning Assisted Recursive QAOA
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Probing many-body Bell correlation depth with superconducting qubits
• Optimization via Quantum Preconditioning
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Qubit-efficient quantum combinatorial optimization solver