Hamiltonian Simulation Algorithms

Hamiltonian simulation constructs a quantum operation approximating $e^{-iHt/\hbar}$. Different algorithms use different ways of supplying the Hamiltonian: executable term exponentials, sparse-entry oracles, selected unitaries, or a block encoding. Their costs can be compared only after specifying those operations and the desired accuracy. An efficient simulation prepares coherent dynamics; it does not print the exponentially many amplitudes of a wavefunction.

This page develops query bounds and finite error estimates for the main algorithm families. Hamiltonian simulation explains how the resulting evolution is used in a physical calculation. Detailed constructions appear in Trotter–Suzuki methods and qubitization and quantum signal processing.

Helpful background. Query complexity distinguishes a call to an input operation from the gates needed to implement it. Algorithmic primitives introduces coherent selection and block encodings.

Hamiltonian evolution and its error

Let $H=H^\dagger$ act on a finite-dimensional system space, let $t\in\mathbb R$, and let $0<\epsilon<1$. With no extra output registers, a useful target is a unitary $\widetilde U$ satisfying

$$U_H(t)=e^{-iHt/\hbar}, \qquad \|\widetilde U-U_H(t)\|_{\mathrm{op}}\leq\epsilon.$$

The operator norm bounds the state-vector error for every normalized input, including inputs entangled with an untouched reference. It also composes: a sequence of $Q$ unitary operations, each approximated to error $\eta$, has total operator error at most $Q\eta$. Controlled evolution needs the correct relative phase between control branches, even when an overall phase would be invisible in an uncontrolled experiment.

Ancillas require a more precise description. If a unitary circuit $V$ starts its ancillas in $|0^a\rangle$, define its successful block

$$B=(\langle0^a|\otimes I)V(|0^a\rangle\otimes I).$$

A bound $\|B-U_H\|\leq\delta$ implies success probability at least $(1-\delta)^2$ on every input. But it does not give the same bound on the full state before measuring or discarding the ancillas. Indeed,

$$\left\|V(|0^a\rangle\otimes I) -(|0^a\rangle\otimes U_H)\right\| \leq\sqrt{2\delta}.$$

To see this, apply the difference to a unit vector: its squared norm is $2-2\operatorname{Re}\langle U_H\psi|B\psi\rangle\leq2\delta$. Thus a coherent use that requires clean ancillas to vector error $\epsilon$ can need a successful-block tolerance of order $\epsilon^2$. A theorem about the reduced-system channel is yet another guarantee; it should be composed in its stated channel or trace norm. Exercise 8 gives an exact example where the square-root difference occurs.

State-specific and local-observable errors can be smaller than a full-unitary error because they ask for less output. Likewise, a bound for an averaged randomized channel need not hold for each sampled circuit. Before applying a result below, identify the Hamiltonian representation, the available controlled and inverse operations, and which of these error guarantees is required. Preparation and measurement remain additional application costs.

Access models and energy normalizations

The normalization multiplying time sets the dimensionless difficulty parameter. Its value depends on how the Hamiltonian is represented, as the first worked example will show.

For term-exponential access, write

$$H=\sum_{\ell=1}^{L}H_\ell$$

and declare which values of $s$ permit coherent implementation of $e^{-iH_\ell s/\hbar}$. A primitive exponential may itself be a large compiled circuit. Controlled and inverse versions are separate capabilities unless the construction proves them at stated cost.

For an LCU interface, absorb coefficient phases into unitary terms and write

$$H = \sum_{\ell=0}^{L-1}\alpha_\ell U_\ell, \qquad \lambda := \sum_{\ell=0}^{L-1}|\alpha_\ell|, \qquad T := \frac{\lambda|t|}{\hbar}.$$

A typical interface includes a coefficient preparation and a multiplexed unitary,

$$\operatorname{PREPARE}|0\rangle = \sum_\ell \sqrt{\frac{|\alpha_\ell|}{\lambda}} |\ell\rangle, \qquad \operatorname{SELECT} = \sum_\ell |\ell\rangle\!\langle\ell|\otimes \widehat U_\ell,$$

where $\widehat U_\ell$ includes the coefficient phase. A SELECT query does not include PREPARE automatically, and neither primitive specifies the gate cost of loading the coefficients or implementing the selected term.

For a block encoding, a unitary $U$ on $a$ ancillas and the system obeys

$$\left\| H - \alpha (\langle0^a|\otimes I) U (|0^a\rangle\otimes I) \right\|_{\mathrm{op}} \leq \delta_{\mathrm{BE}},$$

where $\alpha$ has energy units. The dimensionless action is

$$\tau := \frac{\alpha|t|}{\hbar}.$$

The normalization $\alpha$, ancilla count, block error, and cost of $U$, $U^\dagger$, controls, and signal-state reflections must all be specified. An LCU construction often gives $\alpha=\lambda$, but that equality follows from that construction; it is not a universal identity.

For a sparse black-box interface, let at most $d_{\mathrm{sp}}$ entries in each row be nonzero. A standard pair of reversible oracles has the form

$$O_F|j,\ell\rangle = |j,f(j,\ell)\rangle,$$ $$O_H|j,k,z\rangle = |j,k,z\mathbin\oplus \operatorname{enc}(H_{jk})\rangle.$$

