A note about claw function with a small range

Abstract

In the claw detection problem we are given two functions $f:D\to R$ and $g:D\to R$ ($|D|=n$, $|R|=k$), and we have to determine if there is exist $x,y\in D$ such that $f(x)=g(y)$. We show that the quantum query complexity of this problem is between $\Omega \left(n^{1/2}{k}^{1/6}\right)$ and $O\left(n^{1/2+\epsilon }{k}^{1/4}\right)$ when $2\le k<n$.

arXiv commentSubmitted to TQC 2021

References in corpus (4)

• Claw Finding Algorithms Using Quantum Walk
• Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
• The quantum query complexity of read-many formulas
• Adversary Lower Bound for Element Distinctness with Small Range