[1]   S. Aaronson: Quantum lower bound for the collision problem. In Proceedings of STOC’02, pp. 635–642, 2002. [STOC:509907.509999, arXiv:quant-ph/0111102].

[2]   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 [1] and [22]. [JACM:1008731.1008735].

[3]   A. Ambainis: Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64:750–767, 2002. [JCSS:10.1006/jcss.2002.1826, arXiv:quant-ph/0002066].

[4]   A. Ambainis: Polynomial degree vs. quantum query complexity. In Proceedings of FOCS’03, pp. 230–239, 2003. [FOCS:10.1109/SFCS.2003.1238197, arXiv:quant-ph/0305028].

[5]   A. Ambainis: Quantum walk algorithm for element distinctness. In Proceedings of FOCS’04, pp. 22–31, 2004. [FOCS:10.1109/FOCS.2004.54, arXiv:quant-ph/0311001].

[6]    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].

[7]    G. Brassard, P. Høyer, and A. Tapp: Quantum algorithm for the collision problem. SIGACT News, 28:14–19, 1997. [arXiv:quant-ph/9705002].

[8]   G. Brassard, P. Høyer, and A. Tapp: Quantum counting. In Proceedings of ICALP’98, pp. 820–831, 1998. [ICALP:ap2mrf08d8gcqppe, arXiv:quant-ph/9805082].

[9]   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].

[10]   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].

[11]   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].

[12]   H. Buhrman and R. Špalek: Quantum verification of matrix products. [arXiv:quant-ph/0409035].

[13]   T. Cormen, C. Leiserson, R. Rivest, and C. Stein: Introduction to Algorithms, 2nd edition. The MIT Press and McGraw-Hill Book Company, 2001.

[14]   L. Grover: A fast quantum mechanical algorithm for database search. In Proceedings of STOC’96, pp. 212–219, 1996. [STOC:237814.237866, arXiv:quant-ph/9605043].

[15]   L. Grover: A framework for fast quantum mechanical algorithms. In Proceedings of STOC’98, pp. 53–62, 1998. [STOC:276698.276712, arXiv:quant-ph/9711043].

[16]   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].

[17]   S. Kutin: Quantum lower bound for the collision problem. Theory of Computing, 1(2):29–36, 2005. [ToC:v001/a002, arXiv:quant-ph/0304162].

[18]   F. Magniez, M. Santha, and M. Szegedy: Quantum algorithms for the triangle problem. In Proceedings of SODA’05, 2005. [arXiv:quant-ph/0310134].

[19]    A. Nayak and F. Wu: The quantum query complexity of approximating the median and related statistics. In Proceedings of STOC’99, pp. 384–393, 1999. [STOC:301250.301349, arXiv:quant-ph/9804066].

[20]   N. Nisan and M. Szegedy: On the degree of boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994.

[21]   Y. Shi: Approximating linear restrictions of boolean functions. Manuscript.

[22]   Y. Shi: Quantum lower bounds for the collision and the element distinctness problems. In Proceedings of FOCS’02, pp. 513–519, 2002. [FOCS:10.1109/SFCS.2002.1181975, arXiv:quant-ph/0112086].