Quantum linear systems algorithms: a primer

1.1 Motivation

• HHL offers an exponential speed-up over the best known classical algorithm for the quantum-state input/output problem, while classical-data input and output require careful consideration.The notes review HHL and subsequent improvements for sampling from linear-system solutions.Source: §1.1 · pp. 2–3

1.2 Quantum linear systems algorithms

• Classical conjugate gradient returns the full solution vector, whereas quantum algorithms sample from the solution, conditional on efficient preparation of |b⟩.Table 1 compares runtimes for conjugate gradient and quantum linear-systems algorithms; its caption identifies N, s, κ, ϵ, and ∥·∥F as parameters.Source: §1.2 · p. 3, Table 1 · p. 3

1.3 Quantum computing

• The circuit model prepares a quantum input state, applies a unitary, and measures a classical output; qubits encode normalized superpositions and quantum states may require exponentially many coefficients to describe.The notes also introduce measurements, universal gates, and oracles.Source: §1.3 · pp. 4–5

1.4 Quantum algorithms and machine learning

• The notes connect HHL-based quantum algorithms to machine learning, citing recommendation systems, perceptrons, and support vector machines as examples of quantum-learning work.The text states that the algorithms mentioned use HHL or another quantum linear-systems algorithm as a subroutine.Source: §1.4 · pp. 5–6

1.5 Structure

• The presentation is modular: it reviews quantum subroutines, develops HHL and its analysis, then surveys improvements in condition-number and precision dependence and QSVE-based methods.The later QSVE discussion is an overview of key ideas rather than a full pedagogical treatment.Source: §1.5 · p. 6

• The section reviews fundamental ideas routinely used in quantum algorithm design, which are subsequently applied in HHL.Source: §2 · p. 6

• Integers from 0 to N − 1, with N = 2^n, are represented as n-bit strings, and the notes also introduce binary fractional notation and vector and matrix norms.Source: §2.1 · p. 7

2.2 Quantum Fourier transform

• The QFT is the quantum analogue of the DFT, and the notes present its efficient quantum-circuit implementation.Source: §2.2 · p. 7

2.2.1 The discrete Fourier transform

• The DFT is an invertible matrix whose orthonormal columns form the Fourier basis; direct multiplication costs O(N^2), while the FFT reduces this to O(N log N).Source: §2.2.1 · p. 7

2.2.2 The quantum Fourier transform

• The QFT is defined as a linear operator acting on computational-basis states, and its output encodes the input string in relative phases recoverable by the inverse QFT or Fourier-basis measurement.Source: §2.2.2 · pp. 7–8

2.2.3 Implementation of the QFT

• The circuit construction uses Hadamard gates, controlled rotations, and final SWAP operations; its gate count scales as O(n^2).The construction prepares the qubits in sequence, applying controlled rotations to encode the phases.Source: §2.2.3 · p. 8

2.3 Hamiltonian simulation

• Quantum simulation implements U = e^-iHt to given error; efficient simulation uses poly(n, t, 1/epsilon) gates, while generic Hamiltonian simulation is BQP-hard.Classical matrix-exponential methods can require O(N^3) time, and generic Hamiltonian evolution is difficult to decompose into elementary gates.Source: §2.3 · pp. 8–9

2.3.1 Trotter-Suzuki methods

• Efficient simulation is available for structured cases such as constant-local Hamiltonians and sparse Hamiltonians with efficiently accessible nonzero entries.Sparsity is basis-dependent, and row computability requires efficient access to matrix entries.Source: §2.3.1 · pp. 10, 12, §2.3.2 · p. 12
• Trotter-Suzuki methods approximate evolution under sums of noncommuting Hamiltonians by products of simpler evolutions, with higher-order schemes improving the time scaling.The first-order scheme truncates after m steps to control error; higher-order schemes can simulate for time t in t^(1+delta) for arbitrarily small positive delta.Source: §2.3.1 · pp. 10–12

2.3.2 Graph-colouring method

