Time-Dependent Hamiltonian Simulation with Optimal Query Complexity

1.2 Related work

• Existing truncated-Dyson, clock, and Floquet approaches generally incur precision-dependent overhead that multiplies the evolution scale or require special structure.The paper instead addresses worst-case black-box query complexity in HAM-T rather than decomposable, commutator, locality, periodicity, or low-energy settings.Source: §1 · p. 2, §1.2 · pp. 4–5

1 Introduction

• The paper resolves the open question of the optimal query complexity for simulating general time-dependent Hamiltonians.The problem had remained open despite the time-independent query complexity being fully characterized.Source: §1 · pp. 2–3

1.1 Main results

• A one-query transducer encodes the complete sequence of time-ordered steps, while weighted reuse lengths cancel catalyst-omission errors and produce factorial decay.This replaces independent approximation and composition of short-time propagators with transducer reuse.Source: §1 · p. 3, §1.2 · p. 5, §1.3 · p. 6
• General time dependence incurs no asymptotic query overhead: the algorithm matches the lower bound already applying to time-independent Hamiltonians.The result targets Lipschitz-continuous H(t) with bounded norm in the HAM-T access model.Source: §1.1 · p. 3
• The upper bound applies without periodicity or locality assumptions, although the Lipschitz constant affects time sampling, gate complexity, and ancilla complexity.The query bound itself is unaffected by the Lipschitz constant.Source: §1.1 · p. 3

1.3 Discussion and future directions

• The construction is query-optimal but not yet gate-optimal: direct implementation scales with the finite time grid, and no efficient gate implementation is known for the continuous-register variant.A higher-order discretization is suggested as one possible route to reducing the number of time steps.Source: §1.3 · p. 5
• The matched lower bound concerns worst-case full-propagator simulation, whereas low-energy or adiabatic tasks may have lower costs under suitable promises.Such an extension would require controlling catalyst norms and catalyst-omission errors within the relevant low-energy subspace.Source: §1.3 · p. 5

Finite reuse

• Omitting the scaled catalyst causes an O(N^-1/2) error, so generic reuse alone requires a quadratic dependence on 1/ε.The bound follows from the catalyst norm and unitarity, giving ||U_C − P_N|| ≤ ||Γ||/N^1/2.Source: §2 · pp. 6, 8

Factorial error decay

• Weighted combinations of reuse lengths make omission errors partly cancel; surviving contributions follow the order of the short-time steps, and their total size decreases factorially with the largest reuse length.Applying the standard LCU construction produces a block-encoding with normalization Λ; keeping Λ ≤ 2 permits one step of oblivious amplitude amplification with constant overhead.Source: §2 · pp. 6, 9

Transducer construction

• The Cayley approximation uses a time-index register whose labeled components receive the corresponding oracle blocks O_j in parallel through one HAM-T query.The time register labels physical grid points, and the local catalysts are associated with those labels.Source: §2 · pp. 6–7
• A one-query transducer implements the Cayley-product approximation U_C while returning its catalyst unchanged.The catalyst is generally difficult to prepare, so the transducer alone does not yield a catalyst-free circuit.Source: §2 · pp. 6–7

Finite reuse

• Finite reuse replaces the supplied catalyst with zero private input by arranging N transducer calls and block-encoding a catalyst-free operator P_N.With the catalyst supplied, the reuse circuit produces U_C; with zero private input, its public component is P_N.Source: §2 · pp. 7–8

Factorial error decay

• The LCU construction uses reuse lengths N ≤ 4q and requires 12q HAM-T queries after amplification.The factorization E_q(A)=Q(A)^qG_2q(A), together with ||G_2q(A)||≤1, supplies the decay estimate.Source: §2 · p. 9

• The Hamiltonian satisfies ||H(t)||≤α and ||H(t)−H(s)||≤β|t−s| on [0,T].U_H(t) denotes the propagator generated by H.Source: §3 · p. 10
• The construction uses standard block-encoding terminology, with auxiliary registers projected onto their all-zero state to recover the encoded operator.When the normalization is one and the error is zero, the unitary is simply called a block-encoding.Source: §3 · p. 10
• The algorithm discretizes time using a power-of-two grid with a time-index register whose basis state |j⟩ labels t_j.The same grid is used throughout the circuit.Source: §3 · p. 10
• HAM-T is a controlled, time-indexed oracle whose block O_j is a Hermitian unitary block-encoding of H(t_j)/α.A controlled HAM-T application counts as one query, and HAM-T^2=I.Source: §3 · p. 10

