Quantum Interior Point Methods for Semidefinite Optimization
arXiv:2112.06025 · doi:10.22331/q-2023-09-11-1110
Abstract
We present two quantum interior point methods for semidefinite optimization problems, building on recent advances in quantum linear system algorithms. The first scheme, more similar to a classical solution algorithm, computes an inexact search direction and is not guaranteed to explore only feasible points; the second scheme uses a nullspace representation of the Newton linear system to ensure feasibility even with inexact search directions. The second is a novel scheme that might seem impractical in the classical world, but it is well-suited for a hybrid quantum-classical setting. We show that both schemes converge to an optimal solution of the semidefinite optimization problem under standard assumptions. By comparing the theoretical performance of classical and quantum interior point methods with respect to various input parameters, we show that our second scheme obtains a speedup over classical algorithms in terms of the dimension of the problem , but has worse dependence on other numerical parameters.
References in corpus (15)
- Quantum algorithm for solving linear systems of equations
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Creating superpositions that correspond to efficiently integrable probability distributions
- A direct formulation for sparse PCA using semidefinite programming
- A Semidefinite Programming Approach to Optimal Unambiguous Discrimination of Quantum States
- Quantum Recommendation Systems
- Quantum SDP-Solvers: Better upper and lower bounds
- Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
- An improved semidefinite programming hierarchy for testing entanglement
- Faster quantum and classical SDP approximations for quadratic binary optimization
- Quantum state estimation and large deviations
- Complexity of quantum state verification in the quantum linear systems problem
- A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
- Linear Programming using Limited-Precision Oracles