Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer

Abstract

Achieving high-quality solutions faster than classical solvers on computationally hard problems is a challenge for quantum optimization to deliver utility. Using a superconducting quantum computer, we experimentally investigate the performance of a hybrid quantum-classical algorithm inspired by semidefinite programming approaches for solving the maximum-cut problem on 3-regular graphs up to several thousand variables. We leverage the structure of the input problems to address sizes beyond what current quantum machines can naively handle. We attain an average approximation ratio of 99% over a random ensemble of thousands of problem instances. We benchmark the quantum solver against similarly high-performing classical heuristics, including the Gurobi optimizer, simulated annealing, and the Burer-Monteiro algorithm. A run-time analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others on a projected 100-qubit quantum computer. We explore multiple leads to close the gap and discuss prospects for a practical quantum speedup.

35 pages, 26 figures

References in corpus (42)

• Array Programming with NumPy
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Charge insensitive qubit design derived from the Cooper pair box
• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• Adiabatic Quantum Computing
• Strong quantum computational advantage using a superconducting quantum processor
• Randomized Benchmarking of Quantum Gates
• Coherent Josephson qubit suitable for scalable quantum integrated circuits
• Quantum Error Correction for Beginners
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Error Mitigation
• Noise tailoring for scalable quantum computation via randomized compiling
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• 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
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Spectral Methods for Data Science: A Statistical Perspective
• Counterdiabaticity and the quantum approximate optimization algorithm
• 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
• Parametric-resonance entangling gates with a tunable coupler
• Kibble-Zurek mechanism and infinitely slow annealing through critical points
• Dynamic scaling at classical phase transitions approached through non-equilibrium quenching
• Floating tunable coupler for scalable quantum computing architectures
• Constructing Smaller Pauli Twirling Sets for Arbitrary Error Channels
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Towards large-scale quantum optimization solvers with few qubits
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• 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
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Cited by in corpus (5)

• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• SWAP-less Implementation of Quantum Algorithms
• Optimization via Quantum Preconditioning
• Qubit-efficient quantum combinatorial optimization solver