We give a query-optimal algorithm for simulating a general $n$-qubit time-dependent Hamiltonian $H(t)$ on $[0,T]$, assuming that $H$ is Lipschitz continuous and $\|H(t)\|\leqα$. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator $U_H(T)$ to error $\varepsilon$ using $$ O\left(
αT+\frac{\log(1/\varepsilon)}
{\log(e+\log(1/\varepsilon)/(αT))}
\right) $$ $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead.
Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to $U_H(T)$ and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.
We give a query-optimal algorithm for simulating a general n-qubit time-dependent Hamiltonian H(t) on [0,T], assuming that H is Lipschitz continuous and ∥H(t)∥≤α. In the standard HAM\mbox−T access model, the algorithm approximates the time-ordered propagator UH(T) to error ε using $$ O\left(
αT+\frac{\log(1/\varepsilon)}
{\log(e+\log(1/\varepsilon)/(αT))}
\right) $$ HAM\mbox−T queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead.
Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to UH(T) and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.
The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses q=O(αT+log(e+log(1/ε)/(αT))log(1/ε)) queries to $\mathrm{HAM\mbox{-}T}$ within ε error for a Lipschitz-continuous time-dependent Hamiltonian H(t) on [0,T] satisfying ∥H(t)∥≤α. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses O[q(a+log(1+εT(α+βT)))] one- and two-qubit gates, where a is the number of block-encoding ancilla qubits and β is the Lipschitz constant of H. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.
We develop a quantum algorithm for slow analytic Hamiltonians H(t)=H(t/T) with ∥H(s)∥≤α that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of H(s), together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding and optimal time-independent Hamiltonian simulation technique, this gives query complexity O(αT+log(1/ε)) and additional gate complexity O((αT+log(1/ε))2log(1/ε)), assuming coherent access to H′(s) and endpoint derivatives. For slow analytic control Hamiltonians, only block encodings of the time-independent control operators are required, with the same query complexity and lower gate overhead. Our method also extends to Gevrey Hamiltonians and improves the precision dependence for simulating slow analytic semi-dissipative linear differential equations.
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian H and a projected unitary encoding of the stacked jump operator B=∑k=1m∣k⟩⊗Lk, with normalization factors αH and αB, respectively. For evolution time t, set τ=(αH+αB2)t. The algorithm approximates the evolution channel to diamond-norm error ε using O(τ+log(e+log(1/ε)/τ)log(1/ε)) oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.
For the problem of simulating Lindblad evolution for time t to precision ε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(tpolylog(1/ε)), in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.
We give a quantum algorithm for simulating a d-sparse Hermitian Hamiltonian H, assuming a known upper bound Λ on its maximum column Euclidean norm ∥H∥1→2. For tΛ≥1/2, simulation with operator-norm error ε uses O(tΛd+dlog(2/ε)) sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For d>1 and tΛ≥log(2/ε), the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of Λ. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters.
As applications, we obtain O(κdpolylog(κ/ε)) queries for solving d-sparse quantum linear systems with ∥A∥≤1 and ∥A−1∥≤κ, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most d nonzero entries per row and column using O(dlog(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(N) queries for arbitrary N×N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an s-sparse Hermitian matrix with row and column Euclidean norms bounded by η, evolution for time t to error ε uses O(sτ+sτlog(1/ε)+log(1/ε)) queries, where τ=η∣t∣. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in sτ and log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log(Cgˉ/ε)) queries, where τ is the evolution time multiplied by a norm bound, gˉ bounds the ratio of combined input and source norms to the final-solution norm, and C is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give O(κslog(1/ε)) queries when ∥A∥≤1 and ∥A−1∥≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.