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 \(\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}\).
- \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
- A complexity theory for feasible closure properties
- A note on separating the relativized polynomial time hierarchy by immune sets
- A uniform approach to define complexity classes
- An oracle builder's toolkit
- Approximate formulas for some functions of prime numbers
- Complexity classes and sparse oracles
- Complexity classes defined by counting quantifiers
- Complexity limitations on quantum computation
- Computational Complexity of Probabilistic Turing Machines
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Counting classes: Thresholds, parity, mods, and fewness
- Gap-definable counting classes
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3984573 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2163013 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- On the construction of parallel computers from various basis of Boolean functions
- On the power of deterministic reductions to C=P
- On the power of parity polynomial time
- P-Printable Sets
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- PP is as Hard as the Polynomial-Time Hierarchy
- PP-lowness and a simple definition of AWPP
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Probabilistic quantifiers and games
- Quantum Complexity Theory
- Quantum Computability
- Relations among MOD-classes
- Relative complexity of checking and evaluating
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized counting classes: Relations among thresholds, parity, and mods
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- Relativized worlds with an infinite hierarchy
- Strengths and Weaknesses of Quantum Computing
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- The Boolean Hierarchy I: Structural Properties
- The complexity of combinatorial problems with succinct input representation
- The complexity theory companion
- Turing machines with few accepting computations and low sets for PP
- The robustness of LWPP and WPP, with an application to graph reconstruction
- LWPP and WPP are not uniformly gap-definable
- scientific article; zbMATH DE number 1583884 (Why is no real title available?)
- The space ``just above BQP
- The robustness of LWPP and WPP, with an application to graph reconstruction
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Complexity classification of two-qubit commuting Hamiltonians
- On the maximum-likelihood decoding problem
This page was built for publication: Quantum and classical complexity classes: Separations, collapses, and closure properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2486397)