• The graph-colouring method partitions a sparse Hamiltonian into colour-specific terms that form direct sums of two-dimensional blocks, which can be simulated and recombined with Trotter-Suzuki.For sparse graphs, the described local bipartite colouring uses at most d^2 colours and, by reduction, suffices for arbitrary Hamiltonians.Source: §2.3.2 · p. 13
• The method requires efficient local edge colouring; although optimal colouring is NP-hard generally, the section gives polynomial-time non-optimal colouring approaches.The construction uses neighbour and edge-colour information to retrieve matrix entries; complex entries are handled through separate real and imaginary parts.Source: §2.3.2 · pp. 13–15

2.4 Erroneous Hamiltonian simulation

• The faulty-simulator analysis uses matrix concentration bounds under bounded-error-norm and matrix-variance assumptions to control random simulator errors.The matrix variance statistic generalizes variance, and the cited matrix Bernstein result requires independent, centered, uniformly bounded random matrices.Source: §2.4 · pp. 16–17

2.4.1 Modern methods for Hamiltonian simulation

• A Szegedy quantum-walk approach has the best stated dependence on sparsity s and evolution time t, but worse error dependence, scaling as O(s||Hmax||t/sqrt(epsilon)).The section notes that other recent methods approach linear parameter dependence.Source: §2.4.1 · p. 17

2.5 Quantum phase estimation

• Phase estimation approximates an eigenvalue λ = e^(i2πφ) by finding an n-bit approximation of its phase φ using n ancillary qubits.For a unitary U, the stated algorithm estimates eigenphases to error epsilon with probability 1 - 1/poly(n) in time O(TU log(n)/epsilon).Source: §2.5 · pp. 17, 19
• The circuit prepares ancillas in equal superposition, applies controlled powers of U to the eigenstate, then measures in the Fourier basis to obtain the phase bits.For a non-exact phase representation, the measurement may need to be repeated.Source: §2.5 · pp. 17–18, Figure 1 · p. 18, Figure 2 · p. 18
• Phase estimation also works on an arbitrary input state by applying the eigenvalue-to-phase mapping across its decomposition into the operator's eigenbasis.The coefficients in that decomposition are overlaps with the eigenvectors; the eigenbasis need not be explicitly known.Source: §2.5 · p. 19

2.6 Phase kickback

• With the ancillary register prepared for the oracle query, inputs evaluating to 1 acquire a relative phase, which is the phase-kickback effect.The passage assumes the queried function can be computed classically in polynomial time, so the oracle call hides no complexity.Source: §2.6 · p. 19

Grover’s algorithm

• Grover’s algorithm finds a unique marked item using O(√N) oracle queries, versus O(N) classically; this is optimal.The search is modeled by a Boolean oracle that marks exactly one item.Source: §2.7 · pp. 19–20
• Each Grover iteration applies the oracle phase flip and diffusion reflection, rotating the state toward the marked item while suppressing unmarked amplitudes.Geometrically, the two reflections rotate the state by 2θ in the plane spanned by the initial state and marked state.Source: §2.7 · pp. 20–21

Amplitude amplification

• The same amplification framework applies to any oracle-defined good subset, boosting its amplitude so measurement samples a good string more often.The state is viewed as a combination of good and bad subspaces.Source: §2.7 · pp. 21–22
• Amplitude amplification boosts an algorithm’s success probability ε to arbitrarily close to one with O(1/√ε) repetitions.The successful outputs form the good subspace and unsuccessful outputs the bad subspace.Source: §2.7 · p. 22

Why uncompute

• Clearing garbage prevents later computations from inheriting a dirty workspace that could be entangled with the output.The input register is also retained.Source: §2.8 · p. 22

Uncompute trick

• The uncompute trick applies the oracle, copies its output with an added register and CNOT, then applies the inverse oracle and swaps registers to clear the workspace.The result retains |x⟩|f(x)⟩ while the working and ancillary registers return to |0⟩.Source: §2.8 · pp. 22–23

Error analysis

• If the unitary oracle acts within error ε, the mapping |x⟩|0⟩→|x⟩|f(x)⟩ can be enacted within error ε.The argument bounds the overlap between the actual and ideal output states.Source: §2.8 · p. 23

Data structure

• The qRAM data structure stores x_i² and sgn(x_i) at each leaf, with child-value sums at internal nodes; the structure has O(N) nodes.The stored values are precomputed, and the preparation cost is not counted because the structure can be reused to create copies of |x⟩.Source: Figure 4 · p. 24, §2.9 · p. 25

