Technical Summary: Quantum Speedups for Linear Programming via Interior Point Methods

Problem Statement

The paper addresses the fundamental task of solving linear programs (LPs) of the form $\min c^T x$ subject to $Ax \geq b$, where $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$, and $c \in \mathbb{R}^d$. The focus is specifically on "tall" linear programs where the number of inequality constraints $n$ is significantly larger than the number of variables $d$ ($n \gg d$).

While classical Interior Point Methods (IPMs) are the state-of-the-art for solving LPs, their complexity for tall, dense instances is roughly $\tilde{O}(nd + d^{2.5})$. The authors investigate whether quantum algorithms can provide a speedup for IPMs in this regime, aiming for a runtime that is sublinear in the input size (specifically sublinear in $n$).

Methodology

The proposed approach is a quantum interior point method that approximates the Newton step at the core of the IPM iteration. Instead of computing exact Hessians and gradients, the algorithm utilizes quantum subroutines to obtain spectral approximations of the Hessian and approximations of the gradient in the inverse-local norm.

The methodology relies on three primary quantum components:

1. Quantum Spectral Approximation:
   The algorithm constructs a spectral approximation of a matrix $B^T B$ where $B \in \mathbb{R}^{n \times d}$ is a tall matrix. This is achieved using a "repeated halving" strategy combined with leverage score sampling.

   • Mechanism: The algorithm uses Grover search to identify important rows among the $n$ rows of $B$ in $\tilde{O}(\sqrt{n})$ queries, rather than $\tilde{O}(n)$ required classically.
   • Bootstrapping: To avoid the circular dependency of needing leverage scores to sample rows (which requires $B^T B$), the authors adapt a classical bootstrapping technique (Cohen et al.) to the quantum setting. They use a chain of uniformly downsampled matrices to iteratively estimate generalized leverage scores, which are then used to weight the final sampling.

2. Quantum Approximation of Lewis Weights:
   For advanced barriers (Volumetric and Lewis weight barriers), the algorithm requires approximating $\ell_p$-Lewis weights.

   • Mechanism: Lewis weights are defined via a fixed-point equation involving leverage scores of a rescaled matrix. The authors implement an iterative quantum algorithm based on a low-precision classical algorithm (Apers, Gribling, and Sidford).
   • Efficiency: Since explicitly writing down $n$ weights is too expensive for sublinear time, the algorithm maintains implicit data structures that allow efficient querying of intermediate weights without full materialization.

3. Quantum Gradient Approximation (Matrix-Vector Product):
   The algorithm approximates the gradient $g(x)$ in the "inverse-local norm" $\|\cdot\|_{H(x)^{-1}}$.

   • Mechanism: The gradient is viewed as the mean of a random variable. The authors employ a recent quantum algorithm for multivariate mean estimation (Cornelissen, Hamoudi, and Jerbi).
   • Preconditioning: To avoid dependence on the condition number of the Hessian, the algorithm first constructs a spectral approximation $\tilde{H}$ of the Hessian. It then samples from a "pre-conditioned" random variable using $\tilde{H}^{-1/2}$, ensuring the trace of the covariance matrix is controlled and the resulting estimator satisfies the required norm bound.

Key Contributions

1. Quantum Spectral Approximation Algorithm:
   The paper presents a quantum algorithm that returns a $\delta$-spectral approximation of $B^T B$ for a tall matrix $B$ using $\tilde{O}(\sqrt{nd}/\delta)$ row queries. This generalizes previous quantum graph sparsification results to tall matrices and achieves a quadratic speedup over the classical $\tilde{O}(n)$ query lower bound for this specific task.

2. Quantum Lewis Weight Computation:
   The authors develop a quantum algorithm to provide query access to $\epsilon$-multiplicative approximations of $\ell_p$-Lewis weights. This involves a preprocessing phase with $\tilde{O}(\sqrt{n} d^{7/2})$ queries and allows subsequent queries with sublinear cost, enabling the use of Lewis weight barriers in a sublinear quantum setting.

3. Robustness of IPMs to Approximations:
   The paper formally establishes that IPMs based on self-concordant barriers (Logarithmic, Volumetric, and Lewis weight) remain robust when the Newton step is implemented using approximate Hessians and gradients. Specifically, it shows that spectral approximations of the Hessian and approximations of the gradient in the inverse-local norm are sufficient to maintain convergence guarantees.

4. Quantum IPM for Tall LPs:
   By combining the above subroutines, the authors construct a quantum IPM that solves tall LPs with $n$ constraints and $d$ variables.

   • Complexity: For the Lewis weight barrier, the algorithm runs in time $\tilde{O}(\sqrt{n} \cdot \text{poly}(d, \log(1/\epsilon)))$.
   • Query Complexity: The algorithm makes $\tilde{O}(\sqrt{n} d^5)$ row queries to the input data. This is sublinear in $n$ when $n \gg d^{10}$.

Results

The paper provides the following theoretical results:

• Theorem 1.1 (Main Result): A quantum IPM exists that returns a feasible solution $\tilde{x}$ such that $c^T \tilde{x} \leq \text{val} + \epsilon$.

  • For the Logarithmic barrier: $\tilde{O}(nd)$ queries.
  • For the Volumetric barrier: $\tilde{O}(n^{3/4} d^{5/4})$ queries.
  • For the Lewis weight barrier: $\tilde{O}(\sqrt{n} d^5)$ queries.
  • The time complexity for the Lewis weight barrier is $\tilde{O}(\sqrt{n} \cdot \text{poly}(d))$.

• Lower Bounds:

  • The paper proves that any quantum algorithm for spectral approximation of $A^T A$ requires $\Omega(\sqrt{nd})$ row queries, indicating the $\sqrt{n}$ dependency in their algorithm is optimal.
  • It reproduces a lower bound showing that solving LPs to constant precision requires $\Omega(\sqrt{nd})$ quantum queries (or $\Omega(n)$ classical queries), suggesting the $d$-dependency in their algorithm is the primary area for potential improvement.

• Comparison to Benchmarks:

  • The authors compare their result to a quantum speedup based on cutting plane methods (using Grover search on a separation oracle), which achieves $\tilde{O}(\sqrt{n} d)$ queries.
  • They note that while their IPM has a worse dependence on $d$ ($d^5$ vs $d$), it represents a "white-box" approach that exploits the internal structure of IPMs, whereas the cutting plane method is a "black-box" application of Grover search.

Significance and Claims

The paper claims to provide a positive answer to the question of whether quantum algorithms can speed up Interior Point Methods for "tall" linear programs.

• Sublinear Speedup: The primary significance is the achievement of a sublinear time and query complexity in the number of constraints $n$ for tall LPs, a regime where classical algorithms are linear in $n$.
• Novel Subroutines: The work introduces novel quantum subroutines for spectral approximation and Lewis weight computation that are of independent interest for statistical regression and dimensionality reduction.
• Condition Number Independence: Unlike previous quantum IPM proposals that relied on quantum linear system solvers (introducing condition number dependencies), this approach avoids such dependencies by using spectral approximation and preconditioning.
• Error Dependence: The algorithm achieves a $\log(1/\epsilon)$ dependence on the precision, improving upon previous quantum LP algorithms that often had polynomial dependence on $1/\epsilon$.

The authors remain modest regarding the $d$-dependency, acknowledging that their current bound ($d^5$) is significantly worse than the $\sqrt{n} d$ bound of the cutting-plane benchmark. They identify improving the gradient approximation and leveraging dynamic data structures as key open directions to close this gap.