A central promise of quantum computers is their ability to solve some problems dramatically more efficiently than their classical counterparts. Thus, to understand feasible computation in our physical world, we must turn to quantum rather than classical complexity theory. That said, classical complexity theory has a long and successful history of developing tools and techniques to analyze the power of various computing models.
In this talk, I will show that there is actually a very fruitful connection between quantum and classical complexity theory, each field informing the other. I will discuss this connection through two main classification theorems. First, I will show that every regular language has quantum query complexity Theta(1), ~Theta(sqrt(n)), or Theta(n). As it turns out, combining quantum query complexity with these extremely classical languages not only reveals new structure in these languages, but also leads to a generalization of Grover's famous quantum search algorithm. Second, I will discuss the complexity of computing the permanent over various matrix groups. In particular, I will show that computing the permanent of a unitary matrix is #P-complete. The theorem statement is classical, and yet, the proof is almost entirely the result of exploiting well-known theorems in quantum linear optics.
Thesis Supervisor: Dr. Scott Aaronson