We extend Aaronson and Shi's quantum lower bound for the r-to-one collision problem. An r-to-one function is one where every element of the image has exactly r preimages. The r-to-one collision problem is to distinguish between one-to-one functions and r-to-one functions over an n-element domain.

Recently, Aaronson and Shi proved a lower bound of \Omega((n/r)^1/3) quantum queries for the r-to-one collision problem. Their bound is tight, but their proof applies only when the range has size at least 3n/2. We give a modified version of their argument that removes this restriction.