Quantum complexity theory is the study of the computational power and the limitations of quantum computing. A major theme in quantum complexity theory 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 about the 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.