Quantum singular value transformation explained

Short answer: Quantum singular value transformation (QSVT) is a technique, introduced by Gilyen, Su, Low and Wiebe at ACM STOC 2019, that applies a polynomial transformation to the singular values of a linear operator embedded in a unitary matrix. A 2021 tutorial in PRX Quantum argues that it is a single framework comprising quantum search, quantum phase estimation and Hamiltonian simulation, and calls this a grand unification of quantum algorithms. It is a theoretical framework for designing algorithms.

Where QSVT comes from

The 2019 paper "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics" starts from the observation that an n-qubit quantum circuit performs a unitary operation on an exponentially large Hilbert space, of dimension 2 to the power n, which it calls a major source of quantum speed-ups. The authors develop a QSVT algorithm that directly harnesses that exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator.

They say the transformations are realized by quantum circuits with a very simple structure, typically using only a constant number of ancilla qubits, leading to optimal algorithms with appealing constant factors.

What it unifies

The 2019 paper says its framework allows describing many quantum algorithms at a high level, and enables remarkably concise proofs for many prominent quantum algorithms, from optimal Hamiltonian simulation to various quantum machine learning applications. The 2021 tutorial says the 2019 paper encompasses many algorithms, including amplitude amplification, methods for the quantum linear systems problem, and quantum simulation.

The tutorial says the strongest arguments for quantum speed-ups are borne by algorithms for quantum search, quantum phase estimation and Hamiltonian simulation, which appear as subroutines for large families of composite quantum algorithms. It says problems such as factoring large numbers, searching unstructured databases and simulating quantum systems appear at face value to share little structure, and shows how these three central algorithms may be unified as instances of QSVT.

How the tutorial builds it

The tutorial first illustrates how quantum signal processing may be generalized to the quantum eigenvalue transform, from which QSVT naturally emerges. Following the 2019 paper, it then uses QSVT to construct intuitive quantum algorithms for search, phase estimation and Hamiltonian simulation. It also showcases algorithms for the eigenvalue threshold problem and matrix inversion. The authors conclude that QSVT is a single framework comprising the three major quantum algorithms, suggesting a grand unification of quantum algorithms. That phrase is the authors' own.

More results from the original paper

The 2019 abstract lists several further results: a new singular vector transformation algorithm, a way to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and an efficient implementation of principal component regression. It also proves a quantum lower bound on spectral transformations. These are theoretical complexity results. This article does not claim that any of them has been run on hardware.

What this does not tell you

This article summarises two abstracts and the opening of one tutorial. It does not explain the mathematics of polynomial transformations or quantum signal processing, and it makes no claim about practical speed-ups. The framework is a way to describe and prove results about algorithms. Whether a given algorithm helps on a real task depends on the input assumptions that the individual papers state, such as how data is loaded.

FAQ

What does QSVT do?

It applies a polynomial transformation to the singular values of a linear operator embedded in a unitary matrix, according to both papers.

Who introduced it?

Gilyen, Su, Low and Wiebe, in a paper at ACM STOC 2019, often cited as GSLW 19.

Why is it called a grand unification?

A 2021 PRX Quantum tutorial says it is a single framework comprising quantum search, quantum phase estimation and Hamiltonian simulation.

Does it need many ancilla qubits?

The 2019 paper says the circuits typically use only a constant number of ancilla qubits.

Is it a hardware result?

No. Both sources are theoretical work on algorithm design and proofs.