Improved sample complexity bound for sample-based Lindbladian simulation

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^{\ast }(t,\epsilon )\le \left(\frac{2d+3}{8}\right)\Vert L{\Vert }_{\infty }^2\left(\frac{t^2}{\epsilon }\right)$, holding for simulation time $t$ and error $\epsilon$. This refines the dimension dependence of the best previously known bound, $O(d^2{t}^2/\epsilon )$, from [Go et al., Quantum Sci. Tech. 10, 045058 (2025)]. Remarkably, we show that this dimensional overhead can be entirely avoided when $\Vert L{\Vert }_{\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/\epsilon )$. On the other hand, in the worst case, we show that WML necessarily requires $\hat{I}\text{c◯}(d{t}^2/\epsilon )$ 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.

31 pages