New Generation Computing, 21(2003)319-327
Ohmsha, Ltd. and Springer-Verlag

A New Quantum Claw-finding Algorithm for Three Functions

Kazuo IWAMA
Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
Quantum Computation and Information Project, ERATO, JST
406, Iseya-cho, Kamigyo-ku, Kyoto 602-0873, Japan
iwama@kuis.kyoto-u.ac.jp

Akinori KAWACHI
Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
Quantum Computation and Information Project, ERATO, JST
406, Iseya-cho, Kamigyo-ku, Kyoto 602-0873, Japan
kawachi@kuis.kyoto-u.ac.jp

Received 31 August 2002
Revised manuscript received 30 April 2003

Abstract

For k functions f₁,...,f_k, a k-tuple (x₁,...,x_k) such that f₁(x₁) = ... = f_k(x_k) is called a claw of f₁,...,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/8logN) queries to find a claw, but our algorithm requires O(N^3/4logN) queries if M≤√N and O(N^7/12M^1/3logN) queries otherwise. Thus, our algorithm is more efficient if M≤N^7/8.

Keywords: Grover Search, Claw-Finding Algorithm, Intermediate Solutions.

[Back]