CS Paper Radar

Robustness of quantum spectrum estimation: weak Schur sampling under noisy inputs

Vladyslav Visnevskyi, Laura Mančinska

cs.IT quant-phmath.RT ·submitted 2026-10-02 16:53 UTC · v3

Abstract

We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the $n$ input copies of the target state $ρ$ are identical, i.e. $ρ^{\otimes n}$. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is $ε$-close in trace distance to the $d$-dimensional target state $ρ$. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to $nε$ on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most $ε+η(n,d)$, where $η(n,d)=O(d/\sqrt n)$ is the noiseless error, and the additive noise term $ε$ is optimal. The output error does not grow with $n$ even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input $ω$ we show that the error is at most $η(n,d)+\frac{1}{n}\|ω-ρ^{\otimes n}\|_{W_1}$, where $W_1$ is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.

Comment
v3: slight correction to the statement of Theorem 3 in Preliminaries; expanded the proof of Proposition 45 in the Appendix for clarity; unified notation in Appendix B; fixed a typo in References

Closest papers

Nearest neighbours by meaning across the whole index.

Statistical Symmetry Release for Equivariant Quantum Learning

cs.LO quant-ph ·2026-09-10 ·Zeyu Chen
similarity 0.67
Abstract

Hard symmetry constraints reduce model complexity, but can also erase label information. Statistical symmetry release determines when finite data and quantum measurements justify relaxing such a constraint, which directions to open, and how far to move. We connect global signal detection to local, loss-dependent improvement. A two-copy twirl--swap gate estimates task information in the symmetry-breaking complement with a dimension-independent copy count under paired-state and group-unitary access; reweighting the same records resolves representation sectors. An exact duality distinguishes this Hilbert--Schmidt signal from the larger signal accessible to bounded-outcome readouts. Local improvement is governed by the release gradient and a loss-corrected double-commutator matrix. Simultaneous confidence bounds convert empirical direction selection into certified descent, using either shared Pauli measurements or scalar probes with state-independent truncation bounds. Gaussian testing lower bounds quantify the cost of searching over unknown directions in the calibrated local experiment. Independent validation controls adaptively generated models, and a fast squared-loss bound preserves the approximation--estimation rate of a nested release path. On an eight-qubit Ising model, shared measurements certify release with 6300 times fewer shots than the specified scalar estimator on the tested budget grids. Quotient quantum natural gradient then controls parameter redundancy during training. Together, these results turn symmetry relaxation into a statistically justified model-selection decision.

0.41

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

On the Power of Adaptivity in Testing Quantum States in Fidelity

cs.DS quant-ph ·2026-09-08 ·Jan Seyfried, Sayantan Sen, Marco Tomamichel
theoryhot direction similarity 0.65
Abstract · 49 pages. Minor updates from previous version

We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state $ρ$ and the description of a state $σ$, the goal is to test whether $ρ=σ$, or whether $ρ$ and $σ$ are far in a given distance measure. In equivalence testing, $σ$ is also unknown and only accessible via samples. Independence testing decides whether $ρ_{AC}=ρ_A\otimesρ_C$, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap $\varepsilon$ in trace distance: in the single-copy measurement setting with $d$-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses $Θ(d^{3/2}/\varepsilon^2)$ samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state $σ$ of rank $r$ does not benefit from adaptivity and requires $\widetildeΘ(r^{3/2}/\varepsilon)$ samples. For equivalence testing and independence testing, we provide adaptive algorithms using $\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})$ and $\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})$ samples, for $d_A\geq d_C$, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in $\ell_2$-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that $\widetildeΩ(1/\varepsilon^2)$ samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.

0.28

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.65
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 Sparse Quantum States

cs.CC quant-phcs.DS ·2026-09-10 ·Aniruddha Sen
similarity 0.64
Abstract · 26 pages

We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.

0.22

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.63
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

A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features

cs.LG quant-phstat.ML ·2026-09-09 ·Natsuto Isogai, Mio Murao, Hayata Yamasaki
similarity 0.62
Abstract · 18 pages, 1 figure

Quantum-inspired classical algorithms have dequantized several quantum machine learning routines by replacing quantum linear-algebra subroutines with classical counterparts. However, the sampler based on quantum singular value transformation (QSVT) for learning with optimized random features is not covered by existing dequantization frameworks, because the matrix to be inverted is not itself available through sampling access. In this work, we develop a classical algorithm to address this type of quantum-advantage candidate. Our method samples heavy indices, reduces the transformation to a small principal block, and outputs a sparse classical representation with operator-norm guarantees. Applying this method dequantizes the sampler for optimized random features, giving a classical sampler with prescribed accuracy and polynomially related runtime. These results show that the factorization underlying a quantum block encoding can itself provide sufficient classical structure even when sampling-and-query access to the composite matrix is unavailable.

0.39

Advantage of Entangled Learning Rules in Quantum Measurement Class Learning

cs.LG quant-ph ·2026-10-05 ·Arka Prabha Das, Abram Magner
similarity 0.62
Abstract · 9 pages

Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).

0.16