Quantum 1-PCA with Pauli Measurements in Nearly Linear Time
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 − ε with high probability using Õ( 2n · η2 / Δ3 ε3) copies and Õ((2n/Δε) · poly(η/Δε)) time, where η= max (1 − λ, ε). 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. ε = Ω(η), our runtime and copy complexity become Õ (2n / ε). 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.
Related
- Enhanced measurements on quantum computers via the simultaneous probing of non-commuting Pauli operators
- Individually Addressed Logical Pauli Measurements by QLDPC Surgery on a Trapped Ion Quantum Computer
- Amenable groups with nearly exponential sofic profile, and quantum channels that need nearly linear memory
- Orientation-dependent Pauli noise in one-dimensional discrete-time quantum walks
- Sublinear Copies Suffice for Fidelity Estimation with Pauli Measurements
BibTeX
@misc{hansen2026quantum,
title = {{Quantum 1-PCA with Pauli Measurements in Nearly Linear Time}},
author = {Dutch Hansen and Jerry Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06808},
eprint = {2610.06808},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06808},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Quantum 1-PCA with Pauli Measurements in Nearly Linear Time
AU - Dutch Hansen
AU - Jerry Li
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06808
UR - https://arxiv.org/abs/2610.06808
AB - 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 − ε with high probability using Õ( 2^n · η^2 / Δ^3 ε^3) copies and Õ((2^n/Δε) · poly(η/Δε)) time, where η= max (1 − λ, ε). 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. ε = Ω(η), our runtime and copy complexity become Õ (2^n / ε). 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.
ER -