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

arXiv:2609.18757

Query-Optimal and Gate-Efficient Lindbladian Simulation

Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

quant-phcs.DSSubmitted Sep 16, 2026• Announced Sep 17, 2026• 9 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks whether general Lindbladian simulation can attain the optimal joint evolution-time and precision dependence known for Hamiltonian simulation. It assumes a block encoding of $H$ with normalization $\alpha_H$ and a projected unitary encoding of the stacked jump operator $B=\sum_k|k\rangle\otimes L_k$ with normalization $\alpha_B$. Writing $\tau=(\alpha_H+\alpha_B^2)t$, it gives a channel approximation with diamond-norm error $\varepsilon$ using $O\!\left(\tau+\frac{\log(1/\varepsilon)}{\log(e+\log(1/\varepsilon)/\tau)}\right)$ oracle queries. This matches the Hamiltonian-subclass lower bound for $\tau\geq1$. The construction discretizes evolution into rational CPTP steps with total error at most $10\tau^2/J$. A one-query transducer implements their product when supplied with an input-dependent catalyst. To avoid preparing that catalyst, the algorithm combines different transducer-reuse lengths through LCU and oblivious amplitude amplification. Tracking monotone time indices and orthogonality between Kraus-label histories yields an approximation error bounded by $\sqrt\tau(C\tau/q)^q$, with $O(q)$ queries. Compressed storage of nonzero Kraus labels and rotation factorization give additional gate complexity $O\!\left(Q[a+\ell(\log(m+1)+\ell)]\right)$, where $Q$ is the query bound and $\ell=\log(e(1+\tau)/\varepsilon)$. The query bound extends to Lipschitz-continuous time-dependent generators under coherent time-indexed oracle access; the Lipschitz constant enters the discretization and gate bounds. Costs exclude implementing the supplied oracles, including coherent jump-operator selection and state preparation when constructing stacked access from individual encodings. Exploiting locality, small commutators, or other generator structure remains open.

Little sign of AI-generated textAI use disclosed
The main ideas underlying the work, including the central proof strategies, were generated by large language models.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
62 pages, 5 figures

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

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.30629•Sep 1, 2026•11 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

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

Optimal Lower Bounds for Hamiltonian Simulation

Alexander Zlokapa, Richard R. Allen, Aram W. Harrow

For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.

quant-pharXiv:2607.19852•Jul 23, 2026•2 citations

Learning Arbitrary Lindbladians from Time Evolution

Zhili Chen, Zhan Yu

We study the problem of learning arbitrary $n$-qubit Lindbladians, the generators of Markovian open-system dynamics, from their time evolution. We give the first known efficient algorithm that learns arbitrary Lindbladians without any structural assumptions. For an $n$-qubit Lindbladian of dynamical strength at most $Λ$, the algorithm estimates every coefficient to error $\varepsilon$ using $\widetilde O(Λ^2/\varepsilon^2)$ experiments and $\widetilde O(Λ/\varepsilon^2)$ total evolution time, with classical running time polynomial in $n$ and $Λ/\varepsilon$. Both experimental costs match known lower bounds up to polylogarithmic factors. The algorithm identifies candidate labels through product Pauli experiments and estimates their coefficients using random stabilizer preparations and Clifford measurements. It requires no ancillas or control during the unknown evolution. For constant $k$, our algorithm learns generic $k$-local Lindbladians of local dynamical strength at most $Λ_{\mathrm{loc}}$ using $\widetilde O(n^2Λ_{\mathrm{loc}}^2/\varepsilon^2)$ experiments and $\widetilde O(nΛ_{\mathrm{loc}}/\varepsilon^2)$ total evolution time, improving the upper bounds of prior works in terms of the dependence on $n$. We further improve the lower bounds of Arad, Chen, Guo, Rebentrost, and Yu (SODA 2027) using a family of $3$-local Lindbladians. They already hold when the support is known, and only one Hamiltonian coefficient is requested, even for adaptive protocols with arbitrary ancillas and quantum memory. These lower bounds establish that our algorithm is optimal up to polylogarithmic factors in both experiment count and total evolution time for every fixed $k \geq 3$.

