An Improved Claw Finding Algorithm Using Quantum Walk
An Improved Claw Finding Algorithm Using Quantum Walk
复制标题
使用量子行走改进的寻爪算法
DOI：
10.1007/978-3-540-74456-6_48
复制
发表时间：
2007
期刊：
影响因子：
2.3
通讯作者：
S. Tani
中科院分区：
文献类型：
--
作者：
S. Tani
作为与密码学密切相关的问题之一，爪发现问题已经从查询复杂度的角度进行了研究。对于给定的两个函数f和g，作为一个oracle，它们分别具有大小为N和M（N ≤ M）的域，并且具有相同的范围，问题的目标是找到x和y，使得f（x）= g（y）。本文描述了一种基于量子行走的算法，解决了这个问题，它改进了以前的上限。我们的算法可以推广到找到一个爪的k个函数，任何常数整数k > 1，其中的功能域可能有不同的大小。
The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N ≤ M), respectively, and the same range, the goal of the problem is to find x and y such that f(x) = g(y). This paper describes a quantum-walk-based algorithm that solves this problem; it improves the previous upper bounds. Our algorithm can be generalized to find a claw of k functions for any constant integer k > 1, where the domains of the functions may have different size.