Lower Bounds for Hamiltonian Simulation
The provable limits on how efficiently any quantum algorithm can simulate time evolution, and why optimal algorithms exist.
Why lower bounds matter
Upper bounds tell us how well the best-known algorithm performs; lower bounds tell us how well any algorithm could ever perform. When the two match, an algorithm is optimal, no future cleverness will beat it asymptotically. Hamiltonian simulation is a rare case where matching bounds are known.
The no-fast-forwarding theorem
Any algorithm simulating evolution for time t under a generic Hamiltonian must make a number of queries growing at least linearly in t. If sublinear-in-t simulation were possible for all Hamiltonians, one could compress arbitrarily long evolution, which would let quantum computers solve problems (such as certain unstructured search tasks) faster than known lower bounds permit. Hence no generic fast-forwarding.
The precision term
A separate bound governs precision: the dependence on the error epsilon cannot be better than logarithmic, roughly log(1/epsilon) / log log(1/epsilon). This reflects the information-theoretic cost of resolving the propagator finely.
- Time: at least linear in t (no-fast-forwarding).
- Precision: at least logarithmic in 1/epsilon.
- Combined optimal scaling: O(t + log(1/epsilon)) queries.
- Sparsity and norm enter through the block-encoding subnormalization alpha.
Matching algorithms
Qubitization and quantum signal processing achieve query complexity O(alpha t + log(1/epsilon)), matching both lower bounds simultaneously. This is why they are called optimal: the additive combination of a linear time term and a logarithmic precision term is the best possible. Product formulas fall short on the precision term (polynomial in 1/epsilon), and Taylor/LCU methods reach near-optimal but with larger overhead.
Special structure escapes the bound
The no-fast-forwarding theorem applies to generic Hamiltonians. Special cases can be fast-forwarded: commuting Hamiltonians, quadratic (free-fermion or Gaussian) systems, and certain integrable models admit sublinear-in-t simulation. Recognizing when a target Hamiltonian has such structure can yield large speedups, which is a practical reason to analyze a problem's algebraic structure before choosing an algorithm.