Robust Structure Learning of $k$-local Lindbladians

• URL: http://arxiv.org/abs/2606.23652v1
• Date: Mon, 22 Jun 2026 17:38:41 GMT
• Title: Robust Structure Learning of $k$-local Lindbladians
• Abstract summary: 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.
• Score: 6.257768263476564
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present an efficient protocol for learning an unknown $k$-local Lindblad generator on $n$ qubits using only product-state preparations, short-time evolution, and single-qubit Pauli measurements, without prior knowledge of the interaction structure. For fixed $k$ and bounded weighted interaction strength, the protocol estimates all Hamiltonian and dissipative Pauli--GKSL coefficients to entrywise accuracy $\varepsilon$ with probability at least $1-δ$ using $\widetilde{\mathcal O}_k(\varepsilon^{-2}n^{2k}\log(1/δ))$ samples and polylogarithmically many evolution times. A semidefinite projection converts these estimates into a valid $k$-local Lindblad generator with diamond-norm error at most $\varepsilon$ using $\widetilde{\mathcal O}_k(\varepsilon^{-2}n^{4k}\log(1/δ))$ samples and polynomial-time classical postprocessing. If a suitable set of influential coefficients is supplied and satisfies a stable sparsity condition, the dependence on $n$ can improve from polynomial to logarithmic; in particular, exact supports of bounded intersection degree require only $\widetilde{\mathcal O}_k(\varepsilon^{-2}\log(n/δ))$ samples, with analogous reductions in system-size dependence for sufficiently decaying long-range interactions. We also provide a robust structure-learning procedure, extend the guarantees to model misspecification, and prove complementary sample-complexity lower bounds. To our knowledge, these are the first efficient learning guarantees for general $k$-local dissipative quantum dynamics under such limited experimental control.

Related papers

• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  We study multicalibration for a sequence of $k$ properties in which each property is identifiable once the preceding properties are fixed.<n>Even with only polylogarithmically many binary groups, achieving multicalibration error $varepsilon$ requires $widetilde(varepsilon-(k+2))$ samples.
  arXiv  Detail & Related papers  (2026-08-04T23:38:54Z)
• Learning Arbitrary Lindbladians from Time Evolution [9.103975636688793]
  We study the problem of learning an unknown Markovian open-system generator from access to its physical time evolution.<n>This generator, called a Lindbladian, contains Hamiltonian and dissipative coefficients indexed by an exponentially large family of possible Pauli terms.<n>We propose an efficient algorithm that learns arbitrary Lindbladians from time evolution under minimal assumptions.
  arXiv  Detail & Related papers  (2026-07-30T17:58:01Z)
• Trotter error compensation with polylogarithmic precision and nested-commutator scaling without ancillas [23.101202672272027]
  We develop a high-order nested-commutator algorithm that preserves the main advantages of product formulas.<n>The resulting time dependence matches that of a product formula of order $2K+1$.
  arXiv  Detail & Related papers  (2026-07-13T17:42:25Z)
• Provably Efficient Learning of Fermionic Correlations under Particle-Number Symmetry [1.7149364927872013]
  Predicting local fermionic correlations is a central task in quantum many-body physics.<n>We develop a framework of number-conserving fermionic-shadow tomography based on random orbital rotations.<n>This work establishes a provably efficient advantage of particlenumber symmetry for fermionic observables estimation.
  arXiv  Detail & Related papers  (2026-06-29T17:40:18Z)
• Near-Optimal Learning of Local Lindbladians [8.542629891640045]
  We study the problem of learning local Lindbladians from black-box access to the physical evolution.<n>We give an algorithm built directly from finite-time channel probes, which runs the unknown evolution for short times.<n>We complement the algorithm with matching lower bounds, showing that the learning algorithm is near-optimal both in physical dynamics accesses and in total evolution time.
  arXiv  Detail & Related papers  (2026-06-18T17:48:31Z)
• Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials [2.5199066832791535]
  We study the problem of learning surrogates over the Boolean hypercube.<n>We require uniform $L_infty$-error guarantees rather than the usual $L$-type guarantees.<n>Our results provide a tight proof of the sample complexity of learning optimization-safe surrogates.
  arXiv  Detail & Related papers  (2026-06-15T22:00:03Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• 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)
• 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)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  We study the problem of learning nonparametric distributions in a finite mixture. We establish tight bounds on the sample complexity for learning the component distributions in such models.
  arXiv  Detail & Related papers  (2022-03-28T23:53:48Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• 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)

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.