Source-linked AI summary
A Quantum Interior Point Method for LPs and SDPs
Iordanis Kerenidis, Anupam Prakash
TL;DR
Existing SDP approaches can remain mainly theoretical for general problems, while quantum interior-point methods address this gap using quantum linear algebra, block encodings, and tomography. The resulting SDP and LP solvers achieve polynomial speedups over corresponding classical methods when intermediate matrices are well conditioned, while the paper focuses on dense SDPs rather than sparse variants.
Problem
The Arora-Kale framework remains mainly theoretical for general SDPs, while classical interior-point methods face expensive Newton-system computations.
Method
The paper develops quantum SDP and LP interior-point solvers using block encodings for Newton systems, quantum linear-system techniques, and tomography to obtain classical updates.
Results
When intermediate matrices are well conditioned, the method achieves eO(n3.5) for dense SDPs and eO(n2) for LPs, compared with O(n6) and O(n3.5) classical baselines, respectively.
Takeaways & Limitations
The results provide the first quantum SDP and LP solvers based on interior-point methods and support further quantum optimization applications.
Takeaways & Limitations
The paper focuses on dense SDPs with m = O(n2) and does not address sparse-case interior-point variants.
Abstract
from arXiv · showhide
We present a quantum interior point method with worst case running time $\widetilde{O}(\frac{n^{2.5}}{ξ^{2}} μκ^3 \log (1/ε))$ for SDPs and $\widetilde{O}(\frac{n^{1.5}}{ξ^{2}} μκ^3 \log (1/ε))$ for LPs, where the output of our algorithm is a pair of matrices $(S,Y)$ that are $ε$-optimal $ξ$-approximate SDP solutions. The factor $μ$ is at most $\sqrt{2}n$ for SDPs and $\sqrt{2n}$ for LP's, and $κ$ is an upper bound on the condition number of the intermediate solution matrices. For the case where the intermediate matrices for the interior point method are well conditioned, our method provides a polynomial speedup over the best known classical SDP solvers and interior point based LP solvers, which have a worst case running time of $O(n^{6})$ and $O(n^{3.5})$ respectively. Our results build upon recently developed techniques for quantum linear algebra and pave the way for the development of quantum algorithms for a variety of applications in optimization and machine learning.
1 Introduction
Semidefinite programming supports broad convex-optimization and approximation applications, but existing classical and quantum approaches face scaling or parameter limitations. The paper introduces quantum interior-point solvers whose polynomial speedups depend on well-conditioned intermediate matrices.
- Semidefinite programming supports convex optimization and approximate solutions to NP-hard problems, including MAXCUT.
- The best known general SDP method has worst-case running time eO(n6) for dense instances with m = O(n2).
- The Arora-Kale framework can become infeasible for general SDPs because its width Rr/ε grows at least linearly with n and m.
- Quantum SDP algorithms improved dependence on n and m but had worse dependence on other parameters, motivating the interior-point approach.
- The paper develops the first quantum SDP and LP interior-point solvers, constructing block encodings for Newton systems and using tomography to recover classical updates.
- eO(n3.5) is achieved for dense SDPs with well-conditioned intermediate matrices, compared with O(n6.5) for the corresponding classical method and O(n6) for the best general SDP solver.
- eO(n2) is achieved for LPs when intermediate Newton matrices and solution vectors are well conditioned, compared with O(n3.5) for the corresponding classical algorithm.
2 Preliminaries
The preliminaries introduce matrix and vector notation, norm facts, and procedures for preparing concatenated quantum states. These procedures support the block encodings required by the quantum interior-point method.
- Notation: The preliminaries define entry-wise products, vector concatenation, quantum vector states, matrix decompositions, singular-value quantities, and norms.
- Linear algebra: For positive definite A, the Frobenius norm of AB is bounded between λmin(A)∥B∥F and λmax(A)∥B∥F.
- Linear algebra: If Y′ ⪯ (1 + ρ)Y, then ∥Y′B∥F ≤ (1 + ρ)∥YB∥F.
- Quantum procedures: Given unitaries preparing |a⟩ and |b⟩, the concatenated state |a ◦ b⟩ can be prepared in time O(T(Ua) + T(Ub)).
- Quantum procedures: With norm estimates accurate within (1 ± δ), the approximate concatenated-state procedure provides an error guarantee proportional to δ.
3 Quantum linear system solvers and QRAM data structures
The section develops the quantum linear-algebra primitives and QRAM/block-encoding assumptions used by the quantum interior point method. Improved solvers provide polylogarithmic precision dependence and linear condition-number dependence, while tensor data structures support the SDP inputs.
- Quantum linear system solvers: The quantum linear-algebra results improve precision dependence to polylog(1/ε) and condition-number dependence to linear.Earlier methods had inverse-polynomial precision dependence and quadratic condition-number dependence.
- Quantum linear system solvers: Quantum linear-system solvers use block encodings with runtime depending on matrix scale, condition number, and logarithmically on precision.The relevant matrices are assumed to have nonzero eigenvalues in [−1, −1/κ] ∪ [1, 1/κ].
- Quantum linear algebra: Composing block-encoded matrix operations yields a state proportional to the product applied to |b⟩ and an estimate of its norm.Amplitude amplification is performed only after the complete product, producing dependence on the composed condition number rather than the product of individual condition numbers.
- QRAM data structures: QRAM data structures implement efficient block encodings for matrices and vectors, with matrix access time O(polylog(n)).These structures provide the operator-model access required by the quantum algorithm.
- QRAM data structures: Tensor QRAM structures store SDP matrices and associated vectors simultaneously, enabling efficient block encodings and state-preparation procedures.The construction maintains separate data structures for matrix slices and vectors obtained from tensor fibers.
4 Tomography for efficient vector states
The section presents a tomography algorithm for recovering real vector states from copies prepared by a unitary. Its sample and time complexity are nearly linear in the state dimension, making it suitable for repeated Newton-step reconstruction.
- Motivation: The tomography algorithm recovers classical information from quantum states corresponding to Newton-system solutions.Those states have dimension d = O(n^2), so super-linear tomography would be prohibitively expensive.
- Tomography procedure: The algorithm uses measurements and a controlled state-preparation unitary to estimate amplitudes and their signs.It assumes real amplitudes and access to both a unitary preparing |x⟩ and its controlled version.
- Correctness: With sufficiently many samples, all sufficiently large-coordinate signs are recovered with probability at least 1 − 1/d^0.83.The sign guarantee follows from multiplicative Chernoff bounds and a union bound.
- Correctness: The output estimate has unit norm and ℓ2 error bounded by 7δ with probability at least 1 − 1/d^0.83.The success probability can be amplified by increasing the sample count.
- Complexity: The algorithm uses eO(d/δ^2) state-preparation calls and time when state preparation is polylogarithmic.This linear-in-dimension tomography result is the reason it can be used across the interior point iterations.
5 The classical interior point method
The classical interior point method follows feasible primal-dual solutions toward the central path while reducing the duality gap. Each iteration solves a Newton linear system, and the method reaches ε accuracy after O(√n log(n/ε)) iterations.
- Classical baselines: The best known general SDP method has worst-case running time O(n^6) for dense instances with m = O(n^2).Its general expression depends on m, matrix multiplication complexity, sparsity, and ε.
- Primal-dual formulation: The duality gap equals Tr(SY) for feasible primal-dual SDP solutions and is zero at optimality.Positive semidefiniteness then implies SY = YS = 0 at optimality.
- Central path: Central-path solutions satisfy SνYν = YνSν = νI, linking the barrier parameter ν to complementarity.The central path is well defined and unique under strict feasibility.
- Convergence: O(√n log(n/ε)) iterations suffice to obtain duality gap ε, provided the iterates remain close to the central path.The analysis allows the Newton systems to be solved approximately for the quantum extension.
- Newton updates: Each iteration updates feasible solutions by solving a Newton linear system that targets a smaller barrier parameter ν′.The nonlinear central-path condition is linearized to obtain the Newton system.
6 Analysis of the approximate interior point method
The approximate-method analysis shows that errors in solving Newton systems can be tolerated while preserving positive definiteness, central-path proximity, and convergence. The proof uses scaling to reduce the analysis to diagonal matrices and bounds the resulting approximation errors.
- Stability: Approximate Newton solutions remain positive definite under χ ≤ η = 0.1 and ξ < 0.01.The result ensures that the updated primal and dual matrices stay inside the positive-semidefinite cone.
- Central-path proximity: The updated solutions remain η-close to the central path despite approximate Newton-system solutions.The analysis explicitly incorporates the approximation error ξ into the distance bound.
- Scaling argument: Scaling preserves the duality gap, central-path distance, and correspondence between Newton systems.This permits analysis after transforming the dual matrix to the identity and diagonalizing the scaled primal matrix.
- Newton-system solvability: The Newton linear system has a unique solution when the scaled primal matrix entries satisfy si ∈ [1 − η, 1 + η].Uniqueness follows by showing that the associated homogeneous system has only the trivial solution.
- Scope of the analysis: The proof does not optimize the constants η, χ, and ξ, and notes that a better bound for ξ may be possible.This is an explicit scope boundary of the presented convergence analysis.
7 The quantum interior point method
The quantum interior point method constructs and solves Newton linear systems through quantum-accessible factorizations, then iterates these updates to obtain approximately feasible, ε-optimal SDP and LP solutions. Its runtime depends on problem dimension, approximation error, data-structure parameter μ, and conditioning, with improved bounds when matrices are well conditioned.
- Newton system: The method represents the Newton linear system as M(dx ◦ dY) = (ν′I − SY ◦ 0_m) for SDP updates.The system encodes the constraints dS ∈ L, dY ∈ L⊥, and dSY + SdY = ν′I − SY.
- Quantum implementation: Quantum block encodings factor the Newton matrix M into efficiently implementable matrices rather than constructing M directly.The factorization uses matrices derived from the stored input data and supports quantum linear-system solving.
- Quantum implementation: Each quantum Newton solve outputs an approximation to dS ◦ dY and an estimate of its norm, enabling the interior point iteration to update the solution.The algorithm uses tomography to obtain a classical description of the quantum solution for subsequent iterations.
- SDP guarantees: After O(√n log(n/ε)) iterations, the SDP method produces positive definite (S, Y) with Tr(SY) ≤ ε and approximately satisfied constraints.The approximation can be expressed as ξ-relative or ξ-absolute constraint error, depending on the guarantee used.