Quantum and classical complexity classes: Separations, collapses, and closure properties

We study the complexity of quantum complexity classes such as EQP, BQP, and NQP (quantum analogs of P, BPP, and NP, respectively) using classical complexity classes such as ZPP, WPP, and C=P. The contributions of this paper are threefold. First, via oracle constructions, we show that no relativizable proof technique can improve the best known classical upper bound for BQP (BQP ⊆ AWPP [Journal of Computer and System Sciences 59(2) (1999) 240]) to BQP ⊆ WPP and the best known classical lower bound for EQP (P ⊆ EQP) to ZPP ⊆ EQP. Second, we prove that there are oracles A and B such that, relative to A, coRP is immune to NQP and relative to B, BQP is immune to PC=P. Extending a result of de Graaf and Valiant [Technical Report quant-ph/0211179, Quantum Physics (2002)], we construct a relativized world where EQP is immune to MODpkP. Third, motivated by the fact that counting classes (e.g., LWPP, AWPP, etc.) are the best known classical upper bounds on quantum complexity classes, we study properties of these counting classes. We prove that WPP is closed under polynomial-time truth-table reductions, while we construct an oracle relative to which WPP is not closed under polynomial-time Turing reductions. The latter result implies that proving the equality of the similar appearing classes LWPP and WPP would require nonrelativizable proof techniques. We also prove that both AWPP and APP are closed under ⩽TUP reductions. We use closure properties of WPP and AWPP to prove interesting consequences, in terms of the complexity of the polynomial-hierarchy, of the following hypotheses: NQP ⊆ BQP and EQP = NQP.