## Abstract

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 language | English |
---|---|

Pages (from-to) | 8973-8979 |

Number of pages | 7 |

Journal | Journal of Physics A: Mathematical and General |

Volume | 33 |

Issue number | 48 |

DOIs | |

Publication status | Published - 8 Dec 2000 |

Externally published | Yes |