Quantum gradient descent for linear systems and least squares

I. INTRODUCTION

• The work improves on HHL’s restrictions that require well-conditioned, polylogarithmically sparse matrices and produce quantum states rather than classical solution vectors.These assumptions limit direct applications because machine-learning matrices are generally not sparse or well structured.Source: §I · p. 2
• The paper develops a quantum gradient-descent framework for affine update rules with polynomial scaling in the number of steps.For fixed matrices, the iterative cost is linear in the number of steps times the cost of one quantum step.Source: §I · p. 2
• QRAM-based singular-value estimation and linear-system solvers extend quantum speedups beyond sparse matrices to classes of dense matrices.Their running time depends on µ(A), with examples including bounded row ℓ1 norm and low-rank structure.Source: §I · p. 2, B. An improved quantum linear systems… · pp. 4–6
• The method addresses quantum iterative algorithms’ difficulty of feeding quantum-state outputs into later steps and restarting after probabilistic failures.The approach works with residual vectors and embeds norm-decreasing updates into unitary operations using an additional garbage state.Source: §I · p. 2
• The paper applies quantum gradient descent to positive semidefinite linear systems and weighted least squares, including stochastic gradient descent for skewed data matrices.Stochastic updates use small batches, and the quantum version is presented as reducing quantum memory requirements.Source: §I · pp. 2–3
• The QRAM solver can achieve a worst-case quadratic speedup over HHL and exponential speedups for dense matrices with polylogarithmic rank.For A = I + J/n, the paper gives µ(A) ≤ s1(A) = O(1), while the Frobenius norm is Ω(√n).Source: B. An improved quantum linear systems… · p. 6

Classical iterative methods

• Gradient descent applies iterative updates to minimize empirical-risk objectives, including weighted least squares and ridge regression with affine gradients.For quadratic objectives, the residual update can be represented by a linear operator.Source: C. Quantum iterative methods · p. 7

Quantum construction

• The method overcomes exponentially decreasing sequential success probabilities by applying updates to residual vectors whose norms contract.A garbage state makes the residual mapping length preserving, enabling implementation as a unitary transformation.Source: C. Quantum iterative methods · p. 8
• The quantum method avoids creating every intermediate parameter state by targeting the final iterate as the sum of update states r_t.It creates a coherent history over time steps, applies conditioned updates, and erases the time register before amplitude amplification.Source: C. Quantum iterative methods · pp. 8–9

Output

• The algorithm outputs a state close to θ_τ while using coherent update histories rather than requiring successful preparation of all intermediate θ_t states.The approach is designed for cases where the final iterate has sufficient norm for amplitude amplification to remain efficient.Source: C. Quantum iterative methods · pp. 8–9

Complexity

• O(τC_V) is the stated runtime for τ affine-update steps when one approximate quantum step costs C_V.For variable matrices, the paper states a runtime of O(τ^2C_V), as in quantum stochastic gradient descent.Source: C. Quantum iterative methods · p. 9

Positive semidefinite linear systems

• The positive semidefinite linear-system application outputs a state close to |A^-1b⟩ using an iterative QRAM-based quantum algorithm.The paper notes an extra factor of κ(A) relative to its direct method.Source: D. Applications of quantum gradient… · p. 9

Weighted least squares

• Weighted least squares minimizes squared loss using examples, labels, and weights, and is the paper’s main application of the quantum iterative method.The method extends quantum least-squares approaches to the weighted setting.Source: D. Applications of quantum gradient… · p. 9

Stochastic gradient descent

• Stochastic gradient descent estimates gradients from randomly sampled batches, avoiding linear-algebra operations on the full large data matrix.The quantum iterative method can perform this stochastic procedure for weighted least squares.Source: D. Applications of quantum gradient… · p. 10

Quantum memory

• Each stochastic-gradient step requires only one data batch in quantum memory, reducing requirements relative to directly solving the system or using HHL.This is useful when large coherent QRAMs are difficult to build.Source: D. Applications of quantum gradient… · p. 10

QRAM implementation

