= Quantum collision finding
Given a <function> $f$ with an $m$-bit output, accessed through the <unitary operator> $U_f|x\rangle|y\rangle=|x\rangle|y\mathbin\oplus f(x)\rangle$, quantum collision finding asks for distinct inputs with equal outputs. Here $\oplus$ is bitwise <exclusive or> on the $m$-bit answer <quantum register>. The distinctness requirement excludes the uninformative pair $(x,x)$. For a two-to-one function on $N$ inputs, <Grover search algorithm> methods yield a cube-root <quantum query complexity>, despite a square-root cost for finding a partner of just one preselected input.
Back to article page