State preparation

• A depth-first traversal uses controlled rotations to allocate amplitude mass among subtrees and handles each element’s sign at the leaves.The procedure assigns the desired amplitude x_i to basis state |i⟩.Source: §2.9 · p. 25
• Algorithm 1 prepares |x⟩ from a stored, normalized vector in O(log N) time.The runtime assumes constant-cost rotations.Source: §2.9 · pp. 25, 27

Error analysis

• Because the loading procedure uses O(N) rotations in total, constant-precision state preparation requires per-rotation error ε=O(1/N).The rotation errors add, giving total state error O(Nε).Source: §2.9 · p. 27

Limitations and assumptions

• Whether vectors can be prepared with sufficient precision in polylogarithmic time at application scales remains unclear, so the notes assume the qRAM operation exists.The required qRAM time is at most polylogarithmic in N for an exponential speed-up when the corresponding classical task is polynomial-time computable.Source: §2.9 · pp. 23, 27

3.1 Problem definition

• The QLSP takes a quantum state |b⟩ as input and returns an approximation to the normalized solution state, rather than the full vector x.Reading every component takes O(N), so polylogarithmic-time solutions are useful when sampling from x suffices.Source: §3.1 · pp. 28–29

3.2 The HHL algorithm

• HHL uses phase estimation, a controlled rotation to encode eigenvalue inversion, and uncomputation; postselecting the flag outcome 1 yields a state close to |x⟩.Amplitude amplification can boost the success probability instead of relying only on measurement and postselection.Source: §3.2.1 · pp. 29–30

3.2.1 Algorithm summary

• HHL is exponentially faster in N than conjugate gradient, but linearly slower in sparsity s and condition number κ, and exponentially worse in precision ε.The precision slowdown was later eliminated by Childs et al..Source: §3.2.1 · pp. 30–31

3.2.2 Algorithm details

• The inversion filters restrict inversion to well-conditioned eigenvalues; the algorithm returns the well-conditioned component and uses O(κ) amplitude-amplification repetitions.The filter functions interpolate across an intermediate eigenvalue range to improve numerical stability.Source: §3.1 · p. 28, §3.2.2 · pp. 33–34
• The detailed HHL runtime is eO(κTB + κ²s² log(N)/ε), including input-state preparation cost TB.Here κ is the condition number, s is matrix sparsity, and ε is the desired precision; the κ factor includes amplitude amplification.Source: §3.2.2 · p. 34

3.3.1 A short analysis

• The filter map λ → |h(λ)⟩ is O(κ)-Lipschitz, supporting the short analysis’s bound on phase-estimation error.The filter functions invert the well-conditioned eigenvalues and flag ill-conditioned ones, interpolating when 1/κ′ < |λ| < 1/κ with κ′ = 2κ.Source: §3.3.1 · p. 34
• With phase estimation accuracy δ, the short analysis gives runtime O(κ · polylog(N)/ϵ), assuming postselection succeeds.The passage also notes that the original improved phase-estimation scheme makes the analysis more complex.Source: §3.3.1 · p. 35
• The postselection success probability is at least 1/κ^2; amplitude amplification raises it to 1/κ, so O(κ) repetitions suffice on average.The short analysis assumes the eigenvalues lie in the well-conditioned subspace for its postselection calculation.Source: §3.3.1 · p. 36

3.3.2 Detailed analysis

• The detailed analysis bounds the error of the postselected output by comparing ideal and estimated filter-function values under phase-estimation error.It expresses the difference in postselection probabilities as expectations of differences in f and g and their squares.Source: §3.3.2 · pp. 37–38
• The detailed analysis combines the state-error bound with the postselection cost, which amplitude amplification can reduce from O(κ^2) to O(κ).The cited runtime passages give only incomplete expressions, so they do not support a complete overall runtime formula.Source: §3.3.2 · p. 39

3.4 Matrix inversion is BQP-complete

