Abstract: What is the computational power of quantum computers? To answer such a question it is logical to study BQP-complete problems. Approximating the Jones polynomial is perhaps the most natural BQP-complete problem known today. The tutorial begins with a brief overview of knot theory. The Jones polynomial is discussed and its relation to quantum computing. Finally, some results are derived on the computational complexity of approximating the Jones polynomial. This tutorial is primarily based on a paper by Aharonov and Arad (arXiv:quant-ph/0605181), and another by Aharonov, Jones and Landau (arXiv:quant-ph/0511096).

Date: 18 November 2015