Robust Structure Learning of $k$-local Lindbladians

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 a supplied weighted interaction-strength bound $\bar{\alpha }$, the protocol estimates all Hamiltonian and dissipative Pauli--GKSL coefficients with total coefficient error at each site at most $\epsilon$ with probability at least $1-\delta$ using ${\tilde{\mathcal{O}}}_k({\bar{\alpha }}^2{n}^{2k-2}{\epsilon }^{-2}\log (n/\delta ))$ samples and polylogarithmically many distinct evolution times. This guarantee requires no degree, sparsity, or tail promise. A convex optimization converts these estimates into a valid $k$-local Lindblad generator with diamond-norm error at most $\epsilon$ using ${\tilde{\mathcal{O}}}_k({\bar{\alpha }}^2{n}^{2k}{\epsilon }^{-2}\log (n/\delta ))$ samples and polynomial-time classical postprocessing. With a supplied local effective-sparsity bound $r$ and a sufficiently small sitewise subthreshold tail ${\mathcal{O}}_k(\epsilon )$, coefficient recovery requires only ${\tilde{\mathcal{O}}}_k({\bar{\alpha }}^2{r}^2{\epsilon }^{-2}\log (n/\delta ))$ samples, without a supplied threshold or coefficient locations and without a coefficient-gap assumption. In particular, exactly sparse bounded-degree models have logarithmic sample dependence on $n$. We also provide guard-band support recovery and complementary supplied-candidate guarantees, extend the guarantees to model misspecification, and prove complementary sample-complexity lower bounds.