PaperlayerView exact revision on arXiv

Source-linked AI summary

The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation

Shantanav Chakraborty, András Gilyén, Stacey Jeffery

arXiv:1804.01973v2quant-phcs.DS

TL;DR

Quantum algorithms for linear systems and related tasks depend strongly on how matrices are accessed, motivating techniques that work beyond sparse inputs. This paper develops block-encoding tools and obtains improved quantum least-squares and electrical-network algorithms, including a sixth-power condition-number improvement for weighted least squares.

  • Problem

    Matrix-access models limit quantum linear-system algorithms, while extending efficient techniques beyond sparse inputs remains important for broader applications.

    Source: §1 · pp. 3–4

  • Method

    The paper develops block-encoding tools for singular-value estimation, linear-system solving, Hamiltonian simulation, and variable-time amplitude estimation.

    Source: §1 · pp. 4–5

  • Results

    The weighted least-squares solver improves condition-number dependence from κ6 to κ and precision dependence from 1/ε to polylog(1/ε), while also introducing GLS and electrical-network solvers.

    Source: §1 · p. 5

  • Takeaways & Limitations

    The block-encoding framework supports quantum algorithms across quantum data-structure and sparse-access models, including improved least-squares and electrical-network estimation.

    Source: §1 · pp. 4–5

    The presented singular-value estimation permits entangled auxiliary or garbage states, which can be undesirable in some scenarios.

    Source: §4.2 · p. 28

Abstract

from arXiv · show

We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

1 Introduction

The paper develops a block-encoding framework for quantum algorithms with sparse-access and quantum-data-structure inputs, introducing tools including variable-time amplitude estimation. It applies these techniques to Hamiltonian simulation, linear-system and least-squares problems, and electrical-network quantity estimation.

1 Introduction

  • Block-encodings unify sparse-access, quantum-data-structure, and hybrid input models, transferring Hamiltonian-simulation and other block-encoding results across them.Quantum-data-structure matrices admit ε-approximate block-encodings in polylog(N/ε) complexity, and sparse-access matrices do likewise.Source: §1 · p. 3
  • Variable-time amplitude estimation estimates a variable-stopping-time algorithm’s success probability to multiplicative error ε, while separately estimating amplification phases and improving amplification complexity logarithmically.This avoids repeatedly running the full algorithm when branches terminate at earlier stages.Source: §1 · pp. 4–5

1.2 Application to least squares

  • The quantum weighted least-squares solver improves condition-number dependence from κ6 in [KP17] to κ and precision dependence from 1/ε to polylog(1/ε), while the paper introduces the first quantum generalized least-squares solver.Both solvers operate with block-encoded inputs and apply to quantum-data-structure or sparse-access models.Source: §1 · p. 5, §1.2 · p. 9

1.1 Techniques for block-encodings

  • The framework combines block-encodings algebraically, supports singular-value estimation and inverse powers, and reduces block-encoded linear-system solving from quadratic to linear condition-number dependence via variable-time amplification.It also derives Hamiltonian simulation in eO(tµ(A)polylog(N/ε)) for quantum-data-structure Hermitian matrices and extends solvers to A^-c.Source: §1.1 · pp. 6–7

1.2 Application to least squares

  • The quantum weighted least-squares solver improves dependence on κ by a 6-th power and dependence on 1/ε exponentially over [KP17], while its sparse-access version replaces µ with sparsity.Its ordinary least-squares special case has linear κ dependence and polylog(1/ε) precision dependence, though prior subroutines may permit further improvements.Source: §1.2 · p. 9
  • The paper gives the first quantum generalized least-squares solver, including a block-encoding formulation and a quantum data structure special case.The corresponding sparse-access algorithm replaces µX and µΩ with the respective sparsities of X and Ω.Source: §1.2 · p. 9

1.3 Application to estimating electrical network quantities

  • The electrical-network applications estimate dissipated power for external vertex currents and effective resistance as the unit-current special case, including dense networks and quantum data structure inputs.The quantum data structure model stores the weighted vertex-edge incidence matrix and input current vector quantum-accessibly.Source: §1.3 · pp. 9–10
  • In the sparse-access model, the algorithm estimates dissipated power or effective resistance to ε-multiplicative error and always outperforms Wang’s linear-systems-based algorithm.Against Wang’s quantum-walk algorithm, speedups hold in parameter regimes stated in the paper; compared with [IJ16], improvement occurs when Rs,t ≫d4/N2, though the input models differ.Source: §1.3 · p. 11
  • The quantum data structure algorithm is the first for these electrical-network quantities and outperforms Wang’s linear-system algorithms when the maximum degree is Ω(N1/3).It uses a block-encoding QLS solver and variable-time amplitude estimation, while comparisons with prior algorithms remain input-model dependent.Source: §1.3 · p. 11