• Even under the stated weak definition, matrix inversion is BQP-complete.The task takes a sparse, Hermitian matrix with a bounded condition number and returns a measurement statistic of the normalized solution state.Source: §3.4 · p. 39
• The HHL construction represents a circuit using n qubits and T gates by an O(1)-sparse matrix of dimension N = O(2^nκ).The passage attributes this construction to.Source: §3.4 · p. 39
• For any quantum circuit, an associated matrix can be inverted and sampled to reproduce the circuit’s output in a fixed fraction of instances.The reduction constructs a unitary that applies the circuit’s gates and their inverses across an ancillary time register, then postselects a time interval.Source: §3.4 · p. 40

3.5 Optimality of HHL

• If matrix inversion runs in time κ^(1−δ) poly(log N), the reduction implies PSPACE = BQP.The argument uses iterative simulation of a quantum circuit and the PSPACE-completeness of TQBF.Source: §3.5 · p. 41

3.6 Non-Hermitian Matrices

• For non-square, non-Hermitian A, HHL outputs the state |x⟩ := A+|b⟩ after discarding the ancillary |1⟩ register.The construction embeds A in a Hermitian matrix with eigenvalues ±σ_i and applies HHL to the augmented input.Source: §3.6 · p. 41
• When the system is over-constrained and |b⟩ is outside the span of A’s left singular vectors, the returned state minimizes squared error.When |b⟩ lies in that span, applying the construction returns a valid solution.Source: §3.6 · p. 41

4.1 Variable time amplitude amplification for improved condition number dependence

• Ambainis [Amb10] reduces HHL’s condition-number dependence from κ^2 to κ log^3 κ using variable-time amplitude amplification.VTAA amplifies success across branches with different stopping times, potentially improving on conventional amplitude amplification when average branch runtime is much smaller than the maximum.Source: §4 · p. 42, §4.1 · p. 43

4.2 Exponentially improved precision number dependence

• Childs, Kothari, and Somma reduce QLSP precision dependence from O(poly(1/ϵ)) to O(poly log(1/ϵ)) using an LCU framework that avoids phase estimation.Their Fourier approach approximates 1/x on the well-conditioned eigenvalue interval; a Chebyshev-polynomial alternative can be slightly more efficient to implement but requires explicit access to A’s entries.Source: §4 · p. 42, §4.2 · pp. 43–46

4.3 QSVE based QLSA

• The QSVE-based QLSP algorithm [WZP18] gives a polynomial speedup for dense matrices and uses quantum singular-value estimation.The section says this approach removes HHL’s sparsity requirement; QSVE requires efficient preparation of quantum states corresponding to A’s rows and columns using a suitable data structure such as qRAM.Source: §4 · p. 42, §4.3 · p. 46

4.3.1 Singular values and subspaces

• For A ∈ R^(m×n), the singular value decomposition expresses A using unitary left and right singular vectors and positive singular values.In the factorization described, the singular values equal the cosines of principal angles between associated subspaces.Source: §4.3.1 · p. 47

4.3.2 The QSVE algorithm

• QSVE [KP16] encodes singular values through principal angles and estimates them using phase estimation on a quantum walk built from reflections.The walk’s two-dimensional eigenspaces are associated with singular-vector pairs; its rotations encode the singular values relative to the Frobenius norm of A.Source: §4.3 · p. 46, §4.3.2 · pp. 47–48
• QSVE estimates singular values to additive error δ∥A∥F in O(polylog(mn)/δ) time.The estimate follows phase estimation of the rotation angle, with singular-value error bounded by δ∥A∥F.Source: §4.3.2 · p. 49

4.3.3 Extension to QLSA

• For general linear systems, the QSVE-based solver recovers eigenvalue signs using QSVE as a black box, with only constant overhead.This extension is presented in.Source: §4.3.3 · p. 49, §4.3.2 · p. 49
• For dense matrices with bounded spectral norm, the QSVE-based solver runs in O(κ^2√n · polylog(n)/ϵ) and returns the output with constant ϵ-error.When ∥A∥F is bounded by a constant, it instead achieves polylogarithmic time even for non-sparse matrices; for low-rank matrices, the scaling uses the square root of rank rather than the Frobenius norm.Source: §4.3.3 · p. 50
• The QSVE-based solver achieves O(√n) scaling in the stronger memory model, while achieving similar scaling in the black-box model remains an open question.The stronger model provides matrix entries |i, j, Aij⟩.Source: §4.3.3 · p. 51