Grover search, Hamiltonian simulation, phase estimation and matrix inversion look like unrelated tricks. Quantum signal processing reveals them as one idea: interleave a block encoding with single-qubit phase rotations, and you apply a polynomial of your choice to its singular values. Choosing the polynomial is designing the algorithm.
What you’ll learn
State the QSP theorem (degree, parity and modulus conditions) and derive Chebyshev polynomials from the zero-phase sequence.
Explain qubitization: why a block encoding splits into two-dimensional rotations, one per singular value, and why the walk operator encodes Tk(H/α).
State the QSVT theorem and implement projector-controlled phases with one ancilla.
Derive optimal O(αt+log(1/ε)/loglog(1/ε)) Hamiltonian simulation from the Jacobi–Anger expansion.
Translate search, simulation, linear systems and eigenstate filtering into polynomial approximation problems.
Quantum signal processing
Start with one qubit. A signalx∈[−1,1] is encoded in an X-rotation, and we may interleave Z-rotations with phases of our choice:
Chebyshev polynomials of the first and second kind. Degree and parity match the theorem, and Td2+(1−x2)Ud−12=1 is just cos2+sin2=1.
Necessity in general is an induction: each factor W(x)eiφZ raises the degree by one and flips the parity, preserving unitarity. Sufficiency is proved by peeling layers: given an admissible (P,Q) of degree d, condition (iii) lets one choose φ so that multiplying by (W(x)eiφZ)−1 leaves an admissible pair of degree d−1.
Check your understanding
A QSP sequence uses the signal W(x) exactly four times. Which function can be ⟨0∣UΦ(x)∣0⟩?
4x3−3x
x5
8x4−8x2+1
2x2
Show the answer
C.8x4−8x2+1
With d=4, P must be even, of degree at most 4, and bounded by 1 on [−1,1]. 8x4−8x2+1=T4(x) qualifies; it is produced with all phases zero.
From one qubit to matrices: qubitization and QSVT
Now let U be a unitary and Π, Π~ projectors with Π~UΠ=A, a block encoding with singular value decomposition A=∑kσk∣wk⟩⟨vk∣. (For a standard block encoding, Π=Π~=∣0a⟩⟨0a∣⊗I and A is the encoded matrix divided by α.)
DerivationA projector-controlled phase costs one ancilla
CΠNOT:=X⊗Π+I⊗(I−Π)
Flip an extra qubit exactly on the range of Π. For Π=∣0a⟩⟨0a∣⊗I this is a multi-controlled NOT with negated controls.
CΠNOT(e−iφZ⊗I)CΠNOT(∣0⟩⊗∣ξ⟩)=∣0⟩⊗eiφ(2Π−I)∣ξ⟩
On the range of Π the extra qubit is ∣1⟩ during the rotation and picks up e+iφ; elsewhere it stays ∣0⟩ and picks up e−iφ.
Optimal Hamiltonian simulation
We want e−iHt=e−iτ(H/α) with τ=αt, i.e. the function x↦e−iτx applied to the eigenvalues of H/α∈[−1,1]. The Chebyshev expansion of this function is classical:
e−iτx=J0(τ)+2k=1∑∞(−i)kJk(τ)Tk(x),x∈[−1,1]
The Jacobi–Anger expansion; Jk are Bessel functions. Since ∣Tk∣≤1, truncating at degree d costs at most 2∑k>d∣Jk(τ)∣, and ∣Jk(τ)∣≤(τ/2)k/k! decays super-exponentially once k exceeds a constant times τ.
Truncate, and rescale slightly so that ∣p∣≤1 on [−1,1].
21(peven(H/α)−ipodd(H/α))≈21e−iHt
QSVT block-encodes each part; an LCU over one extra qubit combines them with weights 21,21.
normalization 2one round of OAAe−iHt to error O(ε)
The target is unitary and the amplitude is 21 for every input: exactly the setting of oblivious amplitude amplification from the LCU lesson. Total queries: a constant times the degree.
Predict before you look
For τ=αt=1000 and target error ε=10−10, what truncation degree d makes the Jacobi–Anger tail 2∑k>d∣Jk(τ)∣ fall below ε?
Show the answer
1080
A numerical evaluation gives d=1079, only about 8% above τ. A multiplicative estimate τlog(1/ε) would suggest about 23,000. For τ=100 the same ε needs d=137: the overhead beyond τ is additive and grows only like τ1/3 at fixed precision.
The grand unification
Once you can apply bounded polynomials to singular values, designing an algorithm reduces to an approximation problem: find a low-degree polynomial with the right shape.
Task
Polynomial
Degree (queries)
Amplitude amplification and search
T2k+1(x), mapping a=sinθ to ±sin((2k+1)θ)
O(1/a)
Fixed-point search (Yoder, Low & Chuang 2014)
odd approximation to sign(x), close to 1 for x≥a
O(log(1/δ)/a)
Hamiltonian simulation
cos(τx), sin(τx) via Jacobi–Anger
O(τ+loglog(1/ε)log(1/ε))
Linear systems (the HHL problem)
odd approximation to κx1 on κ1≤∣x∣≤1
O(κlog(κ/ε)) per call
Eigenstate filtering (Lin & Tong 2020)
even polynomial peaked at the target eigenvalue, small beyond the gap Δ
O(Δαlogε1)
For linear systems the output amplitude can be as small as about 1/κ; amplitude amplification then costs another factor of κ, which variable-time amplitude amplification (Childs, Kothari & Somma 2017) and adiabatic methods (Costa et al. 2022, O(κlog(1/ε))) remove.
Key takeaways
QSP: interleaving a signal rotation with Z-phases realizes exactly the polynomials of degree ≤d, parity dmod2 and bounded modulus.
Qubitization and QSVT: a block encoding decomposes into one plane per singular value, so a single phase sequence applies f to all of them with d queries.
Jacobi–Anger plus QSVT simulates e−iHt with O(αt+log(1/ε)/loglog(1/ε)) queries, which is optimal.
Search, simulation, linear systems and filtering are polynomial approximation problems, and query lower bounds are approximation-theory lower bounds.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
A QSVT circuit makes d=7 queries to a block encoding of A. Which transformation can it implement (up to normalization)?
Any polynomial of degree at most 7 in the singular values
An odd real polynomial f of degree at most 7 with ∣f∣≤1 on [−1,1], applied to the singular values
An even polynomial of degree 14
The exact inverse A−1
Show the answer
B. An odd real polynomial f of degree at most 7 with ∣f∣≤1 on [−1,1], applied to the singular values
Seven queries give degree at most 7 with parity 7mod2 = odd, and the polynomial must be bounded by 1 on [−1,1] because it sits inside a unitary.
Question 2
Why is the query complexity O(αt+log(1/ε)/loglog(1/ε)) called optimal?
It is independent of α
It is achieved by product formulas
It scales linearly in 1/ε
It matches the lower bounds Ω(t) (no fast-forwarding) and Ω(log(1/ε)/loglog(1/ε)), and the two costs add rather than multiply
Show the answer
D. It matches the lower bounds Ω(t) (no fast-forwarding) and Ω(log(1/ε)/loglog(1/ε)), and the two costs add rather than multiply
Each term is individually necessary for general Hamiltonians, so no algorithm can beat their sum by more than a constant factor.
Question 3
In qubitization, an eigenvector of H/α with eigenvalue λ spans, with its image, a plane on which W=(2Π−I)U has eigenvalues
e±iarccosλ
e±iλ
±λ
e−iλt
Show the answer
A.e±iarccosλ
W acts on the plane as a rotation by arccosλ, so Wk has block cos(karccosλ)=Tk(λ).
Question 4
Which statement about QSVT-based matrix inversion is correct?
It gives an exponential speedup for every linear system Ax=b
Its polynomial degree is independent of the condition number κ
It applies an odd polynomial approximating 1/(κx) on 1/κ≤∣x∣≤1, of degree O(κlog(κ/ε)), and outputs a quantum state proportional to A−1∣b⟩
It requires A to be unitary
Show the answer
C. It applies an odd polynomial approximating 1/(κx) on 1/κ≤∣x∣≤1, of degree O(κlog(κ/ε)), and outputs a quantum state proportional to A−1∣b⟩
The polynomial must stay bounded by 1 while growing like 1/x down to 1/κ, which forces degree ∼κ. The output is a state, not the vector x: reading out useful information is part of the fine print.
Further reading
G. H. Low & I. L. Chuang, "Optimal Hamiltonian simulation by quantum signal processing", Physical Review Letters 118, 010501 (2017).
G. H. Low & I. L. Chuang, "Hamiltonian simulation by qubitization", Quantum 3, 163 (2019).
A. Gilyén, Y. Su, G. H. Low & N. Wiebe, "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics", Proceedings of STOC (2019).
J. M. Martyn, Z. M. Rossi, A. K. Tan & I. L. Chuang, "Grand unification of quantum algorithms", PRX Quantum 2, 040203 (2021).
A. W. Harrow, A. Hassidim & S. Lloyd, "Quantum algorithm for linear systems of equations", Physical Review Letters 103, 150502 (2009).