Special Seminar

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. In Computer Science language: the approximation of the Jones polynomial at certain points is BQP complete. This means that: 1. There is an efficient quantum algorithm to approximate the Jones polynomial of any given link, at certain roots of unity; 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 two recent papers, one together with Jones and Landau and the other with Arad. I will concentrate in my talk mainly on our recent first paper giving an explicit quantum algorithm for the problem. The goal is to give a feel of how quantum computation can be viewed through the lens of beautiful pictorial objects such as the braid group and Temperley-Lieb algebras. No prior knowledge of quantum computation will be assumed.