Abstract
The claw problem is central in the fields of theoretical computer science as well as cryptography. The optimal quantum query complexity of the problem is known to be Ω(√G+(FG)^1/3 ) for input functions f [F]→ Z and g [G]→ Z. However, the lower bound was proved when the range Z is sufficiently large (i.e., |Z|=Ω(FG)). The current paper proves the lower bound holds even for every smaller range Z with |Z|≥ F+G. This implies that Ω(√G+(FG)^1/3 ) is tight for every such range. In addition, the lower bound Ω(√G+F^1/3G^1/6M^1/6) is provided for even smaller range Z=[M] with every M∈ [2,F+G] by reducing the claw problem for |Z|= F+G. The proof technique is general enough to apply to any k-symmetric property (e.g., the k-claw problem), i.e., the Boolean function Φ on the set of k functions with different-size domains and a common range such that Φ is invariant under the permutations over each domain and the permutations over the range. More concretely, it generalizes Ambainis's argument [Theory of Computing, 1(1):37-46] to the multiple-function case by using the notion of multisymmetric polynomials.