[1]   Scott Aaronson: Quantum lower bound for the collision problem. In Proc. of the 34th ACM STOC, pp. 635–642, 2002. [STOC:509907.509999, arXiv:quant-ph/0111102].

[2]   Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 51(4):595–605, 2004. Based on [10] and [1]. [JACM:1008735].

[3]   Andris Ambainis: Quantum walk algorithm for element distinctness. In Proc. of the 45th IEEE FOCS, pp. 22–31, 2004. [FOCS:10.1109/FOCS.2004.54, arXiv:quant-ph/0311001].

[4]   Andris Ambainis: Quantum lower bounds for collision and element distinctness with small range. Theory of Computing, 1(3), 2005. To appear. [ToC:v001/a003, arXiv:quant-ph/0305179].

[5]   Bob Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. In Proc. of the 39th IEEE FOCS, pp. 352–361, 1998. [FOCS:10.1109/SFCS.1998.743485, arXiv:quant-ph/9802049].

[6]   Gilles Brassard, Peter Høyer, and Alain Tapp: Quantum Cryptanalysis of Hash and Claw-Free Functions, volume 1380 of Lecture Notes in CS, pp. 163–169. Springer-Verlag, 1998. [LATIN:11bhjthw46dxl2qa, arXiv:quant-ph/9805082].

[7]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. of the 28th ACM STOC, pp. 212–219, 1996. [STOC:237814.237866, arXiv:quant-ph/9605043].

[8]   Noam Nisan and Márió Szegedy: On the degree of boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994. [STOC:129757].

[9]   Ramamohan Paturi: On the degree of polynomials that approximate symmetric boolean functions. In Proc. of the 24th ACM STOC, pp. 468–474, 1992. [STOC:129758].

[10]   Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. In Proc. of the 43th IEEE FOCS, pp. 513–519, 2002. [FOCS:10.1109/SFCS.2002.1181975, arXiv:quant-ph/0112086].

[11]   Peter W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. [SICOMP:29317].