Claw Finding Algorithms Using Quantum Walk
arXiv:0708.2584 · doi:10.1016/j.tcs.2009.08.030
Abstract
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.
12 pages. Introduction revised. A reference added. Weak lower bound deleted