4 The Cayley transducer

• The Cayley transducer section combines a product of Cayley steps with a single-query implementation of the entire product.The resulting unitary uses one HAM-T query and returns its catalyst unchanged.Source: §4 · p. 10

4.1 Cayley step

• Each Cayley step is norm-preserving and approximates the short-time propagator generated by H(t_j).The Lipschitz condition controls the difference between the constant-Hamiltonian exponential and the exact interval propagator.Source: §4.1 · p. 11
• The local Cayley update is equivalently represented by a Cayley transform, whose local approximation error is bounded spectrally.The product error is obtained by combining the single-step bound with the time-discretization estimate and telescoping over intervals.Source: §4.1 · p. 11

4.2 One-query transducer

• For each time label j, a unitary R_j maps the public state and the queried local catalyst to the next public state while preserving that catalyst.The construction relies on the Hermitian-unitary oracle block and a flag encoding for the public-private direct sum.Source: §4.2 · pp. 12, 14
• Applying R_0 through R_{J−1} after the single oracle query produces U_C|ψ_0⟩⊕Γ|ψ_0⟩.Because the R_j operations are oracle-independent, the factorization uses exactly one HAM-T query.Source: §4.2 · pp. 14–15
• The catalyst map Γ has norm at most αT, setting the scale for later catalyst-removal bounds.The bound follows from unitary Cayley factors and orthogonality of the time-index basis.Source: §4.2 · pp. 14–15

• With the scaled catalyst supplied, each call applies U_C to its public component and returns the catalyst unchanged for the next call.After all calls, uncomputing K leaves the public state U_C|ψ_0⟩.Source: §5 · p. 15
• The reuse construction uses a register K whose first N labels identify the transducer call, distinct from the physical time register.Controlled shifts and Fourier-like preparation distribute the public input across reuse labels.Source: §5 · pp. 15–16
• With zero private input, the same circuit produces a public component P_N, and the reuse unitary block-encodes P_N by projecting auxiliary input and output onto zero.The operator P_N is therefore the catalyst-free counterpart of U_C in the reuse construction.Source: §5 · p. 16
• The reuse-error identity expresses U_C−P_N through the private-to-private and private-to-public blocks of the transducer.The proof tracks private vectors z_ℓ through successive calls and derives the resulting public output.Source: §5 · pp. 15–17

6.1 Lower-triangular structure of the private block

• The private block A has the form A = i(I −∆)HAM-T, with ∆ unable to move a time label earlier.This lower-triangular structure follows from the ordered updates and isolates time ordering in ∆.Source: §6.1 · pp. 18–19

6 Time ordering and factorial decay

• Ordered intermediate time labels make every term in Q(A)^q contain at least q factors of ∆, producing factorial decay.Because ∆ never decreases the time label, the admissible sequences are ordered rather than arbitrary.Source: §6.1 · pp. 18–19, §6.2 · pp. 19–20

6.2 Factorial bound

• For q ≥ max{1, αT} and w ≤ αT/q, the off-diagonal blocks obey ∥[∆]r,j∥ ≤ 2w e^−(r−j−1)w for r > j, while diagonal blocks satisfy ∥[∆]j,j∥ ≤ w.These estimates are the local bounds used to control the ordered block products.Source: §6.2 · p. 19
• The factorial estimate holds uniformly over every admissible Cayley step count J ≥ q because w = αT/J.Thus the bound does not depend on the number of time steps once J meets the stated condition.Source: §6.2 · p. 21

7.1 A weighted combination of reuse lengths

• The reuse-length coefficients satisfy Σ_N λ_N = 1 and have total variation Λ < 2 while preserving the factorial approximation bound.The polynomial includes the factor Q^q, whose error is controlled by the time-ordering result.Source: §7.1 · pp. 21–22

7.2 Circuit implementation and amplification

• The LCU circuit block-encodes the weighted operator Σ_N λ_NP_N with normalization 2, and robust oblivious amplitude amplification suppresses auxiliary-register leakage.The resulting amplified block acts as the simulated unitary up to the controlled approximation error.Source: §7.2 · pp. 23–26
• Each selected reuse length N is implemented using controlled HAM-T queries, and SELECT uses 4q oracle calls before amplification.The construction represents all reuse circuits on shared registers and prepares the coefficient superposition with an auxiliary ⊥ state.Source: §7.2 · pp. 23–24

7.3 Query and gate complexity

