Simple Algorithm
Quantum Computing · Rydberg State · 32 min

LCU & Block Encodings

Implementing non-unitary matrices inside unitaries.

Circuits can only apply unitaries, yet the operators we care about (Hamiltonians, Taylor polynomials, inverses) are not unitary. The trick is to hide them in a corner of a bigger unitary. Linear combinations of unitaries and block encodings turn that trick into an algebra, and with oblivious amplitude amplification they gave the first simulation algorithms whose cost grows only polylogarithmically in 1/ε1/\varepsilon.

What you’ll learn

  • Define (α,a,ε)(\alpha, a, \varepsilon)-block encodings, and compose them by products and linear combinations.
  • Prove the LCU lemma: PREP†⋅SELECT⋅PREP\mathrm{PREP}^\dagger\cdot\mathrm{SELECT}\cdot\mathrm{PREP} block-encodes ∑jαjVj/∥α∥1\sum_j\alpha_jV_j/\norm{\alpha}_1.
  • State and prove oblivious amplitude amplification, and explain why ordinary amplitude amplification does not apply.
  • Derive the truncated-Taylor-series simulation algorithm and its O(τlog⁡(τ/ε)/log⁡log⁡(τ/ε))\order{\tau\log(\tau/\varepsilon)/\log\log(\tau/\varepsilon)} cost.

Hiding a matrix inside a unitary

U=(A/α∗∗∗),U(∣0a⟩∣ψ⟩)=∣0a⟩ A∣ψ⟩α+∣⊥⟩,(⟨0a∣⊗I)∣⊥⟩=0U = \begin{pmatrix} A/\alpha & \ast\\ \ast & \ast\end{pmatrix},\qquad U\big(\ket{0^a}\ket\psi\big) = \ket{0^a}\,\frac{A\ket\psi}{\alpha} + \ket{\perp},\quad \big(\bra{0^a}\otimes\id\big)\ket{\perp} = 0
Measuring the ancillas and finding 0a0^a applies A/αA/\alpha (renormalized), with probability ∥A∣ψ⟩∥2/α2\norm{A\ket\psi}^2/\alpha^2.

A block of a unitary has norm at most 1, so necessarily α≥∥A∥\alpha\ge\norm{A}. Examples: a unitary VV is a (1,0,0)(1,0,0)-block encoding of itself; a dd-sparse matrix with oracle access to its entries has a block encoding with α=d max⁡ij∣Aij∣\alpha = d\,\max_{ij}\abs{A_{ij}}.

Block encodings compose. If UAU_A is an (α,a)(\alpha, a)-block encoding of AA and UBU_B a (β,b)(\beta, b)-block encoding of BB, then applying UBU_B and then UAU_A, on separate ancilla registers, is an (αβ,a+b)(\alpha\beta, a+b)-block encoding of ABAB. Linear combinations come from the LCU lemma below; polynomials come from QSVT (next lesson).

Check your understanding

A (4,2,0)(4, 2, 0)-block encoding of a unitary VV is applied to ∣00⟩∣ψ⟩\ket{00}\ket\psi and the two ancillas are measured. What is the probability of seeing 0000?

  1. 1/41/4
  2. 1/161/16
  3. 1/21/2
  4. It depends on ∣ψ⟩\ket\psi
Show the answer

B. 1/161/16

The 0000 branch is ∣00⟩ V∣ψ⟩/4\ket{00}\,V\ket\psi/4, with squared norm ∥V∣ψ⟩∥2/16=1/16\norm{V\ket\psi}^2/16 = 1/16 for every ∣ψ⟩\ket\psi, because VV is unitary.

The LCU lemma

Write A=∑j=0L−1αjVjA = \sum_{j=0}^{L-1}\alpha_jV_j with αj>0\alpha_j>0 and VjV_j unitary; signs and phases can always be absorbed into the VjV_j (for example, −X-X is unitary). Let ∥α∥1=∑jαj\norm{\alpha}_1 = \sum_j\alpha_j.

