Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1501.05028

Quantum Spectrum Testing

Ryan O’Donnell, Wright, John

Published Jan 21, 2015• 8 citations
arXivHTMLPDF

Abstract

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given $n$ copies of a mixed state $ρ\in\mathbb{C}^{d\times d}$ and the goal is to distinguish whether $ρ$'s spectrum satisfies some property $\mathcal{P}$ or is at least $ε$-far in $\ell_1$-distance from satisfying $\mathcal{P}$. This problem was promoted in the survey of Montanaro and de Wolf under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Here, the hope is for algorithms with subquadratic copy complexity in the dimension $d$. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to $ε$-accuracy using only $\widetilde{O}(d^2/ε^2)$ copies. In this work, we show that given a mixed state $ρ\in\mathbb{C}^{d\times d}$: (i) $Θ(d/ε^2)$ copies are necessary and sufficient to test whether $ρ$ is the maximally mixed state, i.e., has spectrum $(\frac1d, ..., \frac1d)$; (ii) $Θ(r^2/ε)$ copies are necessary and sufficient to test with one-sided error whether $ρ$ has rank $r$, i.e., has at most $r$ nonzero eigenvalues; (iii) $\widetildeΘ(r^2/Δ)$ copies are necessary and sufficient to distinguish whether $ρ$ is maximally mixed on an $r$-dimensional or an $(r+Δ)$-dimensional subspace; and (iv) The EYD algorithm requires $Ω(d^2/ε^2)$ copies to estimate the spectrum of $ρ$ up to $ε$-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.

DOI
10.48550/arxiv.1501.05028

Related papers

Quantum Spectrum Testing

Ryan O’Donnell, John Wright

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈ Cd x d and the goal is to distinguish (with high probability) whether ρ's spectrum satisfies some property P or whether it is at least ε-far in l1-distance from satisfying P. This problem was promoted under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions.

ACM Symposium on Theory of Computing (STOC)•Jun 3, 2015•55 citations

Toward Instance-Optimal State Certification With Incoherent Measurements

Sitan Chen, Jerry Zheng Li, Ryan O’Donnell

We revisit the basic problem of quantum state certification: given copies of unknown mixed state $ρ\in\mathbb{C}^{d\times d}$ and the description of a mixed state $σ$, decide whether $σ= ρ$ or $\|σ- ρ\|_{\mathsf{tr}} \ge ε$. When $σ$ is maximally mixed, this is mixedness testing, and it is known that $Ω(d^{Θ(1)}/ε^2)$ copies are necessary, where the exact exponent depends on the type of measurements the learner can make [OW15, BCL20], and in many of these settings there is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this $d^{Θ(1)}$ dependence for certain kinds of mixed states $σ$, e.g. ones which are approximately low rank? More ambitiously, does there exist a simple functional $f:\mathbb{C}^{d\times d}\to\mathbb{R}_{\ge 0}$ for which one can show that $Θ(f(σ)/ε^2)$ copies are necessary and sufficient for state certification with respect to any $σ$? Such instance-optimal bounds are known in the context of classical distribution testing, e.g. [VV17]. Here we give the first bounds of this nature for the quantum setting, showing (up to log factors) that the copy complexity for state certification using nonadaptive incoherent measurements is essentially given by the copy complexity for mixedness testing times the fidelity between $σ$ and the maximally mixed state. Surprisingly, our bound differs substantially from instance optimal bounds for the classical problem, demonstrating a qualitative difference between the two settings.

arXiv:2102.13098•Feb 25, 2021•8 citations

Learning and testing quantum states via probabilistic combinatorics and representation theory

Ryan O’Donnell, John Wright

In this survey, we give an introduction to the problem of learning and testing quantum states from multiple copies.Special attention is paid to the tasks of estimating the eigenvalues of an unknown state, testing whether a state is maximally mixed, and performing full quantum state tomography.We focus on the representation theory-based approached, developed in [ARS88, KW01, HM02, Har05, Key06, CM06, Chr06, CHW07, MW16, OW21, OW16, HHJ + 17, OW17, BOW19, CLM + 21, AISW19] and elsewhere.Examining this approach also leads to interesting new developments regarding the probabilistic combinatorics of longest increasing subsequences.Note: Modulo minor revisions, Sections 1 to 12 were written jointly with John Wright (Berkeley), and a somewhat condensed version of these sections appeared under the title A primer on the statistics of longest increasing subsequences and quantum states in the Sept. 2017 edition of SIGACT News.Contents 1. Spanish cryptograms 44 2. Quantum contraptions 46 3. Longest increasing subsequences: Robinson, Schensted, Knuth 48 4. Symmetric properties of probabilities: classical vs. quantum 51 5.The RSK bijection and Schur symmetric polynomials 53 6.Two majorization theorems for the RSK algorithm 56 7. Probabilistic combinatorics of longest increasing subsequences 58 8. Mechanics of quantum mechanics 61 9. Noncommutative probability 65 10.Testing for the uniform distribution/maximally mixed state 67 11.Representation theory gives a nice basis for observables 71 12. Symmetric group characters on small conjugacy classes 75

