PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe

arXiv:1806.01838v1quant-phcs.ET

TL;DR

Quantum algorithms often rely on a small set of primitives, motivating a unified view of their apparent diversity. The paper develops singular value transformation for polynomially transforming singular values in projected unitary encodings, and derives applications including non-commutative measurements, singular value estimation, fractional-query simulation, and principal component regression. It also identifies lower bounds that characterize limitations of the method.

  • Problem

    Quantum algorithms based on simulation, quantum walks, linear systems, and related primitives are typically understood separately, leaving open whether they reflect a deeper common concept.

  • Method

    The paper extends qubitization with singular value transformation, implementing bounded polynomial transformations of singular values using projected unitary encodings.

  • Results

    The framework unifies singular value estimation, linear equation solving, quantum simulation, quantum walks, non-commutative measurements, fractional queries, and principal component regression.

  • Takeaways & Limitations

    Singular value transformation provides a common framework from which many prominent quantum algorithms and quantum speed-ups follow as direct consequences.

  • Takeaways & Limitations

    Lower bounds show that singular value transformation has efficiency limitations, including difficulty amplifying spectra close to 1.

Abstract

from arXiv · show

Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new "Singular value transformation" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain "non-commutative" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. "Singular value transformation" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

1 Introduction

The paper introduces singular value transformation as a unifying framework for quantum algorithms based on polynomial transformations of singular values. It develops applications spanning amplification, matrix inversion, measurement, singular value estimation, quantum simulation, and quantum machine learning.

  • Precision and context: Quantum algorithms can achieve exponential improvements in internal precision scaling, but learning state properties to precision ε generally retains polynomial dependence on 1/ε.The paper cites an improvement in quantum semidefinite-program solver scaling from O(1/ϵ^32) to O(1/ϵ^4).
  • Motivation and framework: Singular value transformation generalizes qubitization by applying polynomial transformations to the singular values of an operator encoded as a block of a unitary.The framework is defined for projected unitary encodings and extends qubitization beyond normal operators.
  • Applications: Fixed-point amplitude amplification follows by transforming the success-probability singular value toward one with an appropriately bounded polynomial.The construction gives a conceptually simple and efficient implementation.
  • Applications: The framework directly implements approximations to the Moore-Penrose pseudoinverse and supports principal component regression as a quantum machine learning application.The pseudoinverse is obtained by approximating 1/x on the nonzero singular values.
  • Applications: Singular vector transformation and singular value threshold projectors enable singular value discrimination, non-commutative measurements, and quantum singular value estimation.The threshold procedure distinguishes whether a state has singular value below or above a specified threshold.
  • Applications: The framework incorporates optimal Hamiltonian simulation, robust oblivious amplitude amplification, fast QMA amplification, the fast quantum OR lemma, and certain quantum walk results.It also yields an exponential improvement for fractional queries to unitaries with a gapped spectrum.

2 Preliminaries and notation

This section establishes notation for singular value decompositions, singular value projectors, polynomial parity, matrix blocks, and projector-controlled operations. These definitions support the later construction of singular value transformations.

  • Singular value decomposition: Every matrix A has a singular value decomposition A = WΣV†, with singular values on the diagonal of Σ and corresponding right and left singular vectors in V and W.The singular values are denoted ς_i := Σ_ii.
  • Singular value projectors: Singular value projectors are defined by retaining the singular vectors associated with a selected singular value and projecting onto their corresponding right or left subspaces.The projectors remain uniquely determined even when the singular value decomposition itself is not unique.
  • Polynomial notation: The notation ∥f∥_I′ denotes the supremum of |f(x)| on I′, while even and odd functions satisfy f(−x)=f(x) and f(−x)=−f(x), respectively.Polynomial parity is determined by whether odd or even powers have zero coefficients.
  • Block notation: A dotted block in a matrix denotes arbitrary unspecified entries, while its displayed block is fixed.For example, [.] represents a matrix whose top-left block is A when that block is shown as A.
  • Projector-controlled operations: A Π-controlled NOT coherently flips a qubit according to whether a register lies in the image of the projector Π.For Π = |1⟩⟨1|, this reduces to an ordinary CNOT controlled by the corresponding qubit.

3 Qubitization and Singular value transformations

