Quantum and classical complexity classes: Separations, collapses, and closure properties (Q2486397)

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 \(\mathrm{C}_{=}\mathrm{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 (\(\mathrm{BQP} \subseteq \mathrm{AWPP}\) [\textit{L. Fortnow} and \textit{J. Rogers}, J. Comput. Syst. Sci. 59, No. 2, 240--252 (1999; Zbl 0947.68050)]) to \(\mathrm{BQP} \subseteq \mathrm{WPP}\) and the best known classical lower bound for EQP (\(\mathrm{P} \subseteq \mathrm{EQP}\)) to \(\mathrm{ZPP} \subseteq \mathrm{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 \(\mathrm{P}^{\mathrm{C}_{=}\mathrm{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 \(\mathrm{MOD}_{p^k}\mathrm{P}\). 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 \(\leqslant^{\mathrm{UP}}_{T}\) 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: \(\mathrm{NQP} \subseteq \mathrm{BQP}\) and \(\mathrm{EQP} = \mathrm{NQP}\).