We study sets of divergences or dissimilarity measures in a generalized real-algebraic setting which includes the cases of classical and quantum multivariate divergences. We show that a special subset of divergences, the so-called test spectrum, characterizes the rest of the divergences through barycentres and that the extreme points of relevant convex subsets of general divergences are contained within the test spectrum. Only some special parts of the test spectrum may contain non-extreme elements. We are able to fully characterize the test spectrum in the case of classical multivariate divergences. The quantum case is much more varied, and we demonstrate that essentially all the bivariate and multivariate quantum divergences suggested previously in literature are within the test spectrum and extreme within the set of all quantum (multivariate) divergences. This suggests that the variability of quantum divergences is real since all the previously suggested divergences are independent of each other.We study sets of divergences or dissimilarity measures in a generalized real-algebraic setting which includes the cases of classical and quantum multivariate divergences. We show that a special subset of divergences, the so-called test spectrum, characterizes the rest of the divergences through barycentres and that the extreme points of relevant convex subsets of general divergences are contained within the test spectrum. Only some special parts of the test spectrum may contain non-extreme elements. We are able to fully characterize the test spectrum in the case of classical multivariate divergences. The quantum case is much more varied, and we demonstrate that essentially all the bivariate and multivariate quantum divergences suggested previously in literature are within the test spectrum and extreme within the set of all quantum (multivariate) divergences. This suggests that the variability of quantum divergences is real since all the previously suggested divergences are independent of each other.

arXiv:2509.18725Sep 23, 20250 citations

Quantum Testing

Anonymous

PhysicsApr 26, 20120 citations

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.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, 201555 citations

Quantum Detection

François Chapeau‐Blondeau

Springer eBooksJan 1, 20260 citations

Quantum Testing and Validation

Aruna Jayasena, Emma Andrews, Prabhat Mishra

Springer eBooksJan 1, 20260 citations

Quantum Spectrum Testing

Ryan O’Donnell, Wright, John

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

arXiv:1501.05028Jan 21, 20158 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

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