PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum gradient descent for linear systems and least squares

Iordanis Kerenidis, Anupam Prakash

arXiv:1704.04992v5quant-ph

TL;DR

The paper develops quantum methods for affine-gradient descent and QRAM-based linear-system solving. It applies these methods to weighted least squares and related linear-algebra tasks, including stochastic gradient descent and block-encoding-based quantum algorithms.

  • Problem

    The paper addresses the need for quantum iterative methods that can perform gradient descent with affine update rules and support practical least-squares settings.

  • Method

    The paper combines a quantum iterative framework for affine updates with QRAM-based singular-value estimation and linear-system algorithms.

  • Results

    The paper provides a first-order quantum gradient-descent method with cost polynomial in the number of steps, applications to weighted least squares, and QRAM algorithms for dense-matrix classes.

  • Takeaways & Limitations

    The methods provide quantum subroutines for weighted least squares, stochastic gradient descent, and block encodings used by quantum linear-system solvers.

  • Takeaways & Limitations

    The paper uses positive-semidefinite linear-system solvers for its applications rather than the more general linear-system solver described in the discussion.

Abstract

from arXiv · show

Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim and Lloyd for solving systems of linear equations. The utility of {classical} linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide the first quantum method for performing gradient descent when the gradient is an affine function. Performing $τ$ steps of the gradient descent requires time $O(τC_S)$ for weighted least squares problems, where $C_S$ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.

I. INTRODUCTION

The paper develops quantum iterative methods for affine-gradient descent and QRAM-based linear-system solving, addressing quantum-state outputs, failure probabilities, and sparsity limitations. Applications include weighted least squares, stochastic gradient descent, and dense-matrix problems.

  • 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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).

C. Quantum iterative methods

The paper develops a quantum iterative method for affine-gradient updates by coherently processing residual states and combining them to produce the final iterate. Its cost is polynomial in the number of steps, with O(τC_V) for the stated affine-update procedure and O(τ^2C_V) when matrices vary.

  • 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.
  • 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.
  • Quantum construction: 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.
  • 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.
  • 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.

D. Applications of quantum gradient descent

The paper applies quantum gradient descent to positive semidefinite linear systems and weighted least squares. The weighted least-squares application supports stochastic updates with reduced quantum-memory requirements, while QRAM procedures handle matrix operations for arbitrary input matrices.

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

E. Related Work and Discussion

The discussion positions the work as a QRAM-based route to efficient matrix block encodings and quantum iterative methods beyond sparse or low-rank inputs. The main iterative-method guarantee remains restricted to affine-gradient functions, while several broader applications are left for future work.

  • 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.
  • 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.
  • 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.
  • 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.

II. QUANTUM PRELIMINARIES

The preliminaries define the quantum iterative framework around affine updates, contracting linear residual maps, approximate quantum steps, and amplitude amplification. These ingredients yield a multistep procedure whose runtime scales linearly with the number of steps times the cost of one quantum step.

  • 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.
  • 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.
  • 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.
  • 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δ.

B. The Quantum Iterative Method: general case

The quantum iterative method constructs a unitary procedure for affine updates, then uses amplitude amplification and estimation to produce the final iterate and estimate its norm.

  • 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.
  • The output includes an approximation to the final state |˜θτ⟩ and an estimate of its norm.The parameter T is set to τ+1.
  • The procedure begins with registers encoding the iteration index, an initial residual state, and zero ancillas.
  • Conditioned on a successful flag, controlled operations erase duplicate iteration information and rearrange the registers.
  • A Hadamard transform on the iteration register completes the conditional processing before the registers are exchanged.

C. Analysis

The analysis establishes correctness and running-time bounds for the quantum iterative method, including how implementation costs and approximation requirements scale with the number of steps.

  • 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.
  • 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.
  • 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).
  • The expected running time is O(T(CU + log τ)), because amplitude amplification costs T times the cost O(CU + log τ) of implementing Q.
  • 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).
  • Using the stated linear-system implementation yields O(τ(τ^2µ(A))/δ), which is superlinear in τ.
  • An improved linear-system solver changes the step dependence to O(τµ(A) log(τ^2/δ)), which is linear in τ.
  • 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.

