A New Quantum Claw-finding Algorithm for Three Functions

摘要

For k functions f_1, ..., f_k, a k-tuple (x_1, ..., x_k) such that f_1(x_1) = ··· = f_k(x_k) is called a claw of f_1, ..., f_k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the number M of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requires O(N~(7/8) log N) queries to find a claw, but our algorithm requires O(N~(3/4) log N) queries if M ≤ N~(1/2) and O(N~(7/12) M~(1/3) log N) queries otherwise. Thus, our algorithm is more efficient if M ≤ N~(7/8).