Improved sample complexity bound for sample-based Lindbladian simulation

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² left\(frac{t²}{varepsilon} right\), holding for simulation time t and error varepsilon. This refines the dimension dependence of the best previously known bound, O\(d² t²/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² = O(1/d), a condition satisfied with high probability for random Lindblad operators, yielding a typical-case sample complexity of O\(t²/varepsilon\). On the other hand, in the worst case, we show that WML necessarily requires Ω\(dt²/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.