Hamiltonian simulation: Trotter, Taylor series and qubitization compared

Definition

Hamiltonian simulation is the problem of approximating the unitary e to the minus i H t. H is a Hamiltonian, t is a real evolution time, and the approximation is measured in a stated norm, usually the spectral norm, to an error ε. The algorithm does not, by itself, return an energy. It returns a circuit that acts like the evolution, up to that error, so that some other routine can use the circuit.

What "a circuit" costs depends on how H is handed to the computer. A sum of local terms, a linear combination of unitaries, a sparse matrix given by an oracle, and a block encoding are different input models. A bound proved in one of them is not a bound in the others. The pages that call this routine, quantum phase estimation, VQE, and HHL, each assume one of those models and then spend the unitary on a different question.

Lloyd's 1996 paper is the first explicit quantum algorithm this library cites for the problem. Its abstract states that Feynman's 1982 conjecture is correct: a quantum computer can be programmed to simulate any local quantum system. Childs, Su, Tran, Wiebe, and Zhu describe that algorithm as a product formula. If H is a sum of terms and each term acts on a constant number of qubits, a short-time evolution is approximated by the product of the evolutions under the individual terms, and a long time is a repetition of that short step. Lloyd's paper is the existence result for local systems. The step counts below are the later theorems.

Intuition

If two terms of H commute, the exponential of the sum is the product of the exponentials. If they do not, the product is wrong by an amount that grows with the square of the time step, and with the commutator. Taking many short steps drives that error down. That is the Lie–Trotter, or first-order, product formula. Suzuki's 1991 paper gives a product formula of every positive order. The abstract states two facts this page uses. The formula of order m reproduces the exponential of x times (A plus B) with an error of order x to the power m plus 1. And for every order m at least 3, any finite formula of that order has at least one negative coefficient. A negative coefficient is a step that runs a term backwards in time. Childs and coauthors record the stage count of Suzuki's order-2k formula as 2 times 5 to the power k minus 1. Each stage is one pass over the terms. The formula itself uses no ancilla qubits.

A different idea expands the exponential as a Taylor series and truncates it. The truncation is a sum of products of the terms, and a sum of unitaries can be applied by preparing a superposition of the coefficients and selecting the corresponding unitary. Berry, Childs, Cleve, Kothari, and Somma do this for short segments of the evolution, then use a robust form of oblivious amplitude amplification so that the segment succeeds. The reason the error can be logarithmic is the factorial in the Taylor remainder: once the segment is short, a truncation order that grows like the log of one over the error is enough.

Quantum signal processing takes a third route. A unitary whose eigenvalues encode the eigenvalues of H is interleaved with single-qubit rotations. The rotations are chosen so that the eigenvalues are transformed by a polynomial, and the polynomial is chosen to approximate the exponential. Low and Chuang's 2017 paper does this for a sparse Hamiltonian. Their 2019 paper isolates the step they call qubitization: controlled applications of the block-encoding oracles embed H in an invariant two-dimensional subspace, one subspace for each eigenvector, so the same single-qubit polynomial applies. The exponential is one choice of polynomial. Other functions of H use the same walk.

Complexity

These are bounds in a named access model. They are not one query complexity that can be copied from a table into a molecule, and they are not a count of gates until someone has compiled the oracle.

Childs, Su, Tran, Wiebe, and Zhu, Theorem 11, bound the error of a product formula by nested commutators of the summands rather than by a power of the sum of the norms. Corollary 12 is the step count this page quotes. They state it for anti-Hermitian summands, the convention in which the evolution operator is the exponential of t times the sum. For the Schrödinger form, each term is multiplied by minus i. That factor has absolute value 1, so it does not change the norms of the nested commutators. For a pth-order formula, the number of steps r that brings the error to order ε is on the order of α_comm to the power 1/p, times t to the power 1 plus 1/p, divided by ε to the power 1/p. The quantity α_comm is the sum, over every way of nesting p plus 1 of the summands, of the norm of that nested commutator. At constant error, a large enough order makes the step count α_comm to a power o(1), times t to a power 1 plus o(1). Lemma 6 is the older bound they compare with, in which the same power falls on the sum of the norms instead of on the commutators. When the terms nearly commute, Corollary 12 is the tighter one.

