Qubitization (Overview)

LCU gives us a block-encoding of $H$ : a larger unitary $U$ whose top-left block, selected by an ancilla in $|0\rangle$ , equals $H/\lambda$ . The trouble is that $U$ itself is not the time evolution we want — and the post-selected branch succeeds only probabilistically. Qubitization fixes this by building, from any block-encoding, a single unitary walk operator $W$ whose eigenvalues directly encode the spectrum of $H$ , so that powers of $W$ generate the dynamics deterministically.

Starting point: a block-encoding

Assume we have an $(\alpha, m)$ -block-encoding $U$ of $H$ on $m$ ancilla qubits:

\bigl(\langle 0|_a \otimes I\bigr)\,U\,\bigl(|0\rangle_a \otimes I\bigr) = \frac{H}{\alpha},

where $\alpha \ge \lVert H\rVert$ is the normalisation (for an LCU encoding, $\alpha = \lambda$ , the coefficient 1-norm). Write $|G\rangle = |0\rangle_a$ for the "good" ancilla state and let $\Pi = |0\rangle\langle 0|_a \otimes I$ be the projector onto it.

The two-dimensional invariant subspaces

Here is the key structural fact. Let $|\lambda_k\rangle$ be an eigenstate of $H$ with eigenvalue $E_k = \alpha\cos\theta_k$ . Define the reflected ancilla state $Z_\Pi = 2\Pi - I$ . Then the pair

\bigl\{\, |G\rangle|\lambda_k\rangle, \ U|G\rangle|\lambda_k\rangle \,\bigr\}

spans a two-dimensional subspace that $U$ and the reflection $Z_\Pi$ leave invariant. Inside each such block the operator $W = Z_\Pi\,U$ acts as a $2\times 2$ rotation — exactly like a single qubit. This is the origin of the name: the high-dimensional problem decomposes into a direct sum of qubit rotations, one per eigenvalue. (Low and Chuang call this the SU(2) structure of the iterate.)

Eigenphases of the walk operator

Within the block for eigenvalue $E_k$ , the walk operator $W$ rotates by angle $\theta_k$ , so its two eigenvalues are

e^{\pm i\theta_k}, \qquad \theta_k = \arccos\!\left(\frac{E_k}{\alpha}\right).

The spectrum of $H$ is thus mapped, eigenvalue by eigenvalue, onto the phases of the unitary $W$ — and $W$ needs no post-selection, because it is genuinely unitary on the whole space, not just on a projected branch.

From eigenphases to time evolution

We want $e^{-iHt}$ , i.e. the function $E_k \mapsto e^{-iE_k t}$ . But $W$ gives us $\theta_k = \arccos(E_k/\alpha)$ . So we need to implement the function

\cos\theta_k \;\longmapsto\; e^{-i\alpha t \cos\theta_k},

which is a transformation of the eigenphase of $W$ . Applying a suitable sequence of $W$ 's interleaved with single-ancilla rotations realises a polynomial (in $\cos\theta$ ) approximation of $e^{-i\alpha t\cos\theta}$ — and that machinery is precisely quantum signal processing, the subject of the next lesson. Using the Jacobi–Anger expansion of $e^{-i x \cos\theta}$ in Chebyshev polynomials, degree $O(\alpha t + \log(1/\varepsilon))$ suffices.

Cost and significance

Qubitization simulates $e^{-iHt}$ to error $\varepsilon$ with

O\!\left(\alpha t + \log(1/\varepsilon)\right)

queries to the block-encoding $U$ . This is optimal: it matches the known lower bounds, achieving both the additive-in- $\log(1/\varepsilon)$ accuracy of LCU and a query count linear in $\alpha t$ with no hidden Trotter blow-up. The price is the block-encoding ancillas and the SELECT/PREPARE overhead inherited from LCU.

Takeaways

Any block-encoding of $H$ yields a unitary walk operator $W = Z_\Pi U$ .
$W$ splits the space into 2D qubit-like blocks, one per eigenvalue $E_k$ .
$W$ has eigenphases $\pm\arccos(E_k/\alpha)$ — the spectrum of $H$ lives in the phase of $W$ .
Transforming those phases (via QSP) yields $e^{-iHt}$ with optimal $O(\alpha t + \log 1/\varepsilon)$ cost.