Quantum Computers Speed Up Classical with Probability Zero

Details Quantum Computers Speed Up Classical with Probability Zero Quantum Computers Speed Up Classical with Probability Zero

1998-03-24

arxiv.org/abs/quant-ph/9803064v1

Chaos Solitons Fractals 10 (1999) 1707-1714

Physics

Quantum Physics

11 pages, LATEX

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Quantum Computers Speed Up Classical with Probability Zero does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Computers Speed Up Classical with Probability Zero, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Computers Speed Up Classical with Probability Zero will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-500178