Improved sample complexity bound for sample-based Lindbladian simulation

• URL: http://arxiv.org/abs/2605.30301v1
• Date: Thu, 28 May 2026 17:46:25 GMT
• Title: Improved sample complexity bound for sample-based Lindbladian simulation
• Abstract summary: We establish improved sample-complexity bounds for sample-based Lindbladian simulation based on the Wave Matrix Lindbladization (WML) algorithm.<n>For a jump operator $L$ with dimension $d$, we derive an explicit non-asymptotic sample complexity bound $n_d*(t,varepsilon) le left( frac2d+38 right) |L|_infty2 left( fract2varepsilon right)
• Score: 10.583368233681378
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Robust Structure Learning of $k$-local Lindbladians [6.257768263476564]
  We present an efficient protocol for learning an unknown $k$-local Lindblad generator on $n$ qubits.<n>For fixed $k$ and bounded weighted interaction strength, the protocol estimates all Hamiltonian and dissipative Pauli-GKSL coefficients to entrywise accuracy.<n>We extend the guarantees to model misspecifications and prove sample-complexity lower bounds.
  arXiv  Detail & Related papers  (2026-06-22T17:38:41Z)
• On efficient robust regression with subquadratic samples [2.017649213266693]
  We show that a near-linear-time algorithm that uses $widetildeO(d/4)$ samples achieves prediction error $O(sqrt)$ under the condition $lesssim 1$.<n>We also prove a low-degree lower bound that gives fine-grained evidence that, without assumptions such as $lesssim 1$, efficient algorithms may require $tildeleft(mind22, 2d2right)$ samples.
  arXiv  Detail & Related papers  (2026-05-18T08:34:07Z)
• Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
  We study the sample complexity of shadow tomography in the high-precision regime.<n>We use possibly adaptive measurements that act on $O(mathrmpolylog(d))$ number of copies of $$ at a time.
  arXiv  Detail & Related papers  (2026-02-04T19:00:00Z)
• Reducing Circuit Depth in Lindblad Simulation via Step-Size Extrapolation [2.847280100380157]
  We study algorithmic error mitigation via Richardson-style extrapolation for quantum simulations of open quantum systems modelled by the Lindblad equation.<n>We show that an extrapolator reduces the maximum circuit depth needed for accuracy $varepsilon$ from $mathcalO ((lT)2/varepsilon)$ to polylogarithmic $mathcalO ((lT)2/varepsilon)$ scaling.
  arXiv  Detail & Related papers  (2025-07-30T02:56:07Z)
• Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity [11.214304423266304]
  We present detailed sample complexity analyses for Density matrix exponentiation (DME) and Wave matrix Lindbladization (WML)<n>Both algorithms are prototypical sample-based quantum algorithms.<n>We prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially.
  arXiv  Detail & Related papers  (2024-12-03T03:46:42Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  This paper deals with the problem of efficient sampling from a differential equation, given the drift function and the diffusion matrix. It is possible to obtain independent and identically distributed (i.i.d.) samples at precision $varepsilon$ with a cost that is $m2 d log (1/varepsilon)$ Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
  arXiv  Detail & Related papers  (2023-03-30T02:50:49Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.