Pauli Measurements Are Not Optimal for Single-Copy Tomography

Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N-qubit state ρϵλ.,^{d× d},d=2^N, the goal is to learn the state up to an accuracy ϵ in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O(N· 12^N/ϵ²), and no non-trivial lower bound is known besides the general single-copy lower bound of ω(8^N/ϵ²), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O(10^N/ϵ²). To complement it, we also obtain a lower bound of ω(9.118^N/ϵ²), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement's capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k-outcome measurements, where we recover existing results and establish new ones.