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

The paper addresses how to apply quantum linear-algebra and machine-learning algorithms across sparse-access, quantum-data-structure, and block-encoding input models. It develops block-encoding tools and variable-time amplitude estimation, yielding improved Hamiltonian simulation and quantum solvers for weighted and generalized least squares, alongside electrical-network estimation algorithms. The main reported applications include a 6-th power improvement in weighted least-squares condition-number dependence, the first quantum generalized least-squares solver, and speedups for electrical-network quantities in supported regimes.

  • Problem

    Quantum linear-algebra algorithms depend strongly on how matrices are represented, motivating techniques that work across sparse-access and quantum-data-structure input models.

  • Method

    The paper develops block-encoding tools, quantum linear-system methods, and variable-time amplitude estimation applicable to block-encoded inputs.

  • Results

    Applications include a weighted least-squares solver improving condition-number dependence from κ^6 to κ, the first quantum generalized least-squares solver, and electrical-network estimation algorithms with speedups in certain regimes.

  • Takeaways & Limitations

    Block-encoding results transfer to sparse-access and quantum-data-structure models, supporting improved quantum algorithms for linear algebra and electrical-network quantities.

  • Takeaways & Limitations

    The singular-value-estimation definition allows an entangled auxiliary or garbage state, which can be undesirable in some scenarios.

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 block-encoding and variable-time amplitude-estimation techniques that apply across sparse-access and quantum-data-structure input models. These tools support improved quantum linear-algebra algorithms, including weighted and generalized least squares, Hamiltonian simulation, and electrical-network estimation.

  • Input models: Sparse-access and quantum-data-structure inputs can be converted into block-encodings, extending block-encoding results to both models.This provides the common input framework underlying the paper’s applications.
  • Techniques: Variable-time amplitude estimation multiplicatively estimates a quantum algorithm’s success probability by separately estimating amplification in each phase and combining the estimates.The technique addresses the difficulty that variable-time amplification uses phases with a priori unknown amplification amounts.
  • Applications: The weighted least-squares solver improves condition-number dependence from κ^6 to κ and precision dependence from 1/ε to polylog(1/ε).The solver works in both the quantum-data-structure and sparse-access input models.
  • Applications: The paper gives the first quantum generalized least-squares solver, with complexity polynomial in log(1/ε) and the input matrices’ condition numbers.The solver is obtained first for block-encoded inputs and then specialized to the quantum-data-structure model.
  • Applications: Electrical-network algorithms estimate effective resistance and dissipated power, improving Wang’s sparse-access results for certain parameters and giving speedups in quantum-data-structure regimes.In the quantum-data-structure model, a speedup occurs when the network’s maximum degree is Ω(n^1/3).
  • Techniques: Hamiltonian simulation from a quantum data structure implements e^{itA} for Hermitian A with complexity eO(tµ(A)polylog(N/ε)).The result follows by combining quantum data structures, block-encodings, and Low–Chuang Hamiltonian simulation.
  • Techniques: Quantum singular value estimation is generalized to block-encoded matrices, recovering the Kerenidis–Prakash result when the block-encoding comes from a quantum data structure.The block-encoding formulation broadens the input representation for singular-value estimation.
  • Techniques: The block-encoding framework also reduces block-encoded quantum linear-system solvers’ condition-number dependence from quadratic to linear using variable-time amplification.The resulting solver can be applied to block-encoded matrices and supports quantum-data-structure implementations.

2 Preliminaries

The preliminaries define quantum-accessible data structures and block-encodings as representations supporting efficient quantum operations on matrices and vectors. They establish basic composition rules and explain how sparse-access oracles and data structures yield block-encodings.

  • Quantum-accessible data structures: Quantum-accessible data structures store matrix entries in binary trees, enabling polylogarithmic-time quantum access after initialization.The structure uses row-wise trees and controlled rotations to implement relevant unitaries approximately.
  • Quantum state preparation: The data structure also supports preparation of normalized vector states and alternative quantum representations of matrix rows.These operations rely on storing squared magnitudes and signs in binary trees.
  • Block-encodings: A block-encoding represents A as the top-left block of a larger unitary, up to normalization and approximation error.This representation is the framework used to implement matrix functions and related quantum algorithms.
  • Block-encoding operations: Products of block-encoded matrices produce a block-encoding of the product, with normalization factors multiplied and errors combined additively.Zero-padding handles matrices whose dimensions are not powers of two.
  • Input models: Sparse-access matrix oracles can also be converted efficiently into block-encodings.For nonsymmetric matrices, analogous column oracles are assumed as well.

3 Variable-time amplitude amplification and estimation

