Algorithm Zoo · Primitives
Linear Combination of Unitaries (LCU)
First described: Childs, Wiebe, 2012
The problem
Implement a non-unitary linear combination A = Σ αi Ui of unitaries.
Prepare an ancilla register encoding the coefficients (PREP), apply controlled Ui (SELECT), unprepare (PREP†). Measuring 0 on the ancilla heralds successful application of A/||α||₁. Backbone of Hamiltonian simulation, QSVT block encodings, ground-state algorithms.
Best classical
n/a (primitive)
Quantum complexity
O(log L) ancillas + cost(PREP) + cost(SELECT) for L unitaries
Our verdict
The 'addition' for the unitary world. Every modern quantum algorithm has LCU somewhere underneath. Getting the PREP cost down via structured decompositions of the coefficient vector is where real-chemistry resource estimates have shaved orders of magnitude over the past five years.
When to use it
- Anytime you need to apply a sum of unitaries — chemistry Hamiltonians, polynomial expansions.
- Inside QSVT to build block encodings of weighted matrix sums.
- When oblivious amplitude amplification gives you a deterministic version with √L savings.
When not to use it
- When L is very large and PREP becomes expensive — chemistry uses double-factorized or tensor-hypercontracted decompositions to keep PREP cheap.
Classical baseline
n/a
Hardware cost
log₂(L) ancillas; PREP and PREP† together cost O(L) gates in the naive case but much less with structured coefficients. SELECT is the dominant cost.
Key papers
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations ↗
Childs, Wiebe · 2012 · Quantum Information & Computation
Deep-dive tutorials
Last verified: 2026-05-24