# Quantum collision-resistance of non-uniformly distributed functions

Quantum collision-resistance of non-uniformly distributed functionsE. E. Targhi, G. N. Tabia, and D. Unruh (QCrypt 2015). Poster.  [publisher's version]

Abstract: We study the quantum query complexity of finding a collision for a function $f$ whose outputs are chosen according to a distribution with min-entropy $k$. We prove that $Ω(2^{k/9})$ quantum queries are necessary to find a collision for function f.