DerivationProof
  1. (PREP⊗I)∣0⟩∣ψ⟩=∑jαj∥α∥1 ∣j⟩∣ψ⟩\big(\mathrm{PREP}\otimes\id\big)\ket{0}\ket\psi = \sum_j\sqrt{\tfrac{\alpha_j}{\norm{\alpha}_1}}\,\ket{j}\ket\psi

    Load the weights into the index register.

  2. SELECT: ∑jαj∥α∥1 ∣j⟩∣ψ⟩ ⟼ ∑jαj∥α∥1 ∣j⟩ Vj∣ψ⟩\mathrm{SELECT}:\ \sum_j\sqrt{\tfrac{\alpha_j}{\norm{\alpha}_1}}\,\ket{j}\ket\psi\ \longmapsto\ \sum_j\sqrt{\tfrac{\alpha_j}{\norm{\alpha}_1}}\,\ket{j}\,V_j\ket\psi

    Apply VjV_j controlled on the index jj.

  3. (⟨0∣PREP†⊗I)=∑jαj∥α∥1 ⟨j∣⊗I\big(\bra{0}\mathrm{PREP}^\dagger\otimes\id\big) = \sum_j\sqrt{\tfrac{\alpha_j}{\norm{\alpha}_1}}\,\bra{j}\otimes\id

    Projecting onto ∣0⟩\ket0 after PREP†\mathrm{PREP}^\dagger is projecting onto the prepared state PREP∣0⟩\mathrm{PREP}\ket0.

  4. (⟨0∣⊗I) W (∣0⟩⊗I)=∑jαj∥α∥1 Vj=A∥α∥1■\big(\bra{0}\otimes\id\big)\,W\,\big(\ket{0}\otimes\id\big) = \sum_j\frac{\alpha_j}{\norm{\alpha}_1}\,V_j = \frac{A}{\norm{\alpha}_1}\qquad\blacksquare

    The two square roots multiply to αj/∥α∥1\alpha_j/\norm{\alpha}_1.

The normalization is ∥α∥1\norm{\alpha}_1, not ∥A∥\norm{A}, and it governs the success probability and, later, the query complexity. Choosing a decomposition with small ∥α∥1\norm{\alpha}_1 is a central optimization in fault-tolerant chemistry, where factorized representations of the Coulomb operator lower it by large factors.

Oblivious amplitude amplification

A success probability 1/∥α∥121/\norm{\alpha}_1^2 is too small to rely on post-selection, and a failure destroys the unknown input. Ordinary amplitude amplification would need reflections about the initial state W∣0a⟩∣ψ⟩W\ket{0^a}\ket\psi, which requires a fresh copy of ∣ψ⟩\ket\psi. The oblivious version needs only the ancilla reflection R=2 ∣0a⟩ ⁣⟨0a∣⊗I−IR = 2\,\dyad{0^a}\otimes\id - \id, provided the success amplitude is the same for every input. That holds exactly when A/α=sin⁡θ⋅VA/\alpha = \sin\theta\cdot V with VV unitary.

