2005/04/26 by Dave Bacon, Andrew M. Childs, Wim van Dam · 3 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum and electron transport phenomena #quant-ph
paper · pdf · doi:10.1109/sfcs.2005.38
published as Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 469-478 · 18 pages; v2: updated references on optimal measurement
arxiv created 2005/04/26 · openalex publication_date 2005/11/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.