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:2605.30301

Improved sample complexity bound for sample-based Lindbladian simulation

Siheon Park, Youngjin Seo, Byeongseon Go, Dhrumil Patel, Mark M. Wilde, Hyukjoon Kwon

quant-phSubmitted May 28, 2026• Announced May 29, 2026• 0 citations
arXivHTMLPDF

Abstract

We establish improved sample-complexity bounds for sample-based Lindbladian simulation based on the Wave Matrix Lindbladization (WML) algorithm. For a jump operator $L$ with dimension $d$, we derive an explicit non-asymptotic sample complexity bound $n_d^*(t,\varepsilon) \le \left( \frac{2d+3}{8} \right) \|L\|_\infty^2 \left( \frac{t^2}{\varepsilon} \right)$, holding for simulation time $t$ and error $\varepsilon$. This refines the dimension dependence of the best previously known bound, $O(d^2 t^2/\varepsilon)$, from [Go et al., Quantum Sci. Tech. 10, 045058 (2025)]. Remarkably, we show that this dimensional overhead can be entirely avoided when $\| L\|_\infty^2 = O(1/d)$, a condition satisfied with high probability for random Lindblad operators, yielding a typical-case sample complexity of $O(t^2/\varepsilon)$. On the other hand, in the worst case, we show that WML necessarily requires $Ω(dt^2/\varepsilon)$ samples by constructing an explicit example with a rank-one Lindblad operator. Our results reveal a sharp dichotomy between typical and adversarial sample complexities in Lindbladian simulation, thereby strengthening the theoretical foundations of sample-based quantum algorithms.

Comments
31 pages

Related papers

Sample-based Hamiltonian and Lindbladian simulation: non-asymptotic analysis of sample complexity

Byeongseon Go, Hyukjoon Kwon, Siheon Park +2 more

Abstract Density matrix exponentiation (DME) is a quantum algorithm that processes multiple copies of a program state σ to realize the Hamiltonian evolution e − i σ t . Wave matrix Lindbladization (WML) similarly processes multiple copies of a program state ψ L in order to realize a Lindbladian evolution. Both algorithms are prototypical sample-based quantum algorithms and can be used for various quantum information processing tasks, including quantum principal component analysis, Hamiltonian simulation, and Lindbladian simulation. In this work, we present detailed sample complexity analyses for DME and sample-based Hamiltonian simulation, as well as for WML and sample-based Lindbladian simulation. In particular, we prove that the sample complexity of DME is no larger than 4 t 2 / ε , where t is the desired evolution time and ɛ is the desired imprecision level, as quantified by the normalized diamond distance. We also establish a fundamental lower bound on the sample complexity of sample-based Hamiltonian simulation, which matches our DME sample complexity bound up to a constant multiplicative factor, thereby proving that DME is optimal for sample-based Hamiltonian simulation. Additionally, we prove that the sample complexity of WML is no larger than 3 t 2 d 2 / ε , where d is the dimension of the space on which the Lindblad operator acts nontrivially, and we prove a lower bound of 10 − 4 t 2 / ε on the sample complexity of sample-based Lindbladian simulation. These results prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially on a constant-sized system. Finally, we point out that the DME sample complexity analysis in Kimmel et al(2017 npj Quantum Inf. 3 13) and the WML sample complexity analysis in Patel and Wilde (2023 Open Syst. Inf. Dyn. 30 2350010) appear to be incomplete, highlighting the need for the results presented here.

arXiv:2412.02134•Quantum Science and Technology•Sep 17, 2025•17 citations

Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials

Dhrumil Patel, Mark M. Wilde

In this paper, we investigate the problem of simulating open system dynamics governed by the well-known Lindblad master equation. In our prequel paper [Patel and Wilde, Open Sys. & Info. Dyn., 30:2350010 (2023)], we introduced an input model in which Lindblad operators are encoded into pure quantum states, called program states, and we also introduced a method, called wave matrix Lindbladization, for simulating Lindbladian evolution by means of interacting the system of interest with these program states. Therein, we focused on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Here, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexity, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to full tomography of encoded operators, by proving that the sample complexity for tomography is dependent on the dimension of the system, whereas the sample complexity of wave matrix Lindbladization is dimension independent.

arXiv:2309.14453•Open Systems & Information Dynamics•Sep 1, 2023•18 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

A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation

Hongrui Chen, Bowen Li, Jianfeng Lu +1 more

