Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper presents a quantum algorithm for principal component analysis (PCA) on mixed states, recovering the leading eigenvector with high fidelity using non-adaptive, single-qubit Pauli measurements. The algorithm achieves a runtime and copy complexity of $\tilde{O}(2^n / \varepsilon)$ under constant spectral gap and $\varepsilon = \Omega(\eta)$ conditions, generalizing prior work on pure states to mixed states with state misspecification. A key technical innovation is a novel structured Pauli sampling scheme enabling fast batched computation of projected Pauli matrices, leading to nearly linear time dependence on Hilbert space dimension.
Quantum PCA on mixed states matches pure state performance rates, even with state misspecification, by leveraging a novel structured Pauli sampling for near-linear time complexity.
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.