arXiv:2609.31312

Causal Query Compression for Lindblad Dynamics: Optimal Queries and Nearly Linear Local Simulation

Jacob Kitchen

quant-phSubmitted Sep 25, 2026• Announced Sep 28, 2026• 0 citations

Abstract

We construct a causal query compiler for time-dependent Lindblad dynamics and establish query and gate bounds under distinct input models. With coherent block encodings of the Hamiltonian and individual jump operators, a Lipschitz generator can be simulated to diamond-norm error $\varepsilon$ using $O(1+τ+\log(1/\varepsilon)/\log(e+\log(1/\varepsilon)/τ))$ controlled queries, where $τ=T(α_H+\sum_μα_μ^2)$. This bound is independent of the time-grid size and is worst-case optimal for $τ\ge1$. Weak active entry and clean return yield a factorial history tail; combining two reuse lengths removes the auxiliary input. A three-call polar correction supplies the Lindblad cells. The compiler also characterizes the minimum oracle action of bounded adaptive Markovian protocols by quantum query complexity and the general adversary bound, up to constant factors. For finite-range dynamics on $n$ lattice sites, efficient coherent evaluation of the local matrices and fixed local parameters give $O(n(T+1)\operatorname{polylog}X)$ elementary gates, where $X=\max\{e,n(T+1)(1+K_t+B)/\varepsilon\}$, for piecewise Hölder generators with fixed exponent, local variation bound $K_t$, and at most $B$ breakpoints per term. The jumps need not commute. This gate bound includes evaluation, arithmetic, selection, routing, and environment storage. Its proof combines a spatial decomposition on a common bath, compilation on occupied inputs, and routing on compressed records. Reusing bath storage between short segments gives depth $(T+1)\operatorname{polylog}X$ and space $n\operatorname{polylog}X$.

Comments: 27 pages

Related papers

Query-Optimal and Gate-Efficient Lindbladian Simulation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

quant-pharXiv:2609.18757Sep 17, 20260 citations

Query-optimal quantum simulation of Lindblad evolution

Chunhao Wang, Christopher Ye

quant-pharXiv:2609.17490Sep 16, 20260 citations

Shallow Quantum Circuits for Geometrically Local Lindblad Dynamics

Zheyu Shen, Yusen Wu, Xiao Yuan +1 more

quant-pharXiv:2610.05362Oct 6, 20260 citations

Time-Dependent Hamiltonian Simulation with Optimal Query Complexity

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

quant-pharXiv:2608.06094Aug 7, 20260 citations

Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

Dominic W. Berry, Abhishek Rawat, Sophia Simon +1 more

quant-pharXiv:2610.02939Oct 5, 20260 citations

Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation

Boyang Chen, Minbo Gao, Zhengfeng Ji +3 more

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) $$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$. 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\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] $$ 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.

quant-pharXiv:2608.30629Sep 1, 20260 citations

arXiv:2609.31312

Causal Query Compression for Lindblad Dynamics: Optimal Queries and Nearly Linear Local Simulation

Jacob Kitchen

quant-phSubmitted Sep 25, 2026• Announced Sep 28, 2026• 0 citations

arXiv HTML PDF

Abstract

\varepsilon

using

O(1+τ+\log(1/\varepsilon)/\log(e+\log(1/\varepsilon)/τ))

controlled queries, where

τ=T(α_H+\sum_μα_μ^2)

. This bound is independent of the time-grid size and is worst-case optimal for

τ\ge1

. Weak active entry and clean return yield a factorial history tail; combining two reuse lengths removes the auxiliary input. A three-call polar correction supplies the Lindblad cells. The compiler also characterizes the minimum oracle action of bounded adaptive Markovian protocols by quantum query complexity and the general adversary bound, up to constant factors. For finite-range dynamics on

n

lattice sites, efficient coherent evaluation of the local matrices and fixed local parameters give

O(n(T+1)\operatorname{polylog}X)

elementary gates, where

X=\max\{e,n(T+1)(1+K_t+B)/\varepsilon\}

, for piecewise Hölder generators with fixed exponent, local variation bound

K_t

, and at most

B

breakpoints per term. The jumps need not commute. This gate bound includes evaluation, arithmetic, selection, routing, and environment storage. Its proof combines a spatial decomposition on a common bath, compilation on occupied inputs, and routing on compressed records. Reusing bath storage between short segments gives depth

(T+1)\operatorname{polylog}X

and space

n\operatorname{polylog}X

Comments: 27 pages

Related papers

