A hidden shift quantum algorithm

J. Twamley*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


We examine the application of quantum algorithms to the non-Abelian hidden subgroup problem and focus on the dihedral hidden subgroup problem (DHSP). Ettinger and Høyer have recently discovered an algorithm which, although efficient in the number of operations of the quantum computation, requires classical post-processing which grows exponentially with the size of the input. We first show that the DHSP can be reduced to another problem: how to efficiently estimate an unknown shift k, in a one-to-one map f : ℤM → ℤM, given two oracles which provide x → f(x), and x → f(x ⊕ k), with k and f unknown. We devise an algorithm which uses amplitude amplification to obtain an estimate for the unknown shift k in a number script O sign(√M) oracle calls.

Original languageEnglish
Pages (from-to)8973-8979
Number of pages7
JournalJournal of Physics A: Mathematical and General
Issue number48
Publication statusPublished - 8 Dec 2000
Externally publishedYes


Dive into the research topics of 'A hidden shift quantum algorithm'. Together they form a unique fingerprint.

Cite this