Complexity limitations on quantum computation
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10930159,p. 202-209
- https://doi.org/10.1109/ccc.1998.694606
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. BQP is low for PP, i.e., PP/sup BQP/=PP. There exists a relativized world where P=BQP and the polynomial-time hierarchy is infinite. There exists a relativized world where BQP does not have complete sets. There exists a relativized world where P=BQP but P/spl ne/UP/spl cap/coUP and one-way functions exist. This gives a relativized answer to an open question of Simon.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Quantum lower bounds by polynomialsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Relationships between quantum and classical space-bounded complexity classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- Quantum ComputationPublished by Springer Nature ,1997
- A fast quantum mechanical algorithm for database searchPublished by Association for Computing Machinery (ACM) ,1996
- When do extra majority gates help? Polylog (N) majority gates are equivalent to onecomputational complexity, 1994
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMSIzvestiya: Mathematics, 1994
- Graph isomorphism is low for PPcomputational complexity, 1992
- Complexity Measures for Public-Key CryptosystemsSIAM Journal on Computing, 1988