DerivationProof: one plane per input
  1. Π:=∣0a⟩ ⁣⟨0a∣⊗I:Π W(∣0a⟩⊗I)=sin⁡θ ∣0a⟩⊗V\Pi := \dyad{0^a}\otimes\id:\qquad \Pi\,W\big(\ket{0^a}\otimes\id\big) = \sin\theta\,\ket{0^a}\otimes V

    The hypothesis as an operator identity, valid for all inputs at once.

  2. ∣μ⟩:=∣0a⟩V∣ψ⟩:Π W†∣μ⟩=sin⁡θ ∣0a⟩∣ψ⟩\ket\mu := \ket{0^a}V\ket\psi:\qquad \Pi\,W^\dagger\ket\mu = \sin\theta\,\ket{0^a}\ket\psi

    Take adjoints: ⟨0a,φ∣W†∣μ⟩=sin⁡θ ⟨φ∣V†V∣ψ⟩=sin⁡θ⟨φ∣ψ⟩\bra{0^a,\varphi}W^\dagger\ket\mu = \sin\theta\,\bra{\varphi}V^\dagger V\ket\psi = \sin\theta\braket{\varphi|\psi} for every φ\varphi. This is where unitarity of VV enters.

  3. W∣0aψ⟩=sin⁡θ∣μ⟩+cos⁡θ∣Φψ⟩,W∣Φ′⟩=cos⁡θ∣μ⟩−sin⁡θ∣Φψ⟩W\ket{0^a\psi} = \sin\theta\ket\mu + \cos\theta\ket{\Phi_\psi},\qquad W\ket{\Phi'} = \cos\theta\ket\mu - \sin\theta\ket{\Phi_\psi}

    Define ∣Φ′⟩\ket{\Phi'} by W†∣μ⟩=sin⁡θ∣0aψ⟩+cos⁡θ∣Φ′⟩W^\dagger\ket\mu = \sin\theta\ket{0^a\psi}+\cos\theta\ket{\Phi'} with Π∣Φ′⟩=0\Pi\ket{\Phi'} = 0. Then WW maps the plane spanned by ∣0aψ⟩,∣Φ′⟩\ket{0^a\psi}, \ket{\Phi'} onto the plane spanned by ∣μ⟩,∣Φψ⟩\ket\mu, \ket{\Phi_\psi}.

  4. S∣span⁡{∣μ⟩,∣Φψ⟩}=(cos⁡2θsin⁡2θ−sin⁡2θcos⁡2θ)S\big|_{\operatorname{span}\{\ket\mu,\ket{\Phi_\psi}\}} = \begin{pmatrix}\cos2\theta & \sin2\theta\\ -\sin2\theta & \cos2\theta\end{pmatrix}

    RR is +1+1 on ∣0aψ⟩\ket{0^a\psi}, ∣μ⟩\ket\mu and −1-1 on ∣Φ′⟩\ket{\Phi'}, ∣Φψ⟩\ket{\Phi_\psi}. In these bases WW is the reflection matrix (sin⁡θcos⁡θcos⁡θ−sin⁡θ)\begin{pmatrix}\sin\theta&\cos\theta\\ \cos\theta&-\sin\theta\end{pmatrix}, so SS is a rotation that adds 2θ2\theta to the angle, exactly as in Grover's algorithm, but in a plane that exists for every input. ■\blacksquare

If the encoded operator is only δ\delta-close to unitary (a truncated series, say), robust oblivious amplitude amplification still produces an output O(δ)\order{\delta}-close to the ideal one. That is exactly what the simulation algorithm below needs.

Simulation by a truncated Taylor series

Write H=∑ℓβℓPℓH = \sum_\ell\beta_\ell P_\ell as a combination of Pauli strings with βℓ>0\beta_\ell>0 (signs absorbed), β=∑ℓβℓ\beta = \sum_\ell\beta_\ell. Split the time tt into rr segments with βt/r=ln⁡2\beta t/r = \ln 2 and implement each segment as an LCU (Berry, Childs, Cleve, Kothari & Somma 2015).

DerivationThe algorithm and its cost
  1. e−iHt/r≈∑k=0K(−iHt/r)kk!=∑k=0K∑ℓ1,…,ℓk(t/r)kk! βℓ1⋯βℓk (−i)kPℓ1⋯Pℓke^{-iHt/r}\approx\sum_{k=0}^{K}\frac{(-iHt/r)^k}{k!} = \sum_{k=0}^{K}\sum_{\ell_1,\dots,\ell_k}\frac{(t/r)^k}{k!}\,\beta_{\ell_1}\cdots\beta_{\ell_k}\,(-i)^kP_{\ell_1}\cdots P_{\ell_k}

    Every term is a positive weight times a unitary (a phase times a product of Pauli strings): an LCU.

  2. ∥α∥1=∑k=0K(βt/r)kk!≤eβt/r=2\norm{\alpha}_1 = \sum_{k=0}^{K}\frac{(\beta t/r)^k}{k!}\le e^{\beta t/r} = 2

    The normalization is at most 2; shortening the segment slightly makes it exactly 2, so one round of oblivious amplitude amplification implements each segment, robustly since the truncated series is only approximately unitary.

  3. ∑k>K(ln⁡2)kk!≤εr⟸K=O(log⁡(r/ε)log⁡log⁡(r/ε))\sum_{k>K}\frac{(\ln2)^k}{k!}\le\frac{\varepsilon}{r}\quad\Longleftarrow\quad K = \order{\frac{\log(r/\varepsilon)}{\log\log(r/\varepsilon)}}

    The factorial makes the tail super-exponentially small: (K+1)!≳r/ε(K+1)!\gtrsim r/\varepsilon suffices.

  4. r=O(βt),cost=O(rK)=O(βt log⁡(βt/ε)log⁡log⁡(βt/ε))r = \order{\beta t},\qquad\text{cost} = \order{rK} = \order{\beta t\,\frac{\log(\beta t/\varepsilon)}{\log\log(\beta t/\varepsilon)}}

    Each segment uses three LCU applications (WW, W†W^\dagger, WW), each with KK controlled SELECT\mathrm{SELECT}s; segment errors add.

Compare with product formulas, whose cost grows like ε−1/p\varepsilon^{-1/p}: the Taylor method pays only log⁡(1/ε)/log⁡log⁡(1/ε)\log(1/\varepsilon)/\log\log(1/\varepsilon), an exponential improvement in precision, at the price of O(Klog⁡L)\order{K\log L} ancilla qubits and the cost of PREP\mathrm{PREP} and SELECT\mathrm{SELECT}. Note also the parameter: cost scales with β=∥α∥1\beta = \norm{\alpha}_1, the 1-norm of the Pauli coefficients, which can greatly exceed ∥H∥\norm{H}.

Key takeaways

  • A block encoding places A/αA/\alpha in the top-left block of a unitary; post-selection succeeds with probability ∥A∣ψ⟩∥2/α2\norm{A\ket\psi}^2/\alpha^2, and α≥∥A∥\alpha\ge\norm{A}.
  • LCU: PREP† SELECT PREP\mathrm{PREP}^\dagger\,\mathrm{SELECT}\,\mathrm{PREP} block-encodes ∑jαjVj\sum_j\alpha_jV_j with normalization ∥α∥1\norm{\alpha}_1, the key cost parameter.
  • Oblivious amplitude amplification boosts input-independent success amplitudes with ancilla reflections only: S=−WRW†RS = -WRW^\dagger R rotates by 2θ2\theta.
  • Truncated Taylor series plus OAA simulates e−iHte^{-iHt} with O(βtlog⁡(βt/ε)/log⁡log⁡(βt/ε))\order{\beta t\log(\beta t/\varepsilon)/\log\log(\beta t/\varepsilon)} cost, exponentially better in precision than product formulas.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

H=0.5 Z⊗Z−0.3 X⊗I+0.2 I⊗XH = 0.5\,Z\otimes Z - 0.3\,X\otimes\id + 0.2\,\id\otimes X is block-encoded by PREP/SELECT\mathrm{PREP}/\mathrm{SELECT} over its Pauli strings. What is the normalization ∥α∥1\norm{\alpha}_1?

  1. 0.40.4
  2. 1.01.0
  3. 0.38≈0.62\sqrt{0.38}\approx0.62
  4. 33
Show the answer

B. 1.01.0

Signs are absorbed into the unitaries (−X⊗I-X\otimes\id is unitary), so ∥α∥1=0.5+0.3+0.2=1.0\norm{\alpha}_1 = 0.5+0.3+0.2 = 1.0.

Question 2

Why can't ordinary amplitude amplification boost the success probability of an LCU applied to an unknown input ∣ψ⟩\ket\psi?

  1. The LCU success amplitude is already too large
  2. Amplitude amplification requires intermediate measurements
  3. It only works for search problems
  4. It needs a reflection about the initial state W∣0a⟩∣ψ⟩W\ket{0^a}\ket\psi, which depends on the unknown ∣ψ⟩\ket\psi
Show the answer

D. It needs a reflection about the initial state W∣0a⟩∣ψ⟩W\ket{0^a}\ket\psi, which depends on the unknown ∣ψ⟩\ket\psi

Reflecting about W∣0a⟩∣ψ⟩W\ket{0^a}\ket\psi requires preparing that state, i.e. having ∣ψ⟩\ket\psi available. OAA replaces it by the input-independent ancilla reflection, valid because the success amplitude is the same for all inputs.

Question 3

In the truncated-Taylor-series algorithm, why are the segments chosen so that the LCU normalization is 2?

  1. Then sin⁡θ=12\sin\theta = \tfrac12, and one round of OAA rotates to 3θ=π/23\theta = \pi/2: each segment succeeds (almost) deterministically
  2. The Taylor series of exe^{x} only converges for ∣x∣<ln⁡2\abs{x}<\ln2
  3. Because exactly two ancilla qubits are used
  4. To make the truncation order KK independent of ε\varepsilon
Show the answer

A. Then sin⁡θ=12\sin\theta = \tfrac12, and one round of OAA rotates to 3θ=π/23\theta = \pi/2: each segment succeeds (almost) deterministically

With normalization 2 the success amplitude is 12\tfrac12, so θ=π/6\theta = \pi/6 and S WS\,W produces amplitude sin⁡(π/2)=1\sin(\pi/2) = 1.

Question 4

UAU_A is an (α,a)(\alpha, a)-block encoding of AA and UBU_B an (β,b)(\beta, b)-block encoding of BB. Applying UBU_B then UAU_A on separate ancilla registers block-encodes

  1. A+BA+B with normalization α+β\alpha+\beta
  2. ABAB with normalization max⁡(α,β)\max(\alpha,\beta)
  3. ABAB with normalization αβ\alpha\beta, using a+ba+b ancillas
  4. ABAB with normalization α+β\alpha+\beta
Show the answer

C. ABAB with normalization αβ\alpha\beta, using a+ba+b ancillas

Projecting both ancilla registers onto ∣0⟩\ket0 gives (A/α)(B/β)=AB/(αβ)(A/\alpha)(B/\beta) = AB/(\alpha\beta). Normalizations multiply, which is why long products of block encodings get expensive.

Further reading

  • A. M. Childs & N. Wiebe, "Hamiltonian simulation using linear combinations of unitary operations", Quantum Information & Computation 12, 901 (2012).
  • D. W. Berry, A. M. Childs, R. Cleve, R. Kothari & R. D. Somma, "Exponential improvement in precision for simulating sparse Hamiltonians", Proceedings of STOC (2014).
  • D. W. Berry, A. M. Childs, R. Cleve, R. Kothari & R. D. Somma, "Simulating Hamiltonian dynamics with a truncated Taylor series", Physical Review Letters 114, 090502 (2015).
  • 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).
  • G. H. Low & I. L. Chuang, "Hamiltonian simulation by qubitization", Quantum 3, 163 (2019).