Complexity of quantum tomography from genuine non-Gaussian entanglement

Quantum state tomography typically requires exponentially many copies of a quantum state, due to the complex correlations present in large systems. We show that, for bosonic systems, the scaling is completely determined by the nature of these correlations. Motivated by the Hong-Ou-Mandel effect and boson sampling, we define Gaussian-entanglable (GE) states, produced by generalized interference between separable bosonic modes. GE states greatly extend the Gaussian family, encompassing separable states, multi-mode Gottesman-Kitaev-Preskill codes, entangled cat states, and boson-sampling outputs-resources for error correction and quantum advantage. We prove that any pure GE state of m modes can be learned efficiently, requiring only poly(m) copies, via a protocol based on Gaussian unitaries, local tomography, and classical post-processing; for boson-sampling states, no Gaussian unitaries are needed. For states outside GE, we define an operational monotone-the minimal number of ancillary modes needed to make them GE-which exactly characterizes the exponential tomography overhead. We also show that deterministic generation of NOON states with N ≥ 3 via two-mode interference is impossible.