Claw Finding Algorithms Using Quantum Walk
arXiv:0708.2584 · doi:10.1016/j.tcs.2009.08.030
Abstract
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 an optimal algorithm using quantum walk that solves this problem. 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.
12 pages. Introduction revised. A reference added. Weak lower bound deleted
References in corpus (7)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Amplitude Amplification and Estimation
- Quantum Algorithm for the Collision Problem
- Quantum Search on Bounded-Error Inputs
- Quantum query complexity of some graph problems
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Algorithms for Element Distinctness