Exploring the power of quantum computation by constructing new BQP-complete problems
Dr. Dominik Janzing
Tuesday, April 17, 2007
11:00AM ~ 12:15PM, Harris Center 125
Abstract
We have identified a simple BQP-complete problem in linear algebra related to the estimation of diagonal entries of powers of large sparse matrices. It follows that the quantum computer is better at linear algebra than the classical computer unless the class of efficiently solvable problems coincide for both types of computers (i.e. BQP=BPP).
Moreover, we have constructed a BQP-complete combinatorial problem concerning the number of walks on a sparse graph leading from one node to another. Our result shows that the quantum computer is also more powerful in analyzing classical random walks unless BQP=BPP.
These results suggest that a broad class of problems could be solved more efficiently on a quantum computer.
Short Bio
Dominik Janzing studied Physics and Mathematics at the Universitaet Tuebingen (Germany) and University College Cork (Ireland). In 1995, he received his Diplom in Physics. His main interests were the foundations of quantum theory and thermodynamics. In 1998, he completed his Ph.D. thesis in Mathematics under the supervision of Manfred Wolff on the relation between quantum and classical dynamics in infinite quantum spin chains. In 1998, he joined Thomas Beth's Quantum Computing group at the Faculty for Computer Science of the Universitaet Karlsruhe.
His main interest is to understand the physical foundations of complexity and relations between complexity and statistical physics. Since 2004 he has been working on new methods for causal inference which are based on analyzing the complexity of conditional probability measures. In 2006 he joined Bernhard Schoelkopf's group at the Max-Planck-Institute for Biological Cybernetics in Tuebingen to intensify this work. In July 2006 he was awarded the postdoctoral degree Habilitation in Computer Science at the Universitaet Karlsruhe. He is currently Visiting Professor at the School of Electrical Engineering and Computer Science at UCF.
