Can quantum 1-PCA recover leading eigenvectors with Pauli measurements in nearly linear time?

Quantum 1-PCA asks for the top eigenvector, not the state

Quantum 1-PCA starts from copies of an unknown n-qubit mixed state ρ and asks for a classical description of its leading eigenvector |ψ⟩. The paper assumes the top eigenvalue λ is unique, the second eigenvalue is λ₂ < λ, and the spectral gap is Δ = λ - λ₂. Success means outputting a pure state |ψ̂⟩ with |⟨ψ̂|ψ⟩|² ≥ 1 - ε for a target error ε.

The motivation is misspecification. In many settings the state one wants is pure, but noise or state-preparation error makes the observed ρ mixed. Recovering ρ itself is then the wrong goal; the natural question is to recover its top eigenvector. This is why the paper treats the mixed-state case rather than assuming ρ = |ψ⟩⟨ψ|.

Single-qubit Pauli bases are the practical constraint

Earlier work showed that quantum PCA is possible with Õ(2^n/ε) copies, which is nearly linear in the Hilbert-space dimension and known to be tight. But that algorithm needs measurements entangled across the n qubits and across multiple copies of the state, which puts it largely out of reach for existing or near-term quantum devices except at very small scale.

A later result matched those statistical guarantees using single-qubit, single-copy measurements, but only when ρ is exactly pure. That algorithm leans heavily on ρ being rank 1 and, to the authors' knowledge, fails to generalize even under very small amounts of noise. The paper's central question is whether both properties can hold at once: non-adaptive single-qubit Pauli measurements, and general mixed states.

The guarantees scale with noise through η and Δ

For an n-qubit state with top eigenvalue λ and spectral gap at least Δ > 0, the algorithm recovers the leading eigenvector to fidelity at least 1 - ε with high probability using Õ(2^n · η²/Δ³ε³) copies and Õ((2^n/Δε) · poly(η/Δε)) time, where η = max(1 - λ, ε). All measurements are non-adaptively chosen and performed in single-qubit Pauli bases.

The quantity η measures how far ρ is from pure, so it acts as an inverse signal-to-noise ratio. The ratio η/ε is therefore the key comparison: it says whether the target accuracy is comparable to the mass of noise in the system. In the regime where the spectral gap is constant and ε = Ω(η), both runtime and copy complexity become Õ(2^n/ε).

The result generalizes pure-state tomography to mixed states

The earlier single-qubit algorithm of Grewal et al. achieved similar rates under the assumption η = 0, meaning the state was pure. The present paper shows the same rates hold in the presence of state misspecification, up to polylogarithmic factors. In the special case λ = 1, η/ε = Θ(1), so the new result recovers both the copy and runtime complexity of that pure-state tomography result.

The authors note that although the algorithm shares a similar initial framework with the earlier work, the techniques end up being quite different, even in the pure-state setting. That makes the new algorithm a different route to pure-state tomography, which the paper says may be of independent interest.

Recursive low-dimensional subspaces replace exact reconstruction

The algorithm proceeds qubit-wise. For a prefix string s ∈ {0,1}^ℓ, let ρ_s be the unnormalized state obtained by measuring the first ℓ qubits of ρ in the coordinate basis and receiving outcome s, with |ψ_s⟩ defined similarly. The earlier pure-state algorithm reconstructed |ψ_s⟩ directly from |ψ_s0⟩ and |ψ_s1⟩, which works because purity implies ρ_s = |ψ_s⟩⟨ψ_s|.

That identity fails for mixed states: after basis measurements, the post-measurement state can have a top eigenvector completely orthogonal to |ψ_s⟩. So even exact top eigenvectors of ρ_s0 and ρ_s1 would not generally approximate |ψ_s⟩. Instead, the algorithm maintains at every node s a low-dimensional subspace Π_s that approximately contains |ψ_s⟩, and merges two child subspaces into a parent subspace while controlling error and dimension.

Classical k-PCA pruning keeps the subspace dimension small

The naive merge has projector Π̃_s = |0⟩⟨0| ⊗ Π_s0 + |1⟩⟨1| ⊗ Π_s1, which satisfies the needed error bounds but doubles the dimension at each layer. To prevent that blow-up, the algorithm interleaves classical k-PCA steps: before the dimension grows too large, it uses the naive projections with chosen Pauli measurements to build an estimate ρ̂_s ≈ (⟨s| ⊗ Π̃_s) ρ (|s⟩ ⊗ Π̃_s), then prunes each Π̃_s into a k-dimensional Π_s passed to the next layer.

The paper states that k need only be logarithmic in the dimension of |ψ⟩ to give global error guarantees, because at any prefix the residual satisfies a bound of the form ‖(I - Π_s) Π̃_s |ψ_s⟩‖²₂ ≲ tr(|s⟩⟨s| ⊗ I ν)/λk + ‖ξ_s‖∞/λ. Summing over all prefixes at a layer and then over all layers sends the first term to ε with k = O(n), ignoring spectral terms. The algorithm sets k = ⌈nη/(Δε)⌉ and mass threshold p = εΔ/n.

Structured Pauli sampling makes exponentially many projections computable

A remaining obstacle is computational: the projected Pauli matrices Π_s σ_{x,z} Π_s cannot be written down explicitly, and roughly 2^n of them are needed per layer even if k were constant. The paper dispenses with the natural uniform distribution over Pauli matrices and instead samples from a structured distribution derived from the commutation structure of the Paulis.

Viewing a Pauli sample as a random subset of phase space F₂^n ⊕ F₂^n, the algorithm selects F as a random affine space F = {(x, Ax + c)} with A uniform over symmetric F₂ matrices and c uniform. The marginals are uniform over {x} × F₂^n and pairwise independent, and along this affine space the Pauli matrices factor into σ_{x,0} times diagonals, so the needed forms reduce to entry-wise pre-processing followed by a fast Walsh-Hadamard transform. This is what enables fast batched computation of exponentially many projected Pauli matrices and yields the nearly linear runtime dependence on the Hilbert-space dimension.

The near-linear rate holds when accuracy matches the noise

The headline Õ(2^n/ε) rate is not unconditional. It requires a constant spectral gap and ε = Ω(η), meaning the target accuracy is comparable to the noise level. Outside that regime, the copy complexity carries the factor η²/Δ³ε³ and the runtime carries poly(η/Δε), so a small gap or a target accuracy far below the noise level raises the cost. The paper also notes that the full algorithm does not require exact knowledge of λ; the same guarantees hold for any Δ, η, ε > 0 with λ ≥ 1 - η, λ - λ₂ ≥ Δ, and ε ≤ η.

The practical reading is a threshold on η/ε rather than on dimension alone. When the state is nearly pure or the requested fidelity is loose relative to the noise mass, the algorithm matches the best known copy complexity for quantum PCA while using only non-adaptive single-qubit Pauli measurements. When the gap shrinks or ε drops well below η, the polynomial factors in η/Δε dominate, and that is the regime where the advantage over general-measurement approaches should be weighed against the added cost.

Sources used in this answer