Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer

Understand

Recent works on quantum algorithms for solving semidefinite optimization (SDO) problems have leveraged a quantum-mechanical interpretation of positive semidefinite matrices to develop methods that obtain quantum speedups with respect to the dimension $n$ and number of constraints $m$.

• While their dependence on other parameters suggests no overall speedup over classical methodologies, some quantum SDO solvers provide speedups in the low-precision regime.
• We exploit this fact to our advantage, and present an iterative refinement scheme for the Hamiltonian Updates algorithm of Brand\~ao et al.
• (Quantum 6, 625 (2022)) to exponentially improve the dependence of their algorithm on precision.