Source-linked AI summary
A quantum linear system algorithm for dense matrices
Leonard Wossnig, Zhikuan Zhao, Anupam Prakash
TL;DR
The paper addresses the cost of solving high-dimensional linear systems, which limits machine-learning and optimization applications, especially for dense matrices. It constructs a quantum linear-system solver from QSVE and reports sparsity-independent runtime scaling, including O(κ^2√n polylog(n)/ε) for dense matrices with bounded spectral norm.
Problem
Inverting high-dimensional matrices is a bottleneck in statistical learning and machine learning, while existing quantum linear-system speedups can be lost for dense matrices.
Method
The algorithm uses QSVE to estimate singular values and a procedure to recover eigenvalue signs, with quantum-accessible data structures for preparing states from matrix rows and row Frobenius norms.
Results
O(κ^2√n polylog(n)/ε) runtime is achieved for dense matrices with spectral norm bounded by a constant.
Takeaways & Limitations
The proposed solver provides sparsity-independent scaling and a quadratic improvement over known quantum linear-system algorithms for the stated dense-matrix setting.
Takeaways & Limitations
The paper leaves open whether similar scaling is possible with black-box access to matrix entries and whether the algorithm has a more advantageous fault-tolerant gate overhead.
Abstract
from arXiv · showhide
Solving linear systems of equations is a frequently encountered problem in machine learning and optimisation. Given a matrix $A$ and a vector $\mathbf b$ the task is to find the vector $\mathbf x$ such that $A \mathbf x = \mathbf b$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}(κ^2 \|A\|_F \text{polylog}(n)/ε)$, where $n\times n$ is the dimensionality of $A$ with Frobenius norm $\|A\|_F$, $κ$ denotes the condition number of $A$, and $ε$ is the desired precision parameter. When applied to a dense matrix with spectral norm bounded by a constant, the runtime of the proposed algorithm is bounded by $\mathcal{O}(κ^2\sqrt{n} \text{polylog}(n)/ε)$, which is a quadratic improvement over known quantum linear system algorithms. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows and row Frobenius norms of $A$.
APPENDIX
The appendix analyzes error bounds for the QSVE-based solver, including filtering of ill-conditioned eigenspaces and the runtime implications of precision and post-selection.
- Error control: The filter functions f and g separate well-conditioned inversion from ill-conditioned and uninverted components.They satisfy f^2(λ)+g^2(λ) ≤ 1 and define the behavior across the transition region.
- Error control: The solver can invert only the well-conditioned part of the matrix while flagging ill-conditioned components.Filter functions interpolate between inversion and no inversion for eigenvalues with 1/(2κ) < |λ| < 1/κ.
- Error analysis: The QSVE error analysis bounds eigenvalue distance by δ∥A∥F and uses the Lipschitz property of the state map.The appendix states that the eigenvalue-distance bound follows from phase-estimation accuracy and the O(κ)-Lipschitz property.
- Runtime: Requiring final error O(ε) determines the phase-estimation precision needed by the algorithm.The resulting QSVE runtime is O(κ∥A∥F · polylog(n)/ε), before the post-selection repetition cost is included.
- Runtime: Post-selection requires repeating the algorithm on average κ^2 times, although amplitude amplification can reduce this factor to κ.The appendix then combines the precision and post-selection costs into the final runtime bound.