Pauli Measurements Are Near-Optimal for Single-Qubit Tomography

We provide the first non-trivial lower bounds for single-qubit tomography algorithms and show that at least $\mathrm{\Omega }\left(\frac{{10}^N}{\sqrt{N}{\epsilon }^2}\right)$ copies are required to learn an $N$-qubit state $\rho \in {\mathbb{C}}^{d\times d},d=2^N$ to within $\epsilon$ trace distance. Pauli measurements, the most commonly used single-qubit measurement scheme, have recently been shown to require at most $O\left(\frac{{10}^N}{{\epsilon }^2}\right)$ copies for this problem. Combining these results, we nearly settle the long-standing question of the complexity of single-qubit tomography.