Consider the following state distinciton problem in quantum information: There is a known ensemble of quantum states i.e. density matrices. We are given some number of independent copies of one of these states. By doing individual measurements on each copy, we would like to determine with high probability which state is given. An important special case is when the ensemble consists of pure states.
In this talk, I will show that measuring each copy in a random orthonormal basis gives enough information to identify the unknown state. The number of copies required is polynomial in the inverse of the minimum pairwise Frobenius distance of the ensemble, and the logarithm of the ensemble size. In particular for pure states, the number of copies required is polynomial in the inverse of the minimum trace distance of the ensemble, and the logarithm of the ensemble size. This is optimal to within constant factors.
As an application, single register Fourier sampling suffices to solve the hidden subgroup problem information-theoretically for the Heisenberg group and related groups. An efficient quantum algorithm for the hidden subgroup problem over the Heisenberg group was recently obtained using a completely different approach by Bacon, Childs and van Dam.