We provide positive and negative results concerning the
standard method
of identifying a hidden subgroup of a
nonabelian group using a quantum computer.
Mathematics Subject
Classification (2000): 81P68 - 68Q17
* Supported in part by NSF grants CCR-9820931 and
CCR-0208929.
Supported in part by NSF CAREER grant 0049092, the
NSF Institute for Quantum Information, the Charles Lee Powell
Foundation, and the Mathematical Sciences Research
Institute.
Supported in part by an NSF Mathematical Sciences
Postdoctoral Research Fellowship and NSF grant
DMS-0301320.§ Supported in part by DARPA QUIST grant
F30602-01-2-0524, ARO grant DAAD19-03-1-0082, and NSF ITR grant
CCR-0121555.