Quantum Simulation

Linear Combination of Unitaries (LCU)

A technique to implement a weighted sum of unitaries on a quantum computer using select and prepare oracles plus ancilla qubits.

The idea

Many useful operators are not unitary but can be written as a sum M = sum_j a_j U_j of unitaries with positive coefficients a_j. The LCU method (Childs and Wiebe) implements such a sum probabilistically using two building blocks: a PREPARE oracle and a SELECT oracle, coordinated with ancilla qubits.

PREPARE and SELECT

Kronos motion — quantum verdict

PREPARE maps |0> on the ancilla to sum_j sqrt(a_j / lambda) |j>, encoding the coefficients as amplitudes, where lambda = sum_j a_j.
SELECT applies U_j to the system conditioned on the ancilla being |j>: SELECT = sum_j |j>
The sequence PREPARE^dagger . SELECT . PREPARE, followed by projecting the ancilla onto |0>, applies M / lambda to the system.

Success probability and amplification

The projection onto the all-zero ancilla succeeds with probability related to ||M|psi>||^2 / lambda^2. Because lambda can be large, direct success may be unlikely, so LCU is combined with amplitude amplification to boost the success probability, or with oblivious amplitude amplification when M is (nearly) unitary.

LCU for time evolution

To simulate e^(-iHt), expand it in a truncated Taylor series: e^(-iHt) is approximately sum over k of (-it)^k H^k / k!. Writing H = sum_l c_l P_l as Paulis makes each H^k a sum of unitary Pauli products, so the whole series is an LCU. Truncating at order K = O(log(1/epsilon) / log log(1/epsilon)) gives the celebrated logarithmic dependence on precision.

Why it matters

LCU achieves error scaling of O(log(1/epsilon)), exponentially better in precision than product formulas, at the cost of ancilla qubits and more complex control. It is the conceptual root of Taylor-series simulation and a stepping stone to qubitization, which reframes the same select-and-prepare structure to walk through the spectrum of H optimally. LCU is a general primitive: beyond simulation it implements matrix functions, filters, and linear-systems solvers.