Simple Algorithm
Quantum Computing · Rydberg State · 34 min

Quantum Signal Processing & QSVT

A grand unification of quantum algorithms.

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/α)T_k(H/\alpha).
  • State the QSVT theorem and implement projector-controlled phases with one ancilla.
  • Derive optimal O(αt+log⁡(1/ε)/log⁡log⁡(1/ε))\order{\alpha t + \log(1/\varepsilon)/\log\log(1/\varepsilon)} 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 signal x∈[−1,1]x\in[-1,1] is encoded in an XX-rotation, and we may interleave ZZ-rotations with phases of our choice:

W(x)=eiarccos⁡(x) X=(xi1−x2i1−x2x),UΦ(x)=eiφ0Z∏k=1dW(x) eiφkZ.W(x) = e^{i\arccos(x)\,X} = \begin{pmatrix}x & i\sqrt{1-x^2}\\ i\sqrt{1-x^2} & x\end{pmatrix},\qquad U_\Phi(x) = e^{i\varphi_0Z}\prod_{k=1}^{d}W(x)\,e^{i\varphi_kZ}.

Which functions of xx can appear as matrix elements of UΦ(x)U_\Phi(x)?

DerivationZero phases give Chebyshev polynomials
  1. x=cos⁡ϑ:W(x)d=eidϑX=cos⁡(dϑ) I+isin⁡(dϑ) Xx = \cos\vartheta:\qquad W(x)^d = e^{id\vartheta X} = \cos(d\vartheta)\,\id + i\sin(d\vartheta)\,X

    W(x)W(x) is a rotation by angle 2ϑ2\vartheta about xx; dd of them add up.

  2. ⟨0∣W(x)d∣0⟩=cos⁡(dϑ)=Td(x),⟨0∣W(x)d∣1⟩=isin⁡ϑ sin⁡(dϑ)sin⁡ϑ=i1−x2 Ud−1(x)\bra0W(x)^d\ket0 = \cos(d\vartheta) = T_d(x),\qquad \bra0W(x)^d\ket1 = i\sin\vartheta\,\frac{\sin(d\vartheta)}{\sin\vartheta} = i\sqrt{1-x^2}\,U_{d-1}(x)

    Chebyshev polynomials of the first and second kind. Degree and parity match the theorem, and Td2+(1−x2)Ud−12=1T_d^2+(1-x^2)U_{d-1}^2 = 1 is just cos⁡2+sin⁡2=1\cos^2+\sin^2 = 1.

  3. Necessity in general is an induction: each factor W(x)eiφZW(x)e^{i\varphi Z} raises the degree by one and flips the parity, preserving unitarity. Sufficiency is proved by peeling layers: given an admissible (P,Q)(P, Q) of degree dd, condition (iii) lets one choose φ\varphi so that multiplying by (W(x)eiφZ)−1\big(W(x)e^{i\varphi Z}\big)^{-1} leaves an admissible pair of degree d−1d-1.

Check your understanding

A QSP sequence uses the signal W(x)W(x) exactly four times. Which function can be ⟨0∣UΦ(x)∣0⟩\bra0U_\Phi(x)\ket0?

  1. 4x3−3x4x^3-3x
  2. x5x^5
  3. 8x4−8x2+18x^4-8x^2+1
  4. 2x22x^2
Show the answer

C. 8x4−8x2+18x^4-8x^2+1

With d=4d = 4, PP must be even, of degree at most 4, and bounded by 1 on [−1,1][-1,1]. 8x4−8x2+1=T4(x)8x^4-8x^2+1 = T_4(x) qualifies; it is produced with all phases zero.

From one qubit to matrices: qubitization and QSVT

Now let UU be a unitary and Π\Pi, Π~\tilde\Pi projectors with Π~UΠ=A\tilde\Pi U\Pi = A, a block encoding with singular value decomposition A=∑kσk∣wk⟩ ⁣⟨vk∣A = \sum_k\sigma_k\ketbra{w_k}{v_k}. (For a standard block encoding, Π=Π~=∣0a⟩ ⁣⟨0a∣⊗I\Pi = \tilde\Pi = \dyad{0^a}\otimes\id and AA is the encoded matrix divided by α\alpha.)

DerivationA projector-controlled phase costs one ancilla
  1. CΠNOT:=X⊗Π+I⊗(I−Π)C_\Pi\mathrm{NOT} := X\otimes\Pi + \id\otimes(\id-\Pi)

    Flip an extra qubit exactly on the range of Π\Pi. For Π=∣0a⟩ ⁣⟨0a∣⊗I\Pi = \dyad{0^a}\otimes\id this is a multi-controlled NOT with negated controls.

  2. CΠNOT (e−iφZ⊗I) CΠNOT (∣0⟩⊗∣ξ⟩)=∣0⟩⊗eiφ(2Π−I)∣ξ⟩C_\Pi\mathrm{NOT}\,\big(e^{-i\varphi Z}\otimes\id\big)\,C_\Pi\mathrm{NOT}\,\big(\ket0\otimes\ket\xi\big) = \ket0\otimes e^{i\varphi(2\Pi-\id)}\ket\xi

    On the range of Π\Pi the extra qubit is ∣1⟩\ket1 during the rotation and picks up e+iφe^{+i\varphi}; elsewhere it stays ∣0⟩\ket0 and picks up e−iφe^{-i\varphi}.

