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.

arXiv comment9 pages, 5 figures (+ 12 pages, 11 figures)

References in corpus (37)

• Elementary gates for quantum computation
• Variational Quantum Algorithms
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Efficient simulation of one-dimensional quantum many-body systems
• The Variational Quantum Eigensolver: a review of methods and best practices
• Randomized Benchmarking of Quantum Gates
• Quantum annealing with more than one hundred qubits
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Defining and detecting quantum speedup
• Quantum Error Mitigation
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• A Race Track Trapped-Ion Quantum Processor
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Characterizing large-scale quantum computers via cycle benchmarking
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Quantum Optimization of Fully-Connected Spin Glasses
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Implementation of the XY interaction family with calibration of a single pulse
• MAXCUT QAOA performance guarantees for p >1
• Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
• CORE Technology and Exact Hamiltonian Real-Space Renormalization Group Transformations
• Quantum speedup of branch-and-bound algorithms
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Quantum Instruction Set Design for Performance
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Constrained Optimization via Quantum Zeno Dynamics
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm

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