Paper Info
Title
Quantum Computer Can Not Speed Up Iterated Applications of a Black Box
Abstract
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 a 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.
Year
Venue
Keywords
1998
QCQC
iterated application,time t.,iterated applications,classical algorithm,classical computer,quantum computer,sequential application,black box,general method,time complexity,lower bound
Field
DocType
Volume
Black box (phreaking),Quantum,Combinatorics,Oracle,Quantum computer,Quantum algorithm,Iterated function,Mathematics,Speedup
Conference
1509
ISSN
ISBN
Citations 
0302-9743
3-540-65514-X
1
PageRank 
References 
Authors
0.44
3
1
Name
Order
Citations
PageRank
Yuri Ozhigov192.84