Quantum Computers Speed Up Classical with Probability Zero

Simple item page
dc.creatorOzhigov, Yuri
dc.date1998-03-24
dc.date.accessioned2026-07-07T06:14:53Z
dc.date.available2026-07-07T06:14:53Z
dc.descriptionLet $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 $Ω(\sqrt {T})$ evaluations of $f$.
dc.description11 pages, LATEX
dc.identifierhttps://arxiv.org/abs/quant-ph/9803064
dc.identifierhttp://arxiv.org/abs/quant-ph/9803064
dc.identifierChaos Solitons Fractals 10 (1999) 1707-1714
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93636
dc.subjectQuantum Physics
dc.titleQuantum Computers Speed Up Classical with Probability Zero
dc.typetext

Files

Collections

arXiv