arXiv:2609.31312
Causal Query Compression for Lindblad Dynamics: Optimal Queries and Nearly Linear Local Simulation
Jacob Kitchen
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$.
AI Summary
The paper addresses query complexity for time-dependent Lindblad simulation and gate complexity for finite-range lattice dynamics, separating coherent oracle access from local-matrix evaluation. With coherently selectable block encodings of the Hamiltonian and individual jumps, a Lipschitz generator is simulated to diamond error $\varepsilon$ using $O(1+\tau+\log(1/\varepsilon)/\log(e+\log(1/\varepsilon)/\tau))$ controlled queries, where $\tau=T(\alpha_H+\sum_\mu\alpha_\mu^2)$. The count is independent of the discretization size and worst-case optimal for $\tau\ge1$, already for Hamiltonians. A chronological transducer compresses weak query cells through a factorial history-tail estimate. Combining two reuse lengths removes its auxiliary input; a three-call polar correction constructs the Lindblad cells. The compiler also establishes constant-factor equivalence between minimum oracle action in a bounded adaptive Markovian model, ordinary quantum query complexity, and the general adversary bound. For $n$ lattice sites with fixed dimension, range, degree, jump count, and normalization bounds, efficiently evaluable local matrices give $O(n(T+1)\operatorname{polylog}X)$ gates, depth $(T+1)\operatorname{polylog}X$, and space $n\operatorname{polylog}X$, where $X=\max\{e,n(T+1)(1+K_t+B)/\varepsilon\}$. Here local generators are piecewise Hölder with fixed exponent, variation bound $K_t$, and at most $B$ breakpoints per term; jumps need not commute. The construction combines common-bath spatial decomposition, occupied-input compilation, compressed bath records, and occupation cutoffs. Query optimality does not imply gate efficiency without these additional assumptions. No matching local gate lower bound is claimed, and the polylogarithmic exponents are unoptimized. The adaptive characterization excludes old-bath reinteraction, expected-action accounting, unbounded generators, and uncharged postselection. Independent concurrent query-optimal Lindblad simulation is noted.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 27 pages