The paper combines quantum signal processing with qubitization to transform singular values of projected unitary matrices. This provides the common implementation underlying its later applications.

  • Quantum signal processing: Quantum signal processing supplies the phase-modulation techniques used to construct polynomial transformations.The paper presents a self-contained and streamlined treatment with slightly improved versions of earlier results.
  • Singular value transformation: Qubitization ideas are leveraged to perform singular value transformation on projected unitary matrices.The resulting framework is presented as a common generalization from which optimized applications are derived.

3.1 Parametrized SU(2) unitaries induced by Pauli rotations

This section characterizes the polynomial pairs realizable by alternating Pauli-rotation sequences and develops constructive criteria for their implementation. It also simplifies earlier quantum signal processing formalism and proofs.

  • Parametrized SU(2) unitaries: Quantum signal processing builds 2×2 unitaries whose entries are trigonometric polynomials from rotation and phase gates applied to an unknown signal unitary.The achievable unitary is characterized by the polynomial entries generated by the sequence.
  • Polynomial characterization: The construction uses a phase sequence Φ to realize polynomial components with prescribed parity constraints.The sequence representation is characterized through polynomials P and Q satisfying degree, parity, and unitarity conditions.
  • Implementation: The phase sequence can be found constructively with O(arithmetic operations), although some characterizations rely on high-degree polynomial root finding that is harder to execute in practice.The root-finding issue is identified as an implementation drawback rather than a limitation of the characterization itself.
  • Polynomial characterization: The paper gives constructive necessity-and-sufficiency characterizations for when polynomial pairs can arise from the unitary sequence.The proofs use induction and polynomial factorization to construct the phase angles.
  • Improvements over prior formalism: The revised formulation improves conceptual simplicity and generality over the earlier treatment while avoiding the earlier reliance on the Weierstrass substitution.The paper also discusses numerical-stability advantages of the revised proof approach.
  • Polynomial constructions: The characterization can be used to construct Chebyshev polynomials through quantum signal processing.Chebyshev polynomials are defined by T_d(x) = cos(d arccos(x)).

3.2 Singular value transformation by qubitization

This section generalizes qubitization to singular value transformation, applying polynomial transformations to singular values of arbitrary operators represented as projected unitary blocks. The construction uses invariant subspaces and alternating phase sequences, with parity-dependent forms and essentially necessary constraints.

  • Projected unitary encoding: Singular value transformation extends qubitization from Hermitian or normal operators to arbitrary operators represented as projected unitary blocks.The central encoding is A = eΠUΠ, where U is unitary and Π, eΠ are orthogonal projectors.
  • Invariant-subspace construction: Two-dimensional invariant subspaces derived from the singular value decomposition allow alternating applications of U and phase operators to transform singular values polynomially.This lifts quantum signal processing into carefully chosen invariant subspaces.
  • Alternating phase modulation: The alternating phase modulation sequence implements P(SV)(A) for odd polynomials and the corresponding even-polynomial transformation with a parity-dependent projector.The odd case uses eΠUΦΠ, while the even case uses ΠUΦΠ.
  • Relation to prior techniques: The framework generalizes flexible quantum signal processing and certain quantum walk techniques while removing the restriction to Hermitian or normal matrices.The result also removes the even-degree constraint Pℜ(0) = 0 described for earlier work.
  • Optimality conditions: The polynomial must satisfy boundedness and parity conditions, and these requirements are essentially optimal for projected-unitary implementations.The degree also lower-bounds the number of uses of U in cases such as Chebyshev polynomial transformations.

3.3 Robustness of singular value transformation

This section develops robustness bounds for singular value transformation under perturbations of the encoded matrix. The bounds use operator-function continuity and improve under spectral separation from singular value magnitude one.

  • General robustness: Robustness analysis bounds the difference between singular value transformations of two nearby matrices represented by projected unitary encodings.The analysis addresses how perturbations propagate through polynomial or general function transformations.
  • Continuity tools: Direct Lipschitz continuity does not generally transfer from scalar functions to induced Hermitian matrix functions, but operator-function results provide logarithmic-factor bounds.The relevant continuity theorem is attributed to Farforovskaya and Nikolskaya.
  • General robustness: The first robustness result applies a modulus of continuity to even or odd functions acting on matrices with operator norm at most one.This gives a general continuity-based bound for singular value transformation.
  • Improved error dependence: Bootstrapping exact transformations yields error bounds scaling with the square root of the initial perturbation, with linear dependence available when singular values stay away from magnitude one.The improved dependence requires singular values to be bounded away from 1 in absolute value.
  • Tightness: The robustness upper bound is tight up to a constant factor for arbitrarily large degree and arbitrarily small error, although joint degree-error dependence may remain nonoptimal.The Chebyshev-polynomial example establishes the near-tightness claim.

