Hamiltonian Simulation Algorithms

Hamiltonian simulation is a typed algorithmic problem: from a specified coherent interface for a finite-dimensional Hermitian operator $H$, construct an approximation to $e^{-iHt/\hbar}$ with a declared output and error guarantee. A matrix written on paper is not such an interface. Sparse-entry oracles, executable term exponentials, PREPARE/SELECT access, block encodings, and native physical evolution expose different operations and therefore lead to different theorems.

This page compares the resulting algorithm families only after their access, normalization, output, error, and counted query have been matched. A query is not an elementary gate, a unit of physical runtime, or a free memory lookup. Likewise, a circuit that approximates the evolution unitary does not return a classical wavefunction. It supplies coherent dynamics that a separately specified preparation, readout, or larger algorithm may use.

The simulation-facing definition, truncation and observable workflow belong to Hamiltonian Simulation. Detailed product-formula design belongs to Trotter–Suzuki Methods, and signal-space construction and phase synthesis belong to Qubitization and Quantum Signal Processing. The role here is narrower: a theorem-level atlas of applicability, normalized query bounds, lower-bound regimes, and the obligations incurred when a query claim is expanded into an executable resource estimate.

Required background. Hamiltonian Simulation supplies the target evolution, access-instance, norm, error, truncation, and output contract. Query Complexity supplies fixed-query measures, reductions, lower-bound semantics, and the separation between query and implementation cost.

Helpful background. The Quantum Algorithms and Complexity guide supplies the chapter claim discipline. Algorithmic Primitives supplies the access–processing–interference–readout vocabulary. Trotter–Suzuki Methods and Qubitization and Quantum Signal Processing supply the specialist constructions summarized here. What Is Quantum Simulation? places unitary simulation inside the larger scientific workflow of model choice, state preparation, observable extraction, validation, and matched classical comparison.

The Hamiltonian-Simulation Algorithm Problem

Let $H=H^\dagger$ act on a declared finite-dimensional system space. Given a real time $t$ and $0<\epsilon<1$, the standard coherent target is

$$U_H(t) := e^{-iHt/\hbar},$$

with an approximation $\widetilde U$ satisfying, for example,

$$\left\| \widetilde U-U_H(t) \right\|_{\mathrm{op}} \leq \epsilon.$$

That equation is not a complete algorithmic problem. One must also specify the family of Hamiltonians, the representation of each instance, which coherent operations are licensed, whether inverse and controlled calls are available, and what a query counts. If ancillas are used, the guarantee must say whether they are restored, postselected, or allowed to leak. If the simulation is randomized, it must distinguish a guarantee for one sampled circuit from a guarantee for the ensemble channel. If a controlled evolution is required, a known global phase can become a measurable relative phase and cannot be dismissed without checking the control convention.

Operator-norm error is convenient because it composes under products and implies a worst-case state-vector bound. Other valid targets include a channel distance, a state-specific error, or the error of a local observable. They are not interchangeable. A local-observable theorem can avoid the system-size dependence of a full-unitary theorem without contradicting it, because it asks for less output. Similarly, native analog evolution and a digital circuit may approximate the same mathematical unitary while having incomparable access and error ledgers.

This page therefore treats every result as a conditional statement:

$$\text{declared access} + \text{declared promises} \Longrightarrow \text{declared guarantee at declared cost}.$$

State preparation, phase estimation, expectation estimation, tomography, and scientific validation are downstream tasks. They may dominate the end-to-end cost even when the simulation subroutine has optimal query complexity.

The Ten-Field Hamiltonian-Simulation Claim Record

A cross-family comparison is admissible only when all ten entries below refer to the same typed claim.

1. Problem family and size. Name the finite Hamiltonian family, Hilbert space or encoded subspace, system-size variable, time regime, and quantity that tends asymptotically large or small.
2. Promise and instance. State Hermiticity, locality, sparsity, norm or coefficient bounds, smoothness, finite truncation, and any special commuting, integrable, low-energy, or fast-forwarding promise.
3. Access and encoding. Give the complete oracle or executable primitive, its registers and precision, and separately license forward, inverse, controlled, powered, state-preparation, reflection, and arithmetic access.
4. Output and use. Specify a coherent full-system unitary, controlled unitary, state, channel, local observable, or subroutine call, together with the downstream consumer.
5. Success and error. Name the norm or operational metric, simulation and representation budgets, failure or leakage convention, and whether the guarantee is deterministic, average-channel, or high probability.
6. Algorithmic idea. Identify product splitting, a walk, a truncated series, linear-combination interference, signal processing, or an interaction-picture transformation without substituting one interface for another.
7. Executable procedure. List the coherent calls, inverses, controls, clocks, reflections, segment schedule, synthesis, cleanup, measurements, and classical preprocessing in runnable order.
8. Resource ledger. Count each query species, primitive exponential, logical gate, depth, ancilla, coefficient bit, data-load operation, synthesis tolerance, error-correction overhead, and physical-time cost that the claim includes.
9. Classical comparator. Match the represented input, permitted preprocessing and data structure, output, error, confidence, and total-cost currency before asserting an advantage.
10. Evidence and limits. Label upper bound, lower bound, matching theorem, exact finite audit, numerical observation, or experiment, then state the access regimes and outputs to which it does not extend.

