{"id":"arxiv/2610.06808","url":"https://arxiv.org/abs/2610.06808","tags":["quant-ph","cs.DS"],"score":0,"title":"Quantum 1-PCA with Pauli Measurements in Nearly Linear Time","domain":"quant-ph","source":"arxiv","authors":["Dutch Hansen","Jerry Li"],"reviews":0,"subject":"quant-ph","summary":"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 $λ$ and spectral gap at least $Δ> 0$, we give an algorithm that recovers the leading eigenvector to fidelity at least $1 - \\varepsilon$ with high probability using $\\tilde{O}\\left( {2^n \\cdot η^2} / {Δ^3 \\varepsilon^3}\\right)$ copies and $\\tilde{O}((2^n/Δ\\varepsilon) \\cdot \\operatorname{poly}(η/Δ\\varepsilon))$ time, where $η= \\max…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}