• The QRAM-based weighted least-squares solver updates the data structure using W before invoking matrix multiplication procedures.It operates with X, W, and y to implement operations involving (X^T W X)^-1 and X^T W y.Source: D. Applications of quantum gradient… · p. 10

QRAM and block encodings

• The QRAM results provide a family of algorithms for efficient block encodings of arbitrary matrices, parameterized by μ.These encodings can serve as subroutines for quantum linear-system solvers and quantum singular-value transformation.Source: E. Related Work and Discussion · pp. 10–11

Relation to dequantization

• The paper contrasts its QRAM-based quantum algorithms with dequantized low-rank methods whose polynomial overheads can remain large.It identifies smaller classical overheads in k and 1/ε as an open question.Source: E. Related Work and Discussion · p. 11

Scope

• The paper’s quantum iterative method achieves polynomial scaling in the number of steps only for functions whose gradient is affine.Finding broader quantum iterative frameworks remains future work.Source: E. Related Work and Discussion · p. 11

Future applications

• The stochastic-gradient approach is suited to settings where the system matrix is revealed incrementally rather than known in advance.The paper gives dynamic-programming and reinforcement-learning examples as possible future applications.Source: E. Related Work and Discussion · p. 11

Amplitude amplification

• Amplitude amplification extracts the desired state from the time-superposition procedure when the target component has sufficient amplitude.The paper’s amplitude-amplification statement gives exact state recovery upon successful amplification.Source: A. Quantum Algorithms · pp. 11–12

Iterative formulation

• The framework represents affine updates through residual vectors generated by an affine map L followed by a contracting linear operator S.This formulation covers linear-system and least-squares iterations.Source: A. The quantum step · p. 12

Approximate quantum steps

• An approximate quantum step estimates the affine and linear transformations within error ε, each succeeding with probability at least 1−δ.The procedure includes unnormalized garbage states to preserve the quantum transformation.Source: A. The quantum step · pp. 12–13

Multistep procedure

• An approximate multistep procedure can implement τ iterations with cost O(τC_V), while its accumulated error and failure probability scale with τ.The stated guarantee bounds the deviation by tε with probability at least 1−tδ.Source: A. The quantum step · pp. 13–14

• The method’s central construction is a unitary Q used with amplitude amplification and estimation.These procedures improve the running time of the quantum iterative method.Source: B. The Quantum Iterative Method:… · p. 14
• The output includes an approximation to the final state |˜θτ⟩ and an estimate of its norm.The parameter T is set to τ+1.Source: B. The Quantum Iterative Method:… · p. 14
• The procedure begins with registers encoding the iteration index, an initial residual state, and zero ancillas.Source: B. The Quantum Iterative Method:… · p. 14
• Conditioned on a successful flag, controlled operations erase duplicate iteration information and rearrange the registers.Source: B. The Quantum Iterative Method:… · p. 14
• A Hadamard transform on the iteration register completes the conditional processing before the registers are exchanged.Source: B. The Quantum Iterative Method:… · p. 15

• Theorem III.3 gives running time O(T(CU + log τ)) for τ affine-update steps, with T = τ+1.The result assumes a unitary U implementing an (ε, δ)-approximate quantum multistep procedure.Source: C. Analysis · p. 15
• The algorithm’s correctness follows by bounding the ℓ2 distance between the approximate and correct final states.The proof first bounds unnormalised distance and then applies Claim II.3 to obtain the normalised bound.Source: §1 · p. 15
• Amplitude estimation supplies a constant-relative-error estimate of the final-state norm under the stated norm and step-size conditions.The applications assume ∥θτ∥ = Ω(1), ∥θτ∥ = O(τ), and α = O(1).Source: §1 · p. 16
• The expected running time is O(T(CU + log τ)), because amplitude amplification costs T times the cost O(CU + log τ) of implementing Q.Source: §2 · p. 16
• For fixed-matrix updates, the applications achieve O(τ(CV + log τ)); stochastic gradient descent can instead incur O(τ^2CV).The latter occurs when each step uses a different matrix and CU = O(τCV).Source: §2 · p. 16
• Using the stated linear-system implementation yields O(τ(τ^2µ(A))/δ), which is superlinear in τ.Source: §2 · p. 16
• An improved linear-system solver changes the step dependence to O(τµ(A) log(τ^2/δ)), which is linear in τ.Source: §2 · p. 16
• The QRAM data structure supports efficient preparation of normalized row- and column-related states and implements its unitary in eO(log(mn)) time.Matrix updates require O(log^2(mn)) time per entry.Source: A. A generalized state preparation… · pp. 16–17

