Quantum Algorithms Database
Quantum Singular Value Transformation (QSVT)
A unifying framework that encompasses nearly all known quantum speedups by expressing them as polynomial transformations of singular values of a block-encoded matrix.
Year
2018 (arXiv); 2019 (STOC)
Inventor(s)
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe
Speedup Type
Polynomial Speedup
Difficulty
★★★★★
Overview
Quantum singular value transformation, or QSVT, is a framework that expresses a very large number of quantum algorithms as one procedure: take a matrix stored inside a quantum circuit, and apply a chosen polynomial to its singular values. By changing the polynomial, the same circuit structure performs search, phase estimation, Hamiltonian simulation, matrix inversion, and more.
The significance of QSVT is as much conceptual as practical. It gives optimal or near-optimal query complexity for many tasks, and it shows that the sprawling collection of quantum algorithms is built from a small number of ideas. Martyn, Rossi, Tan, and Chuang called it a grand unification of quantum algorithms in 2021.
The problem it solves
Many quantum algorithms (HHL, quantum walk, phase estimation, amplitude amplification) seemed unrelated — QSVT reveals they are all special cases of one unified mathematical structure.
History and background
QSVT grew out of quantum signal processing by Low and Chuang, which applied polynomials to a single rotation angle, and qubitization, which embedded a Hermitian matrix into a unitary walk operator. Gilyén, Su, Low, and Wiebe posted the general framework in 2018 and presented it at STOC in 2019, in a paper whose title promises exponential improvements for quantum matrix arithmetic.
The paper unified earlier results and gave new ones, including improved algorithms for Hamiltonian simulation, linear systems, and quantum machine learning. Chia, Gilyén, Li, Lin, Tang, and Wang showed in 2020 that for low-rank matrices with classical sampling access, a classical analogue of QSVT exists, which dequantized several quantum machine learning speedups. Since then, QSVT has been implemented in software such as pyqsp, and it appears in most modern fault-tolerant resource estimates.
How it works
Block-encodes a matrix A into a larger unitary. Uses alternating projectors and phase shifts to apply a polynomial transformation to the singular values of A. Choosing different polynomials recovers Grover search, phase estimation, Hamiltonian simulation, and more.
Every matrix A has a singular value decomposition, which writes it as a sum of terms, each scaling one input direction by a singular value and mapping it to an output direction. A function of the matrix, such as its inverse or a polynomial, acts on the singular values while leaving the directions unchanged.
QSVT starts with a block encoding: a unitary U on a larger space whose top-left block equals the matrix A, up to a scale factor. Applying U is like applying A, with some probability, to the part of the state in the block. By alternating U and its inverse with simple phase rotations that depend on whether the ancilla qubits are in the zero state, the procedure builds a polynomial of the singular values in the same block.
The phases are chosen by classical computation so that the polynomial matches the function you want. For example, a polynomial approximating 1 over x on the range of singular values gives the pseudoinverse, which solves linear systems. A polynomial approximating the exponential gives time evolution. A polynomial that is close to a step function gives projection onto small singular values, which is used for ground state preparation.
Step by step
- Choose the function f to apply to the singular values, and the interval on which they lie after normalization.
- Find a polynomial P of degree d that approximates f on that interval and satisfies the required parity and boundedness conditions, for example by Chebyshev expansion.
- Compute the d plus 1 phase angles that implement P through the quantum signal processing theory, using a numerically stable classical routine.
- Build a block encoding U of the matrix A, for example from a sparse-access oracle or a linear combination of unitaries.
- Alternate applications of U and its inverse with projector-controlled phase rotations using the computed angles, for a total of d applications.
- Apply the resulting circuit to the input state, and measure the ancilla register to post-select, or use amplitude amplification to boost the success probability.
A worked example
To solve the linear system A x equal to b, apply QSVT with a polynomial of degree about kappa times the logarithm of kappa over epsilon, where kappa is the condition number and epsilon is the target error. The polynomial approximates 1 over x on the interval from 1 over kappa to 1. The resulting circuit applies the pseudoinverse of A to the state b, producing the state of the solution up to normalization.
For Hamiltonian simulation, choose the polynomial that approximates e to the minus i x t with degree proportional to t plus a logarithmic term. The same QSVT circuit then evolves the system for time t using a number of calls to the block encoding that matches the known optimal bound.
Complexity and resources
| Item | Detail |
|---|---|
| Queries | d applications of the block encoding for a polynomial of degree d |
| Matrix inversion | O(kappa log(1 over epsilon)) block-encoding queries, which is optimal in kappa |
| Hamiltonian simulation | O(t plus log(1 over epsilon) over log log(1 over epsilon)), which is optimal |
| Extra qubits | A few ancillas for the block encoding and one qubit for the phase rotations |
| Classical preprocessing | Computing d plus 1 phase angles; stable algorithms exist |
What hardware it needs
- Fault-tolerant hardware, since circuits for useful degrees are deep.
- A block encoding of the matrix, whose construction cost often dominates the algorithm.
- Precise single-qubit z rotations, which are cheap, and multi-controlled phase gates.
Applications
- Hamiltonian simulation for chemistry and materials with optimal scaling.
- Solving linear systems and least squares problems with improved dependence on condition number.
- Amplitude amplification, search, and eigenvalue filtering.
- Preparing ground states and Gibbs states, and quantum machine learning subroutines.
Limitations and caveats
- The speedups depend on the cost of the block encoding and on data access, which can remove the advantage.
- Dequantization shows that classical analogues exist for low-rank problems with sampling access.
- The circuits are deep and need error correction.
- Finding stable phase angles for very high degree polynomials requires careful numerics.
Common misconceptions
- QSVT does not itself give an exponential speedup. Whether a speedup exists depends on the application and the input model.
- It is not limited to Hermitian matrices. It works with singular values of general matrices.
- It does not remove the need for state preparation and readout.
How it compares
- Quantum signal processing applies a polynomial to a single qubit rotation, while QSVT applies it to the singular values of a matrix.
- HHL solves linear systems with worse scaling in condition number and precision than QSVT.
- Trotter-based simulation is simpler but has worse scaling with precision.
Real-world impact
Has provided optimal query complexity algorithms for Hamiltonian simulation, linear systems, and quantum machine learning — and has revealed the fundamental limits of quantum speedups across all these domains.
Why it matters
QSVT is now the standard way to design and analyze fault-tolerant quantum algorithms. It reduces the question of what a quantum computer can do with a matrix to what polynomials can approximate a function, which connects quantum algorithms to approximation theory.
For learners, it also provides a single picture in which many algorithms can be understood, which makes the field easier to navigate than a list of unrelated techniques.
Frequently asked questions
What is quantum singular value transformation?
A framework that applies a polynomial function to the singular values of a matrix block-encoded in a quantum circuit, using alternating applications of the block encoding and phase rotations.
What is a block encoding?
A unitary operation that contains a matrix as one of its sub-blocks, so that applying the unitary acts on the state like the matrix, up to scaling and post-selection.
Which algorithms does QSVT unify?
Grover search, amplitude amplification, phase estimation, Hamiltonian simulation, matrix inversion, and several quantum machine learning routines.
Does QSVT give exponential speedups?
It provides optimal scalings for many tasks, and some tasks, such as simulating quantum systems, have exponential advantage over classical methods. Others have only polynomial advantage.
What are the phase angles?
Classical parameters that determine which polynomial the circuit applies. They are computed once by numerical methods.
Keep learning
- Related algorithm: Quantum Signal Processing (QSP)
- Related algorithm: Linear Combination of Unitaries (LCU)
- Related algorithm: HHL Algorithm
- Related algorithm: Quantum Phase Estimation (QPE)
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.