Computational Algebra Seminar

The foundations for the field of quantum computation were laid by Richard Feynman, Paul Benioff, and Yuri Manin already in the early 80s by studying the relationship between the physical and computational processes. Starting from the observation that quantum mechanical processes are hard to simulate on classical computers, they concluded that quantum mechanics might help to speed-up some computations. After preliminary results which were mainly of a theoretical nature, in 1994 Peter Shor presented an algorithm of practical interest for a computer based on the principles of quantum mechanics [Sho94]. His quantum algorithm for factoring integers is exponentially faster than any classical algorithm known so far. Another algorithm showing the advantage of quantum mechanical systems is the quantum "search" algorithm of Grover [Gro96]. This algorithm achieves a square root speed-up compared to a classical algorithm when solving the satisfiability problem of an unstructured Boolean function.

After an introduction to the mathematical framework of quantum information processing, I will present the algorithms of Grover and Shor. The latter gives rise to a large class of algorithms which solve the so-called hidden subgroup problem establishing a connection to group theory and representation theory in particular.

[Sho94]

Shor, P. W., "Algorithms for Quantum Computation: Discrete Logarithm and Factoring".
Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 1994, pp. 124-134.

[Gro96]

Grover, L. K., "A fast quantum mechanical algorithm for database search".
Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 1996, pp. 212-219.