Quantum algorithms for Simon's problem over nonabelian groups
Abstract
Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z 2 n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G , this is the problem of recovering an involution m = ( m 1 ,…, m n ) ∈ G n from an oracle f with the property that f ( x ⋅ y ) = f ( x ) ⇔ y ∈ {1, m }. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G n , where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 01, 2009
- Source ID
- 10.1145/1644015.1644034
Entities
People
- Alexander Russell
- Cristopher Moore
- Gorjan Alagic
Organizations
- Army Research Office
- Division of Computing and Communication Foundations
- National Science Foundation
- University of Connecticut
- University of New Mexico
- University of Waterloo