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.
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.
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×d and the goal is to distinguish whether ρ's spectrum satisfies some property P or is at least ε-far in ℓ1-distance from satisfying 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 O(d2/ε2) copies. In this work, we show that given a mixed state ρ∈Cd×d: (i) Θ(d/ε2) copies are necessary and sufficient to test whether ρ is the maximally mixed state, i.e., has spectrum (d1,...,d1); (ii) Θ(r2/ε) copies are necessary and sufficient to test with one-sided error whether ρ has rank r, i.e., has at most r nonzero eigenvalues; (iii) Θ(r2/Δ) 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 Ω(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.
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.