This record prevents common silent substitutions: $\|H\|$ for an LCU coefficient norm, an ideal SELECT call for its compiled circuit, an average randomized channel for one sampled formula, or a worst-case oracle lower bound for every structured physical system.

Access Models, Normalizations, and Query Units

The normalization multiplying time is part of the input model. It is not a property that may be changed while retaining the same theorem row.

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 all belong in the record. 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 contract must define padding, duplicate positions, value precision, Hermitian consistency, and 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. 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}.$$

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,$$

before allocating synthesis and representation error. 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 owns order selection, locality grouping, compilation, and convergence tests; the Trotter Product Formula owns 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 owns the general discrete- and continuous-time walk models and walk applications such as graph search, detection, and hitting; this page retains quantum walks only as Hamiltonian-simulation techniques, including sparse-oracle conversions, access normalization, evolution error, and simulation-query bounds.

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.

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 returns the coherent full evolution 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 ledger 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 owns 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. The detailed parity constraints, phase conventions, and signal reflections are owned by 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 source-level degree record 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 output is the coherent full evolution with spectral-norm error $\epsilon$ and failure probability $O(\epsilon)$. 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. The resource record must state whether one query means $U$, controlled-$U$, $U^\dagger$, a state preparation, or a compound qubiterate call. Approximate block encodings can contribute up to $|t|\delta_{\mathrm{BE}}/\hbar$ under the energy-error convention used 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 coherent output is the full time-ordered evolution; after the theorem’s segment budgets, both its spectral-norm error and its LCU projection failure probability are $O(\epsilon)$. 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 always refers to a specified access model and asymptotic regime. The following ledger is intentionally conditional.

family	normalized parameter	theorem-level query statement	principal qualification
product formula	commutator certificate and $\lvert t\rvert/\hbar$	$m_pr$ exponentials for a proved $r$	full-unitary operator norm, deterministic success; no universal $\Gamma_{p+1}$
truncated Taylor LCU	$T=\lambda\lvert t\rvert/\hbar$	$O(rK)$ SELECT calls	projected-branch bound and reduced-state trace-distance error after fresh-ancilla discard; robust OAA, no retry
exact block encoding	$\tau=\alpha\lvert t\rvert/\hbar$	$\Theta(q_*)$ controlled $G,U,G^\dagger,U^\dagger$ calls	full-unitary spectral-norm error $\epsilon$, failure $O(\epsilon)$; signal reflections and joint time–precision form
sparse black box	$\tau_{\mathrm{sp}}=d_{\mathrm{sp}}h\lvert t\rvert/\hbar$	optimal joint dependence after the proved sparse reduction	full-unitary spectral-norm error $\epsilon$, failure $O(\epsilon)$; location/value queries exclude their data structure
interaction picture	integrated residual action	truncated-Dyson HAM-T upper bound	full-evolution spectral error and failure $O(\epsilon)$; variable-time $A$ evolution remains charged

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.

Lower Bounds and Limitations owns the cross-resource interpretation of no-fast-forwarding and the separate assumptions needed to infer gates, depth, or runtime; this page retains the hard Hamiltonian families, access and normalization, output and error conditions, structured exceptions, and sharp simulation-query bounds.

From Oracle Queries to Executable Resources

A query theorem becomes an implementation claim only after every ideal call is expanded. A useful schematic gate ledger 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.

Representation and synthesis precision must be assigned before selecting an algorithm. A conservative composition has the form

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

Choosing each oracle tolerance only after seeing $Q_j$ prevents a nominally optimal query theorem from exceeding the final error target when compiled.

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 owns the end-to-end circuit workflow; this page stops at the qualified algorithm and resource atlas. Quantum Algorithms for Chemistry and Materials specializes qualified simulation-method choice to molecular and materials representations, state preparation, and observables; this page retains the access-model and query-complexity atlas.

Two Reproducible Finite Audits

These two audits check exact finite statements, not hardware performance or asymptotic advantage. The same ten-field discipline used for the headline claim is applied to each instance.