Optimal Hamiltonian simulation

We want e−iHt=e−iτ(H/α)e^{-iHt} = e^{-i\tau(H/\alpha)} with τ=αt\tau = \alpha t, i.e. the function x↦e−iτxx\mapsto e^{-i\tau x} applied to the eigenvalues of H/α∈[−1,1]H/\alpha\in[-1,1]. The Chebyshev expansion of this function is classical:

e−iτx=J0(τ)+2∑k=1∞(−i)kJk(τ) Tk(x),x∈[−1,1]e^{-i\tau x} = J_0(\tau) + 2\sum_{k=1}^{\infty}(-i)^kJ_k(\tau)\,T_k(x),\qquad x\in[-1,1]
The Jacobi–Anger expansion; JkJ_k are Bessel functions. Since ∣Tk∣≤1\abs{T_k}\le1, truncating at degree dd costs at most 2∑k>d∣Jk(τ)∣2\sum_{k>d}\abs{J_k(\tau)}, and ∣Jk(τ)∣≤(τ/2)k/k!\abs{J_k(\tau)}\le(\tau/2)^k/k! decays super-exponentially once kk exceeds a constant times τ\tau.
DerivationFrom polynomials to e^{-iHt}
  1. cos⁡(τx)=J0(τ)+2∑k≥1(−1)kJ2k(τ) T2k(x),sin⁡(τx)=2∑k≥0(−1)kJ2k+1(τ) T2k+1(x)\cos(\tau x) = J_0(\tau)+2\sum_{k\ge1}(-1)^kJ_{2k}(\tau)\,T_{2k}(x),\qquad \sin(\tau x) = 2\sum_{k\ge0}(-1)^kJ_{2k+1}(\tau)\,T_{2k+1}(x)

    Split into even and odd parts, each with the definite parity QSVT requires.

  2. ∣cos⁡(τx)−peven(x)∣≤ε4,∣sin⁡(τx)−podd(x)∣≤ε4,deg⁡p=O(τ+log⁡(1/ε)log⁡log⁡(1/ε))\abs{\cos(\tau x)-p_{\mathrm{even}}(x)}\le\tfrac{\varepsilon}{4},\quad\abs{\sin(\tau x)-p_{\mathrm{odd}}(x)}\le\tfrac{\varepsilon}{4},\qquad \deg p = \order{\tau+\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}}

    Truncate, and rescale slightly so that ∣p∣≤1\abs{p}\le1 on [−1,1][-1,1].

  3. 12(peven(H/α)−i podd(H/α))≈12 e−iHt\tfrac12\Big(p_{\mathrm{even}}(H/\alpha) - i\,p_{\mathrm{odd}}(H/\alpha)\Big)\approx\tfrac12\,e^{-iHt}

    QSVT block-encodes each part; an LCU over one extra qubit combines them with weights 12,12\tfrac12,\tfrac12.

  4. normalization 2 → one round of OAA  e−iHt  to error O(ε)\text{normalization } 2\ \xrightarrow{\ \text{one round of OAA}\ }\ e^{-iHt}\ \text{ to error } \order{\varepsilon}

    The target is unitary and the amplitude is 12\tfrac12 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\tau = \alpha t = 1000 and target error ε=10−10\varepsilon = 10^{-10}, what truncation degree dd makes the Jacobi–Anger tail 2∑k>d∣Jk(τ)∣2\sum_{k>d}\abs{J_k(\tau)} fall below ε\varepsilon?

Show the answer

1080

A numerical evaluation gives d=1079d = 1079, only about 8% above τ\tau. A multiplicative estimate τlog⁡(1/ε)\tau\log(1/\varepsilon) would suggest about 23,000. For τ=100\tau = 100 the same ε\varepsilon needs d=137d = 137: the overhead beyond τ\tau is additive and grows only like τ1/3\tau^{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.

TaskPolynomialDegree (queries)
Amplitude amplification and searchT2k+1(x)T_{2k+1}(x), mapping a=sin⁡θa = \sin\theta to ±sin⁡((2k+1)θ)\pm\sin((2k+1)\theta)O(1/a)\order{1/a}
Fixed-point search (Yoder, Low & Chuang 2014)odd approximation to sign⁡(x)\operatorname{sign}(x), close to 11 for x≥ax\ge aO(log⁡(1/δ)/a)\order{\log(1/\delta)/a}
Hamiltonian simulationcos⁡(τx)\cos(\tau x), sin⁡(τx)\sin(\tau x) via Jacobi–AngerO(τ+log⁡(1/ε)log⁡log⁡(1/ε))\order{\tau+\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}}
Linear systems (the HHL problem)odd approximation to 1κx\frac{1}{\kappa x} on 1κ≤∣x∣≤1\frac1\kappa\le\abs{x}\le1O(κlog⁡(κ/ε))\order{\kappa\log(\kappa/\varepsilon)} per call
Eigenstate filtering (Lin & Tong 2020)even polynomial peaked at the target eigenvalue, small beyond the gap Δ\DeltaO(αΔlog⁡1ε)\order{\frac{\alpha}{\Delta}\log\frac1\varepsilon}
For linear systems the output amplitude can be as small as about 1/κ1/\kappa; amplitude amplification then costs another factor of κ\kappa, which variable-time amplitude amplification (Childs, Kothari & Somma 2017) and adiabatic methods (Costa et al. 2022, O(κlog⁡(1/ε))\order{\kappa\log(1/\varepsilon)}) remove.

