1999/01/14 by Mark Ettinger, Ettinger, Mark, Peter Hoyer +4
Computer Science · Mathematics · Physics and Astronomy · #Algebraic structures and combinatorial models #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum many-body systems #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9901034
5 pages, no figures
arxiv created 1999/01/14 · openalex publication_date 1999/01/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that quantum computers can efficiently find a hidden subgroup H of a finite Abelian group G. This implies that after only a polynomial (in log |G|) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group G in only a linear (in log |G|) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.