Two BQP- Complete Problems: Eigenvalue Sampling and Estimating Diagonal Entries of Powers Sparse Symmetric Matrices
Dr. Pawel M. Wocjan
Thursday, June 29, 2006
2:00PM - CSB-232
Abstract
A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying the hardest such task, known as BQP-complete problems, we deepen our understanding of the power and limitations of quantum computers. In this talk, I explain two BQP-complete problems: Eigenvalue Sampling and Estimating Diagonal Entries of Powers of Sparse Symmetric Matrices. Different than the previous known BQP-complete problems (the Quadratically Signed Weight Enumerator and the Approximation of the Jones Polynomial), our two problems are of basic linear algebra nature and are closely related to the well-known quantum phase estimation algorithm and the Local Hamiltonian problem. Furthermore, problems of the form of Estimating Diagonal Entries arise in graph theory.
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. Dr. Wocjan will join the UCF School of EECS in the Fall of 2006 as an Assistant Professor. His research is focused on quantum computing and quantum information theory.
|
