Nearly Time-Optimal Pure State Tomography with Pauli Measurements

[2026-06-12, Sabee Grewal (UT Austin) ] We give an algorithm for pure state tomography with near-optimal copy complexity using single-qubit measurements. Specifically, given \widetilde{O}(2^n/\epsilon) copies of an unknown pure n-qubit state \lvert\psi\rangle, the algorithm performs only \textit{nonadaptive Pauli measurements}, runs in time \mathrm{poly}(2^n,1/\epsilon), and outputs \lvert \widehat{\psi} \rangle that has fidelity 1-\epsilon with \lvert \psi \rangle with high probability. This improves upon the previous best copy complexity bound of \widetilde{O}(3^n/\epsilon).