Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
Theory of Computing, Volume 1(3), pp. 37-46, 2005
Bibliography with links to cited articles
 S. Aaronson and Y. Shi: Quantum lower bounds for the collision and the element distinctness problems. Journal of ACM, 51(4):595–605, 2004. Earlier versions in  and . [JACM:1008731.1008735].
 R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf: Quantum lower bounds by polynomials. Journal of ACM, 48:778–797, 2001. Earlier version at FOCS’98. [JACM:502090.502097, arXiv:quant-ph/9802049].
 G. Brassard, P. Høyer, and A. Tapp: Quantum algorithm for the collision problem. SIGACT News, 28:14–19, 1997. [arXiv:quant-ph/9705002].
 H. Buhrman, R. Cleve, and A. Wigderson: Quantum vs. classical communication and computation. In Proceedings of STOC’98, pp. 63–68, 1998. [STOC:276698.276713].
 H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288:21–43, 2002. [TCS:10.1016/S0304-3975(01)00144-X].
 H. Buhrman, C. Durr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf: Quantum algorithms for element distinctness. In 16th IEEE Annual Conference on Computational Complexity (CCC’01), pp. 131–137, 2001. [CCC:10.1109/CCC.2001.933880, arXiv:quant-ph/0007016].
 H. Buhrman and R. Špalek: Quantum verification of matrix products. [arXiv:quant-ph/0409035].
 P. Hoyer, J. Neerbek, and Y. Shi: Quantum lower bounds of ordered searching, sorting and element distinctness. Algorithmica, 34:429–448, 2002. Earlier version at ICALP’01. [Algorithmica:25gl9elr5rxr3q6a, arXiv:quant-ph/0102078].
 F. Magniez, M. Santha, and M. Szegedy: Quantum algorithms for the triangle problem. In Proceedings of SODA’05, 2005. [arXiv:quant-ph/0310134].