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 .
What you’ll learn
- Define -block encodings, and compose them by products and linear combinations.
- Prove the LCU lemma: block-encodes .
- State and prove oblivious amplitude amplification, and explain why ordinary amplitude amplification does not apply.
- Derive the truncated-Taylor-series simulation algorithm and its cost.
Hiding a matrix inside a unitary
A block of a unitary has norm at most 1, so necessarily . Examples: a unitary is a -block encoding of itself; a -sparse matrix with oracle access to its entries has a block encoding with .
Block encodings compose. If is an -block encoding of and a -block encoding of , then applying and then , on separate ancilla registers, is an -block encoding of . Linear combinations come from the LCU lemma below; polynomials come from QSVT (next lesson).
A -block encoding of a unitary is applied to and the two ancillas are measured. What is the probability of seeing ?
- It depends on
Show the answer
B.
The branch is , with squared norm for every , because is unitary.
The LCU lemma
Write with and unitary; signs and phases can always be absorbed into the (for example, is unitary). Let .
Load the weights into the index register.
Apply controlled on the index .
Projecting onto after is projecting onto the prepared state .
The two square roots multiply to .
The normalization is , not , and it governs the success probability and, later, the query complexity. Choosing a decomposition with small 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 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 , which requires a fresh copy of . The oblivious version needs only the ancilla reflection , provided the success amplitude is the same for every input. That holds exactly when with unitary.
The hypothesis as an operator identity, valid for all inputs at once.
Take adjoints: for every . This is where unitarity of enters.
Define by with . Then maps the plane spanned by onto the plane spanned by .
is on , and on , . In these bases is the reflection matrix , so is a rotation that adds to the angle, exactly as in Grover's algorithm, but in a plane that exists for every input.
If the encoded operator is only -close to unitary (a truncated series, say), robust oblivious amplitude amplification still produces an output -close to the ideal one. That is exactly what the simulation algorithm below needs.
Simulation by a truncated Taylor series
Write as a combination of Pauli strings with (signs absorbed), . Split the time into segments with and implement each segment as an LCU (Berry, Childs, Cleve, Kothari & Somma 2015).
Every term is a positive weight times a unitary (a phase times a product of Pauli strings): an LCU.
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.
The factorial makes the tail super-exponentially small: suffices.
Each segment uses three LCU applications (, , ), each with controlled s; segment errors add.
Compare with product formulas, whose cost grows like : the Taylor method pays only , an exponential improvement in precision, at the price of ancilla qubits and the cost of and . Note also the parameter: cost scales with , the 1-norm of the Pauli coefficients, which can greatly exceed .
Key takeaways
- A block encoding places in the top-left block of a unitary; post-selection succeeds with probability , and .
- LCU: block-encodes with normalization , the key cost parameter.
- Oblivious amplitude amplification boosts input-independent success amplitudes with ancilla reflections only: rotates by .
- Truncated Taylor series plus OAA simulates with 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.
is block-encoded by over its Pauli strings. What is the normalization ?
Show the answer
B.
Signs are absorbed into the unitaries ( is unitary), so .
Why can't ordinary amplitude amplification boost the success probability of an LCU applied to an unknown input ?
- The LCU success amplitude is already too large
- Amplitude amplification requires intermediate measurements
- It only works for search problems
- It needs a reflection about the initial state , which depends on the unknown
Show the answer
D. It needs a reflection about the initial state , which depends on the unknown
Reflecting about requires preparing that state, i.e. having available. OAA replaces it by the input-independent ancilla reflection, valid because the success amplitude is the same for all inputs.
In the truncated-Taylor-series algorithm, why are the segments chosen so that the LCU normalization is 2?
- Then , and one round of OAA rotates to : each segment succeeds (almost) deterministically
- The Taylor series of only converges for
- Because exactly two ancilla qubits are used
- To make the truncation order independent of
Show the answer
A. Then , and one round of OAA rotates to : each segment succeeds (almost) deterministically
With normalization 2 the success amplitude is , so and produces amplitude .
is an -block encoding of and an -block encoding of . Applying then on separate ancilla registers block-encodes
- with normalization
- with normalization
- with normalization , using ancillas
- with normalization
Show the answer
C. with normalization , using ancillas
Projecting both ancilla registers onto gives . 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).