119
Part Three · B · Algorithms

Quantum signal processing and QSVT

Grover’s search, Hamiltonian simulation, matrix inversion and phase estimation were discovered separately, over twenty years. In 2019 András Gilyén, Yuan Su, Guang Hao Low and Nathan Wiebe showed they are all one algorithm with different settings: choose a polynomial, and a sequence of simple phase rotations applies that polynomial to the singular values of a matrix. The framework, the quantum singular value transformation, has become the common language of quantum algorithms.

On the plate: a sequence of phase angles and the polynomial it produces.

Quantum signal processing

Take a single-qubit “signal” rotation that encodes a number x∈[−1,1]x\in[-1, 1]:

W(x)=(xi1−x2i1−x2x)W(x) = \begin{pmatrix}x & i\sqrt{1-x^2}\\ i\sqrt{1-x^2} & x\end{pmatrix}

Interleave it with phase rotations eiϕkZe^{i\phi_kZ}: eiϕ0Z∏k=1dW(x)eiϕkZe^{i\phi_0Z}\prod_{k=1}^dW(x)e^{i\phi_kZ}. The top-left entry is a polynomial P(x)P(x) of degree dd. Low and Chuang proved in 2016–17 that, with appropriate phases, PP can be essentially any polynomial of definite parity with ∣P∣≤1|P| \le 1 on [−1,1][-1, 1]. All phases zero give the Chebyshev polynomial Td(x)=cos⁡(darccos⁡x)T_d(x) = \cos(d\arccos x). Established

Shape a polynomial

Choose the degree d=d = 3 and a phase pattern: , , , or set a common phase 0.00 added to the middle phases. The plate computes the 2 × 2 product exactly and plots Re P(x)\mathrm{Re}\,P(x) and ∣P(x)∣2|P(x)|^2. Finding phases for a target polynomial, such as a step function for search or 1/x1/x for inversion, is a classical preprocessing problem with efficient, stable algorithms.

Block encodings and QSVT

To act on a matrix AA rather than a number, embed it in the top-left block of a larger unitary, a block encoding, U=(A/α⋅⋅⋅)U = \begin{pmatrix}A/\alpha & \cdot\\ \cdot & \cdot\end{pmatrix}, built for instance by linear combinations of unitaries (Chapter 118). Alternating UU, U†U^\dagger and phase rotations on the ancilla then applies PP to every singular value of A/αA/\alpha at once. That is the QSVT. Its special cases: PP close to a step function gives search and amplitude amplification; P(x)≈e−ixtP(x) \approx e^{-ixt} gives Hamiltonian simulation with optimal cost; P(x)≈1/xP(x) \approx 1/x on the relevant range gives matrix inversion (Chapter 120); and phase estimation can be phrased the same way. John Martyn and colleagues called it a “grand unification” in 2021.

What you now have

Quantum signal processing and the polynomials it produces, Chebyshev polynomials from zero phases, block encodings, the quantum singular value transformation, and how search, simulation and inversion are special cases.

· · ·

Three questions to carry with you.

What does QSP with all phases zero produce?tap
The Chebyshev polynomial T_d(x) = cos(d arccos x).
What is a block encoding?tap
A unitary whose top-left block is the matrix of interest, scaled to norm at most 1.
Which polynomial gives matrix inversion?tap
An approximation to 1/x on the range of singular values.

And one to work out. With all phases zero and d=3d = 3, P(x)=T3(x)=4x3−3xP(x) = T_3(x) = 4x^3 - 3x. What is P(0.5)P(0.5)?

P(0.5) =

Sources: G. H. Low and I. L. Chuang, Phys. Rev. Lett. 118, 010501 (2017). A. Gilyén, Y. Su, G. H. Low and N. Wiebe, Proc. 51st ACM STOC, 193 (2019). J. M. Martyn, Z. M. Rossi, A. K. Tan and I. L. Chuang, PRX Quantum 2, 040203 (2021). L. Lin, arXiv:2201.08309. Checked by code: QSP with zero phases equals T_d(x) to 10⁻¹⁶ for d = 1, 2, 3, 5; the plate computes the full 2 × 2 product.

Next · Chapter 120
HHL and quantum linear algebra, with input/output caveats

An exponential speedup for linear equations, with five asterisks.

Turn the page