  The current paper improves the number of queries of the previous quantum
multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt
2017. Let an $l$-collision be a tuple of $l$ distinct inputs that result in the
same output of a target function. In cryptology, it is important to study how
many queries are required to find $l$-collisions for random functions of which
domains are larger than ranges. The previous algorithm finds an $l$-collision
for a random function by recursively calling the algorithm for finding
$(l-1)$-collisions, and it achieves the average quantum query complexity of
$O(N^{(3^{l-1}-1) / (2 \cdot 3^{l-1})})$, where $N$ is the range size of target
functions. The new algorithm removes the redundancy of the previous recursive
algorithm so that different recursive calls can share a part of computations.
The new algorithm finds an $l$-collision for random functions with the average
quantum query complexity of $O(N^{(2^{l-1}-1) / (2^{l}-1)})$, which improves
the previous bound for all $l\ge 3$ (the new and previous algorithms achieve
the optimal bound for $l=2$). More generally, the new algorithm achieves the
average quantum query complexity of $O\left(c^{3/2}_N N^{\frac{2^{l-1}-1}{
2^{l}-1}}\right)$ for a random function $f\colon X\to Y$ such that $|X| \geq l
\cdot |Y| / c_N$ for any $1\le c_N \in o(N^{\frac{1}{2^l - 1}})$. With the same
query complexity, it also finds a multiclaw for random functions, which is
harder to find than a multicollision.
