Jayadev Acharya

We prove that to learn an $N$-qubit state with $\varepsilon$ error in trace distance, $\Tilde{\Theta}(\frac{10^N}{\eps^2})$ copies are necessary and sufficient using Pauli measurements, where $\Tilde{\Theta}$ hides a $\sqrt{N}$ factor. The lower bound holds under adaptivity. Thus, we nearly settle the worst-case copy complexity of Pauli tomography, which has been a long-standing problem. Our main technical contribution is a novel lower bound framework for adaptive single-copy state tomography with measurement constraints. Our method allows measurement-dependent hard instances for tighter lower bounds, and characterizes the hardness of learning using the \emph{measurement information channel}. The power of our framework extends beyond Pauli measurements: We prove that Pauli measurements are near-optimal among single-qubit measurements, and further prove tight lower bounds for adaptive $k$-outcome measurements.