Audit 1 — Pauli access and product-formula ledger

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$	$\|e^{-iH}-V_r\|$	commutator certificate $1/r$	term exponentials
1	0.79921417396605876	1	2
2	0.36240992388368953	0.5	4
4	0.17626096761776416	0.25	8
8	0.087512727535962564	0.125	16

The audit record is:

1. Problem family and size. The instance is one qubit, two Pauli terms, four finite step counts, and a full-unitary operator-norm comparison.
2. Promise and instance. The Hamiltonian is exactly $X+Z$ with $t=\hbar=1$; term exponentials and deterministic binary64 matrix arithmetic are licensed for the check.
3. Access and encoding. One view supplies executable $X$ and $Z$ exponentials, one supplies an LCU with coefficients $(1,1)$, and one supplies the two-nonzero-per-row value/position interface.
4. Output and use. The output under audit is the one-qubit unitary $V_r$, compared directly with $e^{-iH}$; no state preparation or measurement is included.
5. Success and error. The construction is deterministic, and error is the spectral norm of the $2\times2$ matrix difference at each listed $r$.
6. Algorithmic idea. Lie–Trotter splitting alternates the exact $X$ and $Z$ exponentials; the nonzero commutator supplies a certified $1/r$ bound.
7. Executable procedure. Construct the Pauli matrices, exponentiate each analytically, multiply the ordered steps, form the exact target, and compute the largest singular value of their difference.
8. Resource ledger. The formula uses $2r$ term exponentials. The audit separately records $\lambda=2$, sparse normalization $2$, commutator norm $2$, and no compilation or physical-gate cost.
9. Classical comparator. Direct $2\times2$ matrix arithmetic is the finite verification method, not a claimed scalable classical competitor to the oracle problem.
10. Evidence and limits. The four values lie below $1/r$ and decrease strictly. Their near-halving supports this finite first-order instance but establishes neither a universal prefactor nor device performance.

Audit 2 — Interaction-picture normalization is not free

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 audit record is:

1. Problem family and size. This is a one-qubit decomposition with one dominant Pauli term, one residual term, and three exact interaction-time samples.
2. Promise and instance. The declared decomposition is $10Z+X$ at unit time with tight term-norm bounds $10$ and $1$; it is not chosen by an optimizer.
3. Access and encoding. The record licenses exact $X$ access and coherent controlled variable-time $Z$ rotations used to construct each time-indexed interaction query.
4. Output and use. The checked objects are the residual matrices $B_I(s)$ and their normalization; the audit does not execute a full Dyson-series simulation.
5. Success and error. All matrix identities are deterministic within the stated binary64 tolerance; no statistical success probability is claimed.
6. Algorithmic idea. Conjugation moves the rapid $10Z$ motion into the oracle while leaving a unit-norm rotating residual in the $X$–$Y$ plane.
7. Executable procedure. Build $e^{i10Zs}Xe^{-i10Zs}$, compare it with the analytic Pauli combination, and compute its spectral norm at all three times.
8. Resource ledger. The normalization changes from the chosen separate- term sum $11$ to residual value $1$, but every coherent time-indexed query charges both controlled $A$ evolutions, $B$ access, and clock precision.
9. Classical comparator. Direct one-qubit matrix multiplication checks the identities only; it does not establish an end-to-end quantum advantage.
10. Evidence and limits. The calculation verifies the normalization ratio, rotation sign, samples, and norms. It proves neither a factor-eleven runtime speedup nor favorable scaling for a larger family.

One deterministic program reproduces both audits:

const TOL = 5e-15;
const assert = (condition, label) => {
  if (!condition) throw new Error(label);
};
const close = (actual, expected, label) => {
  assert(Math.abs(actual - expected) < TOL,
    `${label}: ${actual} != ${expected}`);
};

const c = (re, im = 0) => ({ re, im });
const add = (a, b) => c(a.re + b.re, a.im + b.im);
const sub = (a, b) => c(a.re - b.re, a.im - b.im);
const mul = (a, b) => c(
  a.re * b.re - a.im * b.im,
  a.re * b.im + a.im * b.re,
);
const conj = (z) => c(z.re, -z.im);
const abs2 = (z) => z.re * z.re + z.im * z.im;

const I = [[c(1), c(0)], [c(0), c(1)]];
const X = [[c(0), c(1)], [c(1), c(0)]];
const Y = [[c(0), c(0, -1)], [c(0, 1), c(0)]];
const Z = [[c(1), c(0)], [c(0), c(-1)]];

const matrixAdd = (A, B) => A.map((row, i) =>
  row.map((value, j) => add(value, B[i][j])));