This section formalizes variable-stopping-time quantum algorithms and develops variable-time amplitude amplification and estimation. The framework tracks branches that stop at different costs and exploits their stopping-time distribution in complexity bounds.

  • Amplitude estimation: Variable-time amplitude estimation seeks an ε-multiplicative estimate of a variable-stopping-time algorithm’s initial success probability.This extends variable-time amplification, which exploits branches that terminate early after being marked bad.
  • Variable-stopping-time algorithms: Variable-stopping-time algorithms proceed through stages with increasing costs, while branches are marked good, bad, or left neutral at different stopping times.Later stages act only on branches whose flags remain unset.
  • Complexity analysis: The analysis defines stopping-time projectors and probability distributions to quantify the good, bad, and unresolved portions of the evolving state.The stopping-time random variable and its generalized inverse express complexity in distributional terms.
  • Complexity bounds: Uniformly bounded variable-time amplifications admit query and gate complexity bounds depending on amplification, overhead, and stopping-time parameters.The framework recovers and improves a bound associated with Ambainis.
  • Complexity bounds: The stopping-time distribution can be compressed to at most 1 + log(Tmax/t1) distinct times with only a constant-factor increase in the relevant bound.This reduces the number of stages needed for analysis and implementation.
  • Amplification phases: Ordinary amplitude amplification is applied phase by phase, with its efficiency analyzed through the success amplitude and the number of amplification steps.The analysis also notes that a logarithmic Tmax factor may be unavoidable for some stopping-time distributions.

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

The section constructs efficient variable-time amplification and estimation procedures by combining state preparation, amplitude estimation, phase-wise amplification, and sparsified stopping times. The resulting analysis provides final query and gate complexity bounds for the variable-time framework.

  • Complexity: The resulting query and gate complexity follows from the uniformly bounded amplification corollary and the cost of constructing the amplified algorithm.The construction itself may require additional logarithmic overhead relative to using the resulting amplification algorithm.
  • Main theorem: Theorem 23 gives efficient variable-time amplification and estimation under a state-preparation unitary, a variable-stopping-time algorithm, and known lower bounds on preparation success.The theorem assumes a state-preparation query cost and lower bounds on pprep.
  • Complexity: A more careful analysis can reduce the Tmax√m term to Tmax while using m = O(log(2Tmax/t1)) stopping-time stages.This refinement improves the dependence on the number of stages.
  • Construction: The construction first prepares a constant-amplitude useful component, then estimates and amplifies phase-specific amplitudes to build a variable-time amplification algorithm.Stopping times are sparsified before the inductive amplification construction.
  • Construction: The construction estimates the maybe-good amplitude at each stage and applies a chosen number of amplification steps so the phase requirements are satisfied.The overall success probability is bounded using the number of sparsified stages and repeated estimates.

4 Linear system solving using blocks of unitaries

This section applies block-encoding and variable-time techniques to matrix application, inversion, Hamiltonian simulation, singular value estimation, and quantum linear systems. The applications extend to quantum data structures and yield improved precision and condition-number dependences in several settings.

  • Matrix application and inversion: A block-encoding can be applied to a quantum state using amplitude amplification, producing a state proportional to A|b⟩.The cost depends on state preparation, block-encoding implementation, normalization, and target precision.
  • Matrix application and inversion: Block-encoding techniques implement negative powers such as A^-1 and can therefore support quantum linear system solving.Variable-time amplitude amplification improves the direct inversion approach.
  • Singular value estimation: The framework provides block-encoding singular value estimation and recovers the Kerenidis–Prakash running time when the matrix is given through their quantum data structure.The estimation procedure permits an auxiliary garbage state in its relaxed definition.
  • Quantum linear systems: The direct block-encoding inversion method has quadratic condition-number dependence, while variable-time techniques reduce the dependence to linear and improve precision dependence exponentially in the stated setting.The comparison is made against sparse-access quantum linear system methods and is summarized as an application of Theorem 30.
  • Quantum linear systems: Variable-time quantum linear system algorithms prepare states proportional to H^-1|ψ⟩ and support pseudoinverse state preparation and amplitude estimation.The results assume spectral bounds excluding eigenvalues between -1/κ and 1/κ around zero.

5 Applications

The paper applies its block-encoding QLS framework to least-squares problems and electrical-network estimation across quantum data-structure and sparse-access models. These applications improve weighted least squares, introduce generalized least squares, and improve electrical-network algorithms in supported regimes.

  • Applications: The applications use the QLS solver for weighted and generalized least squares, plus effective-resistance and dissipated-power estimation.The algorithms are developed for block-encoding inputs and extended to quantum data structures and sparse-access models.
  • Weighted least squares: A 6th-power improvement in κA and an exponential improvement in ε are obtained for the quantum weighted least-squares solver.The solver is available with quantum data-structure or sparse-access input, with corresponding input-dependent complexity parameters.
  • Generalized least squares: The quantum generalized least-squares solver is formulated for block-encodings and extended to quantum data structures and sparse oracles.Its complexity depends on the condition numbers κΩ and κX and on input-dependent quantities µΩ and µX, or their respective sparsities.
  • Electrical-network quantities: The electrical-network algorithms estimate dissipated power with multiplicative accuracy ε and include effective resistance as a special case.The block-encoding approach replaces Wang’s QLS solver with the paper’s block-encoding QLS solver and uses variable-time amplitude estimation.
  • Electrical-network quantities: The sparse-access electrical-network algorithm outperforms Wang’s linear-system-based algorithm, while the quantum-data-structure version provides an algorithm for that input model.The sparse-access method also improves on Wang’s quantum-walk method in some parameter regimes.
  • Electrical-network quantities: In the quantum data-structure model, the electrical-network complexity is better than Wang’s linear-system algorithm when d ≫ 3√Nλ/wmax.Comparison with Wang’s quantum-walk algorithm yields an improvement only in certain regimes; comparison with adjacency-query work is also parameter-dependent.

