dorsal/arxiv
View SchemaQuantum Computers Speed Up Classical with Probability Zero
| Authors | Yuri Ozhigov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9803064 |
| URL | https://arxiv.org/abs/quant-ph/9803064 |
| Journal | Chaos Solitons Fractals 10 (1999) 1707-1714 |
Abstract
Let $f$ denote length preserving function on words. A classical algorithm can be considered as $T$ iterated applications of black box representing $f$, beginning with input word $x$ of length $n$. It is proved that if $T=O(2^{n/(7+e)}), e >0$, and $f$ is chosen randomly then with probability 1 every quantum computer requires not less than $T$ evaluations of $f$ to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity $T$ and $f$ chosen randomly with probability 1 every quantum simulation of classical computation requires at least $\Omega (\sqrt {T})$ evaluations of $f$.
{
"annotation_id": "eb71d522-786b-457f-9007-e136c66168c6",
"date_created": "2026-03-02T18:02:41.097000Z",
"date_modified": "2026-03-02T18:02:41.097000Z",
"file_hash": "89f059841ab4ab7721e25945bc19a4fd6d65c620bb0e508748de02e95cf55557",
"private": false,
"record": {
"abstract": "Let $f$ denote length preserving function on words. A classical algorithm can\nbe considered as $T$ iterated applications of black box representing $f$,\nbeginning with input word $x$ of length $n$.\n It is proved that if $T=O(2^{n/(7+e)}), e \u003e0$, and $f$ is chosen randomly\nthen with probability 1 every quantum computer requires not less than $T$\nevaluations of $f$ to obtain the result of classical computation. It means that\nthe set of classical algorithms admitting quantum speeding up has probability\nmeasure zero.\n The second result is that for arbitrary classical time complexity $T$ and $f$\nchosen randomly with probability 1 every quantum simulation of classical\ncomputation requires at least $\\Omega (\\sqrt {T})$ evaluations of $f$.",
"arxiv_id": "quant-ph/9803064",
"authors": [
"Yuri Ozhigov"
],
"categories": [
"quant-ph"
],
"journal_ref": "Chaos Solitons Fractals 10 (1999) 1707-1714",
"title": "Quantum Computers Speed Up Classical with Probability Zero",
"url": "https://arxiv.org/abs/quant-ph/9803064"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "589ddcb9-ed65-4308-bc36-db6eee8eb13f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}