3.4 Singular vector transformation and singular value amplification

This section derives singular vector transformation and uniform singular value amplification from the polynomial framework. It also recovers fixed-point and robust oblivious amplitude amplification results, including optimal scaling with a controlled phase error.

  • Singular vector transformation: Singular vector transformation maps right singular vectors to corresponding left singular vectors above a singular-value threshold.The construction uses an efficiently approximated sign function and a single ancilla qubit.
  • Amplitude amplification: Fixed-point amplitude amplification achieves optimal asymptotic scaling in target overlap and error while making the amplified-state phase error ε-close to zero.This combines the favorable overlap scaling of one prior method with the fast error convergence of another without retaining its unknown phase.
  • Amplitude amplification: Robust oblivious amplitude amplification is obtained as a direct corollary of singular value transformation.The resulting circuit uses one ancilla qubit and repeated applications of U, U†, controlled projector operations, and single-qubit gates.
  • Singular value amplification: Uniform singular value amplification constructs a projected encoding whose singular values are multiplied by γ above a threshold, within multiplicative error ε.The implementation uses polynomial approximations to the rectangle and sign functions.
  • Singular value amplification: The amplification procedure is efficient and can be implemented with a single ancilla qubit using m applications of the relevant unitary, controlled projector gates, and single-qubit gates.The degree m is determined by the polynomial approximation used in the construction.

3.5 Singular value discrimination, quantum walks and the fast OR lemma

Singular value discrimination uses polynomial transformations to distinguish separated singular-value regimes, yielding quadratic quantum-walk speedups and fast amplification and OR procedures.

  • Singular value discrimination: Singular value threshold projectors implement approximate projections onto singular values below or above a threshold using a single ancilla qubit and repeated oracle uses.The construction uses polynomial approximation and singular value transformation; its cost is determined by the polynomial degree.
  • Singular value discrimination: When the threshold is close to 1, complementary singular-value projections can improve the scaling with the gap quadratically.The complementary construction replaces eΠUΠ by (I−eΠ)UΠ.
  • Singular value discrimination: Singular value discrimination distinguishes singular values at most a from those at least b with error probability at most ε.The error can be made one-sided when a = 0 or b = 1.
  • Quantum walks: Singular value transformation detects marked elements in reversible Markov chains quadratically faster than the corresponding classical hitting-time bound.The framework distinguishes hitting time at most K from the absence of marked elements and also supports finding marked elements under a singular-value-gap promise.
  • Amplification and OR: The framework directly derives fast QMA amplification and a fast quantum OR lemma with controlled acceptance and rejection probabilities.The QMA construction targets acceptance probabilities 1−ε and ε; the OR construction gives separate bounds for its two cases.

3.6 “Non-commutative measurements” and singular value estimation

Singular value transformation efficiently realizes a coherence-preserving non-commutative measurement and provides a singular value estimation procedure based on controlled walk steps and Fourier analysis.

  • Non-commutative measurements: The non-commutative measurement problem distinguishes states in ker(Πc) from right singular vectors of ΠcΠF and rotates the latter into corresponding left singular vectors.The desired channel must preserve coherence between singular vectors with different singular values.
  • Non-commutative measurements: Singular value transformation implements the exact quantum channel with maximal failure probability ε using controlled projector operations.The construction sets A := ΠcΠF and applies the singular value transformation theorem.
  • Non-commutative measurements: The implementation improves ε dependence exponentially and ς dependence quadratically while solving the stronger coherence-preserving problem.These improvements also reduce the final complexity of the associated ground-state preparation algorithm.
  • Singular value estimation: The framework addresses an ambiguity in phase labels from earlier singular value estimation procedures by combining singular value transformation with quantum-walk ideas.The cited approach targets singular vector projectors with complexity similar to the threshold-projector construction.
  • Singular value estimation: Singular value estimation uses controlled quantum-walk steps, Fourier transformation of a time register, and half the resulting absolute value as the estimate.The analysis uses quantum phase estimation and the identity cos(x) = (e^ix+e^−ix)/2.

