1997/12/22 by Yuri Ozhigov, Ozhigov, Yuri · 2 citations
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9712051
8 pages, Latex
arxiv created 1997/12/22 · arxiv updated 2009/12/01
Let a classical algorithm be determined by sequential applications of a black box performing one step of this algorithm. If we consider this black box as an oracle which gives a value F(a) for any query a, we can compute T sequential applications of F on a classical computer relative to this oracle in time T. It is proved that if T=O(2n/7), where n is the length of input, then the result of T sequential applications of F can not be computed on quantum computer with oracle for F for all possible F faster than in time Ω(T). This means that there is no general method of quantum speeding up of classical algorithms provided in such a general method a classical algorithm is regarded as iterated applications of a given black box. For an arbitrary time complexity T a lower bound for the time of quantum simulation was found to be Ω(T1/2).