Quantum Computational Models, Algorithms and Complexity Theory

Dr. Pawel M. Wocjan
Thursday, March 9, 2006
2:00PM - CSB-232

Abstract


I will describe a control-theoretic model for quantum computing on which I focused in my Ph.D. thesis. This model is closer to physics and provides a physical justification for the quantum circuit model. I will explain how lower bounds on the complexity of realizing desired transformations can be obtained by using techniques from algebraic graph theory. I will also explain how to construct efficient control algorithms using methods of group theory and combinatorics. These algorithms yield upper bounds that often coincide with the lower bounds.

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 Bio


Pawel 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.