2 Preliminaries

This section establishes matrix notation and introduces block-encodings as a unified framework for quantum-accessible and sparse input models. It develops composition, Hamiltonian-simulation, and matrix-power tools used later.

2.1 Notation

  • Notation defines row and column spaces, singular-value-based pseudoinverses, and related matrix constructions used throughout the paper.Source: §2.1 · p. 12

2.2 Quantum-accessible data structure

  • A quantum-accessible data structure stores sparse matrix entries with polylogarithmic-time quantum access, O(w log^2(MN)) memory, and supports quantum state preparation.It uses binary trees to enable ε-approximate unitaries in O(polylog(MN/ε)) time and later supports block-encoding A.Source: §2.2 · pp. 12–14

2.3 Unitary block-encoding of matrices

  • Block-encodings represent subnormalized matrices as unitary blocks, compose with multiplicative normalization and additive error, and enable Hamiltonian simulation and positive or negative matrix powers.Hamiltonian simulation uses O(|αt| + log(1/ε)) controlled block-encoding calls, while power constructions apply under spectral bounds I/κ ⪯ H ⪯ I.Source: §2.3 · pp. 14–16

2.4 Sparse-access input model

  • In the sparse-access model, row and column sparsity oracles provide efficient block-encodings of matrices, as established by Lemma 11 [GSLW18, Lemma 48].Source: §2.4 · p. 16

3 Variable-time amplitude amplification and estimation

The section defines variable-stopping-time algorithms and variable-time amplification, then develops complexity analyses and an estimation strategy based on mindful amplification followed by amplitude estimation.

3 Variable-time amplitude amplification and estimation

  • Variable-time amplitude estimation seeks an ε-multiplicative estimate of an algorithm’s initial success amplitude or probability while exploiting branches that stop at different times.Variable-time amplification instead amplifies success while accounting for branches marked “bad” at intermediate stopping times.Source: §3 · p. 17, §3.1 · p. 17
  • Mindful amplification first raises the amplitude to Θ(1) while estimating its gain to ε/3-multiplicative precision, after which amplitude estimation incurs an overhead of ≈1/ε.Estimating the amplified amplitude to ε/3-multiplicative precision produces an ε-multiplicative approximation to the initial amplitude.Source: §3 · p. 17

3.1 Variable-stopping-time algorithms and variable-time amplification

  • Variable-stopping-time algorithms use control registers to mark branches that have stopped, after which later segments leave those branches unchanged.The construction acts on a control register and an algorithm register, with segments controlled by earlier stopping information.Source: §3.1 · p. 17
  • The analysis yields complexity bounds for uniformly bounded variable-time amplifications and allows the number of distinct stopping times to be reduced to ≤1 + log(Tmax/t1).The resulting upper bound depends on the stopping-time distribution through T^2, and the stopping-time discretization increases that quantity by at most a constant factor.Source: §3.1 · pp. 19–21

3.2 Efficient variable-time amplitude amplification and estimation

  • Ordinary amplitude amplification is analyzed phase by phase, with efficiency controlled when amplification does not overamplify the success amplitude.The approach selects amplification amounts in each phase so that inefficiencies remain bounded; the derived upper bound can contain a logarithmic Tmax factor.Source: §3.2 · pp. 21–22

Using A′ the variable-time amplification problem can be solved with query complexity15

The section constructs an efficient variable-time amplification algorithm A′ with constant success amplitude and uses it to obtain variable-time amplitude estimation and ε-mindful amplification. The construction estimates the initial success probability, amplifies it, sparsifies stopping times, and inductively applies amplitude amplification.

Complexity analysis

  • Corollary 19 supplies the final variable-time amplification complexity claim, with a refined analysis reducing the Tmax√m term to Tmax.The resulting amplification algorithm need only be constructed once; its query and gate costs match those of the resulting variable-time amplification.Source: Using A′ the variable-time… · pp. 23–24

