Jerusalem Mathematics Colloquium

Thursday, 8th December 2005, 4:00 pm
Mathematics Building, Lecture Hall 2

Dorit Aharonov
(Computer Science Dept, Hebrew University)

"The Jones polynomial and Quantum Computation"

Abstract: I will explain a very intriguing connection between low dimensional topology, knot invariants, and quantum computation: It turns out that in some well defined sense, quantum computation is equivalent to certain approximations of the Jones polynomial. This means that:

  1. There is an efficient quantum algorithm to approximate the Jones polynomial of any given link;
  2. The approximation of the Jones polynomial is the hardest problem a quantum computer can possibly solve;
  3. Shor's factoring algorithm can be presented as the approximation of the Jones polynomial of a certain link.
The results are based on works of Kitaev, Freedman, Larsen and Wang, as well as on a recent paper by myself, together with Jones and Landau. I will concentrate in my talk mainly on our recent paper. The goal is to give a feel of how quantum computation can be viewed through the lense of beautiful pictorial objects such as the braid group and Temperley-Lieb algebras. No prior knowledge of quantum computation will be assumed.

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2005-06
Archive of talks