• The generalized SVE procedure uses phase estimation on a walk whose eigenphases encode the singular values of A.The relation is cos(θi/2) = σi/µ, allowing singular-value estimates within additive error O(δ).Source: B. Improved Singular Value Estimation · p. 18
• The procedure accepts A, an input state |x⟩, and a precision parameter, then estimates singular values through phase estimation and uncomputing.Source: B. Improved Singular Value Estimation · p. 18
• QRAM data structures prepare normalized states associated with matrix rows and columns, enabling efficient implementation of the required unitaries.Source: B. Improved Singular Value Estimation · p. 19
• For suitable factorizations, SVE runs in eO(µ(A)/δ), with µ(A) selected from a constant-size set of candidate values.Source: B. Improved Singular Value Estimation · p. 19
• A single-pass construction achieves µ(A) = min(∥A∥F, s1(A)) while retaining SVE time eO(µ(A)/δ).This choice covers sparse and low-rank matrices used in the iterative method.Source: B. Improved Singular Value Estimation · pp. 19–20

• Singular value estimation implements matrix multiplication through conditional rotations proportional to singular values and inversion through rotations proportional to their inverses.Source: C. Quantum matrix multiplication and… · p. 20
• The algorithm extends matrix multiplication to affine maps, sending |x⟩ to a state close to |Ax + b⟩.Source: C. Quantum matrix multiplication and… · p. 20
• The paper’s applications use positive semidefinite systems rather than the more general sign-recovery procedure for arbitrary symmetric matrices.Source: C. Quantum matrix multiplication and… · p. 20
• For positive semidefinite matrices, the quantum multiplication and linear-system procedures use singular-value estimation, conditional rotations, and amplitude amplification.Source: C. Quantum matrix multiplication and… · p. 20
• The linear-system and matrix-multiplication algorithms achieve expected time eO(κ^2(A)µ(A)/δ) for δ-accurate output states.Source: C. Quantum matrix multiplication and… · pp. 20–21
• The approach assumes QRAM access, and the optimal factorization may be unavailable because Perron–Frobenius eigenvectors cannot generally be computed with the required update efficiency.Source: C. Quantum matrix multiplication and… · pp. 21–22
• QRAM-based solvers can have sub-linear running time for dense matrices, with dependence on µ(A) rather than sparsity.The paper states a worst-case quadratic speedup over solvers in the HHL input model.Source: C. Quantum matrix multiplication and… · p. 21
• Under max-entry normalization, µ(A) is no larger than the maximum ℓ1 norm, which is no larger than maximum sparsity; some matrices therefore yield exponential improvement.The stated example is A = I + J/n or a small perturbation of a permutation matrix.Source: C. Quantum matrix multiplication and… · p. 21

Algorithm

• The algorithm estimates η := ∥A∥/∥A∥F by binary search over threshold tests using singular value estimation and amplitude estimation.It refines τ over O(log 1/ε) iterations, setting a register according to whether singular values exceed τ.Source: §1 · p. 22

Purpose

• The estimate for η yields an estimate for ∥A∥ because ∥A∥F can be computed when A is efficiently loaded into QRAM.Source: §1 · p. 22

Complexity

• eO(log(1/ε)/(εη)) is the algorithm’s running time for estimating ∥A∥ to error ε∥A∥F.The bound includes the repeated amplitude-estimation procedure and the binary-search iterations.Source: §1 · p. 22

Applications

