Quantum Algorithms Database
Linear Combination of Unitaries (LCU)
A general technique for implementing operations that aren't directly unitary by expressing them as a weighted combination of simpler unitary operations.
Year
2012
Inventor(s)
Andrew Childs and Nathan Wiebe; extended by Dominic Berry, Andrew Childs, Richard Cleve, Robin Kothari, and Rolando Somma
Speedup Type
Exponential Speedup
Difficulty
★★★★★
Overview
Quantum gates must be unitary, which means they preserve probabilities. But many useful mathematical operations are not unitary, for example a sum of unitary operations or a polynomial of a matrix. The linear combination of unitaries, or LCU, technique lets a quantum computer apply such a sum of unitaries probabilistically, with the help of an ancilla register, and with a success probability that can be boosted to nearly 1.
LCU is not an algorithm for a specific problem. It is a design tool, and it is the foundation of several of the most efficient algorithms for simulating physical systems, including the Taylor-series method for Hamiltonian simulation and the block-encoding technique that underlies quantum singular value transformation.
The problem it solves
Many useful mathematical operations in quantum simulation and algorithms aren't directly realizable as quantum gates (which must be unitary) — LCU provides a way around this.
History and background
Childs and Wiebe introduced LCU in 2012 in a paper called Hamiltonian Simulation Using Linear Combinations of Unitary Operations. Their goal was to improve the precision of Hamiltonian simulation beyond what product formulas, such as Trotter-Suzuki, can deliver. They expressed the evolution operator as a sum of simple unitary terms and implemented that sum directly.
In 2014 and 2015, Berry, Childs, Cleve, Kothari, and Somma developed the technique into an algorithm for simulating sparse Hamiltonians with a cost that grows only logarithmically in the inverse of the target error, an exponential improvement in precision over earlier methods. Their key tool was oblivious amplitude amplification, which boosts the success probability without knowing the input state. Later, Low and Chuang's qubitization and Gilyén and coauthors' block-encoding framework used the same ideas, and Babbush and colleagues applied them to chemistry in 2018.
How it works
Decomposes a desired (possibly non-unitary) operation into a weighted sum of unitary operations, implementing it probabilistically using extra ancilla qubits and post-selection.
Suppose you want to apply an operator A that is a weighted sum of unitaries, A equal to the sum over i of alpha sub i times U sub i, with positive weights. You cannot apply A directly because it is not unitary. But you can apply each U sub i, and you can prepare a superposition of the index i with amplitudes proportional to the square roots of the weights.
The trick is to use an ancilla register that stores the index i. First, a PREPARE operation puts the ancilla into a superposition with amplitudes proportional to the square root of alpha sub i. Then a SELECT operation applies U sub i to the system, controlled on the ancilla being in state i. Finally, the inverse of PREPARE is applied. If the ancilla is then found in the all-zeros state, the system has been acted on by A divided by the total weight.
The probability of that outcome is smaller than 1, since A divided by the total weight has norm less than 1. When A is nearly unitary, as in Hamiltonian simulation, oblivious amplitude amplification boosts the success probability to nearly 1 with a small number of rounds, and the final result is an almost exactly unitary operation.
Step by step
- Write the target operator as a sum of unitaries, A equal to the sum of alpha sub i times U sub i, and compute the total weight alpha, the sum of the alpha sub i.
- Build the PREPARE circuit, which maps the ancilla's zero state to the superposition of indices i with amplitudes equal to the square root of alpha sub i over alpha.
- Build the SELECT circuit, which applies U sub i to the system when the ancilla register holds the index i.
- Apply PREPARE, then SELECT, then the inverse of PREPARE.
- Measure the ancilla. If it is in the zero state, the system has been transformed by A over alpha. Otherwise the attempt failed.
- Use oblivious amplitude amplification, or repeat until success, to make the transformation deterministic when A is close to unitary.
A worked example
Take A equal to one half of the identity plus one half of the Pauli X gate. That is the average of two unitaries, so alpha is 1. The PREPARE circuit is a Hadamard on a single ancilla qubit. SELECT applies X to the system when the ancilla is 1. After the inverse PREPARE, the ancilla is 0 with probability that depends on the input state, and the system has been acted on by A.
For Hamiltonian simulation of a molecule, the Hamiltonian is a sum of thousands of Pauli strings with coefficients. The Taylor series for e to the minus i H t is a sum of products of Pauli strings with computable weights. LCU applies that truncated series directly, with a cost that depends on the total weight of the Hamiltonian and grows only slowly with the desired accuracy.
Complexity and resources
| Item | Detail |
|---|---|
| Success probability | About the square of the ratio of the operator's norm to the total weight, boosted by amplitude amplification |
| Hamiltonian simulation (Taylor series) | O(tau log(tau over epsilon) over log log(tau over epsilon)) queries for evolution time t and norm scale tau |
| Dependence on precision | Logarithmic in 1 over epsilon, an exponential improvement over product formulas |
| Ancilla qubits | About log of the number of terms in the sum |
| Key subroutines | State preparation of the weight distribution and a controlled selection of unitaries |
What hardware it needs
- Fault-tolerant hardware, since the PREPARE and SELECT circuits are deep.
- Efficient circuits for loading the weight distribution, often through lookup tables or QROM.
- Ancilla qubits to hold the index register.
Applications
- Hamiltonian simulation with high precision, including for molecules and materials.
- Implementing polynomials and other functions of matrices, as in quantum linear systems algorithms.
- Block-encoding of matrices, which is the entry point to quantum singular value transformation.
- Preparing ground states and thermal states through filtering and projection techniques.
Limitations and caveats
- The cost depends on the total weight alpha, which can be large for Hamiltonians with many terms.
- The circuits are deep, so it is a fault-tolerant technique, not one for noisy devices.
- It needs access to the coefficients and the unitaries as efficiently implementable circuits.
Common misconceptions
- LCU does not violate the unitarity of quantum mechanics. The non-unitary operation is applied only on the successful branch.
- It is not a standalone algorithm. It is a primitive that other algorithms use.
How it compares
- Trotter-Suzuki decompositions are simpler and work well on near-term devices but have worse precision scaling.
- Quantum signal processing and qubitization achieve optimal complexity using block-encodings that are often built by LCU.
- Randomized compilers such as qDRIFT use the same idea of sampling from a sum of terms but accept some random error.
Real-world impact
An important theoretical tool underlying modern quantum simulation algorithms, including advanced techniques for simulating quantum chemistry and physics beyond basic Trotterization.
Why it matters
LCU turned the question of what operations a quantum computer can perform into a more flexible one. It is part of the toolkit behind the current best algorithms for chemistry simulation, where its logarithmic dependence on precision is crucial.
For students, it is also a clean illustration of how to implement something that looks non-unitary using unitaries plus measurement, a recurring idea in quantum algorithms.
Frequently asked questions
What is linear combination of unitaries?
A technique for implementing a weighted sum of unitary operations on a quantum computer using an ancilla register and a measurement.
Why is it useful?
It lets you apply operators that are not directly unitary, such as sums or polynomials of matrices, and it gives high precision in Hamiltonian simulation.
What are PREPARE and SELECT?
PREPARE creates a superposition over term indices with the right weights. SELECT applies the chosen unitary to the system conditioned on the index.
What is oblivious amplitude amplification?
A variant of amplitude amplification that boosts the success probability of a transformation without needing to know or disturb the input state.
Does it work on current hardware?
Not for large problems. It needs deep circuits and is intended for fault-tolerant machines.
Keep learning
- Related algorithm: Quantum Signal Processing (QSP)
- Related algorithm: Quantum Singular Value Transformation (QSVT)
- Related algorithm: Trotter-Suzuki Decomposition
- Related algorithm: HHL Algorithm
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.