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.

arXiv comment42 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 (23)

• Quantum state tomography via compressed sensing
• Quantum random access memory
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Quantum Metropolis Sampling
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Sample-optimal tomography of quantum states
• A Quantum-Quantum Metropolis Algorithm
• Practical sketching algorithms for low-rank matrix approximation
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Phase Transitions in Semidefinite Relaxations
• Extremal Cuts of Sparse Random Graphs
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Efficient Pure State Quantum Tomography from Five Orthonormal Bases
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Online Learning of Quantum States
• Quantum Tomography From Few Full-Rank Observables
• Fast and robust quantum state tomography from few basis measurements
• A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
• Binary component decomposition Part II: The asymmetric case
• Cut-norms and spectra of matrices
• Perfect Sampling for Quantum Gibbs States

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