Improved sample complexity bound for sample-based Lindbladian simulation

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

Read Improved sample complexity bound for sample-based Lindbladian simulation by Siheon Park, Youngjin Seo, Byeongseon Go, Dhrumil Patel, Mark M. Wilde, Hyukjoon Kwon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30301.txt.

Introduction

Siheon Park and five co-authors improve sample bounds for sample Lindbladian work with the Wave Matrix Lindbladization. For a jump operator, they derive a bound cutting size dependence from squared to linear. Extra cost disappears when the operator norm squared shrinks as size grows. This likely holds for random Lindblad cases, yielding typical cost linear in time squared over error. In the worst case, the method needs samples linear in size, shown by a rank-one Lindblad operator example. Results reveal a split between typical and hostile sample costs.

Catalog record

CREATORSiheon Park, Youngjin Seo, Byeongseon Go, Dhrumil Patel, Mark M. Wilde, Hyukjoon Kwon
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74228
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30301

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improved sample complexity bound for sample-based Lindbladian simulation Siheon Park, Youngjin Seo, Byeongseon Go, Dhrumil Patel, Mark M. Wilde, Hyukjoon Kwon 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 L with dimension d d , we derive an explicit non-asymptotic sample complexity bound n d ∗ ​ ( t , ε ) ≤ ( 2 ​ d + 3 8 ) ​ ‖ L ‖ ∞ 2 ​ ( t 2 ε ) n_{d}^{*}(t,\varepsilon)\leq\left(\frac{2d+3}{8}\right)\left\|L\right\|_{\infty}^{2}\left(\frac{t^{2}}{\varepsilon}\right) , holding for simulation time t t and error ε \varepsilon . This refines the dimension dependence of the best previously known bound, O ⁡ ( d 2 ​ t 2 / ε ) 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 ‖ ∞ 2 = O ⁡ ( 1 / d ) \|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 / ε ) O(t^{2}/\varepsilon) . On the other hand, in the worst case, we show that WML necessarily requires Ω ⁡ ( d ​ t 2 / ε ) \Omega(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. I Introduction The accurate simulation of quantum systems is a cornerstone of quantum information science 8 ; 49 ; 71 ; 69 ; 24 , with broad implications ranging from quantum chemistry 67 ; 3 ; 57 ; 54 to condensed-matter physics 56 ; 19 . Hamiltonian simulation 43 ; 6 ; 44 ; 15 has been used to model the unitary dynamics of closed quantum systems, enabling the study of phenomena such as quantum phase transitions and entanglement growth. However, many realistic quantum systems are inherently open because they interact with external environments, leading to dissipation and decoherence. The dynamics of such systems can be described by the Gorini–Kossakowski–Sudarshan–Lindblad (GKSL) master equation, commonly referred to as Lindbladian dynamics, which provides a general framework for Markovian non-unitary time evolution arising from environmental coupling 8 ; 26 ; 41 . Despite substantial progress in quantum simulation, the efficient simulation of Lindbladian dynamics remains comparatively underexplored relative to Hamiltonian simulation. While this is partly because quantum computation has conventionally been formulated in terms of unitary operations, the simulation of open quantum dynamics has increasingly been studied in the contexts of dissipative quantum computing 55 ; 18 ; 75 , quantum error mitigation 64 , and Gibbs sampling 30 ; 40 , to name a few. Several approaches have been proposed to simulate open quantum systems, including higher-order Trotterization and product-formula methods 39 ; 10 ; 14 , qDrift -like randomization 33 ; 53 ; 13 , quantum trajectory methods known as unraveling 20 ; 23 ; 12 ; 11 , embeddings of Lindbladian dynamics into effective Hamiltonian simulations 17 ; 39 ; 22 ; 45 , and vectorized linear-combination techniques for superoperators 32 ; 60 . These methods exploit unitary primitives to emulate dissipative evolution, thereby narrowing the gap between closed- and open-system simulation and enabling the study of quantum dynamics in realistic settings. Wave Matrix Lindbladization (WML) was recently proposed as a sample-based Lindbladian simulation algorithm 51 ; 52 , and it offers potential advantages analogous to those of sample-based Hamiltonian simulation 42 ; 34 ; 68 ; 25 . In WML, one has access to multiple copies of a program state that encodes the target Lindbladian dynamics. The goal is to implement the Lindbladian evolution e^{\mathcal{L}t} approximately for a desired evolution time t\geq 0 , where the Lindbladian operator \mathcal{L} is the generator of the Lindbladian dynamics. While Hamiltonian terms and multiple dissipative terms could be included in more general Lindbladian dynamics, in this work, we focus instead on a single Lindblad operator L , which serves as the foundation for understanding the algorithms for general Lindbladians presented in Ref. 52 . The sample complexity of sample-based quantum simulation is defined as the number of copies of a program state, \pi , required to realize the target quantum channel e^{\mathcal{L}t} up to a desired error tolerance \varepsilon\in[0,1] . The state-of-the-art sample complexity upper bound of WML was shown as O(d^{2}t^{2}/\varepsilon) for L acting on a d -dimensional Hilbert space and normalized as \left\|L\right\|_{2}=1 25 . Although d remains small for most physically relevant systems governed by local Lindbladians, a comprehensive analysis for arbitrary, not necessarily local, Lindbladians is crucial for a more complete theoretical understanding of simulating open quantum dynamics 36 ; 18 ; 17 ; 72 ; 40 . As the algorithm-independent sample complexity lower bound \Omega(t^{2}/\varepsilon) has no explicit dependence on d 25 , the resulting d^{2} -gap between the WML upper bound and the general lower bound leaves open the possibility of sample-based quantum algorithms, or even hybrid quantum–classical algorithms, that outperform WML. This possibility is particularly relevant in light of the fact that quantum state tomography requires \Omega(d^{2}/\varepsilon^{2}) samples to achieve trace distance \varepsilon 27 ; 28 ; 74 ; 52 ; 2 . Our contribution. In this work, we establish a tighter upper bound on the sample complexity of WML for Lindbladian simulation, namely O(d\left\|L\right\|_{\infty}^{2}t^{2}/\varepsilon), (1) showing that its dimension dependence is at most linear, given that \left\|L\right\|_{\infty}^{2}\leq\left\|L\right\|_{2}^{2}=1 . This result narrows the gap with the previously known sample-complexity lower bound 25 while preserving the t^{2}/\varepsilon scaling. Crucially, reducing the dimension dependence from quadratic to linear restores a provably strict separation between the sample complexity of Lindbladian simulation and that of program-state tomography. Furthermore, using random matrix theory, we show that the dimensional overhead can even disappear for typical random instances. More precisely, Lindblad operators randomly drawn from the Frobenius-normalized Ginibre ensemble satisfy \left\|L\right\|_{\infty}^{2}=O(1/d) with high probability, in which case the WML sample-complexity upper bound becomes dimension-independent in the large- d limit. In contrast, we construct an explicit worst-case example for which the sample complexity of WML necessarily scales linearly with d , indicating an irreducible dimensional gap between typical and worst-case sample complexities. The resulting upper and lower bounds are summarized in Table 1 . Upper bound Lower bound General case n_{d}^{\ast}(t,\varepsilon)=O\!\left(\frac{d^{2}t^{2}}{\varepsilon}\right) ( 25 , Theorem 9) n_{d}^{\ast}(t,\varepsilon)=\Omega\!\left(\frac{t^{2}}{\varepsilon}\right) ( 25 , Theorem 12) n_{d}^{\ast}(t,\varepsilon)=O\!\left(\frac{d\|L\|_{\infty}^{2}t^{2}}{\varepsilon}\right) [Theorem 3 ] Typical case \overline{n}_{d}(t,\varepsilon,\delta)=O\!\left(\frac{t^{2}}{\varepsilon}\right) [Theorem 8 ] Worst case n_{d}^{\ast}(t,\varepsilon)=O\!\left(\frac{dt^{2}}{\varepsilon}\right) [Theorem 3 ] n_{\mathrm{WML}}(t,\varepsilon;\mathcal{L})=\Omega\!\left(\frac{dt^{2}}{\varepsilon}\right) [Theorem 10 ] Special case n_{d}^{\ast}(t,\varepsilon)=O\!\left(\frac{t^{2}}{\varepsilon}\right) n_{d}^{\ast}(t,\varepsilon)=\Omega\!\left(\frac{t^{2}}{\varepsilon}\right) ( 25 , Theorem 12) Table 1: Summary of sample-complexity upper and lower bounds of sample-based simulation. The row labeled “Special case” corresponds to local Lindbladians where d=O(1) is the dimension of the system on which the Lindblad operator acts. Structure of the paper. In Section II , we introduce basic notation and review sample-based Lindbladian simulation, especially WML. We also recall the formal definition of the sample complexity of sample-based Hamiltonian and Lindbladian simulation ( 25 , Definition 1) . In Section III , we establish an improved upper bound on the sample complexity of Lindbladian simulation algorithms, based on a rigorous analysis of WML. In

Read the complete text