They are explicit that the proof of Theorem 11 does not evaluate the constant prefactor. Section 5 compares the bound numerically with the Heisenberg model and reports that, for an even-odd ordering, their fourth-order analysis overestimates the gate count of that example by a factor of about 5. That factor is a numerical observation about one model, not a universal constant.

For a k-local Hamiltonian on n qubits they then estimate the gate count, at constant error and large order, as n to the k, times the induced 1-norm of H, times the ordinary 1-norm to a power o(1), times t to a power 1 plus o(1). The induced 1-norm can be much smaller than the 1-norm. For power-law interactions that decay faster than the spatial dimension, they record a gate count on the order of n to the 2 plus o(1), times t to the 1 plus o(1). The same section says this scaling can be faster than qubitization for those Hamiltonians. The comparison is asymptotic and inside their accounting. It is not a claim that a compiled chemistry circuit should prefer Trotter at every size.

Berry, Childs, Cleve, Kothari, and Somma treat H as a sum of α_ℓ times a unitary H_ℓ. They break the time into segments and truncate the Taylor series of each segment at an order on the order of log of (r over ε), divided by log log of (r over ε), provided the number of segments r is at least the norm of H times t. They state that the simulation complexity is the quantity T, defined as the sum of the α_ℓ times t, multiplied by a factor logarithmic in one over ε. In the gate-count paragraph they take the number of segments on the order of T. Low and Chuang, summarizing that algorithm in 2019, write the query count as the 1-norm of the coefficients times t, times log of that quantity over ε, divided by log log of the same ratio. This page uses Berry and coauthors for the statement that the cost is T times a logarithm, and uses the 2019 summary when a query formula is required.

Low and Chuang, 2017, Theorem 3, is the sparse-oracle bound. A d-sparse Hamiltonian on n qubits, with matrix elements specified to m bits, can be simulated for time t to error ε, with success probability at least 1 minus 2ε, using a number of queries on the order of t d times the largest absolute entry, plus the log of one over ε divided by the log log of one over ε, together with an additional gate factor on the order of n plus m times a polylog of m. The paragraph after the theorem says this additive form is valid when the time parameter τ is on the order of that logarithmic term, and that this is a stronger range than earlier analyses which took τ constant. Their 2019 paper, looking back at this result, says the precise tradeoff sits between a lower bound of τ plus that logarithmic term and an upper bound of τ plus log of one over ε, and that writing the sum as if it were automatic for every intermediate pair of τ and ε is not what the bound says. The no-fast-forwarding theorem is why the τ term cannot be removed.

Low and Chuang, 2019, Theorem 1, changes the input. The Hamiltonian is the block of a unitary: the matrix element of that unitary against a state prepared by a second unitary. In that normalization the norm of H is at most 1. The theorem says that the exponential of minus i H t can be simulated to spectral-norm error ε, with failure probability on the order of ε, using a number of queries Q on the order of t plus log of one over ε. The exact Q they minimize is the smallest positive integer whose factorial truncation meets the error, and they state that this minimum is on that order. The qubit total is the log of the dimension, plus the log of the ancilla dimension of the encoding, plus 2. The abstract describes the overhead beyond the encoding as at most two extra qubits.

Lemma 5 says what a linear combination of unitaries actually encodes. If H is the sum of α_j times a unitary, the prepare and select oracles encode H divided by the 1-norm of the coefficients. Simulating the physical H for time t is therefore Theorem 1 applied for time equal to that 1-norm times t. Lemma 6 is the sparse version of the same fact: the oracles encode H divided by d times the largest absolute entry, using a constant number of queries to the sparse oracles. The query count picks up that factor in front of t. Neither lemma compiles the prepare and select circuits. For a list of d Pauli terms, the paper says the prepare oracle costs on the order of d primitive gates and the select oracle costs on the order of d times the cost of one term.