Theorem 23

  • A′ prepares a target state with amplitude a = Θ(1), has complexity O(Q), and supports solving the ε-mindful-amplification problem for any ε ∈ (0, 1).The circuit construction succeeds with probability at least 1 − δ.Source: Using A′ the variable-time… · p. 24

Construction of A′

  • The construction first estimates p_prep, amplifies the state-preparation procedure using Θ(1/√p_prep) steps, and appends this amplified procedure to the variable-stopping-time algorithm.This creates a new algorithm whose first stopping-time segment incurs the amplification overhead C.Source: Using A′ the variable-time… · p. 24
  • Stopping times are sparsified, then A′ is built inductively by estimating each maybe-good amplitude and applying amplitude amplification enough times to satisfy the required invariants.The procedure achieves overall success probability at least 1 − δ/2.Source: Using A′ the variable-time… · p. 24

4 Linear system solving using blocks of unitaries

This section develops block-encoding-based primitives and variable-time quantum linear-system solvers, including matrix application, inversion, pseudoinverse, and negative-power state preparation. It connects these methods to quantum-accessible data structures for efficiently preparing |b⟩ and analyzes the resulting complexity, including improved condition-number and precision dependence.

4 Linear system solving using blocks of unitaries

  • Block-encoding A enables preparation of a state approximating A|b⟩/||A|b⟩|| by applying the encoding and amplitude amplification, with negative powers handled through block-encoding transformations.The resulting complexity and success guarantees depend on the block-encoding cost, state-preparation cost, normalization, and approximation error.Source: §4 · pp. 25–26
  • Quantum-accessible data structures yield efficiently implementable block-encodings, enabling the framework’s Hamiltonian-simulation and quantum-linear-system applications.The construction supports both weighted row-norm encodings with normalization µ_p(A) and Frobenius-norm encodings, under sufficient stored precision.Source: §4 · p. 26

4.1 Hamiltonian simulation with quantum data structure

  • Hamiltonian simulation combines these data-structure block-encodings with Low and Chuang’s optimal simulation method to block-encode e^{itH} with normalization 1 and error ε.The result applies when either suitable powered row-norm data structures or a quantum-accessible data structure stores the Hermitian Hamiltonian.Source: §4.1 · p. 28

4.2 Quantum singular value estimation

  • The block-encoding QSVE algorithm estimates singular values to additive precision ∆ with failure probability ε, and recovers Kerenidis and Prakash’s runtime in the quantum-data-structure setting [KP16].The method uses Hamiltonian simulation of a Hermitian dilation of A; its relaxed definition permits an entangled auxiliary or garbage state, which can be undesirable.Source: §4.2 · pp. 28, 31, 32

4.3 Quantum linear system solvers

  • A direct block-encoding linear-system solver initially incurs quadratic dependence on the condition number κ, while Ambainis-style variable-time techniques reduce this dependence to linear.The solver prepares a state proportional to A^+|b⟩ by applying a block-encoding of A^-1 followed by amplitude amplification.Source: §4.3 · p. 32
  • For κ ≥ 2, if H is Hermitian with nonzero eigenvalues in [−1,−1/κ] ∪ [1/κ,1] and has a block-encoding, a variable-time algorithm outputs a state ε-close to H−1|ψ⟩.The input state |ψ⟩ spans the eigenvectors of H.Source: §4.3 · p. 34
  • The construction supports non-symmetric matrices by Hermitian embedding, and its implementation cost includes a logarithmic construction overhead that is omitted when analyzing the resulting variable-time amplification algorithm.The overhead is justified when the input-state preparation unitary is fixed because the variable-time algorithm is constructed only once.Source: §4.3 · p. 34
  • Corollary 31 extends the solver to pseudoinverse state preparation when |ψ⟩ has sufficient overlap with the supported eigenspaces, with complexity reduced according to that overlap parameter.The assumption is that the input-state overlap with the relevant range is at least √γ.Source: §4.3 · p. 37
  • Corollary 32 replaces variable-time amplitude amplification with variable-time amplitude estimation to estimate the pseudoinverse output norm with improved condition-number dependence.The procedure outputs a number Γ under the same assumptions as Corollary 31.Source: §4.3 · p. 37
  • Theorem 33 generalizes the construction from H^-1 to H^-c for any c > 0, providing variable-time algorithms for both state preparation and estimating the corresponding output quantity.The complexity uses q = max(1, c), while the construction retains the same multi-scale stopping-time structure.Source: §4.3 · p. 38
  • Compared with Wossnig, Zhao and Prakash [WZP18], the resulting data-structure solver has linear rather than quadratic condition-number dependence and exponentially better precision dependence.The solver applies when A is supplied through the specified quantum-accessible data structures and |b⟩ can be prepared by a unitary.Source: §4.3 · p. 39
  • For quantum-accessible b, the state |b⟩ can be prepared in time T_b = O(polylog(N/ε)).Source: §4.3 · p. 39
  • Under this data-access assumption, the complexity of solving case (i) in Theorem 34 is specified separately.Source: §4.3 · p. 39
  • The complexity of solving case (ii) in Theorem 34 is likewise given separately using eO notation.Source: §4.3 · p. 39