Key takeaways

  • QSP: interleaving a signal rotation with ZZ-phases realizes exactly the polynomials of degree ≤d\le d, parity d mod 2d\bmod2 and bounded modulus.
  • Qubitization and QSVT: a block encoding decomposes into one plane per singular value, so a single phase sequence applies ff to all of them with dd queries.
  • Jacobi–Anger plus QSVT simulates e−iHte^{-iHt} with O(αt+log⁡(1/ε)/log⁡log⁡(1/ε))\order{\alpha t + \log(1/\varepsilon)/\log\log(1/\varepsilon)} 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=7d = 7 queries to a block encoding of AA. Which transformation can it implement (up to normalization)?

  1. Any polynomial of degree at most 7 in the singular values
  2. An odd real polynomial ff of degree at most 7 with ∣f∣≤1\abs{f}\le1 on [−1,1][-1,1], applied to the singular values
  3. An even polynomial of degree 14
  4. The exact inverse A−1A^{-1}
Show the answer

B. An odd real polynomial ff of degree at most 7 with ∣f∣≤1\abs{f}\le1 on [−1,1][-1,1], applied to the singular values

Seven queries give degree at most 7 with parity 7 mod 27\bmod2 = odd, and the polynomial must be bounded by 1 on [−1,1][-1,1] because it sits inside a unitary.

Question 2

Why is the query complexity O(αt+log⁡(1/ε)/log⁡log⁡(1/ε))\order{\alpha t + \log(1/\varepsilon)/\log\log(1/\varepsilon)} called optimal?

  1. It is independent of α\alpha
  2. It is achieved by product formulas
  3. It scales linearly in 1/ε1/\varepsilon
  4. It matches the lower bounds Ω(t)\Omega(t) (no fast-forwarding) and Ω(log⁡(1/ε)/log⁡log⁡(1/ε))\Omega(\log(1/\varepsilon)/\log\log(1/\varepsilon)), and the two costs add rather than multiply
Show the answer

D. It matches the lower bounds Ω(t)\Omega(t) (no fast-forwarding) and Ω(log⁡(1/ε)/log⁡log⁡(1/ε))\Omega(\log(1/\varepsilon)/\log\log(1/\varepsilon)), 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/αH/\alpha with eigenvalue λ\lambda spans, with its image, a plane on which W=(2Π−I)UW = (2\Pi-\id)U has eigenvalues

  1. e±iarccos⁡λe^{\pm i\arccos\lambda}
  2. e±iλe^{\pm i\lambda}
  3. ±λ\pm\lambda
  4. e−iλte^{-i\lambda t}
Show the answer

A. e±iarccos⁡λe^{\pm i\arccos\lambda}

WW acts on the plane as a rotation by arccos⁡λ\arccos\lambda, so WkW^k has block cos⁡(karccos⁡λ)=Tk(λ)\cos(k\arccos\lambda) = T_k(\lambda).

Question 4

Which statement about QSVT-based matrix inversion is correct?

  1. It gives an exponential speedup for every linear system Ax=bAx = b
  2. Its polynomial degree is independent of the condition number κ\kappa
  3. It applies an odd polynomial approximating 1/(κx)1/(\kappa x) on 1/κ≤∣x∣≤11/\kappa\le\abs{x}\le1, of degree O(κlog⁡(κ/ε))\order{\kappa\log(\kappa/\varepsilon)}, and outputs a quantum state proportional to A−1∣b⟩A^{-1}\ket b
  4. It requires AA to be unitary
Show the answer

C. It applies an odd polynomial approximating 1/(κx)1/(\kappa x) on 1/κ≤∣x∣≤11/\kappa\le\abs{x}\le1, of degree O(κlog⁡(κ/ε))\order{\kappa\log(\kappa/\varepsilon)}, and outputs a quantum state proportional to A−1∣b⟩A^{-1}\ket b

The polynomial must stay bounded by 1 while growing like 1/x1/x down to 1/κ1/\kappa, which forces degree ∼κ\sim\kappa. The output is a state, not the vector xx: 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).