Query-Optimal and Gate-Efficient Lindbladian Simulation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

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=\sum_{k=1}^m \lvert k\rangle\otimes L_k$ , with normalization factors $α_H$ and $α_B$ , respectively. For evolution time $t$ , set $τ=(α_H+α_B^2)t$ . The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ 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.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=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $α_H$ and $α_B$, respectively. For evolution time $t$, set $τ=(α_H+α_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ 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.

quant-pharXiv:2609.18757Sep 17, 20260 citations

Query-optimal quantum simulation of Lindblad evolution

Chunhao Wang, Christopher Ye

For the problem of simulating Lindblad evolution for time $t$ to precision $ε$ , Hamiltonian simulation provides an additive query lower bound, informally, $Ω(t + \mathrm{polylog}(1/ε))$ . However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(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.For the problem of simulating Lindblad evolution for time $t$ to precision $ε$, Hamiltonian simulation provides an additive query lower bound, informally, $Ω(t + \mathrm{polylog}(1/ε))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(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.

quant-pharXiv:2609.17490Sep 16, 20260 citations

Shallow Quantum Circuits for Geometrically Local Lindblad Dynamics

Zheyu Shen, Yusen Wu, Xiao Yuan +1 more

Open-system dynamics govern decoherence, transport, and engineered dissipation in quantum many-body systems. We propose a quantum algorithm for simulating time-independent, finite-range Lindblad dynamics with bounded local strength on a constant-dimensional lattice of $n$ sites, allowing noncommuting jump operators. For time $T\ge1$ and diamond-norm error at most $ε$ , it has depth $O(T\operatorname{polylog}(nT/ε))$ and gate count $O(nT\operatorname{polylog}(nT/ε))$ . These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density. We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are $Ω(nT)$ for the expected gate count and $Ω(T)$ for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of $Ω(\log n/\log\log n)$ , showing that global accuracy can require increasing depth as the lattice grows.Open-system dynamics govern decoherence, transport, and engineered dissipation in quantum many-body systems. We propose a quantum algorithm for simulating time-independent, finite-range Lindblad dynamics with bounded local strength on a constant-dimensional lattice of $n$ sites, allowing noncommuting jump operators. For time $T\ge1$ and diamond-norm error at most $ε$, it has depth $O(T\operatorname{polylog}(nT/ε))$ and gate count $O(nT\operatorname{polylog}(nT/ε))$. These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density. We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are $Ω(nT)$ for the expected gate count and $Ω(T)$ for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of $Ω(\log n/\log\log n)$, showing that global accuracy can require increasing depth as the lattice grows.

quant-pharXiv:2610.05362Oct 6, 20260 citations

Time-Dependent Hamiltonian Simulation with Optimal Query Complexity

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

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)\|\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.

quant-pharXiv:2608.06094Aug 7, 20260 citations

Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

Dominic W. Berry, Abhishek Rawat, Sophia Simon +1 more

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 $\mathcal{O}(\sqrt{s}τ+\sqrt{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 $\sqrt{s}τ$ and $\log(1/ε)$ . For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ is the evolution time multiplied by a norm bound, $\bar 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 $\mathcal{O}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$ , 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.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 $\mathcal{O}(\sqrt{s}τ+\sqrt{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 $\sqrt{s}τ$ and $\log(1/ε)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ is the evolution time multiplied by a norm bound, $\bar 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 $\mathcal{O}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$, 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.

quant-pharXiv:2610.02939Oct 5, 20260 citations

Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation

Boyang Chen, Minbo Gao, Zhengfeng Ji +3 more

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right)$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$ . 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\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right]$ 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.The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) $$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$. 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\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] $$ 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.

quant-pharXiv:2608.30629Sep 1, 20260 citations

\varepsilon

using

O(1+τ+\log(1/\varepsilon)/\log(e+\log(1/\varepsilon)/τ))

controlled queries, where

τ=T(α_H+\sum_μα_μ^2)

. This bound is independent of the time-grid size and is worst-case optimal for

τ\ge1

n

lattice sites, efficient coherent evaluation of the local matrices and fixed local parameters give

O(n(T+1)\operatorname{polylog}X)

elementary gates, where

X=\max\{e,n(T+1)(1+K_t+B)/\varepsilon\}

, for piecewise Hölder generators with fixed exponent, local variation bound

K_t

, and at most

B

(T+1)\operatorname{polylog}X

and space

n\operatorname{polylog}X

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=\sum_{k=1}^m \lvert k\rangle\otimes L_k

, with normalization factors

α_H

and

α_B

, respectively. For evolution time

t

, set

τ=(α_H+α_B^2)t

. The algorithm approximates the evolution channel to diamond-norm error

\varepsilon

using

O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)

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 + \mathrm{polylog}(1/ε))

. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally,

\mathcal{O}(t\,\mathrm{polylog}(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.

n

sites, allowing noncommuting jump operators. For time

T\ge1

and diamond-norm error at most

ε

, it has depth

O(T\operatorname{polylog}(nT/ε))

and gate count

O(nT\operatorname{polylog}(nT/ε))

. These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density. We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are

Ω(nT)

for the expected gate count and

Ω(T)

for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of

Ω(\log n/\log\log n)

, showing that global accuracy can require increasing depth as the lattice grows.

We give a query-optimal algorithm for simulating a general

n

-qubit time-dependent Hamiltonian

H(t)

[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 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

\mathcal{O}(\sqrt{s}τ+\sqrt{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

\sqrt{s}τ

and

\log(1/ε)

. For dissipative linear differential equations we obtain

\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))

queries, where

τ

is the evolution time multiplied by a norm bound,

\bar 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

\mathcal{O}(κ\sqrt{s}\log(1/ε))

queries when

\|A\|\le1

and

\|A^{-1}\|\leκ

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

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses

q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right)

queries to $\mathrm{HAM\mbox{-}T}$ within

\varepsilon

error for a Lipschitz-continuous time-dependent Hamiltonian

H(t)

[0,T]

satisfying

\left\lVert H(t)\right\rVert\leqα

. 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\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right]

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.