Access	Result quoted here	Dependence on ε
Sum of terms, product formula of order p	Corollary 12 of Childs et al. 2021: steps on the order of α_comm to the 1/p, times t to the 1 plus 1/p, over ε to the 1/p	Polynomial
Linear combination of unitaries, truncated Taylor series	Berry et al. 2015: T times a factor logarithmic in 1/ε, with T the sum of the coefficients times t	Logarithmic
d-sparse oracle	Theorem 3 of Low and Chuang 2017, in the regime they state	Additive, log over log log
Block encoding of norm at most 1	Theorem 1 of Low and Chuang 2019: queries on the order of t plus log of 1/ε	Additive logarithm

Applications and limits

The chemistry proposal in this library is Aspuru-Guzik, Dutoi, Love, and Head-Gordon: prepare an approximate ground state, simulate the molecular Hamiltonian, and read the phase. The overlap hypothesis and the precision bound are on the phase estimation page. The simulation cost is the cost of the controlled powers that page assumes. VQE is the later algorithm that drops the long coherent evolution and estimates an expectation value with many short preparations. That is a change of problem, from approximating the unitary to approximating one number, and it is why VQE has no proved runtime of the kind in the table above.

HHL calls the same subroutine on a sparse Hermitian matrix and then inverts the eigenvalues. The simulation cost that page quotes is the one Harrow, Hassidim, and Lloyd attribute to the sparse product-formula literature they cite. This page does not replace that quotation. Linear systems keeps the output-state limit next to it.

The chemistry topic is where the comparison among phase estimation, VQE, and simulation is kept. A recent product-formula result for atomic orbitals is the digest on Günther and Harrow. In their class of molecular Hamiltonians, with a constant number of orbitals per atom and a fixed minimum distance between nuclei, Theorem 8 gives a three-dimensional gate count of N to the 5/3, times t, times (N t over ε) to a power o(1), in depth N to the 2/3 times the same factors, and with no ancilla. That is a theorem about that class. It is not a gate count for an arbitrary basis set, and they say they did not investigate the system size at which the scaling outweighs the overhead.

Open problems

The asymptotic comparison between product formulas and qubitization is not a decision procedure for a molecule of practical size. Childs and coauthors show that commutator scaling can beat the general qubitization bound for some structured Hamiltonians, and they leave the constant in Theorem 11 unevaluated. Günther and Harrow show a sublinear-depth Trotter algorithm for one atomic-orbital class, and they explicitly leave the crossover against qubitization, including constants and logarithmic factors, as future work. A page that picks a winner for chemistry from the big-O column has gone past both papers.

Compiling the oracle is open in a different sense. Jordan–Wigner turns a fermionic Hamiltonian into a linear combination of Pauli operators, which is an input Lemma 5 accepts, and the number of terms and the weight of each Pauli are then part of the gate count. The query theorems do not do that compilation. A sparse oracle that, given a row, returns the nonzero entries is a different compilation, and it is the one HHL assumes.

The additive logarithmic dependence on ε matters when simulation is a subroutine of phase estimation, because the phase has to be precise. It does not remove the hypothesis on the phase estimation page that the prepared state has an overlap which is not exponentially small. Berry and coauthors outline a discretization for time-dependent Hamiltonians. The query theorems quoted in the table are for time-independent H. A time-dependent molecular Hamiltonian, or a Hamiltonian that changes because a control pulse changes, is not covered by copying Theorem 1.

Reading the source

Read Lloyd's abstract for the claim that local quantum systems can be simulated, and read Childs et al., section 1.1, for the product-formula description of that algorithm before quoting a step count from 1996. Read Suzuki's abstract for arbitrary order and for the negative-coefficient theorem. Read Berry, Childs, Cleve, Kothari, and Somma for the truncated Taylor series and for the statement that the complexity is T times a logarithm. Read Low and Chuang 2017, Theorem 3, together with the paragraph that states the regime, before dropping the log-log into an arbitrary time. Read Low and Chuang 2019, Theorem 1 and Lemmas 5 and 6, before treating a block encoding and a Pauli list as the same oracle. Read Childs et al., Theorem 11 and Corollary 12, and their warning about the constant prefactor, before using the commutator step count as a compiled gate count. The digest is the account of the October 2026 atomic-orbital preprint.