A Quantum Dual Logarithmic Barrier Method for Linear Optimization

Quantum computing has the potential to speed up some optimization methods. One can use quantum computers to solve linear systems via quantum linear system algorithms (QLSAs). QLSAs can be used as a subroutine for algorithms that require solving linear systems, such as the dual logarithmic barrier method (DLBM) for solving linear optimization (LO) problems. In this paper, we use a QLSA to solve the linear systems arising in each iteration of the DLBM. To use the QLSA in a hybrid setting, we read out quantum states via a tomography procedure that introduces considerable error and noise. Thus, this paper first proposes an inexact feasible variant of DLBM for LO problems and then extends it to a quantum version. Our quantum approach has quadratic convergence toward the central path with inexact directions, and we show that this method has the best known $\mathcal{O}(\sqrt{n}\hspace{0.17em}\log (n{\mu }_0/ϵ))$ iteration complexity, where n is the number of variables, ${\mu }_0$ is the initial duality gap, and $ϵ$ is the accuracy. We further use iterative refinement to improve the complexity dependence on accuracy and condition number. For LO problems with quadratically more constraints than variables, the quantum complexity of our method has a sublinear dependence on dimension.

Funding: This research was supported by Defense Advanced Research Projects Agency [Grant W911NF2010022] and the National Science Foundation [Grant 2128527].