A Technical results about block-encodings

The technical framework treats block-encodings as composable algorithmic objects. It gives procedures for combining block-encodings, including matrix products, with controlled normalization and error parameters.

  • Block-encoding products: A subnormalized block-encoding can be amplified before multiplication to improve the construction’s complexity.The amplification incurs cost O(α(TU + a) log(1/γ)) for an input scaling factor α.
  • Block-encoding products: Block-encodings of A and B can be combined to produce a block-encoding of AB.The preamplified product construction has scaling factor 2 and implementation time O((α(TU + a) + β(TV + b)) log(1/γ)).
  • Block-encoding products: The product construction combines amplified block-encodings while tracking the input errors and an additional precision parameter γ.The resulting error is bounded by 2(δ + ε + γ).

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

This section analyzes how block-encoding errors propagate through multiplication and Hamiltonian simulation. It bounds accumulation under repeated products and states the resulting simulation complexity.

  • Error propagation: Multiplying block-encoded unitaries adds the two input errors and an extra term proportional to their geometric mean.For unit scaling, the product error is bounded by δ + ε + 2√(δε).
  • Error propagation: For K block-encoded unitaries, binary-tree analysis limits error growth to at most quadratic in the number of factors.This avoids the potentially super-linear accumulation suggested by repeatedly applying the two-factor bound.
  • Hamiltonian simulation: The simulation theorem’s precision analysis relies on bounding error accumulation between nearby Hermitian operators.The appendix notes a refined logarithmic precision factor for the optimal result.
  • Hamiltonian simulation: An ε-precise simulation of e^itH can be implemented from an (α, a, ε/|2t|)-block-encoding of H.The construction uses O(|αt| + log(1/ε)) controlled block-encoding queries and O(a|αt| + a log(1/ε)) two-qubit gates.

A.2 Implementing smooth functions of Block-Hamiltonians

The appendix constructs smooth functions and power functions of block-encoded Hermitian matrices using controlled Hamiltonian simulation. Negative and positive powers are obtained with precision- and condition-number-dependent costs.

  • Smooth functions: Smooth functions of a Hamiltonian are implemented from a power-series expansion and controlled Hamiltonian simulation.The resulting unitary is a block-encoding of f(H), with complexity determined by the coefficient expansion, spectral interval, and target precision.
  • Controlled simulation: Controlled Hamiltonian simulation is built from a block-encoding of H using a sequence of controlled simulations indexed by a signed bitstring.The construction uses O(|αMγ| + J log(J/ε)) controlled block-encoding queries and corresponding two-qubit gates.
  • Power functions: The power-function constructions derive their precision dependence by expanding f(1+x) over an interval determined by κ.Negative powers use f(y)=y^-c, while positive powers use f(y)=y^c.
  • Power functions: For I/κ ⪯ H ⪯ I, a block-encoding of H can be transformed into a block-encoding of H^-c for c > 0.The negative-power construction has scaling factor 2κ^c and uses controlled simulation with time O(κ max(1,c) log(κ^c/ε)).
  • Power functions: For c ∈ (0,1], the same framework constructs a block-encoding of H^c under the same spectral bounds.The stated construction uses O(κ log(κ/ε) log(1/ε)) two-qubit gates and has ancilla overhead O(log log(1/ε)).

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

Theorem 33 gives 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 an algorithm for outputting a number Γ and analyzes its success probability and final VTAA complexity.

  • Theorem statement: Theorem 33 assumes a Hermitian matrix H with eigenvalues in a specified condition-number-dependent range and a block-encoding implementable with T_U elementary gates.The theorem also assumes κ ≥ 2 and introduces parameters c and q = max(1, c).
  • Theorem statement: The variable-time algorithm outputs a state ε-close to the normalized negative power H^−c|ψ⟩, given an input state spanned by H's eigenvectors.The input state can be prepared in time T_ψ.
  • Theorem statement: A second variable-time quantum algorithm outputs a number Γ associated with the negative-power procedure.The supplied passage introduces Γ but does not include the displayed expression defining it.
  • Proof: The proof follows the argument of Theorem 30 while choosing ε′ = ε/(mα_max), with α_max = O(κ^c).This parameter choice controls the approximation analysis for the negative-power implementation.
  • Proof: The proof derives bounds on the success probability, including a term-by-term comparison for c ∈ [0, 1], before applying variable-time amplitude amplification.The final complexity is obtained from Theorem 23, with constants neglected.
Loading 1804.01973v2…