Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.

August 31, 2006
12:30 PM

Howard Barnum,
CCS-3, Los Alamos National Labratory

Part 2 of 2 -A Mini-Course on the Aharonov-Jones-Landau Algorithm for Approximating the Jones Polynomial

Abstract

Approximation of the Jones polynomial to a certain accuracy can be done in polynomial time on a quantum computer. Moreover, this is a complete problem for bounded-error polynomial-time quantum computation (BQP): any problem in BQP can be done by approximations of Jones polynomials. The work of Kitaev, Freedman, and Zhang showing that certain models of computation arising in for example in topological quantum field theory allow universal quantum computation (and also showing that QC can simulate these topological models), implies the existence of such an algorithm, but Aharonov, Jones, and Landau (AJL) gave an explicit construction. This pedagaogical series of two talks presents the AJL algorithm at an elementary level, concentrating on full conceptual understanding rather than detailed derivations. I will concentrate on the elementary background of knot theory (with digressions on its relation to statistical physics), the braid group and simple algebraic constructions needed to understand the Jones polynomial and the AJL algorithm, and then on a complete presentation of structure of the proof, but without tedious detail. This is part of the basics of understading topological quantum computation, and its relation to standard (and classical!) computation.