01297nas a2200133 4500008004100000245009900041210006900140260001500209520083300224100002301057700002101080700001801101856004401119 2006 eng d00aWeak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
0 aWeak FourierSchur sampling the hidden subgroup problem and the q c2006/09/143 a 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.
1 aChilds, Andrew, M.1 aHarrow, Aram, W.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0609110v1