Claw Finding Algorithms Using Quantum Walk

Details Claw Finding Algorithms Using Quantum Walk Claw Finding Algorithms Using Quantum Walk

2007-08-20

arxiv.org/abs/0708.2584v2

Theoretical Computer Science, 410(50): 5285-5297 (2009)

Physics

Quantum Physics

12 pages. Introduction revised. A reference added. Weak lower bound deleted

Scientific paper

10.1016/j.tcs.2009.08.030

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N<=M), respectively, and the same range, the goal of the problem is to find x and y such that f(x)=g(y). This paper describes an optimal algorithm using quantum walk that solves this problem. Our algorithm can be generalized to find a claw of k functions for any constant integer k>1, where the domains of the functions may have different size.

Affiliated with

Also associated with

No associations

Rating

Claw Finding Algorithms Using Quantum Walk 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 Claw Finding Algorithms Using Quantum Walk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Claw Finding Algorithms Using Quantum Walk will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-532774