The displayed in-place $O_F$ requires an injective location list for each row, including distinct padding positions, and a reversible permutation extension on the remaining basis states. Its inverse must be available when the construction uses it. A simpler out-of-place oracle $|j,\ell,z\rangle\mapsto|j,\ell,z\mathbin\oplus f(j,\ell)\rangle$ is always reversible, but converting it to the in-place interface can require additional computation. Values must have specified precision and obey Hermitian symmetry, including on padded or invalid indices. With a certified entry bound $h\geq\|H\|_{\max}$, a common sparse construction has normalization of order $d_{\mathrm{sp}}h$ and action

$$\tau_{\mathrm{sp}} := \frac{d_{\mathrm{sp}}h|t|}{\hbar}.$$

The precise constant is construction-dependent. Quantum Oracles explains why a sparse matrix listing, a channel, and a coherent oracle are not equivalent access.

Representation error also consumes simulation accuracy. For Hermitian $H$ and $H'$, if $\|H-H'\|\leq\delta_H$, Duhamel’s formula gives

$$\left\| e^{-iHt/\hbar} - e^{-iH't/\hbar} \right\| \leq \frac{|t|\delta_H}{\hbar}.$$

For example, an approximate block encoding can be treated as an exact encoding of a nearby Hamiltonian only when its encoded block $H'$ is Hermitian. Closeness to a Hermitian matrix alone does not imply Hermiticity. If that condition fails, use an explicit Hermitian construction or a robustness theorem for the actual signal-processing algorithm; simply inserting $\delta_{\mathrm{BE}}$ into the displayed bound is unjustified.

If a circuit uses $Q$ approximate coherent calls, each within operator-norm error $\eta$, unitary telescoping contributes at most $Q\eta$. These terms sit beside algorithmic approximation, phase synthesis, arithmetic, and physical implementation error; none disappears by renaming it a query.

Product-Formula Algorithms

Product formulas use executable exponentials of pieces of $H$. Let $S_p(\Delta)$ be an order-$p$ unitary product for a step of duration $\Delta$, with $m_p$ term exponentials per step. The formal order does not by itself give a finite guarantee. Suppose a cited bounded-operator analysis provides the local certificate

$$\left\| e^{-iH\Delta/\hbar} - S_p(\Delta) \right\| \leq \Gamma_{p+1} \frac{|\Delta|^{p+1}}{\hbar^{p+1}}.$$

Because both factors are unitary, a telescoping sum over $r$ equal steps gives

$$\left\| e^{-iHt/\hbar} - S_p(t/r)^r \right\| \leq \frac{ \Gamma_{p+1}|t|^{p+1} }{ r^p\hbar^{p+1} }.$$

Thus the certificate is met by

$$r \geq \left\lceil \left( \frac{ \Gamma_{p+1}|t|^{p+1} }{ \epsilon\hbar^{p+1} } \right)^{1/p} \right\rceil,$$

with $r\geq1$, before allocating synthesis and representation error. At $t=0$ use the identity directly; if the error coefficient vanishes, a nonzero-time product still uses at least one step. The primitive- exponential count is $m_pr$, subject to any proved boundary merging or parallel schedule. The constant $\Gamma_{p+1}$ is a defined sum or bound on nested commutators. It depends on the decomposition, ordering, locality, and the output being controlled. It must not be replaced by a universal number. Childs, Su, Tran, Wiebe, and Zhu develop general commutator-sensitive bounds and show why structure can be much more informative than a sum of term norms.

For two bounded Hermitian terms, the first-order Lie–Trotter formula has the finite certificate

$$\left\| e^{-i(A+B)t/\hbar} - \left( e^{-iAt/(r\hbar)} e^{-iBt/(r\hbar)} \right)^r \right\| \leq \frac{ t^2\|[A,B]\| }{ 2r\hbar^2 }.$$

This follows from an integral representation of the one-step error and a second telescope. It applies to the full unitary in operator norm; a theorem for a local observable can have different scaling. With exact term exponentials, the ordered product is deterministic—its success probability is one—and the displayed operator norm is its error metric.

Lloyd’s local simulation construction established product splitting as an early digital route. Modern locality-aware algorithms can approach linear spacetime volume for suitable lattice families, but their hypotheses are essential. For example, Haah, Hastings, Kothari, and Low use geometric locality and Lieb–Robinson structure and prove a matched worst-case gate lower bound for their lattice setting. Neither result licenses a universal ranking against a block-oracle algorithm.

Randomized product formulas require another distinction. If $V_\omega$ is the unitary produced by a random ordering, a theorem may bound the averaged channel $\mathbb E_\omega[V_\omega(\cdot)V_\omega^\dagger]$. That guarantee does not say that every sampled $V_\omega$ has the same operator-norm error. The specialist Trotter–Suzuki Methods page develops order selection, locality grouping, compilation, and convergence tests; the Trotter Product Formula derives the operator limit and Suzuki recursion.

Sparse-Oracle and Quantum-Walk Algorithms

Sparse simulation begins with row-computable locations and coherently returnable values, not with a dense array whose zeros happen to be numerous. The location oracle $O_F$ and value oracle $O_H$ must be reversible at a stated bit precision. A query theorem can count a constant number of these calls per walk or block-encoding query while leaving their gate and memory costs outside the query model.

The early sparse algorithms of Berry, Ahokas, Cleve, and Sanders combined decomposition and simulation techniques under black-box sparsity assumptions. Continuous-time Hamiltonian evolution and discrete-time quantum walks are related but not identical interfaces; Childs gives a precise conversion framework rather than treating the two notions of time as interchangeable. Later work by Berry, Childs, and Kothari achieved nearly optimal dependence on sparse action and precision in that oracle setting.

Quantum walk algorithms develops the walk models and their applications to search, detection and hitting. Here the walk is an intermediate operation used to approximate continuous-time Hamiltonian evolution.

For a common sparse-to-signal construction, the relevant action is

$$\tau_{\mathrm{sp}} = \frac{d_{\mathrm{sp}}h|t|}{\hbar}, \qquad h\geq\|H\|_{\max}.$$

This is not generally $\|H\||t|/\hbar$. The factor $d_{\mathrm{sp}}h$ is an access normalization, and it can be loose. A better problem-specific block encoding may have smaller normalization, but its construction and cost must be shown. Conversely, replacing $d_{\mathrm{sp}}h$ by $\|H\|$ inside a sparse query theorem silently changes the interface.

Hermitian-consistent finite-precision values define a nearby Hamiltonian. If value truncation and position errors induce $\|H-H'\|\leq\delta_H$, then $|t|\delta_H/\hbar$ must fit the error budget. It is not enough to state that each matrix entry has $b$ bits: the conversion from entrywise error to operator error can depend on sparsity and dimension.

Modern signal processing can consume the block encoding built from sparse oracles, so “walk method” and “qubitization method” are not necessarily disjoint end-to-end categories. The comparison must identify the primitive at which queries are counted. A sparse-oracle lower bound applies to algorithms using that black box; it does not price a structured arithmetic circuit that computes entries, nor does it show that a physical device needs the same depth. After the sparse-to-standard-form reduction, the Low–Chuang convention below approximates the full-system evolution in its successful ancilla block with spectral-norm error $\epsilon$ and failure probability $O(\epsilon)$; each standard-form signal call must still be expanded into the declared controlled and inverse $O_F,O_H$ calls.

Linear Combinations and Truncated Taylor Series

Linear-combination methods use interference to implement a weighted sum of unitaries. Childs and Wiebe developed Hamiltonian simulation based on linear combinations rather than products. The truncated-Taylor algorithm of Berry, Childs, Cleve, Kothari, and Somma supplies a particularly transparent finite construction for

$$H = \sum_{\ell=0}^{L-1}\alpha_\ell U_\ell, \qquad T = \frac{\lambda|t|}{\hbar}.$$

For $t\neq0$, put $\sigma:=\operatorname{sgn}(t)$. A selected word of Taylor order $k$ carries the phase $(-i\sigma)^k$; negative time therefore uses the $+i$ phases that implement the inverse evolution, not the forward $|t|$ construction. The nonnegative quantities $T$ and $x$ below control only the segment count and tail bound. At $t=0$, the identity circuit suffices.

Divide the evolution into

$$r := \left\lceil \frac{T}{\ln2} \right\rceil$$

equal segments when $T>0$, and define

$$x := \frac{T}{r} \leq \ln2.$$

The positive LCU coefficient sum of the order-$K$ segment is

$$s_K(x) := \sum_{k=0}^{K} \frac{x^k}{k!}.$$

Equal segmentation needs an explicit normalization step: when $x<\ln2$, $s_K(x)$ need not be close to $2$. Let $W_K$ denote the ordinary PREPARE–SELECT–unprepare unitary for the truncated operator $\widetilde U_K$, so its ancilla-zero block is $\widetilde U_K/s_K$. Append a one-qubit compensation rotation $C_K$ with

$$\langle0|C_K|0\rangle = \frac{s_K}{2}.$$

The joint-zero block of $C_K\otimes W_K$ is then exactly $\widetilde U_K/2$; the flag-one component is orthogonal to the joint success projector and contributes zero to that block. Computing and synthesizing $C_K$ to finite precision belongs in every short segment’s error budget. This is the equal-segment version of the extra-ancilla compensation needed for a short residual segment in the original construction; it must be applied to every short segment here, not silently inferred from the Taylor-tail bound.

For one segment, the order-$K$ Taylor approximation has a uniform operator tail bounded by the exact positive scalar tail

$$R_K(x) := e^x - \sum_{k=0}^{K} \frac{x^k}{k!} = \sum_{k=K+1}^{\infty} \frac{x^k}{k!}.$$

The finite prescription is to choose the smallest $K$ satisfying the theorem’s allocated inequality, such as

$$R_K(x) \leq \frac{\epsilon_{\mathrm{tail}}}{C r},$$

where $C$ records the constants introduced by the robust amplification and error composition being used. It is unsafe to choose a numerical $K$ from big-$O$ notation alone. In the usual regime, bounded $x$ gives

$$K = O\!\left( \frac{ \log(r/\epsilon) }{ \log\log(r/\epsilon) } \right), \qquad Q_{\mathrm{SELECT}} = O(rK).$$

For $T\geq1$ and sufficiently small error this is commonly summarized as

$$O\!\left( T \frac{ \log(T/\epsilon) }{ \log\log(T/\epsilon) } \right)$$

SELECT-style queries, with the multiplication by $T$ understood. The finite $r,K$ definition, rather than the shorthand, resolves small arguments and log domains.

The truncated series is not exactly unitary. PREPARE and SELECT first expose it as a block, and robust oblivious amplitude amplification produces a unitary circuit whose ancilla-zero projected branch approximates the desired segment. That step uses PREPARE, PREPARE$^\dagger$, SELECT, SELECT$^\dagger$, and reflections a constant number of times per segment. The cited analysis initializes and discards a fresh ancilla for every segment and bounds the resulting reduced-system trace-norm error by $O(\epsilon)$—equivalently, trace-distance error $O(\epsilon)$ up to the conventional factor $1/2$. It does not assert a full-dilation operator-norm bound. The circuit has no heralded postselection or repeat-until-success step, so deterministic execution of that discard channel is the success convention. Amplitude Amplification explains the general reflection geometry. Coefficient precision, unary order registers, selected-unitary compilation, segment cleanup, and synthesis remain outside a bare SELECT-query count.

Block Encodings, Qubitization, and Quantum Signal Processing

An exact block encoding exposes the normalized Hermitian signal $H/\alpha$, whose spectrum lies in $[-1,1]$. Separate the signed phase from the nonnegative query-cost parameter:

$$\theta := \frac{\alpha t}{\hbar}, \qquad \tau = |\theta| = \frac{\alpha|t|}{\hbar}.$$

Hamiltonian simulation asks for the spectral transformation

$$f(x) = e^{-i\theta x}.$$

Thus $\tau$ controls the query count, whereas $\theta$ retains the sign of time. For $t<0$, the inverse signal-processing sequence implements $e^{+i\tau x}$ rather than reusing the forward-$|t|$ transformation.

The Jacobi–Anger expansion gives one approximation certificate:

$$e^{-i\theta x} = J_0(\theta) + 2\sum_{k=1}^{\infty} (-i)^kJ_k(\theta)T_k(x),$$

so truncating after degree $d$ has uniform scalar error at most

$$2\sum_{k=d+1}^{\infty}|J_k(\theta)|.$$

Qubitization creates the invariant signal subspaces, while quantum signal processing realizes an admissible polynomial with a number of signal queries linear in its degree. For the parity constraints, phase conventions, and signal reflections, see Qubitization and Quantum Signal Processing.

The finite theorem is more informative than an isolated asymptotic slogan. Let

$$L_\epsilon := \log\frac1\epsilon.$$

Handle $\tau=0$ separately. More generally, $\|e^{-iHt/\hbar}-I\|\leq\tau$, so the identity circuit already meets an operator-norm target whenever $\tau\leq\epsilon$. For $\tau>0$, a useful theorem-level degree parameter is

$$q_* := \min\!\left\{ q\geq1: 4\frac{(\tau/2)^q}{q!} \leq \epsilon \right\}, \qquad Q = \Theta(q_*),$$

under the exact coherent block-encoding convention of Low and Chuang. In that published theorem, the successful ancilla block approximates the full-system evolution with spectral-norm error $\epsilon$, and the failure probability is $O(\epsilon)$. This is not a claim of $\epsilon$ error for the entire coherent ancilla output. Up to constant factors, $Q$ counts controlled uses of the standard-form state preparation $G$, signal unitary $U$, and their inverses; the signal reflection is part of the qubitization/QSP step. In the nontrivial regime in which the query count grows, Stirling’s approximation gives the joint form

$$\Theta\!\left( \tau + \frac{ L_\epsilon }{ \log(e+L_\epsilon/\tau) } \right).$$

The earlier signal-processing result of Low and Chuang established optimal Hamiltonian simulation in this polynomial-query framework. The joint formula is important. At fixed error it is $\Theta(\tau)$; at fixed nonzero $\tau$ and high precision it has the familiar $\Theta(L_\epsilon/\log L_\epsilon)$ behavior. It is not uniformly equal to $\Theta(\tau+L_\epsilon/\log L_\epsilon)$ when time and precision scale together.

Query optimality is conditional on the exact signal interface. State whether one query means $U$, controlled-$U$, $U^\dagger$, a state preparation, or a compound qubiterate call. If a coherent application requires clean ancillas, choose the block tolerance correspondingly smaller before applying the query bound. Likewise, the displayed factorial tail controls polynomial truncation; the admissibility and phase-synthesis steps require their own error allocation. Its asymptotic scaling does not prescribe an exact phase-sequence length. For an exact encoding of a nearby Hermitian $H'$, the additional Hamiltonian error is at most $|t|\delta_{\mathrm{BE}}/\hbar$; a general approximate block needs the additional analysis described above. QSP phase computation, phase-bit precision, single-qubit rotation synthesis, signal reflections, and the compiled block oracle contribute gates and depth even when the number of signal queries is optimal.

Interaction-Picture and Time-Dependent Algorithms

Suppose a time-independent Hamiltonian has a declared decomposition $H=A+B$. The interaction-picture residual is

$$B_I(s) := e^{iAs/\hbar} B e^{-iAs/\hbar},$$

and the exact factorization is

$$e^{-i(A+B)t/\hbar} = e^{-iAt/\hbar} \mathcal T \exp\!\left[ -\frac{i}{\hbar} \int_0^t B_I(s)\,ds \right].$$

Unitary conjugation preserves the norm, $\|B_I(s)\|=\|B\|$. This can replace a large normalization associated with $A+B$ by an integrated residual normalization. It is useful only when the new interface is executable: the algorithm needs the final $A$ evolution and coherent time-indexed access to $B_I(s)$. Such access may be supplied as a priced HAM-T oracle or constructed from controlled variable-time $e^{\pm iAs/\hbar}$ and access to $B$.

Let $\alpha_A\geq\|A\|$, $\alpha_B\geq\|B\|$, and $\tau_B=\alpha_B|t|/\hbar$. In the long-time regime $\tau_B=\Omega(1)$, the truncated-Dyson interaction-picture theorem of Low and Wiebe uses

$$O\!\left( \tau_B \frac{ \log(\tau_B/\epsilon) }{ \log\log(\tau_B/\epsilon) } \right)$$

HAM-T queries in its stated regime, together with $O(\tau_B)$ segment-level $A$ evolutions. The successful block approximates the full time-ordered evolution; after the theorem’s segment budgets, its spectral-norm error and its LCU projection failure probability are $O(\epsilon)$. The projected-block and full-ancilla distinction still applies. Under its differentiability and discretization analysis, a sufficient time grid has scaling

$$M = O\!\left( \frac{ |t|(\alpha_A+\alpha_B) }{ \hbar\epsilon } \right).$$

In the standard construction, the gate expansion of each HAM-T query contains clocks, controlled variable-time $A$ evolution, the $B$ oracle, inverses, and precision. Thus the dominant $A$ term moves out of the leading residual query normalization but can remain in polylogarithmic factors and oracle cost. Conjugation also need not preserve the sparsity of $B$ in the computational basis.

For a genuinely time-dependent sparse Hamiltonian, a rescaled Dyson series can replace a maximum-over-time bound by an integrated bound. This theorem is stated for a declared positive duration $t_{\mathrm{dur}}>0$. Define

$$\chi := \frac{d_{\mathrm{sp}}}{\hbar} \int_0^{t_{\mathrm{dur}}} h(s)\,ds, \qquad h(s)\geq\|H(s)\|_{\max}.$$

For a negative-time task, one must separately specify the reversed or inverse time-dependent schedule. In general it is not obtained by replacing the upper limit with $|t|$, because $H(s)$ at positive times does not determine that inverse schedule.

Under the sparse location/value interface plus coherent norm and inverse-clock oracles, and with the stated positive differentiable norm bound, Berry, Childs, Su, Wang, and Wiebe obtain

$$O\!\left( \chi \frac{ \log(\chi/\epsilon) }{ \log\log(\chi/\epsilon) } \right)$$

queries in the theorem’s nontrivial regime. Calling this “$L^1$ scaling” does not remove the norm-evaluation and inverse-change-of-variable oracles, and the display is a multiplicative precision overhead rather than the additive joint QSP bound. The rescaling changes the query action, not the coherent truncated-Dyson output, error, or success convention.

Query Bounds, Optimality, and No-Fast-Forwarding

The word optimal refers to a specified access model and asymptotic regime. The table compares what each method counts; it does not rank their compiled gate costs.

Method and action	Counted operations	Error guarantee and condition
Product formula, commutator-dependent	$m_pr$ term exponentials	Deterministic full-unitary bound; use the proved commutator coefficient.
Taylor LCU, $T=\lambda\lvert t\rvert/\hbar$	$O(rK)$ SELECT calls	Successful-block estimate and reduced-state error after fresh-ancilla discard; robust amplification is included.
Exact block encoding, $\tau=\alpha\lvert t\rvert/\hbar$	$\Theta(q_*)$ controlled signal/preparation calls and inverses	Successful-block spectral error $\epsilon$, failure $O(\epsilon)$; retain the joint time–precision dependence.
Sparse input, $\tau_{\mathrm{sp}}=d_{\mathrm{sp}}h\lvert t\rvert/\hbar$	Location/value calls through the proved reduction	Same successful-block convention after signal processing; oracle implementation remains additional.
Interaction picture, residual action	Truncated-Dyson HAM-T calls	Successful-block error and failure $O(\epsilon)$; variable-time $A$ evolutions and clocks remain necessary.

Worst-case no-fast-forwarding says that linear dependence on normalized time cannot be removed for general black-box Hamiltonian families with the matched output and error convention. The sparse lower-bound program culminating in Berry, Childs, and Kothari also exposes the high-precision obstruction. These are family lower bounds: an adversary chooses a hard oracle within the promise. They do not say that every diagonal, commuting, free, integrable, geometrically local, low-energy, or otherwise structured Hamiltonian requires linear physical depth.

A claimed fast-forwarding method must price any basis change, eigenvalue arithmetic, coherent controls, and data access. It must state every structural promise. In a promise problem the algorithm may assume that promise without verifying it; verification is charged only when it is performed or included in the claimed workflow, and otherwise the promise must be labeled assumed and unverified.

Precision lower bounds also require care. The $L_\epsilon/\log L_\epsilon$ shorthand describes a high-precision slice, not a uniform replacement for the joint QSP expression. Conversely, a product formula’s polynomial dependence on $1/\epsilon$ under a coarse norm bound does not show that every structured product formula is asymptotically inferior. There is no access-independent fastest simulation method.

See lower bounds and limitations for the additional assumptions needed to turn a query lower bound into a gate, depth or runtime statement.

From Oracle Queries to Executable Resources

A query theorem becomes an implementation claim only after every ideal call is expanded. A schematic logical-gate count is

$$G_{\mathrm{total}} = \sum_j Q_jG_j + G_{\mathrm{control}} + G_{\mathrm{arithmetic}} + G_{\mathrm{synthesis}} + G_{\mathrm{cleanup}},$$

where $Q_j$ counts each query species and $G_j$ is its compiled logical cost. Depth requires a separate dependency and parallelism analysis; it is not the sum of gates. Fault-tolerant spacetime cost additionally depends on the gate alphabet, rotation synthesis, code, target logical failure, factory throughput, and routing.

For product formulas, expand every $e^{-iH_\ell s/\hbar}$ and every control. For LCU, price coefficient loading, PREPARE and its inverse, SELECT and its inverse, reflections, work registers, and robust amplification. For sparse access, price the reversible computation or memory that realizes positions and values. For qubitization, price the block encoding, inverse, signal reflection, phase sequence, and synthesized rotations. For interaction-picture algorithms, price the clock, HAM-T construction, variable-time $A$ evolutions, $B$ access, and norm or inverse-clock arithmetic.

For a fixed full-isometry operator-norm target, a conservative composition is

$$\epsilon_{\mathrm{total}} \leq \epsilon_{\mathrm{alg}} + \frac{|t|\delta_H}{\hbar} + \sum_j Q_j\eta_j + \epsilon_{\mathrm{synth}} + \epsilon_{\mathrm{physical}}.$$

Here every term must already be a bound in that same norm, with any projected-block error first converted as above. Reduced-state, probability and physical-noise specifications cannot simply be inserted as though they were vector errors. Choose oracle tolerances using the final $Q_j$ so that the complete sum meets the target.

Method selection is consequently conditional. Favor a product formula when term exponentials are cheap and commutators, locality, or parallel structure give a strong certificate. Favor an LCU/Taylor construction when coefficient preparation and SELECT are executable and $\lambda$ is controlled. Favor qubitization/QSP when a tight coherent block encoding and its supporting operations are available. Use a sparse reduction when locations and values are truly row-computable. Use an interaction picture when a dominant part is efficiently evolvable and the residual time-indexed oracle is cheaper after full expansion.

Finally, the output cost belongs to the application. Controlled evolution for Quantum Phase Estimation, state preparation, repeated measurement, and observable estimation are not included by saying “simulate $H$.” Digital Quantum Simulation explains the complete circuit calculation. Quantum algorithms for chemistry and materials applies these choices to molecular representations, state preparation and observables.

Two one-qubit calculations

These examples let us compare the error bound and normalization with explicit matrices. They illustrate the mathematics without assuming a scalable quantum advantage.

Alternating X and Z rotations

Set $H=X+Z$ and $t=\hbar=1$. Direct calculation gives

$$\|H\|=\sqrt2, \qquad \lambda=2, \qquad d_{\mathrm{sp}}\|H\|_{\max}=2, \qquad \|[X,Z]\|=2.$$

With

$$\tau_{\mathrm{sp}} := \frac{ d_{\mathrm{sp}}\|H\|_{\max}|t| }{ \hbar },$$

this representation has $T=\tau_{\mathrm{sp}}=2$. The equality is numerical, not an equivalence between its LCU and sparse interfaces. For

$$V_r := \left( e^{-iX/r} e^{-iZ/r} \right)^r,$$

the exact two-term certificate is $1/r$. Matrix evaluation gives:

$r$	$\lVert e^{-iH}-V_r\rVert$	commutator certificate $1/r$	term exponentials
1	$0.79921417$	1	2
2	$0.36240992$	0.5	4
4	$0.17626097$	0.25	8
8	$0.08751273$	0.125	16

Doubling $r$ approximately halves the error, as expected for this first-order formula, while doubling the number of term exponentials. The rigorous $1/r$ bound is larger than the measured matrix error at all four values. Neither the observed ratio nor the coefficient is universal.

Here is a short NumPy calculation of the table. Diagonalization exponentiates each Hermitian matrix, and the norm argument 2 selects the largest singular value, not the Frobenius norm.

import numpy as np

def evolve(H, time):
    energies, vectors = np.linalg.eigh(H)
    return (vectors * np.exp(-1j * time * energies)) @ vectors.conj().T

X = np.array([[0, 1], [1, 0]], dtype=complex)
Z = np.diag([1., -1.])
target = evolve(X + Z, 1)
for r in [1, 2, 4, 8]:
    step = evolve(X, 1/r) @ evolve(Z, 1/r)
    approx = np.linalg.matrix_power(step, r)
    print(r, np.linalg.norm(target - approx, 2), 1/r, 2*r)

Moving a large Z term into the interaction picture

Set

$$A=10Z, \qquad B=X, \qquad H=A+B, \qquad t=\hbar=1.$$

Choose the tight direct-term normalizations

$$\alpha_A := \|A\| = 10, \qquad \alpha_B := \|B\| = 1.$$

Then

$$\|H\| = \sqrt{101} = 10.04987562112089, \qquad \alpha_A+\alpha_B = 11.$$

These are chosen LCU normalizations, not consequences that every access model must use. Their nominal ratio to the interaction normalization is $11$. Pauli conjugation gives

$$B_I(s) = \cos(20s)X - \sin(20s)Y.$$

At $s=0,\pi/40,\pi/20$, its $(X,Y)$ coefficients are respectively $(1,0),(0,-1),(-1,0)$, and $\|B_I(s)\|=1$ at every sample.

$s$	$(X,Y)$ coefficients	$\lVert B_I(s)\rVert$
$0$	$(1,0)$	$1$
$\pi/40$	$(0,-1)$	$1$
$\pi/20$	$(-1,0)$	$1$

The residual keeps unit norm while its direction rotates rapidly. Constructing $B_I(s)$ coherently requires the two variable-angle $Z$ rotations as well as $X$; representing the time $s$ also costs a clock register and arithmetic. The reduction from normalization $11$ to $1$ is therefore not a factor-eleven runtime prediction. It is a reason to examine the complete interaction-picture implementation.

Exercises

1. Normalize a Simulation Instance

Let $H=3I+2X-Z$ and set $t=\hbar=1$. Compute $\|H\|$, the LCU normalization for the displayed Pauli decomposition, and the action of that LCU construction. Explain why removing $3I$ is harmless for uncontrolled state dynamics but requires care for controlled evolution.

Solution

The nonidentity part $2X-Z$ has eigenvalues $\pm\sqrt5$, so the eigenvalues of $H$ are $3\pm\sqrt5$ and

$$\|H\|=3+\sqrt5.$$

The displayed LCU coefficients have one-norm

$$\lambda=|3|+|2|+|-1|=6,$$

and hence $T=6$. The inequality $\|H\|<\lambda$ illustrates that the LCU normalization belongs to the representation. Removing $3I$ changes $e^{-iH}$ by the known global factor $e^{-i3}$, which has no effect on an uncontrolled output channel. Under coherent control, that factor is relative between the control branches and must either be implemented or corrected.

2. Derive a Product-Formula Certificate

Assume a unitary one-step formula obeys

$$\|e^{-iH\Delta/\hbar}-S_p(\Delta)\| \leq \Gamma_{p+1}|\Delta|^{p+1}/\hbar^{p+1}.$$

Derive the $r$-step bound and solve for a sufficient integer $r$. If a step has $m_p$ term exponentials, state the primitive count before boundary merging.

Solution

Insert and subtract products in which one exact step is replaced at a time. All surrounding factors are unitary, so every summand has the same norm as one local difference. The triangle inequality gives

$$\|e^{-iHt/\hbar}-S_p(t/r)^r\| \leq r\Gamma_{p+1} \frac{|t/r|^{p+1}}{\hbar^{p+1}} = \frac{\Gamma_{p+1}|t|^{p+1}}{r^p\hbar^{p+1}}.$$

It is therefore sufficient to take

$$r \geq \left\lceil \left( \frac{\Gamma_{p+1}|t|^{p+1}} {\epsilon\hbar^{p+1}} \right)^{1/p} \right\rceil.$$

Require $r\geq1$ for nonzero-time stepping, even if the displayed coefficient vanishes; at $t=0$ use the identity. The unmerged primitive count is $m_pr$. This remains conditional on the cited certificate and does not price synthesis of a term exponential.

3. Keep Sparse and Block-Encoding Queries Distinct

A Hermitian matrix is promised to be four-sparse with $\|H\|_{\max}\leq2$, and a sparse theorem uses its standard position/value oracles. A separate construction supplies a block encoding with $\alpha=5$. For $|t|/\hbar=3$, compute both normalized actions. What additional information is needed before choosing the smaller number as the cheaper algorithm?

Solution

The sparse action associated with the stated reduction is

$$\tau_{\mathrm{sp}} = 4\cdot2\cdot3 = 24,$$

whereas the supplied block encoding has

$$\tau=5\cdot3=15.$$

This does not yet prove that the block route is cheaper. One needs the number and types of sparse calls per sparse query; the gates, memory, and precision of the position/value oracles; the cost of the block encoding, inverse, controls, and signal reflection; ancilla and phase-synthesis costs; and the same output and error convention. A smaller normalization alone cannot determine the cheaper implementation.

4. Choose the Taylor order and compensation rotation

Take $T=2$ and allocate $\epsilon_{\mathrm{tail}}=0.01$ to the accumulated raw Taylor tail, with no additional constant. Use equal segments and find the smallest $K$ for which $rR_K(T/r)\leq0.01$. Find $rK$ and explain why it is a scaling estimate rather than an exact total query count.

Solution

The segment count and action are

$$r=\left\lceil\frac2{\ln2}\right\rceil=3, \qquad x=\frac23.$$

Direct evaluation gives

$$R_3(2/3)\approx0.009462, \qquad R_4(2/3)\approx0.0012319834415071.$$

Thus $3R_3>0.01$ but $3R_4\approx0.0036959503245213<0.01$, so the smallest order is $K=4$. The scaling estimate is $rK=12$ selected-unitary positions before theorem- specific constant factors. Here

$$s_4(2/3) = \frac{473}{243},$$

so equal-segment normalization also needs the compensation rotation with $\langle0|C_4|0\rangle=473/486$. This is not an exact total query count and omits PREPARE, inverses, reflections, robust amplification, compensation-rotation precision, ancillas, selected-unitary gates, and all remaining error budgets.

5. Read the Joint Qubitization Bound

Let $L_\epsilon=\log(1/\epsilon)$. Reduce

$$\tau+ \frac{L_\epsilon}{\log(e+L_\epsilon/\tau)}$$

in the fixed-error, growing-$\tau$ regime and in the fixed nonzero-$\tau$, high-precision regime. Explain why the identity circuit must be checked before using either asymptotic expression.

Solution

At fixed error, $L_\epsilon$ is constant and the expression is $\Theta(\tau)$. At fixed nonzero $\tau$ with $L_\epsilon\to\infty$, the denominator is $\Theta(\log L_\epsilon)$, giving

$$\Theta\!\left( \frac{L_\epsilon}{\log L_\epsilon} \right).$$

When both quantities scale, neither reduction is uniformly valid; the joint denominator or finite $q_*$ condition must be retained. Also, $\|e^{-iHt/\hbar}-I\|\leq\tau$. If $\tau\leq\epsilon$, a zero-query identity circuit already meets the target, so an integer query theorem should not be extrapolated into that trivial regime.

6. Find the rotating residual

For $A=\omega Z$ and $B=gX$, derive $B_I(s)$ and its norm. List the resources hidden by a statement that the leading query action is $|g t|/\hbar$ rather than $(|\omega|+|g|)|t|/\hbar$.

Solution

Using $[Z,X]=2iY$ or direct Pauli conjugation,

$$B_I(s) = g\left[ \cos(2\omega s/\hbar)X - \sin(2\omega s/\hbar)Y \right].$$

The Pauli combination squares to $I$, so $\|B_I(s)\|=|g|$ for every $s$. The smaller residual action is meaningful only with executable time-indexed access. A complete implementation includes the final $e^{-iAt/\hbar}$, controlled variable-time $A$ evolutions used to construct the residual oracle, $B$ access, clock registers, time arithmetic, inverses, normalization and coefficient precision, Dyson truncation, discretization, and synthesis. The result is a normalization change, not automatically a runtime ratio.

7. Scope No-Fast-Forwarding Correctly

Evaluate the claim: “No-fast-forwarding proves that every Hamiltonian needs $\Omega(t)$ circuit depth.” Give a corrected statement and explain the status of a commuting-family promise that the algorithm does not verify.

Solution

The claim is too broad. No-fast-forwarding gives a worst-case query lower bound for a specified black-box Hamiltonian family, access interface, output, and error regime. It does not automatically imply physical circuit depth, and it does not apply instance by instance to every commuting, diagonal, integrable, or otherwise structured family.

A corrected statement is: some Hamiltonians in the matched oracle family require query cost linear in the theorem’s normalized time to implement the specified evolution to the stated error. If inputs are promised to commute, the algorithm may assume that promise in a promise-problem formulation. It must label the promise as assumed and unverified; verification is charged only if the workflow performs or claims it.

8. A small successful-block error can hide coherent leakage

For a unitary $U$ and $0<\delta<1$, consider a circuit that acts on initialized ancillas as

$$V(|0\rangle|\psi\rangle) =(1-\delta)|0\rangle U|\psi\rangle +\sqrt{2\delta-\delta^2}|1\rangle U|\psi\rangle.$$

Show that this action has a unitary extension. Compute its successful-block error, failure probability and vector error relative to $|0\rangle U|\psi\rangle$. What happens if the ancilla is discarded? Separately, why does $H'=i\delta I$ show that a block close to a Hermitian target $H=0$ need not be a valid Hamiltonian?

Solution

The two ancilla amplitudes have squared sum one, so an ancilla rotation followed by $U$ realizes the action. The successful block is $(1-\delta)U$, with operator error $\delta$. Failure probability is $2\delta-\delta^2$, whereas the full vector error is

$$\sqrt{\delta^2+(2\delta-\delta^2)}=\sqrt{2\delta}.$$

Discarding the ancilla gives exactly $U|\psi\rangle\langle\psi|U^\dagger$ in this example because the same system state appears in both branches. Thus the successful-block, coherent-vector and reduced-state errors are three different quantities even for this simple circuit.

For the second question, $\|H'-H\|=\delta$, but $H'^\dagger=-H'$. In units with $\hbar=1$, $e^{-iH't}=e^{\delta t}I$ is not unitary; at positive time its distance from $I$ is $e^{\delta t}-1>\delta t$. The simple unitary Duhamel bound required both generators to be Hermitian. A general approximate block-encoding definition must therefore be supplemented before it is used as an exact Hamiltonian signal.