5 Applications

This section applies block-encoding quantum linear-system techniques to weighted and generalized least squares and to electrical-network estimation. It develops algorithms for these problems across sparse-access and quantum-data-structure input models, including estimates of dissipated power and effective resistance.

5 Applications

  • The applications cover quantum weighted and generalized least-squares solvers, plus algorithms for estimating electrical-network quantities.The least-squares solvers output quantum states approximating the minimizing coefficient vectors, while the network algorithms estimate dissipated power and effective resistance.Source: §5 · p. 39, §5.1 · p. 40, §5.2 · p. 44

5.1 Least squares

  • Least squares models minimize weighted or correlated-error residuals, with weights represented by W and error correlations by a positive-definite covariance matrix Ω.The quantum versions receive X, y, and the relevant weighting information, then prepare an approximation to the coefficient-vector state within error ε.Source: §5.1 · p. 40

5.1.1 Weighted least squares

  • The weighted least-squares solver improves over [KP17] with exponential improvement in ε dependence and a 6th power improvement in κ_A dependence.The algorithm assumes sufficiently good weighted fit and supports data-structure access to the weighted response and matrix, with a separate-access version also provided.Source: §5.1.1 · pp. 41–42

5.1.2 Generalized least squares

  • The cited results establish quantum GLS solvers using block-encodings, including an alternate-input corollary and variants for quantum data structures or sparse-access oracles, each with error ε and stated complexity.Source: §5.1.2 · pp. 42–44

5.2 Estimating electrical network quantities

  • The electrical-network algorithm replaces Wang’s [Wan17a] sparse-matrix QLS component with block-encoding QLS and variable-time amplitude estimation, outperforming his linear-system algorithm for all networks.It also improves on the quantum-walk algorithm in some parameter regimes, provides the first quantum-data-structure algorithm for this problem, and applies to effective resistance as a special case.Source: §5.2 · pp. 44–45
  • Theorem 43 estimates dissipated power to multiplicative accuracy ε with bounded success probability from an external-current state and a block-encoding of the incidence matrix.Effective resistance follows by choosing the external current as |s⟩−|t⟩, even without an input state-preparation oracle.Source: §5.2 · p. 46
  • In the sparse-access model, Corollary 44 gives dissipated-power and effective-resistance estimation with bounded-error query and gate complexity, improving on Wang’s QLS-based algorithm.The result also improves on Wang’s quantum-walk algorithm in some parameter regimes.Source: §5.2 · pp. 46–47
  • Quantum-data-structure corollaries estimate dissipated power and effective resistance when the incidence matrix, or its factors and weights, are stored in supported data structures.The complexity is expressed using µ(CG) or µ(BG), and the comparison to Wang’s sparse-access algorithms is not direct.Source: §5.2 · p. 47
  • The quantum-data-structure bounds retain an unresolved parameter: the paper notes that µ(BG) may be bounded for some graph structures but leaves this analysis for future work.Source: §5.2 · p. 47
  • For sparse-access graphs, the algorithm is better than Wang’s method in one degree regime and trades worse degree dependence for better wmax and λ dependence in another.The paper reports a speedup when √wmax/λ < d ≪ √wmax/λ, including d = O(polylog(N)).Source: §5.2 · p. 48
  • In the quantum-data-structure model, the algorithm improves on Wang’s linear-system method for sufficiently large degree and beats the adjacency-query result of [IJ16] when λ = Ω(1) and Rs,t ≫ d^2wmax/N.Compared with Wang’s quantum-walk method, improvement occurs only in certain regimes.Source: §5.2 · p. 48

A Technical results about block-encodings

