zbMATH — the first resource for mathematics

Quantum algorithms. (English) Zbl 0999.68546
Freivalds, Rūsiņš (ed.), Fundamentals of computation theory. 13th international symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2138, 45-46 (2001).
Summary: Quantum computers are the only model of computing to credibly violate the modified Church-Turing thesis, which states that any reasonable model of computation can be simulated by a probabilistic Turing Machine with at most polynomial factor simulation overhead. This is dramatically demonstrated by Shor’s polynomial time algorithms for factorization and discrete logarithms. Shor’s algorithm as well as the earlier algorithm due to Simon can both be cast into the general framework of the hidden subgroup problem. Two recent papers study how well this framework extends to solving the hidden subgroup problem for non-abelian groups (which includes the graph isomorphism problem).
For the entire collection see [Zbl 0969.00084].

68U99 Computing methodologies and applications
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
81P68 Quantum computation
Full Text: Link