In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given @math copies of a mixed state @math and the goal is to distinguish whether @math 's spectrum satisfies some property @math or is at least @math -far in @math -distance from satisfying @math . 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 @math . This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to @math -accuracy using only @math copies. In this work, we show that given a mixed state @math : (i) @math copies are necessary and sufficient to test whether @math is the maximally mixed state, i.e., has spectrum @math ; (ii) @math copies are necessary and sufficient to test with one-sided error whether @math has rank @math , i.e., has at most @math nonzero eigenvalues; (iii) @math copies are necessary and sufficient to distinguish whether @math is maximally mixed on an @math -dimensional or an @math -dimensional subspace; and (iv) The EYD algorithm requires @math copies to estimate the spectrum of @math up to @math -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.
The second result comes from the work of @cite_59 . It can be thought of as a quantum analogue of Fact : Setting @math , Theorem gives a linear lower bound of @math for various properties of spectra. This is in contrast with property testing of probability distributions, in which sublinear algorithms are the main goal, with the Birthday Paradox typically precluding sub- @math -sample algorithms.
@cite_59
2096150384
Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem.We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem.