Seminar by Dr. Rahul Tripathi
Understanding Relationships Between Quantum and Classical Complexity Classes: Separations, Collapses, and Closures
Dr Rahul Tripathi
Department of Computer Science
Rochester University
Rochester, NY, USA
Date: Thu, Dec 23, 2004
Time: 3:45 PM
Venue: CS-101
Abstract
Over the past decade, quantum computing has emerged as a major contender to classical computing with far-reaching implications and challenges for the real world. Efficient quantum algorithms for problems such as the discrete logarithm and factoring have led researchers to rethink the foundations of classical cryptographic schemes. Quantum complexity theory is the study of the computational power and the limitations of quantum computing. A major theme in quantum complexitytheory is to understand the relationships between quantum and classical complexity classes. In this talk, I will illuminate this relationship by means of separations, collapses, and closure results involving quantum and classical counting classes.
The most central quantum complexity classes EQP, BQP, and NQP (the quantum analogs of P, BPP, and NP), are known to be related to classical counting complexity classes. We prove that standard (relativizable) proof techniques cannot improve the best-known classical bounds for EQP and BQP significantly. For relationships between certain quantum and counting classes, we prove stronger results: No standard (relativizable) proof technique can show that every infinite set in one class has a nontrivial approximation in another class (even under the nondemanding approximation notion of merely having an infinite subset belonging to the other class). These results show the limitations of a broad class of proof techniques in resolving questions on relationship between quantum and classical complexity classes. We also obtain interesting consequences, in terms of the complexity of the polynomial hierarchy, of hypotheses involving the quantum complexity classes EQP, BQP, and NQP.
Though we will touch on this just briefly in the talk, our analysis leads to the resolution of important questions in classical complexity theory as well. The foremost among these is that, resolving a question open since the seminal 1994 counting class paper of Fenner, Fortnow, and Kurtz, we prove that the counting classes WPP and LWPP are not uniformly gap-definable.