Pauli Measurements Are Near-Optimal for Single-Qubit Tomography

Abstract

We provide the first non-trivial lower bounds for single-qubit tomography algorithms and show that at least $\hat{I}\text{c◯}\left(\frac{10^N}{\sqrt{N}{\epsilon }^2}\right)$ copies are required to learn an $N$-qubit state $\ddot{I}\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.

22 pages