We study a qDRIFT-type randomized method to simulate Lindblad dynamics by decomposing its generator into an ensemble of Lindbladians, L = ∑ a ∈ A L a , where each L a comprises a simple Hamiltonian and a single jump operator. Assuming an efficient quantum simulation is available for the Lindblad evolution e t L a , we implement e t L a for a randomly sampled L a at each time step according to a probability distribution μ over the ensemble { L a } a ∈ A . This randomized strategy reduces the quantum cost of simulating Lindblad dynamics, particularly in quantum many-body systems with a large or even infinite number of jump operators.Our contributions are two-fold. First, we provide a detailed convergence analysis of the proposed randomized method, covering both average and typical algorithmic realizations. This analysis extends the known results for the random product formula from closed systems to open systems, ensuring rigorous performance guarantees. Second, based on the random product approximation, we derive a new quantum Gibbs sampler algorithm that utilizes jump operators sampled from a Clifford-random circuit. This generator (i) can be efficiently implemented using our randomized algorithm, and (ii) exhibits a spectral gap lower bound that depends on the spectrum of the Hamiltonian. Our results present a new instance of a class of Hamiltonians for which the thermal states can be efficiently prepared using a quantum Gibbs sampling algorithm.

arXiv:2407.06594•Quantum•Nov 20, 2025•35 citations

Optimal Quantum Sample Complexity of Learning Algorithms

Srinivasan Arunachalam, Ronald de Wolf

