Quantum algorithms for subset finding

Details Quantum algorithms for subset finding Quantum algorithms for subset finding

2003-11-06

arxiv.org/abs/quant-ph/0311038v2

Quantum Information and Computation 5, 593 (2005)

Physics

Quantum Physics

7 pages; note added on related results in quant-ph/0310134

Scientific paper

Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.

Affiliated with

Also associated with

No associations

Rating

Quantum algorithms for subset finding 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 algorithms for subset finding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum algorithms for subset finding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-343108