Quantum Spectrum Testing

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 $$\rho \in \mathbb {C}^{d\times d}$$ and the goal is to distinguish (with high probability) whether $$\rho $$ ’s spectrum satisfies some property $${\mathcal {P}}$$ or whether it is at least $$\epsilon $$ -far in $$\ell _1$$ -distance from satisfying $${\mathcal {P}}$$ . This problem was promoted in the survey of Montanaro and de Wolf (A survey of quantum property testing. Technical report, arXiv:1310.2035 , 2013) 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. Unlike property testing probability distributions—where one generally hopes for algorithms with sample complexity that is sublinear in the domain size—here the hope is for algorithms with subquadratic copy complexity in the dimension d. This is because the (frequently rediscovered) “empirical Young diagram (EYD) algorithm” (Alicki et al. in J Math Phys 29(5):1158–1162, 1988; Keyl and Werner in Phys Rev A 64(5):052311, 2011; Hayashi and Matsumoto in Phys Rev A 66(2):022311, 2002; Christandl and Mitchison in Commun. Math. Phys. 261(3):789–797, 2006) can estimate the spectrum of any mixed state up to $$\epsilon $$ -accuracy using only $${\widetilde{O}}(d^2/\epsilon ^2)$$ copies. In this work, we show that given a mixed state $$\rho \in \mathbb {C}^{d \times d}$$ : Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov’s algebra of polynomial functions on Young diagrams.