A Quantum Dual Logarithmic Barrier Method for Linear Optimization

Zeguan Wu, Pouya Sampourmahani · 2024

Read A Quantum Dual Logarithmic Barrier Method for Linear Optimization by Zeguan Wu, Pouya Sampourmahani (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15977.txt.

Introduction

Zeguan Wu and co-authors speed a classic method for straight line optimization with quantum steps, in a paper from 2024. The method walks a curved path to the best point while it solves a line system at each step. A quantum line solver can run that step, but reading its state out adds noise and error that a strict method cannot take.

The team first loosens the method so that rough steps still count as sound. They then build its quantum form on that slack base. The quantum form keeps a fast close in on the path and the best known step count for its class. A polish loop cuts the cost of high accuracy. For tasks with far more rules than picks, cost grows more slowly than size.

Catalog record

CREATORZeguan Wu, Pouya Sampourmahani
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15977

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Quantum Dual Logarithmic Barrier Method for Linear Optimization Zeguan Wu, Pouya Sampourmahani Abstract 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 which 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 𝒪 ⁡ ( n ​ log ⁡ ( n ​ μ 0 / ζ ) ) \mathcal{O}(\sqrt{n}\log(n\mu_{0}/\zeta)) iteration complexity, where n n is the number of variables, μ 0 \mu_{0} is the initial duality gap, and ζ \zeta is the desired accuracy. We further use iterative refinement to improve the time complexity dependence on accuracy. For LO problems with quadratically more constraints than variables, the quantum complexity of our method has a sublinear dependence on dimension. 1 Introduction Quantum Computing has drawn a significant amount of attention recently because of its promising speedups compared to classical computing. Such examples include integer factorization Shor (1994) and Quantum Linear System Algorithms (QLSAs) Childs et al. (2017) ; Harrow et al. (2009) . Due to the wide applications of mathematical optimization, it is natural to design and develop quantum optimization algorithms. There has been an increasing amount of research regarding developing quantum optimization algorithms for solving optimization problems. Such attempts include Quantum Approximation Optimization Algorithms (QAOA) Farhi et al. (2014) , Quantum Simplex Algorithm Nannicini (2022) , and Quantum Interior Point Methods (QIPMs) Augustino et al. (2021) ; Augustino et al. (2023) ; Casares and Martin-Delgado (2020) ; Kerenidis and Prakash (2020) ; Mohammadisiahroudi et al. (2024a) ; Wu et al. (2023) . QIPMs are quantum versions of classical interior point methods (IPMs) that use QLSAs as an oracle to solve the Newton system at each iteration. Given that the solution extraction process done by quantum tomography introduces errors, inexact IPMs must be used in this context. There are variants of interior point methods, i.e., primal, dual, and primal-dual. Previous works in the context of QIPMs include Mohammadisiahroudi et al. (2023b) and Mohammadisiahroudi et al. (2024a) , which proposed an inexact infeasible QIPM (II-QIPM) and an inexact feasible QIPM (IF-QIPM), respectively, for linear optimization (LO) problems. The algorithms proposed in these works are primal-dual IPM algorithms. In Mohammadisiahroudi et al. (2024a) , the authors developed an II-QIPM that exploits QLSA to solve the normal equations system (NES) in each iteration. Their algorithm has a total complexity of \tilde{{\cal O}}_{n,\kappa_{A},\omega}(n^{4}L\|A\|^{4}\omega^{4}\kappa_{A}^{2}) , where n is the number of variables, L is the bit length of the input data, \kappa_{A} is the condition number of matrix A , and \omega is an upper bound on the norm of optimal solution. Among the systems that we can solve to obtain the Newton direction, NES is the most desirable since the coefficient matrix is positive definite. However, solving NES inexactly introduces primal infeasibility. To address this issue, Mohammadisiahroudi et al. Mohammadisiahroudi et al. (2023b) proposed a novel system called the orthogonal subspace system (OSS) and also a modified Newton system, which runs in \tilde{{\cal O}}_{n,\kappa_{A},\omega}(n^{2.5}L\|A\|^{2}\omega^{2}\kappa_{A}) time. In a subsequent work Mohammadisiahroudi et al. (2024b) , they improved their complexity to \widetilde{{\cal O}}_{n,\kappa_{\hat{A}},\|\hat{A}\|,\|\hat{b}\|,\mu^{0}}(m\sqrt{n}L\bar{\chi}^{2}\omega^{2}) , where \bar{\chi}^{2} is an upper bound on the condition number of the Newton system. Evidently, such modification comes at a computational cost. To avoid such preprocessing and modifications, we aim to use the dual logarithmic barrier method. In our algorithm, we solve NES inexactly while maintaining primal feasibility without any modifications. There are two closely related works to ours in the context of dual logarithmic barrier methods, one in classical and one in quantum settings. First, Bellavia et al. Bellavia et al. (2019) proposed a dual logarithmic barrier method for solving semidefinite optimization (SDO) problems with sparse variables. As LO is a special case of SDO, by putting the elements of variables along the diagonal of the semidefinite variable, one can adopt their method for LO. Their method solves a normal equation system at each iteration. They shift the inexactness into primal feasibility, making iterations primal infeasible until optimality. Their method terminates after \lceil 18\sqrt{n}\log(\frac{n\mu_{0}}{\zeta})\rceil inexact Newton steps, where \mu_{0} is the initial duality gap, and \zeta is the desired accuracy. They achieve this complexity by a tight bound on the residual. In our analysis, we show that our method requires a less strict bound on the residual. Second, Apers and Gribling 1 1 1 In Apers and Gribling (2023) the authors use different notations. For consistent and unified presentation, the results of Apers and Gribling (2023) are translated to notations used in this paper. proposed a quantum algorithm based on an IPM for so-called “tall” LO problems, in which n\ggg m , that runs in \sqrt{n}{\rm poly}(m,\log(n),\log(1/\zeta)) , where n is the number of constraints in their dual form problem Apers and Gribling (2023) . Their algorithm avoids dependence on a condition number. Under some mild assumptions and access to QRAM (a quantum-accessible data structure), their framework achieves a quantum speedup under the assumption of n\ggg m . To approximate the Hessian and the gradient of the barrier function in the Newton step, they proposed a quantum algorithm for the spectral approximation of the matrix AA^{T} . Further, they migrated the matrix-vector multiplication into a quantum setting using an algorithm that combines spectral approximation with quantum multivariate mean estimation algorithms. As mentioned earlier, their work focuses on tall LOs. To be more specific, they present their result to be competitive for cases where n\geq\gamma m^{10} for some constant \gamma . Although they refer to some specific applications where such a setting exists, it appears that their result might not show any speedup for general cases of LO problems where n and m are both large and of the same order of magnitude. Moreover, they imposed an assumption on the size of the input data. Given their assumption, the self-dual embedding model is not applicable to finding an initial solution due to dimension restriction. Further, if one uses Khachiyan’s or big-M methods, there will be a contradiction regarding the complexity. Furthermore, they did not clarify how their algorithm maintains feasibility if the gradient is approximated with some error. In addition, in the quantum setting, Augustino et al. Augustino et al. (2023) proposed the first provably convergent quantum interior point for semidefinite optimization. If we apply this framework to LOs, we get the query complexity of \widetilde{{\cal O}}_{n,\kappa,\frac{1}{\zeta}}\left(n^{2}\frac{\kappa^{2}}{\zeta}\right) and \widetilde{{\cal O}}_{n,\kappa,\frac{1}{\zeta}}\left(n^{2.5}\right) arithmetic operations, where \kappa is the condition number of Newton linear system Augustino et al. (2023) . As mentioned earlier, one can adopt such a framework for solving LOs by defining diagonal matrices of input data. However, their complexity has a linear

Read the complete text