• The identity circuit suffices when αT ≤ ε; otherwise the construction chooses q and J so the discretization, reuse, and amplification errors sum to at most ε.The three error contributions are bounded by ε/4, ε/2, and ε/4, respectively.Source: §7.3 · pp. 26–27
• The final circuit uses 12q HAM-T queries and eO(·) one- and two-qubit gates under the theorem’s Lipschitz and norm assumptions.The parameter q is chosen from the target precision and αT, while J controls the Cayley discretization error.Source: §7.3 · pp. 26–27

A Construction with a continuous time register

• For a power-of-two sampling count M, the construction defines intervals and a piecewise-constant Hamiltonian HM(t) from sampled values of H.The sampled Hamiltonian is the finite-step evolution implemented by the continuous-register counterpart.Source: A Construction with a continuous time… · p. 31
• The propagator UM(t,s) generated by HM and the associated continuous-time oracle provide the objects used by the appendix’s transducer.The Lipschitz condition and Duhamel’s formula control the relation between the sampled and target evolutions.Source: A Construction with a continuous time… · p. 31

A.1 An exact transducer on a continuous time register

• The operator R is unitary and independent of the Hamiltonian oracle, with a Volterra kernel whose support preserves time ordering.The exponential factor in the kernel belongs to the unitary construction and is not dissipative dynamics.Source: §A.1 · pp. 31–32
• Applying the oracle once before R yields an exact transducer for UM that uses one HAM-TM query.The private input is transformed through the continuous time register while the public output follows the sampled Hamiltonian evolution.Source: §A.1 · pp. 32–33
• The propagated public state satisfies ˙vt = −iHM(t)vt because the oracle contribution cancels the damping term.This establishes the public output vT = UM|ψ0⟩ while the private output remains the original catalyst.Source: §A.1 · p. 33
• The catalyst is returned unchanged, so the transducer abstraction separates one-query evolution from the later catalyst-removal construction.The paper identifies this auxiliary state as a catalyst and uses reuse constructions to address its preparation difficulty.Source: §A.1 · p. 33

Factorial bound

• Causality makes Q’s kernel depend only on earlier input times, so composing Q repeatedly integrates over ordered intermediate times.The identity term cancels, and the remaining terms contain L0; this establishes the causal support used in the iterative bound.Source: §A.2 · pp. 33–34
• The ordered integrations give a factorial decay bound for Q^q when q is at least max{1, αT}.The continuous estimate is obtained by combining the kernel composition argument with the Laplace-transform bound and choosing θ = q/T.Source: §A.2 · p. 34

Combination of reuse lengths

• The continuous transducer inherits the reusable block identities needed to form reuse circuits and combine them with coefficients λ_N.The construction defines P_N for the continuous transducer and uses the same coefficient framework to build e_U.Source: §A.2 · p. 34
• The weighted combination has coefficient norm below 2 and requires no reuse length larger than 4q.Contraction bounds on A and C control the combined operator while the preceding propositions supply the approximation estimate.Source: §A.2 · p. 34

Finite-dimensional restriction

• Every private state reachable after k transducer calls lies in a subspace V_k indexed by sampling interval and polynomial degree.The multiplication oracle preserves these subspaces, while K0 and subsequent applications of A increase degree by at most one per call.Source: §A.3 · p. 35
• The reachable subspace has dimension M(k + 1), because sampling-interval supports are disjoint and within-interval polynomials are linearly independent.This gives dim V_4q = M(4q + 1) for the maximum reuse length used in the construction.Source: §A.3 · p. 35
• Choosing interval-wise bases makes the oracle block diagonal and preserves its one-query HAM-TM cost.The oracle acts as HAM-TM tensored with an identity on the basis index within each sampling interval.Source: §A.3 · p. 35
• Finite-dimensional unitary extensions reproduce every reuse circuit of up to 4q transducer calls.The extensions agree with the continuous construction on the reachable subspaces, so the circuits entering e_U are preserved.Source: §A.3 · p. 35
• The restriction introduces no truncation error and retains the same asymptotic query scaling, using 12q HAM-TM queries.The result follows after choosing M and q as in the earlier construction and applying LCU and amplification.Source: §A.3 · p. 35
• No efficient circuit is supplied for the restricted K0 or the unitary extension, so the construction makes no gate-complexity claim.The unitary completion is explicitly used only as an existence argument and does not improve the one- and two-qubit gate bound in Theorem 9.Source: §A.3 · p. 35