How significant are the known collision and element distinctness quantum algorithms?

Details How significant are the known collision and element distinctness quantum algorithms? How significant are the known collision and element distinctness quantum algorithms?

2003-09-16

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

Quantum Information & Computation, 4, 201 (2004)

Physics

Quantum Physics

Scientific paper

Quantum search is a technique for searching N possibilities in only O(sqrt(N)) steps. It has been applied in the design of quantum algorithms for several structured problems. Many of these algorithms require significant amount of quantum hardware. In this paper we observe that if an algorithm requires O(P) hardware, it should be considered significant if and only if it produces a speedup of at least O(sqrt(P)) over a simple quantum search algorithm. This is because a speedup of $O(sqrt(P)) $ can be trivially obtained by dividing the search space into $O(P)$ separate parts and handing the problem to independent processors that do a quantum search. We argue that the known algorithms for collision and element distinctness fail to be non-trivial in this sense.

Affiliated with

Also associated with

No associations

Rating

How significant are the known collision and element distinctness quantum algorithms? 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 How significant are the known collision and element distinctness quantum algorithms?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How significant are the known collision and element distinctness quantum algorithms? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-690923