References

• D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, “Efficient Quantum Algorithms for Simulating Sparse Hamiltonians,” Communications in Mathematical Physics 270, 359–371 (2007), doi:10.1007/s00220-006-0150-x.
• D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, “Simulating Hamiltonian Dynamics with a Truncated Taylor Series,” Physical Review Letters 114, 090502 (2015), doi:10.1103/PhysRevLett.114.090502.
• D. W. Berry, A. M. Childs, and R. Kothari, “Hamiltonian Simulation with Nearly Optimal Dependence on All Parameters,” in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 792–809 (2015), doi:10.1109/FOCS.2015.54.
• D. W. Berry, A. M. Childs, Y. Su, X. Wang, and N. Wiebe, “Time-Dependent Hamiltonian Simulation with $L^1$-Norm Scaling,” Quantum 4, 254 (2020), doi:10.22331/q-2020-04-20-254.
• A. M. Childs, “On the Relationship Between Continuous- and Discrete-Time Quantum Walk,” Communications in Mathematical Physics 294, 581–603 (2010), doi:10.1007/s00220-009-0930-1.
• A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, “Theory of Trotter Error with Commutator Scaling,” Physical Review X 11, 011020 (2021), doi:10.1103/PhysRevX.11.011020.
• A. M. Childs and N. Wiebe, “Hamiltonian Simulation Using Linear Combinations of Unitary Operations,” Quantum Information and Computation 12, 901–924 (2012), doi:10.26421/QIC12.11-12.
• J. Haah, M. B. Hastings, R. Kothari, and G. H. Low, “Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians,” in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, 350–360 (2018), doi:10.1109/FOCS.2018.00041.
• S. Lloyd, “Universal Quantum Simulators,” Science 273, 1073–1078 (1996), doi:10.1126/science.273.5278.1073.
• G. H. Low and I. L. Chuang, “Optimal Hamiltonian Simulation by Quantum Signal Processing,” Physical Review Letters 118, 010501 (2017), doi:10.1103/PhysRevLett.118.010501.
• G. H. Low and I. L. Chuang, “Hamiltonian Simulation by Qubitization,” Quantum 3, 163 (2019), doi:10.22331/q-2019-07-12-163.
• G. H. Low and N. Wiebe, “Hamiltonian Simulation in the Interaction Picture,” arXiv:1805.00675 (2018), doi:10.48550/arXiv.1805.00675.