Complexity limitations on quantum computation

Abstract

We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum class BQP. 1. BQP is low for PP, i.e., PP^BQP=PP. 2. There exists a relativized world where P=BQP and the polynomial-time hierarchy is infinite. 3. There exists a relativized world where BQP does not have complete sets. 4. There exists a relativized world where P=BQP but P is not equal to UP intersect coUP and one-way functions exist. This gives a relativized answer to an open question of Simon.

13 pages, no figures; presented at the 13th annual Conference on Computational Complexity (1998); submitted to the Journal of Computer and System Sciences

References in corpus (2)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Strengths and Weaknesses of Quantum Computing

Cited by in corpus (35)

• Quantum algorithms for algebraic problems
• Differentiable Learning of Quantum Circuit Born Machine
• Quantum Lower Bounds by Polynomials
• An Introduction to Quantum Complexity Theory
• Noise and the frontier of quantum supremacy
• The computational landscape of general physical theories
• Quantum Computing: Lecture Notes
• Bounds for Small-Error and Zero-Error Quantum Algorithms
• Succinct quantum proofs for properties of finite groups
• Most tensor problems are NP-hard
• Quantum statistical zero-knowledge
• Power of one non-clean qubit
• Nondeterministic Quantum Query and Quantum Communication Complexities
• Lower Bounds for Quantum Search and Derandomization
• Quantum Proofs for Classical Theorems
• Quantum Bounded Query Complexity
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Applications of the Adversary Method in Quantum Query Algorithms
• On the Complexity of Quantum ACC
• Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy
• Quantum algorithms for solvable groups
• A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines
• Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement
• On quantum and classical space-bounded processes with algebraic transition amplitudes
• Quantum Computation Relative to Oracles
• Quantum versus Classical Learnability
• Modified group non-membership is in AWPP
• Theory of One Tape Linear Time Turing Machines
• Algebraic Extension Ring Framework for Non-Commutative Asymmetric Cryptography
• On exact counting and quasi-quantum complexity
• Quantum interpretations of AWPP and APP
• Quantum Weakly Nondeterministic Communication Complexity
• The Acrobatics of BQP
• Quantum Optimization Problems
• One Complexity Theorist's View of Quantum Computing