Quantum collision-resistance of non-uniformly distributed functions: upper and lower bounds
Ehsan Ebrahimi, Dominique Unruh · Quantum Information and Computation · 2018
We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a non-uniform distribution D. We derive some upper bounds and lower bounds depending on the min-entropy and the collision-entropy of D. In particular, we improve the previous lower bound by Ebrahimi Targhi et al. from \Omega(2^{k/9}) to \Omega(2^{k/5}) where k is the min-entropy of D.