
Quantum Computational Models, Algorithms and Complexity Theory
Dr. Pawel M. Wocjan
Abstract In the second part of my talk, I will present results of my most recent research project on quantum algorithms, quantum complexity theory and their connection to the Jones polynomial. The probabilistic output of topological quantum computers depends on the Jones polynomial (a certain invariant) of the knots which specify their programs. I will outline our simple proof that topological quantum computers can be efficiently simulated by quantum circuits and vice versa. Our results give an efficient algorithm within the quantum circuit model for obtaining additive approximations of the Jones polynomial. Furthermore, our simple method for translating quantum circuits into knots provides a direct proof that in a certain sense this problem is the hardest problem that can be efficiently solved on a quantum computer. I will apply our techniques to characterize the complexity classes BQP (Bounded-Error Quantum Polynomial Time), Quantum-NP, #P, and PSPACE.
Short BioPawel Wocjan studied Computer Science in Germany at the University of Karlsruhe and at the French National Institute for Research in Computer Science and Control. He completed his Ph.D. thesis, "Computational Power of Hamiltonians in Quantum Computing," at the University of Karlsruhe in 2003. He has been a Postdoctoral Scholar in Computer Science at the California Institute of Technology since 2004. His research is focused on quantum computing and quantum information theory. |