Linear Combination of Unitaries (LCU)

Product formulas multiply unitaries together. The linear combination of unitaries (LCU) technique does something a quantum computer cannot do directly: it adds unitaries. A sum $\sum_\ell \alpha_\ell U_\ell$ is generally not unitary, so we cannot just run it as a circuit. LCU implements it anyway, with the help of an ancilla register and a post-selected measurement.

Why we want sums of unitaries

Most Hamiltonians are already given as a weighted sum of unitaries — a Pauli decomposition,

H = \sum_{\ell=1}^{L} \alpha_\ell P_\ell, \qquad \alpha_\ell > 0,\ P_\ell \in \{I, X, Y, Z\}^{\otimes n}.

Each Pauli string $P_\ell$ is itself unitary. If we can apply the operator $H$ — or a function of it, such as a truncated Taylor series of $e^{-iHt}$ , which is again a sum of unitaries — we have a route to simulation that never invokes the product structure of Trotter.

The two ingredients: PREPARE and SELECT

LCU uses an ancilla register of $\lceil \log_2 L \rceil$ qubits and two oracles.

PREPARE encodes the coefficients into ancilla amplitudes. Writing $\lambda = \sum_\ell \alpha_\ell$ ,

\text{PREPARE}\,|0\rangle_a = \frac{1}{\sqrt{\lambda}} \sum_{\ell} \sqrt{\alpha_\ell}\,|\ell\rangle_a.

SELECT applies the $\ell$ -th unitary to the system, controlled on the ancilla holding $\ell$ :

\text{SELECT} = \sum_{\ell} |\ell\rangle\langle\ell|_a \otimes U_\ell.

The LCU circuit

The recipe is PREPARE, then SELECT, then PREPARE $^\dagger$ :

W = (\text{PREPARE}^\dagger \otimes I)\,\text{SELECT}\,(\text{PREPARE} \otimes I).

Apply $W$ to $|0\rangle_a |\psi\rangle$ and project onto the branch where the ancilla returns to $|0\rangle_a$ . A short calculation gives

\bigl(\langle 0|_a \otimes I\bigr)\,W\,\bigl(|0\rangle_a \otimes |\psi\rangle\bigr) = \frac{1}{\lambda} \sum_\ell \alpha_\ell U_\ell\,|\psi\rangle.

So conditioned on measuring the ancilla in $|0\rangle$ , the system carries the desired combination $\sum_\ell \alpha_\ell U_\ell$ applied to $|\psi\rangle$ , divided by the normalisation $\lambda$ . This is exactly a block-encoding: $W$ contains $\tfrac{1}{\lambda}\sum_\ell \alpha_\ell U_\ell$ in its top-left block.

Success probability and amplification

The good branch occurs with probability

p_{\text{success}} = \frac{\bigl\lVert \sum_\ell \alpha_\ell U_\ell\,|\psi\rangle\bigr\rVert^2}{\lambda^2}.

For a single application this can be small, but oblivious amplitude amplification boosts it to near 1 with only $O(\lambda)$ repetitions of $W$ — without needing to know $|\psi\rangle$ . The normalisation $\lambda = \sum_\ell \alpha_\ell$ , the 1-norm of the coefficients, is therefore the key cost parameter of any LCU-based algorithm.

From LCU to simulation

To simulate $e^{-iHt}$ , Childs and Wiebe expand the evolution into a truncated Taylor series,

e^{-iHt} \approx \sum_{k=0}^{K} \frac{(-iHt)^k}{k!},

and substitute the Pauli decomposition of $H$ . Each term is a product of Pauli strings — itself a single unitary — so the whole truncated series is again a sum of unitaries, ready for LCU. Choosing the cutoff $K = O\!\left(\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}\right)$ achieves error $\varepsilon$ . The cost scales as $O(\lambda t)$ in the evolution time and only logarithmically in $1/\varepsilon$ — an exponential improvement over the $O(1/\varepsilon)$ of first-order Trotter.

Cost summary

Ancilla qubits: $O(\log L)$ for the index register (plus a flag for amplification).
Queries: $O(\lambda t + \log(1/\varepsilon))$ to PREPARE and SELECT.
Key parameter: $\lambda = \sum_\ell \alpha_\ell$ , the coefficient 1-norm — smaller is better.

LCU turns "we can only multiply unitaries" into "we can also add them, at the price of an ancilla and a post-selected measurement." The next lesson shows how qubitization removes even the post-selection by turning $W$ into an exactly unitary walk operator.