CS Paper Radar

Quantum 1-PCA with Pauli Measurements in Nearly Linear Time

Dutch Hansen, Jerry Li

cs.DS quant-ph ·submitted 2026-10-05 17:54 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal spectrum estimation

cs.CC quant-phcs.DS ·2026-09-24 ·Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
theoryhighly cited similarity 0.67
Abstract · 37 pages

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

0.35

Near-Optimal Mixedness Testing with Pauli Measurements

cs.CC quant-phcs.IT ·2026-08-19 ·Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu
theory similarity 0.63
Abstract · Added determinstic Pauli mixedness testing results, fixed typos

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task with simple single-qubit measurements, i.e. measurements that are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness testing by showing that its copy-complexity is $\tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.

0.31

Learning sparse quantum states from single-qubit measurements

cs.DS quant-phcs.IT ·2026-09-28 ·Su-un Lee, Liang Jiang, Kunal Sharma
similarity 0.63
Abstract

We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity $s$ is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When $s$ grows polynomially with $n$, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.

0.19

Improved Quantum Random Self-Reduction for Linear Problems

cs.CC quant-ph ·2026-09-30 ·Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
similarity 0.62
Abstract

We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{O}$ and coherent entry access to $M$, we give a uniform quantum reduction that computes $Mx$ on any prescribed input $x$ with probability at least $2/3$ in time $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{O}(n^{3/2}+T)$ reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.

0.27

Covering the Pauli Observables: Sampling Thresholds and the Design Effect of a Measurement Setting

cs.IT quant-pheess.SP ·2026-11-18 ·Kausthubh Chandramouli, Noah Siekierski, Bojko N. Bakalov, Dror Baron
similarity 0.61
Abstract · 30 pages, 5 figures, 3 tables

Quantum state tomography and shadow-based estimation rely on measuring Pauli observables. An experiment does not measure them one at a time: it chooses a measurement setting that assigns one of the bases X, Y or Z to each qubit, and a single run in that setting yields estimates of every Pauli observable compatible with it. We say that the setting covers those observables. We determine how many random settings cover a prescribed fraction of all Pauli observables. As the number of settings grows exponentially with the number of qubits, the covered fraction has a sharp threshold at a growth rate of $3^{3/4}$ per qubit, set by the rate-distortion function of covering at zero distortion. We give an explicit expression for the number of settings needed to reach a target fraction, accurate up to a remainder that reduces to a small oscillation for many qubits, and show that random sampling is asymptotically optimal up to a factor of less than 1.69. Coverage does not determine what a setting contributes to an estimator. Observables covered by one setting are estimated from the same outcomes, so their estimates are correlated. We quantify this correlation through the design effect of a setting, which equals the squared Pauli expectation that the setting captures and depends on the target state. We derive its mean over settings in closed form for every state and show that it can be estimated without bias from the measurement data. In simulations on six qubits, measuring settings needs 7.6 to 38 times fewer circuit runs than measuring the same number of observables independently. At high coverage, fitting the outcome histograms instead of averaged estimates roughly halves the reconstruction error, mainly because the fit counts how many settings cover each observable. The correlation itself costs such a fit about a factor of two, and a larger design effect signals more to gain from modeling it.

0.45

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

cs.DS quant-phcs.ITcs.LG ·2026-09-09 ·Ashwin Nayak, Xingyu Zhou
theoryhighly cited similarity 0.61
Abstract · 70 pages; v2: minor revisions

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

0.51

Learning Clifford-structured quantum unitaries and Hamiltonians

cs.CC quant-ph ·2026-08-10 ·Arkopal Dutt, Dale Jacobs, John Jeang, Saeed Mehraban, Vladimir Podolskii
similarity 0.61
Abstract

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

0.42

Tight Lower Bounds for State Tomography with Limited Entanglement

cs.IT quant-phcs.LG ·2026-09-04 ·Ufuk Keskin, Jason Luo, Mahbod Majid, Matthew Radzihovsky
theoryhighly cited similarity 0.61
Abstract · 36 pages

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $ε$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}ε^2),d^2/ε^2\}$ for every $k$ and all sufficiently small $ε$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

0.41