Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Query-optimal quantum simulation of Lindblad evolution — E8 Intelligence Research

Andrew Stewart Caldin

Published Nov 5, 2026• 0 citations
Publisher

Abstract

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 gate 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. Although our additional gate complexity is higher than that of existing algorithms, our optimal query complexity resolves the question o Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

DOI
10.5281/zenodo.23979014

Related papers

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.

quant-pharXiv:2609.17490•Sep 16, 2026•10 citations

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.

quant-pharXiv:2609.18757•Sep 17, 2026•9 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.

quant-pharXiv:2608.06094•Aug 7, 2026•15 citations

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

Jacob Kitchen

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

quant-pharXiv:2609.31312•Sep 28, 2026•0 citations

Quantum simulation of slow analytic time-dependent Hamiltonians

Chenhao Zhao, Yinan Li, Dong An

We develop a quantum algorithm for slow analytic Hamiltonians $\widetilde H(t)=H(t/T)$ with $\|H(s)\|\leqα$ 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 $\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)$ and additional gate complexity $\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)$, 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.

quant-pharXiv:2608.17653•Aug 19, 2026•1 citation

Hardness of Pathfinding in a Welded Tree — E8 Intelligence Research

Andrew Stewart Caldin

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records. Source: http://arxiv.org/abs/2609.20651v1 (arXiv:2609.20651v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 7, 2026•0 citations
For the problem of simulating Lindblad evolution for time ttt to precision εεε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε))Ω(t + \mathrm{polylog}(1/ε))Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(t polylog(1/ε))\mathcal{O}(t\,\mathrm{polylog}(1/ε))O(tpolylog(1/ε)), in gate 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. Although our additional gate complexity is higher than that of existing algorithms, our optimal query complexity resolves the question o Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
For the problem of simulating Lindblad evolution for time ttt to precision εεε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε))Ω(t + \mathrm{polylog}(1/ε))Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(t polylog(1/ε))\mathcal{O}(t\,\mathrm{polylog}(1/ε))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 Lindbladian simulation given a block encoding of the Hamiltonian HHH and a projected unitary encoding of the stacked jump operator B=∑k=1m∣k⟩⊗LkB=\sum_{k=1}^m \lvert k\rangle\otimes L_kB=∑k=1m​∣k⟩⊗Lk​, with normalization factors αHα_HαH​ and αBα_BαB​, respectively. For evolution time ttt, set τ=(αH+αB2)tτ=(α_H+α_B^2)tτ=(αH​+αB2​)t. The algorithm approximates the evolution channel to diamond-norm error ε\varepsilonε using O ⁣(τ+log⁡(1/ε)log⁡ ⁣(e+log⁡(1/ε)/τ))O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)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.
We give a query-optimal algorithm for simulating a general nnn-qubit time-dependent Hamiltonian H(t)H(t)H(t) on [0,T][0,T][0,T], assuming that HHH is Lipschitz continuous and ∥H(t)∥≤α\|H(t)\|\leqα∥H(t)∥≤α. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator UH(T)U_H(T)UH​(T) to error ε\varepsilonε using O(αT+log⁡(1/ε)log⁡(e+log⁡(1/ε)/(αT))) O\left( αT+\frac{\log(1/\varepsilon)} {\log(e+\log(1/\varepsilon)/(αT))} \right) O(αT+log(e+log(1/ε)/(αT))log(1/ε)​) $\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 UH(T)U_H(T)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.
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/ε)/log⁡(e+log⁡(1/ε)/τ))O(1+τ+\log(1/\varepsilon)/\log(e+\log(1/\varepsilon)/τ))O(1+τ+log(1/ε)/log(e+log(1/ε)/τ)) controlled queries, where τ=T(αH+∑μαμ2)τ=T(α_H+\sum_μα_μ^2)τ=T(αH​+∑μ​αμ2​). This bound is independent of the time-grid size and is worst-case optimal for τ≥1τ\ge1τ≥1. 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 nnn lattice sites, efficient coherent evaluation of the local matrices and fixed local parameters give O(n(T+1)polylog⁡X)O(n(T+1)\operatorname{polylog}X)O(n(T+1)polylogX) elementary gates, where X=max⁡{e,n(T+1)(1+Kt+B)/ε}X=\max\{e,n(T+1)(1+K_t+B)/\varepsilon\}X=max{e,n(T+1)(1+Kt​+B)/ε}, for piecewise Hölder generators with fixed exponent, local variation bound KtK_tKt​, and at most BBB 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)polylog⁡X(T+1)\operatorname{polylog}X(T+1)polylogX and space npolylog⁡Xn\operatorname{polylog}XnpolylogX.
We develop a quantum algorithm for slow analytic Hamiltonians H~(t)=H(t/T)\widetilde H(t)=H(t/T)H(t)=H(t/T) with ∥H(s)∥≤α\|H(s)\|\leqα∥H(s)∥≤α that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of H(s)H(s)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/ε))\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)O(αT+log(1/ε)) and additional gate complexity O~ ⁣((αT+log⁡(1/ε))2log⁡(1/ε))\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)O((αT+log(1/ε))2log(1/ε)), assuming coherent access to H′(s)H'(s)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.
Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height nnn, any quantum query algorithm requires at least Ω(2n/24)Ω(2^{n/24})Ω(2n/24) queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records. Source: http://arxiv.org/abs/2609.20651v1 (arXiv:2609.20651v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com