Robust Structure Learning of $k$-local Lindbladians

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 $\epsilon$ with probability at least $1-\delta$ using ${\tilde{\mathcal{O}}}_k({\epsilon }^{-2}{n}^{2k}\log (1\mathrm{/}\delta ))$ 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 $\epsilon$ using ${\tilde{\mathcal{O}}}_k({\epsilon }^{-2}{n}^{4k}\log (1\mathrm{/}\delta ))$ 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 ${\tilde{\mathcal{O}}}_k({\epsilon }^{-2}\log (n\mathrm{/}\delta ))$ 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.