2006/12/31 by Cristopher Moore, Alexander Russell, Piotr Śniady +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum many-body systems #math.RT #quant-ph
paper · pdf · doi:10.1145/1250790.1250868
published as In: STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 536-545, New York, NY, USA, 2007. ACM Press · An earlier preprint, quant-ph/0609138, gave versions of these results which were conditional on a group-theoretic conjecture. This version provides unconditional results
arxiv created 2007/04/07 · openalex publication_date 2007/06/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
It is known that any quantum algorithm for Graph Isomorphism thatworks within the framework of the hidden subgroup problem (HSP) must performhighly entangled measurements across Ω(n log n) coset states. One ofthe only known models for how such a measurement could be carried outefficiently is Kuperberg's algorithm for the HSP in the dihedral group, in whichquantum states are adaptively combined and measured according to thedecomposition of tensor products into irreducible representations. This "quantum sieve" starts with coset states, and works its way down towardsrepresentations whose probabilities differ depending on, for example, whetherthe hidden subgroup is trivial or nontrivial.