quant-pharXiv:2607.28610•Jul 31, 2026•5 citations
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.
The paper asks whether general Lindbladian simulation can attain the optimal joint evolution-time and precision dependence known for Hamiltonian simulation. It assumes a block encoding of HHH with normalization αH\alpha_HαH​ and a projected unitary encoding of the stacked jump operator B=∑k∣k⟩⊗LkB=\sum_k|k\rangle\otimes L_kB=∑k​∣k⟩⊗Lk​ with normalization αB\alpha_BαB​. Writing τ=(αH+αB2)t\tau=(\alpha_H+\alpha_B^2)tτ=(αH​+αB2​)t, it gives a channel approximation with diamond-norm error ε\varepsilonε using O ⁣(τ+log⁡(1/ε)log⁡(e+log⁡(1/ε)/τ))O\!\left(\tau+\frac{\log(1/\varepsilon)}{\log(e+\log(1/\varepsilon)/\tau)}\right)O(τ+log(e+log(1/ε)/τ)log(1/ε)​) oracle queries. This matches the Hamiltonian-subclass lower bound for τ≥1\tau\geq1τ≥1.
The construction discretizes evolution into rational CPTP steps with total error at most 10τ2/J10\tau^2/J10τ2/J. A one-query transducer implements their product when supplied with an input-dependent catalyst. To avoid preparing that catalyst, the algorithm combines different transducer-reuse lengths through LCU and oblivious amplitude amplification. Tracking monotone time indices and orthogonality between Kraus-label histories yields an approximation error bounded by τ(Cτ/q)q\sqrt\tau(C\tau/q)^qτ​(Cτ/q)q, with O(q)O(q)O(q) queries. Compressed storage of nonzero Kraus labels and rotation factorization give additional gate complexity O ⁣(Q[a+ℓ(log⁡(m+1)+ℓ)])O\!\left(Q[a+\ell(\log(m+1)+\ell)]\right)O(Q[a+ℓ(log(m+1)+ℓ)]), where QQQ is the query bound and ℓ=log⁡(e(1+τ)/ε)\ell=\log(e(1+\tau)/\varepsilon)ℓ=log(e(1+τ)/ε).
The query bound extends to Lipschitz-continuous time-dependent generators under coherent time-indexed oracle access; the Lipschitz constant enters the discretization and gate bounds. Costs exclude implementing the supplied oracles, including coherent jump-operator selection and state preparation when constructing stacked access from individual encodings. Exploiting locality, small commutators, or other generator structure remains open.
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.
The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses q=O(αT+log⁡(1/ε)log⁡(e+log⁡(1/ε)/(αT))) q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) q=O(αT+log(e+log(1/ε)/(αT))log(1/ε)​) queries to $\mathrm{HAM\mbox{-}T}$ within ε\varepsilonε error for a Lipschitz-continuous time-dependent Hamiltonian H(t)H(t)H(t) on [0,T][0,T][0,T] satisfying ∥H(t)∥≤α\left\lVert H(t)\right\rVert\leqα∥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)ε))] O\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] O[q(a+log(1+εT(α+βT)​))] one- and two-qubit gates, where aaa is the number of block-encoding ancilla qubits and βββ is the Lipschitz constant of HHH. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.
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 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.
For Hamiltonian H=∑jhjH = \sum_j h_jH=∑j​hj​, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ∥hj∥\|h_j\|∥hj​∥, time ttt, and trace-distance error εεε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ∥hj∥\|h_j\|∥hj​∥ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε1/ε1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
We study the problem of learning arbitrary nnn-qubit Lindbladians, the generators of Markovian open-system dynamics, from their time evolution. We give the first known efficient algorithm that learns arbitrary Lindbladians without any structural assumptions. For an nnn-qubit Lindbladian of dynamical strength at most ΛΛΛ, the algorithm estimates every coefficient to error ε\varepsilonε using O~(Λ2/ε2)\widetilde O(Λ^2/\varepsilon^2)O(Λ2/ε2) experiments and O~(Λ/ε2)\widetilde O(Λ/\varepsilon^2)O(Λ/ε2) total evolution time, with classical running time polynomial in nnn and Λ/εΛ/\varepsilonΛ/ε. Both experimental costs match known lower bounds up to polylogarithmic factors. The algorithm identifies candidate labels through product Pauli experiments and estimates their coefficients using random stabilizer preparations and Clifford measurements. It requires no ancillas or control during the unknown evolution. For constant kkk, our algorithm learns generic kkk-local Lindbladians of local dynamical strength at most ΛlocΛ_{\mathrm{loc}}Λloc​ using O~(n2Λloc2/ε2)\widetilde O(n^2Λ_{\mathrm{loc}}^2/\varepsilon^2)O(n2Λloc2​/ε2) experiments and O~(nΛloc/ε2)\widetilde O(nΛ_{\mathrm{loc}}/\varepsilon^2)O(nΛloc​/ε2) total evolution time, improving the upper bounds of prior works in terms of the dependence on nnn. We further improve the lower bounds of Arad, Chen, Guo, Rebentrost, and Yu (SODA 2027) using a family of 333-local Lindbladians. They already hold when the support is known, and only one Hamiltonian coefficient is requested, even for adaptive protocols with arbitrary ancillas and quantum memory. These lower bounds establish that our algorithm is optimal up to polylogarithmic factors in both experiment count and total evolution time for every fixed k≥3k \geq 3k≥3.