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

ACM Symposium on Theory of Computing (STOC)

Quantum Spectrum Testing

Ryan O’Donnell, John Wright

Published Jun 3, 2015• 70 citations
Publisher

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 ρ∈ 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.

DOI
10.1145/2746539.2746582

Related papers

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•31 citations

Quantum Algorithms for Testing Properties of Distributions

Sergey B. Bravyi, Aram W. Harrow, Avinatan Hassidim

Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).

arXiv:0907.3920•IEEE Transactions on Information Theory•May 25, 2011•59 citations

Is it Gaussian? Testing bosonic quantum states

Filippo Girardi, Freek Witteveen, Francesco Anna Mele +4 more

Gaussian states are widely regarded as one of the most relevant classes of continuous-variable (CV) quantum states, as they naturally arise in physical systems and play a key role in quantum technologies. This motivates a fundamental question: given copies of an unknown CV state, how can we efficiently test whether it is Gaussian? We address this problem from the perspective of representation theory and quantum learning theory, characterizing the sample complexity of Gaussianity testing as a function of the number of modes. For pure states, we prove that just a constant number of copies is sufficient to decide whether the state is exactly Gaussian. We then extend this to the tolerant setting, showing that a polynomial number of copies suffices to distinguish states that are close to Gaussian from those that are far. In contrast, we establish that testing Gaussianity of general mixed states necessarily requires exponentially many copies, thereby identifying a fundamental limitation in testing CV systems. Our approach relies on rotation-invariant symmetries of Gaussian states together with the recently introduced toolbox of CV trace-distance bounds.

arXiv:2510.07305•Oct 8, 2025•14 citations

Sample-optimal tomography of quantum states

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji +2 more

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples.

ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•131 citations

Constraints on the mixing of bipartite states

Hao Chen

A mixed state may be represented in many different ways as a mixture of pure states ρ=∑pi∣ψi⟩⟨ψi∣. The mixing problem in quantum mechanics asks the characterization of the probability distribution (pi) and the mixed states (ρi) such that ρ=∑piρi for any given mixed state ρ. Some constraints based on eigenvalues of the mixed states are established in uni-party case [see Nielsen, Phys. Rev. A. 63, 052308 (2000), 63, 022144 (2000), Nielsern and Vidal Quantum Inf. Comput. 1 76 (2001)]. We develop some new invariant sets for bipartite mixed states under local unitary operations, which are independent of eigenvalues, and prove some strong constraints based on these invariant sets for the mixing problem in bipartite case. This exhibits a remarkable difference from the uni-party case.

Journal of Mathematical Physics•Dec 1, 2005•1 citation

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
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 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.
Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).
Gaussian states are widely regarded as one of the most relevant classes of continuous-variable (CV) quantum states, as they naturally arise in physical systems and play a key role in quantum technologies. This motivates a fundamental question: given copies of an unknown CV state, how can we efficiently test whether it is Gaussian? We address this problem from the perspective of representation theory and quantum learning theory, characterizing the sample complexity of Gaussianity testing as a function of the number of modes. For pure states, we prove that just a constant number of copies is sufficient to decide whether the state is exactly Gaussian. We then extend this to the tolerant setting, showing that a polynomial number of copies suffices to distinguish states that are close to Gaussian from those that are far. In contrast, we establish that testing Gaussianity of general mixed states necessarily requires exponentially many copies, thereby identifying a fundamental limitation in testing CV systems. Our approach relies on rotation-invariant symmetries of Gaussian states together with the recently introduced toolbox of CV trace-distance bounds.
A mixed state may be represented in many different ways as a mixture of pure states ρ=∑pi∣ψi⟩⟨ψi∣. The mixing problem in quantum mechanics asks the characterization of the probability distribution (pi) and the mixed states (ρi) such that ρ=∑piρi for any given mixed state ρ. Some constraints based on eigenvalues of the mixed states are established in uni-party case [see Nielsen, Phys. Rev. A. 63, 052308 (2000), 63, 022144 (2000), Nielsern and Vidal Quantum Inf. Comput. 1 76 (2001)]. We develop some new invariant sets for bipartite mixed states under local unitary operations, which are independent of eigenvalues, and prove some strong constraints based on these invariant sets for the mixing problem in bipartite case. This exhibits a remarkable difference from the uni-party case.
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