Computer Science/Discrete Mathematics Seminar II

We shall discuss Quantum Computing, and the so called Hidden Subgroup Problem, which in the abelian case was the basis for Shor's celebrated factorization algorithm. The solution for non-abelian groups, and symmetric groups in particular, is one of the challenges in Quantum Computing today (motivated by the graph isomorphism problem in particular). We show how these brand new problems lead naturally to old classical notions in permutation group theory, such as the notion of minimal degree, studied extensively since the days of Jordan 130 years ago. We also use character theory and the Classification of Finite Simple Groups to compare related quantum algorithms with classical ones. The talk is based on two recent joint works: with J. Kempe, and with J. Kempe and L. Pyber.