arXiv:2610.06808
Quantum 1-PCA with Pauli Measurements in Nearly Linear Time
Dutch Hansen, Jerry Li
Abstract
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 (1 - λ, \varepsilon)$. 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. $\varepsilon = Ω(η)$, our runtime and copy complexity become $\tilde{O} (2^n / \varepsilon)$. This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption $η= 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.
AI Summary
The paper studies quantum 1-PCA: given copies of an unknown $n$-qubit mixed state $\rho$, output a classical description of its unique leading eigenvector with fidelity at least $1-\varepsilon$. It asks whether nearly linear dependence on Hilbert-space dimension is achievable using only non-adaptive, single-copy, single-qubit Pauli-basis measurements, without assuming that $\rho$ is pure. Writing $d=2^n$, $\lambda$ for the largest eigenvalue, $\Delta>0$ for the spectral gap, and $\eta=\max(1-\lambda,\varepsilon)$, the algorithm uses $\tilde O(d\eta^2/(\Delta^3\varepsilon^3))$ copies and $\tilde O((d/(\Delta\varepsilon))\operatorname{poly}(\eta/(\Delta\varepsilon)))$ time, with logarithmic dependence on inverse failure probability. For constant gap and $\varepsilon=\Omega(\eta)$, both bounds reduce to $\tilde O(d/\varepsilon)$, recovering the pure-state rate while allowing mixed-state noise. The reconstruction proceeds backwards through computational-basis prefixes, maintaining low-dimensional subspaces that approximately contain the corresponding pieces of the target eigenvector. Subspaces are merged and pruned using estimated compressed density matrices; perturbation inequalities control accumulated loss. A structured sampling scheme selects Pauli operators from random affine families defined by symmetric binary matrices. Walsh–Hadamard transforms then batch-compute projected Pauli matrices, avoiding quadratic-in-$d$ processing. Spectral clipping and Lepskii’s method provide operator-norm estimation guarantees. The optimal-rate regime requires constant spectral gap and target error comparable to or larger than the noise mass. Outside it, the guarantees deteriorate polynomially in inverse gap and noise-to-error ratio. The algorithm requires supplied bounds on the gap and impurity, though not exact knowledge of $\lambda$. Runtime remains exponential in qubit count; the results are theoretical.
Multiple technical steps and optimizations were derived in discussion with GPT-5.6 and GPT-6.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.