𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Quantum Algorithms for Noncommutative Hidden Subgroups

✍ Scribed by Mark Ettinger; Peter Høyer

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
122 KB
Volume
25
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

✦ Synopsis

Quantum algorithms for factoring and finding discrete logarithms have previously been generalized to finding hidden subgroups of finite Abelian groups. This paper explores the possibility of extending this general viewpoint to finding hidden subgroups of noncommutative groups. We present a quantum algorithm for the special case of dihedral groups which determines the hidden subgroup in a linear number of calls to the input function. We also explore the difficulties of developing an algorithm to process the data to explicitly calculate a generating set for the subgroup. A general framework for the noncommutative hidden subgroup problem is discussed and we indicate future research directions.

📜 SIMILAR VOLUMES

Fast algorithm for one-dimensional quant
Fast algorithm for one-dimensional quantum Monte Carlo simulations
✍ Mihail Marcu; Jürgen Müller; Franz-Karl Schmatzer 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 654 KB

A fast algorithm for simulating one-dimensional quantum spin systems on CRAY 1 computers is presented. Various versions of the algorithm suitable for general spin xxz and xyz models with and without magnetic field are discussed.