Current Developments in Mathematics•Jan 1, 2021•2 citations

Spectrum Estimation is Almost as Hard as Tomography

Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa

We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.

quant-pharXiv:2607.29680•Aug 3, 2026•0 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600•Aug 4, 2026•0 citations

Local Test for Unitarily Invariant Properties of Bipartite Quantum States

Kean Chen, Qisheng Wang, Zhicheng Zhang

We study the power of local test for bipartite quantum states. Our central result is that, for properties of bipartite pure states, unitary invariance on one part implies anoptimal(over all global testers) local tester acting only on the other part. As an application, we demonstrate • Purified samples offer no advantage in property testing of mixed states. • A matching lower bound Ω(r2/ε2) for testing the Schmidt rank of bipartite states with perfect completeness, settling an open question raised in the survey of Montanaro and de Wolf (ToC 2016). • A lower bound Ω(( √n+ √r)· √r/ε2) for testing whether ann-partite state is a matrix product state of bond dimensionror ε-far, improving the prior lower bounds Ω( √n/ε2) by Soleimanifar and Wright (SODA 2022) and Ω( √r) by Aaronson et al. (ITCS 2024). • A matching lower bound Ω(d/ε2) for testing whether ad-dimensional bipartite state is maximally entangled or ε-far, showing that the algorithm of O’Donnell and Wright (STOC 2015) is optimal for this task. • A query lower bound Ω(d/ √ Δ) for thed-dimensional entanglement entropy problem with gap Δ, improving the prior lower bounds Ω(4√d) by She and Yuen (ITCS 2023) and Ω(1/ √ Δ) by Wang and Zhang (SICOMP 2025) and Weggemans (Quantum 2025). Moreover, we extend our central result to a robust version where the tested states are subject to noise and are not guaranteed to be pure: in this case, one-way LOCC is sufficient to realize the optimal tester.