The appendix develops block-encoding products using subnormalized block-encoding amplification, then derives a product construction for matrices A and B with controlled normalization, error, and implementation time.

Block-encoding amplification

Product of preamplified block-matrices

A.1 Error propagation of block-encodings under various operations

This section bounds error propagation in block-encoded matrix multiplication and Hamiltonian simulation, including quadratic accumulation for products of unitary block-encodings and precision guarantees for simulated evolutions.

Multiplication error propagation

  • Multiplying two unitary block-encodings while reusing ancillas adds an error term bounded by the geometric mean of the input errors [GSLW18].This motivates analyzing products through a binary-tree structure to control accumulation.Source: §A.1 · p. 53
  • For K unitary block-encodings, binary-tree multiplication bounds the resulting error so that it grows at most quadratically with K [GSLW18].Source: §A.1 · p. 53

Hamiltonian-simulation error propagation

  • An (α, a, ε/|2t|)-block-encoding of Hamiltonian H yields an ε-precise (1, a + 2, ε)-block-encoding of e^itH using O(|αt| + log(1/ε)) controlled uses and O(a|αt| + a log(1/ε)) two-qubit gates [LC16].The result follows by combining block-Hamiltonian simulation with a Hamiltonian perturbation bound.Source: §A.1 · p. 54
  • The Hamiltonian-simulation complexity can be optimized by replacing log(1/ε) with log(1/ε) log(e+log(1/ε)/|αt|) [GSLW18].Source: §A.1 · p. 54

A.2 Implementing smooth functions of Block-Hamiltonians

The section develops smooth-function implementations for block-encoded Hamiltonians using controlled simulation, then specializes the framework to negative and positive matrix powers under spectral bounds. These constructions provide block-encodings with explicit normalization, precision, condition-number, and gate-complexity guarantees.

Smooth-function implementation

  • Smooth functions of Hamiltonians can be implemented from controlled Hamiltonian simulation via Fourier-series decompositions and the LCU Lemma [BCK15].The framework invokes the general techniques of [AGGW17, Appendix B] and uses a smooth-function theorem to produce a block-encoding of f(H).Source: §A.2 · pp. 54–55

Controlled Hamiltonian simulation

  • A block-encoding of H yields controlled (M, γ)-simulation with O(|αMγ| + J log(J/ε)) controlled-query uses and O(a|αMγ| + aJ log(J/ε)) two-qubit gates.This controlled-simulation primitive is the cost basis for the subsequent smooth-function and power-function constructions.Source: §A.2 · p. 54

Negative powers

  • For I/κ ⪯ H ⪯ I, negative powers H^-c admit a (2κ^c, ..., ε)-block-encoding using controlled simulation with time O(κ max(1, c) log(κc/ε)).The construction applies for κ ≥ 2 and c > 0, with the required block-encoding and ancilla overhead specified by Corollary 54.Source: §A.2 · pp. 55–56

Positive powers

  • For I/κ ⪯ H ⪯ I and c ∈ (0, 1], positive powers H^c admit a (2, ..., ε)-block-encoding using O(κ log(κ/ε) log(1/ε)) two-qubit gates.The construction uses controlled simulation for time O(κ log(1/ε)) and has ancilla overhead O(log log(1/ε)).Source: §A.2 · pp. 56–57

A.3 Variable time quantum algorithm for implementing negative powers of Hermitian matrices

The section presents a variable-time quantum algorithm for implementing negative powers of a Hermitian matrix from a block-encoding and an eigenvector-supported input state. It also provides a procedure for estimating an associated quantity Γ.

A.3 Variable time quantum algorithm for implementing negative powers of Hermitian matrices

  • Theorem 33 gives a variable-time algorithm that produces an ε-close state proportional to H^-c|ψ⟩ for Hermitian H with eigenvalues bounded away from zero.The assumptions include κ ≥ 2, c > 0, a block-encoding of H, and an input state |ψ⟩ spanned by H’s eigenvectors.Source: §A.3 · p. 57
  • The same theorem provides a variable-time algorithm that outputs a number Γ under the stated block-encoding and input-state assumptions.Source: §A.3 · pp. 57–58
  • The proof follows the same argument as Theorem 30, except it sets ε′ = ε/(mαmax) with αmax = O(κc), and gives the final VTAA complexity via Theorem 23.Source: §A.3 · pp. 57–58

Related papers

Loading 1804.01973v2…