$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its "richness." In the PAC model $$ Θ\Big(\frac{d}{\eps} + \frac{\log(1/δ)}{\eps}\Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-δ$, a hypothesis $h$ that is $\eps$-close to the target concept $c$. In the related agnostic model, where the samples need not come from a $c\in C$, we know that $$ Θ\Big(\frac{d}{\eps^2} + \frac{\log(1/δ)}{\eps^2}\Big) $$ examples are necessary and sufficient to output an hypothesis $h\in C$ whose error is at most $\eps$ worse than the best concept in $C$. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting, quantum examples cannot be much more powerful: the required number of quantum examples is $$ Ω\Big(\frac{d^{1-η}}{\eps} + d + \frac{\log(1/δ)}{\eps}\Big)\mbox{ for all }η> 0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $\log(d/\eps)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors.

arXiv:1607.00932•Jul 4, 2016•48 citations

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Richard Cleve, Chunhao Wang

We consider the natural generalization of the Schrödinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an $n$-qubit system for time $t$ within precision $ε$. If the Lindbladian consists of $\mathrm{poly}(n)$ operators that can each be expressed as a linear combination of $\mathrm{poly}(n)$ tensor products of Pauli operators then the gate cost of our algorithm is $O(t\, \mathrm{polylog}(t/ε)\mathrm{poly}(n))$. We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of $O(t^2/ε)$ even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.

arXiv:1612.09512•Leibniz international proceedings in informatics•Dec 30, 2016•137 citations
We establish improved sample-complexity bounds for sample-based Lindbladian simulation based on the Wave Matrix Lindbladization (WML) algorithm. For a jump operator LLL with dimension ddd, we derive an explicit non-asymptotic sample complexity bound nd∗(t,ε)≤(2d+38)∥L∥∞2(t2ε)n_d^*(t,\varepsilon) \le \left( \frac{2d+3}{8} \right) \|L\|_\infty^2 \left( \frac{t^2}{\varepsilon} \right)nd∗​(t,ε)≤(82d+3​)∥L∥∞2​(εt2​), holding for simulation time ttt and error ε\varepsilonε. This refines the dimension dependence of the best previously known bound, O(d2t2/ε)O(d^2 t^2/\varepsilon)O(d2t2/ε), from [Go et al., Quantum Sci. Tech. 10, 045058 (2025)]. Remarkably, we show that this dimensional overhead can be entirely avoided when ∥L∥∞2=O(1/d)\| L\|_\infty^2 = O(1/d)∥L∥∞2​=O(1/d), a condition satisfied with high probability for random Lindblad operators, yielding a typical-case sample complexity of O(t2/ε)O(t^2/\varepsilon)O(t2/ε). On the other hand, in the worst case, we show that WML necessarily requires Ω(dt2/ε)Ω(dt^2/\varepsilon)Ω(dt2/ε) samples by constructing an explicit example with a rank-one Lindblad operator. Our results reveal a sharp dichotomy between typical and adversarial sample complexities in Lindbladian simulation, thereby strengthening the theoretical foundations of sample-based quantum algorithms.
Abstract Density matrix exponentiation (DME) is a quantum algorithm that processes multiple copies of a program state σ to realize the Hamiltonian evolution e − i σ t . Wave matrix Lindbladization (WML) similarly processes multiple copies of a program state ψ L in order to realize a Lindbladian evolution. Both algorithms are prototypical sample-based quantum algorithms and can be used for various quantum information processing tasks, including quantum principal component analysis, Hamiltonian simulation, and Lindbladian simulation. In this work, we present detailed sample complexity analyses for DME and sample-based Hamiltonian simulation, as well as for WML and sample-based Lindbladian simulation. In particular, we prove that the sample complexity of DME is no larger than 4 t 2 / ε , where t is the desired evolution time and ɛ is the desired imprecision level, as quantified by the normalized diamond distance. We also establish a fundamental lower bound on the sample complexity of sample-based Hamiltonian simulation, which matches our DME sample complexity bound up to a constant multiplicative factor, thereby proving that DME is optimal for sample-based Hamiltonian simulation. Additionally, we prove that the sample complexity of WML is no larger than 3 t 2 d 2 / ε , where d is the dimension of the space on which the Lindblad operator acts nontrivially, and we prove a lower bound of 10 − 4 t 2 / ε on the sample complexity of sample-based Lindbladian simulation. These results prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially on a constant-sized system. Finally, we point out that the DME sample complexity analysis in Kimmel et al(2017 npj Quantum Inf. 3 13) and the WML sample complexity analysis in Patel and Wilde (2023 Open Syst. Inf. Dyn. 30 2350010) appear to be incomplete, highlighting the need for the results presented here.
In this paper, we investigate the problem of simulating open system dynamics governed by the well-known Lindblad master equation. In our prequel paper [Patel and Wilde, Open Sys. & Info. Dyn., 30:2350010 (2023)], we introduced an input model in which Lindblad operators are encoded into pure quantum states, called program states, and we also introduced a method, called wave matrix Lindbladization, for simulating Lindbladian evolution by means of interacting the system of interest with these program states. Therein, we focused on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Here, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexity, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to full tomography of encoded operators, by proving that the sample complexity for tomography is dependent on the dimension of the system, whereas the sample complexity of wave matrix Lindbladization is dimension independent.
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 study a qDRIFT-type randomized method to simulate Lindblad dynamics by decomposing its generator into an ensemble of Lindbladians, L = ∑ a ∈ A L a , where each L a comprises a simple Hamiltonian and a single jump operator. Assuming an efficient quantum simulation is available for the Lindblad evolution e t L a , we implement e t L a for a randomly sampled L a at each time step according to a probability distribution μ over the ensemble { L a } a ∈ A . This randomized strategy reduces the quantum cost of simulating Lindblad dynamics, particularly in quantum many-body systems with a large or even infinite number of jump operators.Our contributions are two-fold. First, we provide a detailed convergence analysis of the proposed randomized method, covering both average and typical algorithmic realizations. This analysis extends the known results for the random product formula from closed systems to open systems, ensuring rigorous performance guarantees. Second, based on the random product approximation, we derive a new quantum Gibbs sampler algorithm that utilizes jump operators sampled from a Clifford-random circuit. This generator (i) can be efficiently implemented using our randomized algorithm, and (ii) exhibits a spectral gap lower bound that depends on the spectrum of the Hamiltonian. Our results present a new instance of a class of Hamiltonians for which the thermal states can be efficiently prepared using a quantum Gibbs sampling algorithm.
$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a concept class CCC is the most common way to measure its "richness." In the PAC model $$ Θ\Big(\frac{d}{\eps} + \frac{\log(1/δ)}{\eps}\Big) $$ examples are necessary and sufficient for a learner to output, with probability 1−δ1-δ1−δ, a hypothesis hhh that is $\eps$-close to the target concept ccc. In the related agnostic model, where the samples need not come from a c∈Cc\in Cc∈C, we know that $$ Θ\Big(\frac{d}{\eps^2} + \frac{\log(1/δ)}{\eps^2}\Big) $$ examples are necessary and sufficient to output an hypothesis h∈Ch\in Ch∈C whose error is at most $\eps$ worse than the best concept in CCC. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting, quantum examples cannot be much more powerful: the required number of quantum examples is $$ Ω\Big(\frac{d^{1-η}}{\eps} + d + \frac{\log(1/δ)}{\eps}\Big)\mbox{ for all }η> 0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $\log(d/\eps)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors.
We consider the natural generalization of the Schrödinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an nnn-qubit system for time ttt within precision εεε. If the Lindbladian consists of poly(n)\mathrm{poly}(n)poly(n) operators that can each be expressed as a linear combination of poly(n)\mathrm{poly}(n)poly(n) tensor products of Pauli operators then the gate cost of our algorithm is O(t polylog(t/ε)poly(n))O(t\, \mathrm{polylog}(t/ε)\mathrm{poly}(n))O(tpolylog(t/ε)poly(n)). We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of O(t2/ε)O(t^2/ε)O(t2/ε) even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.