Faster quantum and classical SDP approximations for quadratic binary optimization

Abstract

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.

42 pages, one figure. Corrected several typos and added a more thorough discussion on speedups for random instances. Accepted for publication in Quantum

References in corpus (5)

• Quantum random access memory
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• Fast and robust quantum state tomography from few basis measurements
• Binary component decomposition Part II: The asymmetric case

Cited by in corpus (14)

• Challenges and Opportunities in Quantum Optimization
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Integrating Quantum Computing Resources into Scientific HPC Ecosystems
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Quantum many-body systems in thermal equilibrium
• Quantum Interior Point Methods for Semidefinite Optimization
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Fast and robust quantum state tomography from few basis measurements
• Short-time simulation of quantum dynamics by Pauli measurements
• One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency