dorsal/arxiv
View SchemaStrengths and Weaknesses of Quantum Computing
| Authors | Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9701001 |
| URL | https://arxiv.org/abs/quant-ph/9701001 |
| DOI | 10.1137/S0097539796300933 |
| Journal | SIAM Journal on Computing 26(5):1510-1523, 1997 |
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})$.
{
"annotation_id": "7b65501f-b3bb-4379-b763-7e8e8f0dbb67",
"date_created": "2026-03-02T18:02:37.493000Z",
"date_modified": "2026-03-02T18:02:37.493000Z",
"file_hash": "70067ab7128d1da26152d069b8a29c70b5a447595fa0acf20004a80e5b0054e7",
"private": false,
"record": {
"abstract": "Recently a great deal of attention has focused on quantum computation\nfollowing a sequence of results suggesting that quantum computers are more\npowerful than classical probabilistic computers. Following Shor\u0027s result that\nfactoring and the extraction of discrete logarithms are both solvable in\nquantum polynomial time, it is natural to ask whether all of NP can be\nefficiently solved in quantum polynomial time. In this paper, we address this\nquestion by proving that relative to an oracle chosen uniformly at random, with\nprobability 1, the class NP cannot be solved on a quantum Turing machine in\ntime $o(2^{n/2})$. We also show that relative to a permutation oracle chosen\nuniformly at random, with probability 1, the class $NP \\cap coNP$ cannot be\nsolved on a quantum Turing machine in time $o(2^{n/3})$. The former bound is\ntight since recent work of Grover shows how to accept the class NP relative to\nany oracle on a quantum computer in time $O(2^{n/2})$.",
"arxiv_id": "quant-ph/9701001",
"authors": [
"Charles H. Bennett",
"Ethan Bernstein",
"Gilles Brassard",
"Umesh Vazirani"
],
"categories": [
"quant-ph"
],
"doi": "10.1137/S0097539796300933",
"journal_ref": "SIAM Journal on Computing 26(5):1510-1523, 1997",
"title": "Strengths and Weaknesses of Quantum Computing",
"url": "https://arxiv.org/abs/quant-ph/9701001"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "228cc4bd-ee54-4c4e-81e9-8fb86a3468a9",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}