3.7 Direct implementation of the Moore-Penrose pseudoinverse

The paper implements the Moore-Penrose pseudoinverse by approximating inverse singular-value transformations with bounded odd polynomials, while explicitly handling zero and small singular values.

  • Pseudoinverse construction: The Moore-Penrose pseudoinverse maps each nonzero singular value to its inverse while leaving zero singular values unchanged.For A = WΣV†, the pseudoinverse is A+ = VΣ+W†.
  • Pseudoinverse construction: Singular value transformation implements the pseudoinverse when all nonzero singular values are at least δ using an odd polynomial approximating δ/(2x).The polynomial is bounded by 1 on [−1,1], enabling its use in the transformation framework.
  • Pseudoinverse construction: The construction explicitly includes projectors onto zero and above-threshold singular-value subspaces.The theorem defines Π0,≥δ and eΠ0,≥δ for the right and left singular spaces.
  • Polynomial approximation: The required polynomial degree scales as O(log(1/ε)/δ) for the inverse approximation.The construction combines an inverse-approximating odd polynomial with a rectangle-function approximation before applying singular value transformation.
  • Limitations: The assumption ε ≤ δ is natural but can be removed using more general polynomial approximation results.This is stated as a scope qualification on the preceding pseudoinverse result.

3.8 Applications in quantum machine learning

Singular value transformation supports quantum machine learning procedures, including principal component regression, by combining threshold projections, pseudoinverses, and matrix products.

  • Broader applications: Many quantum machine learning methods reduce to implementing the Moore-Penrose pseudoinverse and matrix multiplication within the singular value transformation framework.The paper identifies ordinary, weighted, and generalized least-squares procedures as examples.
  • Principal component regression: The paper develops a quantum algorithm for principal component regression using singular value transformation.Principal component regression reconstructs a target vector using the subspace associated with large singular values.
  • Principal component regression: Principal component regression solves a least-squares problem restricted to singular vectors above a threshold ς.Its closed-form solution is x = Π≥ςA+eΠ≥ςb = A+eΠ≥ςb.
  • Principal component regression: The framework efficiently implements the threshold pseudoinverse Π≥ςA+eΠ≥ς needed for principal component regression.This combines singular-value thresholding with pseudoinverse transformation.
  • Assumptions and improvements: The regression procedure requires a promise concerning overlap with singular vectors near the threshold, although the paper suggests this promise may not be crucial in typical applications.Variable-time amplitude amplification can provide an essentially quadratic runtime improvement.

4 Matrix Arithmetics using blocks of unitaries

The paper develops an operational framework for quantum matrix arithmetic by representing matrices as blocks of unitary operators. It provides reusable constructions for encoding matrices and for composing encodings through basic linear-algebra operations.

  • Framework: The methodology represents matrices as unitary blocks, allowing matrix calculations on quantum states and potentially exponential speed-ups in matrix dimension.It distills techniques from several quantum-algorithmic works into an operational matrix-arithmetic framework.
  • Matrix arithmetic: The framework supports matrix addition, subtraction, multiplication, and error-propagation bounds for inaccurate encodings.These operations are presented to make the resulting techniques reusable across applications.
  • Block-encodings: Block-encoding represents a subnormalized matrix as the upper-left block of a larger unitary.The definition includes a normalization factor, ancilla count, and approximation error.
  • Encoding constructions: Block-encoded matrices can be embedded faithfully when rectangular matrices are padded into larger square matrices.Addition and multiplication of the embedded matrices correspond to the corresponding operations on the original matrices.
  • Connection to singular value transformation: Block-encoding is a special case of projected unitary encoding, enabling later application of singular value transformation results.For block-encodings, the controlled projector operation can be implemented using a Toffoli gate with one additional ancilla qubit.
  • Encoding constructions: Block-encodings can be constructed for unitary matrices, density operators, POVM operators, sparse-access matrices, and matrices stored in quantum data structures.The toolbox includes constructions based on state preparation, sparse-access oracles, purification, and quantum data structures.