const matrixSub = (A, B) => A.map((row, i) =>
  row.map((value, j) => sub(value, B[i][j])));
const matrixScale = (A, scalar) => A.map((row) =>
  row.map((value) => mul(value, scalar)));
const matrixMul = (A, B) => A.map((row, i) => B[0].map((_, j) =>
  row.reduce((sum, __, k) => add(sum, mul(A[i][k], B[k][j])), c(0))));
const matrixPow = (A, exponent) => {
  let result = I;
  let base = A;
  let power = exponent;
  while (power > 0) {
    if (power % 2 === 1) result = matrixMul(result, base);
    base = matrixMul(base, base);
    power = Math.floor(power / 2);
  }
  return result;
};
const matrixClose = (A, B, label) => A.forEach((row, i) =>
  row.forEach((value, j) => {
    close(value.re, B[i][j].re, `${label} re ${i},${j}`);
    close(value.im, B[i][j].im, `${label} im ${i},${j}`);
  }));
const spectralNorm2 = (A) => {
  const aa = abs2(A[0][0]) + abs2(A[1][0]);
  const dd = abs2(A[0][1]) + abs2(A[1][1]);
  const bb = add(
    mul(conj(A[0][0]), A[0][1]),
    mul(conj(A[1][0]), A[1][1]),
  );
  const discriminant = Math.sqrt((aa - dd) ** 2 + 4 * abs2(bb));
  return Math.sqrt((aa + dd + discriminant) / 2);
};
const expMinusIPauli = (P, angle) => matrixAdd(
  matrixScale(I, c(Math.cos(angle))),
  matrixScale(P, c(0, -Math.sin(angle))),
);

// Audit 1: H = X + Z and ordered Lie–Trotter products.
const H1 = matrixAdd(X, Z);
close(spectralNorm2(H1), Math.sqrt(2), 'norm X+Z');
const commutator = matrixSub(matrixMul(X, Z), matrixMul(Z, X));
close(spectralNorm2(commutator), 2, 'commutator norm');
const lambda = 1 + 1;
const sparseDegree = 2;
const maxEntry = 1;
const sparseAction = sparseDegree * maxEntry;
assert(lambda === 2 && sparseAction === 2, 'normalizations');

const exactH1 = matrixAdd(
  matrixScale(I, c(Math.cos(Math.sqrt(2)))),
  matrixScale(H1, c(0, -Math.sin(Math.sqrt(2)) / Math.sqrt(2))),
);
const expectedErrors = [
  0.79921417396605876,
  0.36240992388368953,
  0.17626096761776416,
  0.087512727535962564,
];
const steps = [1, 2, 4, 8];
let previousError = Infinity;
steps.forEach((r, index) => {
  const step = matrixMul(
    expMinusIPauli(X, 1 / r),
    expMinusIPauli(Z, 1 / r),
  );
  const approximation = matrixPow(step, r);
  const error = spectralNorm2(matrixSub(exactH1, approximation));
  close(error, expectedErrors[index], `Trotter error r=${r}`);
  assert(error < 1 / r, `certificate r=${r}`);
  assert(error < previousError, `monotonicity r=${r}`);
  assert(2 * r === [2, 4, 8, 16][index], `term count r=${r}`);
  previousError = error;
});

// Audit 2: A = 10 Z, B = X and the interaction-picture residual.
const A = matrixScale(Z, c(10));
const B = X;
const H2 = matrixAdd(A, B);
close(spectralNorm2(H2), Math.sqrt(101), 'norm 10Z+X');
close(Math.sqrt(101), 10.04987562112089, 'sqrt 101 binary64');
const alphaA = spectralNorm2(A);
const alphaB = spectralNorm2(B);
close(alphaA, 10, 'alpha A');
close(alphaB, 1, 'alpha B');
close(alphaA + alphaB, 11, 'normalization sum');
close((alphaA + alphaB) / alphaB, 11, 'normalization ratio');

const samples = [
  { s: 0, x: 1, y: 0 },
  { s: Math.PI / 40, x: 0, y: -1 },
  { s: Math.PI / 20, x: -1, y: 0 },
];
samples.forEach(({ s, x: expectedX, y: expectedY }, index) => {
  const xCoefficient = Math.cos(20 * s);
  const yCoefficient = -Math.sin(20 * s);
  close(xCoefficient, expectedX, `X coefficient sample ${index}`);
  close(yCoefficient, expectedY, `Y coefficient sample ${index}`);
  const analytic = matrixAdd(
    matrixScale(X, c(xCoefficient)),
    matrixScale(Y, c(yCoefficient)),
  );
  const fromConjugation = matrixMul(
    matrixMul(expMinusIPauli(Z, -10 * s), X),
    expMinusIPauli(Z, 10 * s),
  );
  matrixClose(fromConjugation, analytic, `interaction matrix ${index}`);
  close(spectralNorm2(fromConjugation), 1, `interaction norm ${index}`);
});