B. Improved Singular Value Estimation

The paper generalizes quantum singular value estimation using QRAM data structures, selecting matrix factorizations that yield efficient state preparation and improved dependence on matrix structure.

  • 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(δ).
  • The procedure accepts A, an input state |x⟩, and a precision parameter, then estimates singular values through phase estimation and uncomputing.
  • QRAM data structures prepare normalized states associated with matrix rows and columns, enabling efficient implementation of the required unitaries.
  • For suitable factorizations, SVE runs in eO(µ(A)/δ), with µ(A) selected from a constant-size set of candidate values.
  • 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.

C. Quantum matrix multiplication and linear systems

The paper applies singular value estimation to quantum matrix multiplication and linear systems, obtaining QRAM-based costs governed by µ(A) and describing their scope and limitations.

  • Singular value estimation implements matrix multiplication through conditional rotations proportional to singular values and inversion through rotations proportional to their inverses.
  • The algorithm extends matrix multiplication to affine maps, sending |x⟩ to a state close to |Ax + b⟩.
  • The paper’s applications use positive semidefinite systems rather than the more general sign-recovery procedure for arbitrary symmetric matrices.
  • For positive semidefinite matrices, the quantum multiplication and linear-system procedures use singular-value estimation, conditional rotations, and amplitude amplification.
  • The linear-system and matrix-multiplication algorithms achieve expected time eO(κ^2(A)µ(A)/δ) for δ-accurate output states.
  • 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.
  • 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.
  • 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.

1. Spectral Norm Estimation

The paper gives a QRAM-based procedure for estimating a matrix’s spectral norm relative to its Frobenius norm, enabling matrix rescaling and condition-number estimation. Its running time is eO(log(1/ε)/(εη)).

  • 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 τ.
  • Purpose: The estimate for η yields an estimate for ∥A∥ because ∥A∥F can be computed when A is efficiently loaded into QRAM.
  • 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.
  • Applications: The procedure can estimate a threshold related to the condition number κ for use in the linear-systems solver.
  • Caveat: The spectral norm estimation subroutine is used once and contributes an additive running-time term omitted from the solver’s stated estimates.

D. The iterative step

The iterative step for positive-semidefinite linear systems and least squares is implemented quantumly through singular value estimation and matrix multiplication. A multistep transformation then applies powers of the update in cost O(CV + log τ).

  • 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.
  • 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.
  • 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.
  • Affine update: The affine part initializes the residual by mapping the augmented input to (b − Ar0, 0).
  • 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.

A. Linear systems

The paper applies quantum affine iterative updates to positive-semidefinite linear systems and weighted least squares. For linear systems, the method converges in O(κ log(κ/ε)) iterations and outputs a state approximating |A−1b⟩.

  • 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.
  • A. Linear systems: O(κ log(κ/ε)) iterations suffice for the classical affine iterative method to reach error ε with constant step size and a unit-vector starting point.
  • A. Linear systems: The quantum algorithm outputs |z⟩ with ∥|z⟩−|A−1b⟩∥≤δ using the quantum implementation of the affine iterative steps.
  • A. Linear systems: The quantum multistep procedure avoids sequentially applying the update by estimating eigenvalues and directly rotating by powers of those eigenvalues.
  • 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⟩.
  • B. Weighted Least Squares: The weighted least-squares quantum algorithm has expected running time O(κ(A)^3 log^3 κ(A) ...), as stated in Theorem V.2.
  • B. Weighted Least Squares: 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.
  • B. Weighted Least Squares: 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.

C. Stochastic gradient descent for Weighted Least Squares

Quantum stochastic gradient descent reduces QRAM and coherent-qubit requirements by processing randomly partitioned batches, but its differing update matrices prevent the multistep acceleration available for fixed-matrix updates.

  • 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.
  • Motivation: Stochastic gradient descent can considerably reduce the QRAM size and the number of qubits requiring coherent operations for large datasets.
  • 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.
  • Correctness: Correctness follows because the quantum algorithm simulates each classical stochastic-gradient step with sufficient precision.
  • Method: Different batch matrices have different eigenbases, so stochastic-gradient updates must be applied sequentially rather than simultaneously powered.
  • 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.
Loading 1704.04992v5…