Quantum Interior Point Methods for Semidefinite Optimization
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 n, but has worse dependence on other numerical parameters.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 11, 2023
- Source ID
- 10.22331/q-2023-09-11-1110
Entities
People
- Brandon Augustino
- Giacomo Nannicini
- Luis F. Zuluaga
- Tamás Terlaky
Organizations
- Defense Advanced Research Projects Agency
- Lehigh University
- Oak Ridge National Laboratory
- University of Southern California