Extending relax-and-round combinatorial optimization solvers with quantum correlations

Abstract

We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $p\ge 1$ layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at $p=1$, it is as accurate as its classical counterpart, and maintains the infinite-depth optimal performance guarantee of the QAOA. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.

arXiv comment17 pages (10 figures)

References in corpus (25)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Emergence of scaling in random networks
• Array Programming with NumPy
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Renormalization group analysis of the small-world network model
• Quantum Error Correction for Beginners
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• 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
• 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
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Spectral Methods for Data Science: A Statistical Perspective
• Counterdiabaticity and the quantum approximate optimization algorithm
• Hybrid quantum-classical algorithms for approximate graph coloring
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Quantum simulation of Ising spins on Platonic graphs
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• Quantum-Enhanced Greedy Combinatorial Optimization Solver

Cited by in corpus (11)

• Low-depth Clifford circuits approximately solve MaxCut
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Optimization via Quantum Preconditioning
• Entanglement-assisted variational algorithm for discrete optimization problems
• Generalized Probabilistic Approximate Optimization Algorithm
• Topological order in symmetric blockade structures
• 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