console.log('Hamiltonian-simulation-algorithms audits: PASS');

Common Hamiltonian-Simulation Claim Failures

Treating a matrix as access. A classical formula or stored array does not provide coherent positions, values, selected unitaries, term exponentials, or a block encoding. State the executable interface and its data structure.

Replacing one normalization by another. The quantities $\|H\|$, $\lambda$, $d_{\mathrm{sp}}\|H\|_{\max}$, and $\alpha$ can differ greatly. Substitution requires a proved construction with its resource cost.

Using formal order as a finite error bound. “Order $p$” gives a power of the step size, not the nested-commutator coefficient. Specify the ordering, certificate, step count, and output being controlled.

Confusing a sampled circuit with an averaged channel. A randomized formula can have a strong ensemble-channel guarantee while individual sampled unitaries have different operator errors. Quote the theorem’s actual object.

Calling LCU postselection deterministic. The coherent truncated-series algorithm uses coefficient preparation, selection, inverses, reflections, and robust oblivious amplification. None is supplied by the word “LCU.”

Using the high-precision shorthand uniformly. The $L_\epsilon/\log L_\epsilon$ term is a limiting slice of the joint signal-query bound. When time and precision co-scale, retain the full denominator $\log(e+L_\epsilon/\tau)$ or the finite $q_*$ record.

Making the dominant interaction-picture term free. The leading residual normalization can shrink while controlled $A$ evolution, clocks, arithmetic, and the construction of the time-indexed residual remain costly.

Equating query optimality with implementation optimality. A theorem can minimize ideal block-oracle calls while a different method uses fewer logical gates, less depth, fewer qubits, or cheaper data access on a specific family.

Universalizing no-fast-forwarding. Worst-case black-box lower bounds do not exclude fast evolution for promised commuting, diagonal, integrable, or otherwise structured families. State whether the promise is assumed or verified.

Claiming a wavefunction as output. Simulation supplies coherent evolution. Classical state reconstruction, observables, and confidence require additional preparation and measurement contracts.

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.$$

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. The smaller normalization is only one entry in a matched ledger.

4. Expand a Truncated-Taylor LCU Ledger

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$. State the resulting asymptotic $rK$ SELECT ledger and what it omits.

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 ledger 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$. The ledger 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. Audit an Interaction-Picture Claim

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 full ledger 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. Repair a Hamiltonian-Simulation Advantage Claim

Repair the sentence “Qubitization simulates every sparse Hamiltonian exponentially faster than Trotterization.” Use a complete ten-field record for a defensible comparison rather than merely weakening the adjective.

Solution

One defensible replacement is conditional: for a declared family with a specified sparse-oracle construction and exact coherent block encoding, qubitization has optimal signal-query dependence on the resulting normalized action and joint precision; comparison with a product formula additionally requires executable term exponentials and a proved commutator certificate. The following record makes the claim testable.

1. Problem family and size. Fix an $n$-qubit Hermitian family and state how sparsity, term count, time, and target precision scale with $n$.
2. Promise and instance. Declare the sparsity, entry bound, locality and commutator structure, exact finite-dimensional domain, and any unverified promise.
3. Access and encoding. Supply reversible position/value oracles and their block construction for the signal route, and executable controlled term exponentials for the product route.
4. Output and use. Require the same full-system coherent unitary or the same controlled use from both algorithms.
5. Success and error. Use one operator-norm target and allocate equal representation, oracle, algorithmic, and synthesis budgets.
6. Algorithmic idea. Compare polynomial signal transformation with an explicitly ordered product formula; do not infer either cost from its name.
7. Executable procedure. Expand block preparation, inverse, controls, signal phases, and reflections, and separately expand every term exponential and product step.
8. Resource ledger. Report signal and sparse queries, primitive exponentials, logical gates, depth, ancillas, data loading, arithmetic, synthesis, and fault-tolerant overhead.
9. Classical comparator. If an advantage beyond the quantum-method comparison is claimed, match the same encoded input, output, accuracy, preprocessing, and total cost to a classical method.
10. Evidence and limits. Cite the applicable upper and lower theorems and finite implementation evidence, then exclude unmatched access and unproved gate or runtime conclusions.

This record may show a precision-query advantage for the signal method, a gate advantage for a structured product formula, or no established ordering. No universal exponential separation follows from the family names.

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.