5 Implementing smooth functions of Hermitian matrices

The paper uses singular value transformation to implement smooth functions of Hermitian matrices through polynomial approximations. This yields general matrix-function procedures, optimal block-Hamiltonian simulation, and applications including fractional queries and Gibbs-state preparation.

  • Polynomial matrix functions: Singular value transformation implements smooth functions of Hermitian matrices more efficiently than assembling them from basic matrix-arithmetic operations.For Hermitian A, the singular-value transformation coincides with polynomial transformation of A.
  • Polynomial matrix functions: A parity-general polynomial eigenvalue transformation removes a parity constraint at the cost of a subnormalization factor 1/2.The resulting circuit uses d applications of the encoding and its inverse, one controlled application, and O((a + 1)d) additional one- and two-qubit gates.
  • Hamiltonian simulation: The corrected simulation complexity differs from an earlier claimed formula for some values of t because of a subtle issue in the earlier calculation.The paper modifies the log(log(1/ε)) term and covers the range t ≪ 1.
  • Hamiltonian simulation: 3r(|t|, ε) uses of the block-encoding suffice for ε-precise block-Hamiltonian simulation, with three controlled uses and O(1) ancilla qubits.The complexity is governed by the polynomial-approximation quantity r(t, ε).
  • Applications: Fractional queries to unitaries can be implemented with exponentially improved error dependence compared with the result of Sheridan et al. for δ = Θ(1).The paper also notes that the δ dependence is optimal because Sheridan et al. proved a lower bound.
  • Applications: Singular value transformation provides compact implementations of Gibbs-state preparation steps, including applying e^−β(H+I)/2 and using fixed-point amplitude amplification.When the minimum eigenvalue is not close to −1, shifting by λmin avoids unnecessary subnormalization but generally introduces linear dependence on β.

6 Limitations of the smooth function techniques

The paper develops lower bounds for eigenvalue and singular value transformations, linking approximation-polynomial degree to the number of block-encoding uses. These bounds show that transformations near spectral value 1 are more flexible and often establish optimality.

  • Context: Polynomial-approximation degree provides a route to quantum query lower bounds, although lower-bound results for continuous problems remain comparatively sparse.The paper positions its result as a conceptually simple contribution to the continuous regime.
  • Lower-bound intuition: Continuous lower bounds for eigenvalue transformations relate the required block-encoding uses to the function's maximal derivative.The paper states that a function with derivative d requires Ω(d) uses of the block-encoding, with δ typically proportional to 1/d.
  • Lower-bound theorem: Theorem 73 lower-bounds the query cost of implementing f(H) from a block-encoding of an unknown Hermitian matrix whose spectrum lies in a promised interval.The bound applies uniformly to all block-encodings satisfying the spectral promise.
  • Proof strategy: The proof analyzes a d×d Hermitian matrix with a=1 and a 2d×2d block-encoding before extending the argument to larger ancilla dimensions.For a>1, additional identity tensor factors accommodate the new ancilla qubits.
  • Spectral limitation: The lower bound indicates that spectrum near 1 is quadratically more useful than spectrum contained in [−1/2, 1/2].It also explains why amplifying spectrum close to 1 is difficult, and applies to singular value transformation because eigenvalue transformation is a special case.

7 Conclusion

The conclusion presents quantum singular value transformation as a unifying paradigm for quantum algorithms and matrix arithmetic. It also identifies an open problem: integrating this framework with controlled quantum amplification for quantum walks.

  • Conclusion: Quantum singular value transformation unifies singular value estimation, linear equation solving, quantum simulation, and quantum walks within one algorithmic paradigm.The framework simplifies learning these techniques and reveals previously unknown algorithms.
  • Conclusion: The paper's main result is an efficient singular value transformation method extending earlier qubitization techniques.Applications include certain non-commutative measurements, exponentially improved fractional-query simulation, and improved principal component regression.
  • Conclusion: Block-encoded matrices enable simple and efficient quantum matrix arithmetic, with potential exponential savings in matrix dimension.This matrix-arithmetic perspective fits directly into the singular value transformation framework.
  • Future work: Unifying controlled quantum amplification with the presented techniques remains an open question.The related quantum-walk circuits resemble qubitization, but the paper states that placing the approach within its framework is difficult.
Loading 1806.01838v1…