• The procedure can estimate a threshold related to the condition number κ for use in the linear-systems solver.Source: §1 · p. 22

Caveat

• The spectral norm estimation subroutine is used once and contributes an additive running-time term omitted from the solver’s stated estimates.Source: §1 · p. 23

Update structure

• For linear systems and least squares, the iterative update matrix has the form S = I − αA, with S assumed positive semidefinite and contractive.Source: D. The iterative step · p. 23

Single step

• eO(μ(A|b)/ε) implements an approximate quantum step for S = I − αA when A|b is stored in the QRAM data structure.Here A|b denotes A augmented with an extra row equal to b, with α ≤ 1 and ∥b∥ = 1.Source: D. The iterative step · p. 23

Implementation

• Singular value estimation of A supplies estimates for the singular values of S, while conditional rotations implement the corresponding linear transformation.The resulting norm error is bounded by αε ≤ ε when the singular-value estimates succeed.Source: D. The iterative step · p. 23

Affine update

• The affine part initializes the residual by mapping the augmented input to (b − Ar0, 0).Source: D. The iterative step · p. 23

Multistep implementation

• O(CV + log τ) implements an approximate τ-step unitary without applying the step unitary sequentially τ times.After estimating eigenvalues, the method directly performs conditional rotations using their τ-th powers.Source: D. The iterative step · p. 24

A. Linear systems

• The linear-system task assumes positive-semidefinite A with eigenvalues in [1/κ, 1], unit-norm b stored in QRAM, and target equation Aθ = b.Source: A. Linear systems · p. 24
• O(κ log(κ/ε)) iterations suffice for the classical affine iterative method to reach error ε with constant step size and a unit-vector starting point.Source: A. Linear systems · p. 24
• The quantum algorithm outputs |z⟩ with ∥|z⟩−|A−1b⟩∥≤δ using the quantum implementation of the affine iterative steps.Source: A. Linear systems · p. 24
• The quantum multistep procedure avoids sequentially applying the update by estimating eigenvalues and directly rotating by powers of those eigenvalues.Source: A. Linear systems · p. 25

B. Weighted Least Squares

• Weighted least squares uses A = X^T W X and b = X^T W y, with the quantum algorithm producing a state approximating |A−1b⟩.Source: B. Weighted Least Squares · p. 25
• The weighted least-squares quantum algorithm has expected running time O(κ(A)^3 log^3 κ(A) ...), as stated in Theorem V.2.Source: B. Weighted Least Squares · p. 25
• The weighted least-squares update is mapped to the linear-system form rt = b − Aθt, so Theorem V.1 supplies its running-time guarantee.Source: B. Weighted Least Squares · p. 25
• Generalized singular value estimation implements the weighted matrix products from stored X and streamed weights, while ℓ2 regularization replaces A by X^T W X + λI.Source: B. Weighted Least Squares · pp. 25–26

Motivation

• Stochastic gradient descent estimates gradients over randomly sampled batches rather than summing across the entire dataset.This is useful when the dataset is large and contains redundancy.Source: C. Stochastic gradient descent for… · p. 26
• Stochastic gradient descent can considerably reduce the QRAM size and the number of qubits requiring coherent operations for large datasets.Source: C. Stochastic gradient descent for… · p. 26

Method

• The quantum method stores fixed-size batch matrices Aj = Xj^T Wj Xj and cycles their affine residual updates according to a chosen partition.Source: C. Stochastic gradient descent for… · p. 26

Correctness

• Correctness follows because the quantum algorithm simulates each classical stochastic-gradient step with sufficient precision.Source: C. Stochastic gradient descent for… · pp. 26–27

Method

• Different batch matrices have different eigenbases, so stochastic-gradient updates must be applied sequentially rather than simultaneously powered.Source: C. Stochastic gradient descent for… · p. 27

Complexity

• O(τ^4μ) results with a linear-system solver whose precision dependence is O(1/ε), while the cost becomes eO(τ^2μ) with logarithmic precision dependence.Source: C. Stochastic gradient descent for… · p. 27