arXiv:2404.04599•IEEE Transactions on Information Theory•May 28, 2026•0 citations
In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given nnn copies of a mixed state ρ∈Cd×dρ\in\mathbb{C}^{d\times d}ρ∈Cd×d and the goal is to distinguish whether ρρρ's spectrum satisfies some property P\mathcal{P}P or is at least εεε-far in ℓ1\ell_1ℓ1​-distance from satisfying P\mathcal{P}P. This problem was promoted in the survey of Montanaro and de Wolf under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Here, the hope is for algorithms with subquadratic copy complexity in the dimension ddd. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to εεε-accuracy using only O~(d2/ε2)\widetilde{O}(d^2/ε^2)O(d2/ε2) copies. In this work, we show that given a mixed state ρ∈Cd×dρ\in\mathbb{C}^{d\times d}ρ∈Cd×d: (i) Θ(d/ε2)Θ(d/ε^2)Θ(d/ε2) copies are necessary and sufficient to test whether ρρρ is the maximally mixed state, i.e., has spectrum (1d,...,1d)(\frac1d, ..., \frac1d)(d1​,...,d1​); (ii) Θ(r2/ε)Θ(r^2/ε)Θ(r2/ε) copies are necessary and sufficient to test with one-sided error whether ρρρ has rank rrr, i.e., has at most rrr nonzero eigenvalues; (iii) Θ~(r2/Δ)\widetildeΘ(r^2/Δ)Θ(r2/Δ) copies are necessary and sufficient to distinguish whether ρρρ is maximally mixed on an rrr-dimensional or an (r+Δ)(r+Δ)(r+Δ)-dimensional subspace; and (iv) The EYD algorithm requires Ω(d2/ε2)Ω(d^2/ε^2)Ω(d2/ε2) copies to estimate the spectrum of ρρρ up to εεε-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.
In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈ Cd x d and the goal is to distinguish (with high probability) whether ρ's spectrum satisfies some property P or whether it is at least ε-far in l1-distance from satisfying P. This problem was promoted under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions.
We revisit the basic problem of quantum state certification: given copies of unknown mixed state ρ∈Cd×dρ\in\mathbb{C}^{d\times d}ρ∈Cd×d and the description of a mixed state σσσ, decide whether σ=ρσ= ρσ=ρ or ∥σ−ρ∥tr≥ε\|σ- ρ\|_{\mathsf{tr}} \ge ε∥σ−ρ∥tr​≥ε. When σσσ is maximally mixed, this is mixedness testing, and it is known that Ω(dΘ(1)/ε2)Ω(d^{Θ(1)}/ε^2)Ω(dΘ(1)/ε2) copies are necessary, where the exact exponent depends on the type of measurements the learner can make [OW15, BCL20], and in many of these settings there is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this dΘ(1)d^{Θ(1)}dΘ(1) dependence for certain kinds of mixed states σσσ, e.g. ones which are approximately low rank? More ambitiously, does there exist a simple functional f:Cd×d→R≥0f:\mathbb{C}^{d\times d}\to\mathbb{R}_{\ge 0}f:Cd×d→R≥0​ for which one can show that Θ(f(σ)/ε2)Θ(f(σ)/ε^2)Θ(f(σ)/ε2) copies are necessary and sufficient for state certification with respect to any σσσ? Such instance-optimal bounds are known in the context of classical distribution testing, e.g. [VV17]. Here we give the first bounds of this nature for the quantum setting, showing (up to log factors) that the copy complexity for state certification using nonadaptive incoherent measurements is essentially given by the copy complexity for mixedness testing times the fidelity between σσσ and the maximally mixed state. Surprisingly, our bound differs substantially from instance optimal bounds for the classical problem, demonstrating a qualitative difference between the two settings.
In this survey, we give an introduction to the problem of learning and testing quantum states from multiple copies.Special attention is paid to the tasks of estimating the eigenvalues of an unknown state, testing whether a state is maximally mixed, and performing full quantum state tomography.We focus on the representation theory-based approached, developed in [ARS88, KW01, HM02, Har05, Key06, CM06, Chr06, CHW07, MW16, OW21, OW16, HHJ + 17, OW17, BOW19, CLM + 21, AISW19] and elsewhere.Examining this approach also leads to interesting new developments regarding the probabilistic combinatorics of longest increasing subsequences.Note: Modulo minor revisions, Sections 1 to 12 were written jointly with John Wright (Berkeley), and a somewhat condensed version of these sections appeared under the title A primer on the statistics of longest increasing subsequences and quantum states in the Sept. 2017 edition of SIGACT News.Contents 1. Spanish cryptograms 44 2. Quantum contraptions 46 3. Longest increasing subsequences: Robinson, Schensted, Knuth 48 4. Symmetric properties of probabilities: classical vs. quantum 51 5.The RSK bijection and Schur symmetric polynomials 53 6.Two majorization theorems for the RSK algorithm 56 7. Probabilistic combinatorics of longest increasing subsequences 58 8. Mechanics of quantum mechanics 61 9. Noncommutative probability 65 10.Testing for the uniform distribution/maximally mixed state 67 11.Representation theory gives a nice basis for observables 71 12. Symmetric group characters on small conjugacy classes 75
We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For ddd-dimensional states, and for every γ>0γ>0γ>0, we prove a sample complexity lower bound of Ω(d2−γ)Ω(d^{2-γ})Ω(d2−γ) for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an fff-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr⁡(φ(dρ))/d\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/dLφ​(ρ)=tr(φ(dρ))/d, where ρρρ is an unknown ddd-dimensional quantum state and φφφ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ)\mathcal{L}_φ(ρ)Lφ​(ρ) from properties of φφφ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ ⁣(d2εlog⁡2(d)max⁡{1,εlog⁡2(d)}+log⁡2(d)ε2), Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), Θ(εlog2(d)max{1,εlog2(d)}d2​+ε2log2(d)​), and the sample complexity of spectrum estimation is Θ ⁣(d2ε2log⁡2(d)max⁡{1,ε2log⁡2(d)}). Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). Θ(ε2log2(d)max{1,ε2log2(d)}d2​). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
We study the power of local test for bipartite quantum states. Our central result is that, for properties of bipartite pure states, unitary invariance on one part implies anoptimal(over all global testers) local tester acting only on the other part. As an application, we demonstrate • Purified samples offer no advantage in property testing of mixed states. • A matching lower bound Ω(r2/ε2) for testing the Schmidt rank of bipartite states with perfect completeness, settling an open question raised in the survey of Montanaro and de Wolf (ToC 2016). • A lower bound Ω(( √n+ √r)· √r/ε2) for testing whether ann-partite state is a matrix product state of bond dimensionror ε-far, improving the prior lower bounds Ω( √n/ε2) by Soleimanifar and Wright (SODA 2022) and Ω( √r) by Aaronson et al. (ITCS 2024). • A matching lower bound Ω(d/ε2) for testing whether ad-dimensional bipartite state is maximally entangled or ε-far, showing that the algorithm of O’Donnell and Wright (STOC 2015) is optimal for this task. • A query lower bound Ω(d/ √ Δ) for thed-dimensional entanglement entropy problem with gap Δ, improving the prior lower bounds Ω(4√d) by She and Yuen (ITCS 2023) and Ω(1/ √ Δ) by Wang and Zhang (SICOMP 2025) and Weggemans (Quantum 2025). Moreover, we extend our central result to a robust version where the tested states are subject to noise and are not guaranteed to be pure: in this case, one-way LOCC is sufficient to realize the optimal tester.