Abstract

Recently a great deal of attention has focused on quantum computation following a sequence of results suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of NP can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time $o(2^{n/2})$. We also show that relative to a permutation oracle chosen uniformly at random, with probability 1, the class $NP \cap coNP$ cannot be solved on a quantum Turing machine in time $o(2^{n/3})$. The former bound is tight since recent work of Grover shows how to accept the class NP relative to any oracle on a quantum computer in time $O(2^{n/2})$.

Keywords

Strengths and weaknessesComputer scienceQuantum computerApplied mathematicsTheoretical computer scienceQuantumMathematicsComputational sciencePhysicsQuantum mechanicsPsychology

Related Publications

Publication Info

Year
1997
Type
article
Citations
23
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

23
OpenAlex

Cite This

Charles H. Bennett, Gilles Brassard, Umesh Vazirani et al. (1997). Strengths and Weaknesses of Quantum Computing. . https://doi.org/10.48550/arxiv.quant-ph/9701001

Identifiers

DOI
10.48550/arxiv.quant-ph/9701001

Data Quality

Data completeness: 70%