Quantum 1-PCA with Pauli Measurements in Nearly Linear Time

We consider the problem of quantum 1-PCA: given copies of an unknown $n$-qubit mixed state, recover a classical description of its leading eigenvector. Our goal is to do so using non-adaptive and single-qubit measurements. For an $n$-qubit state with top eigenvalue $\lambda$ and spectral gap at least $\mathrm{\Delta }>0$, we give an algorithm that recovers the leading eigenvector to fidelity at least $1-\epsilon$ with high probability using $\tilde{O}\left(2^n\cdot {\eta }^2\mathrm{/}{\mathrm{\Delta }}^3{\epsilon }^3\right)$ copies and $\tilde{O}((2^n\mathrm{/}\mathrm{\Delta }\epsilon )\cdot \mathrm{poly}(\eta \mathrm{/}\mathrm{\Delta }\epsilon ))$ time, where $\eta =\max (1-\lambda ,\epsilon )$. All of our measurements are non-adaptively chosen, and performed in single-qubit Pauli bases. When the spectral gap is constant and the desired accuracy is comparable to the noise level, i.e. $\epsilon =\mathrm{\Omega }(\eta )$, our runtime and copy complexity become $\tilde{O}(2^n\mathrm{/}\epsilon )$. This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption $\eta =0$, i.e., that the state was pure. Our results show that the same rates hold in the presence of state misspecification, up to polylogarithmic factors. From a technical perspective, our algorithm works by recursively constructing low-dimensional subspaces that approximately preserve the target eigenvector. To achieve nearly linear runtime dependence on the dimension of the Hilbert space, we develop a novel structured Pauli sampling scheme that enables fast batched computation of exponentially many projected Pauli matrices.