Abstract: 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 in Targhi, Tabia, Unruh, Quantum Collision-Resistance of Non-Uniformly Distributed Functions, 2016 from Ω(2^{k/9}) to Ω(2^{k/5}) where k is the min-entropy of D.
Permalink: http://www.ut.ee/~unruh/publications/collision2.html