Finding Gaussian Structure in Bosonic States

We study agnostic tomography of pure bosonic Gaussian states: given copies of an arbitrary n-mode bosonic state ρ, the goal is to output a pure Gaussian state whose infidelity with ρ is at most opt + ε, where opt is the minimum infidelity achievable by any pure Gaussian state. We give efficient protocols achieving this in both the high and low fidelity regimes. When opt is below some universal constant, our protocol has runtime and copy complexity which is strongly polynomial in n, 1/ε and log log E, where E is the energy of the closest pure Gaussian state. For arbitrary opt, our protocol uses (n+1)poly(1/ε) polyleft(1+loglog(E)right) copies and runtime. As a corollary, we obtain the first truly tolerant Gaussianity testing protocol for distinguishing whether opt > c + ε or opt < c - ε, for any threshold c∈(0,1). We also prove poly(n,1/ε) runtime is impossible, unless NPsubseteqBQP. Our protocols follow a shared paradigm: first, we iteratively use general Gaussian measurements combined with techniques from classical robust statistics to obtain a good warm start estimate, then we leverage non-Gaussian measurements to refine this warm start using convex and non-convex optimization methods. Interestingly, we prove that non-Gaussian measurements are necessary to match the strong agnostic guarantees we obtain, and in fact these guarantees are provably superior to what is possible for robustly estimating classical Gaussians.