We give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O(N/r sup 1/3) expected evaluations of the function, where N is the cardinality fo the domain. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We aslo give a similar algorithm for finding claws in paris of functions. Further, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum seaching algorithm in a novel way.
展开▼
机译：我们给出了一种量子算法，该算法仅在对该函数进行O（N / r sup 1/3）个预期评估后即可发现任意一对一函数中的冲突，其中N是域的基数。假设函数是由黑匣子给出的，那么它比最佳的经典算法更有效，甚至允许出现概率。我们还给出了一种类似的算法，用于在巴黎功能中寻找爪子。此外，我们展示了我们技术的时空权衡。我们的方法以新颖的方式使用了Grover的量子搜索算法。
展开▼
