[1]   S. Aaronson and Y. Shi: Quantum lower bounds for the collision and the element distinctness problem. Journal of the ACM, 51(4):595–605, 2004. [JACM:1008731.1008735, arXiv:quant-ph/0111102].

[2]   A. Ambainis: Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750–767, 2002. Earlier version in STOC ’00. [JCSS:10.1006/jcss.2002.1826, STOC:335305.335394, arXiv:quant-ph/0002066].

[3]   A. Ambainis: Polynomial degree vs. quantum query complexity. In Proc. of 44th IEEE FOCS, pp. 230–239, 2003. [FOCS:10.1109/SFCS.2003.1238197, arXiv:quant-ph/0305028].

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

[5]   A. Ambainis: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1:37–46, 2005. [ToC:v001/a003, arXiv:quant-ph/0305179].

[6]   H. Barnum and M. Saks: A lower bound on the quantum query complexity of read-once functions. Journal of Computer and System Sciences, 69(2):244–258, 2004. [JCSS:10.1016/j.jcss.2004.02.002, arXiv:quant-ph/0201007].

[7]   H. Barnum, M. Saks, and M. Szegedy: Quantum decision trees and semidefinite programming. In Proc. of 18th IEEE Complexity, pp. 179–193, 2003. [CCC:10.1109/CCC.2003.1214419].

[8]   R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf: Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. Earlier version in FOCS ’98. [JACM:502090.502097, FOCS:10.1109/SFCS.1998.743485, arXiv:quant-ph/9802049].

[9]   H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani: Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. [SICOMP:30093, arXiv:quant-ph/9701001].

[10]   H. Buhrman and R. Špalek: Quantum verification of matrix products. In Proc. of 17th ACM-SIAM SODA, pp. 880–889, 2006. [SODA:1109557.1109654, arXiv:quant-ph/0409035].

[11]   H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21–43, 2002. [TCS:10.1016/S0304-3975(01)00144-X].

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

[13]   P. Høyer, M. Mosca, and R. de Wolf: Quantum search on bounded-error inputs. In Proc. of 30th ICALP, pp. 291–299, 2003. LNCS 2719. [ICALP:214dhep41d6vk3d2, arXiv:quant-ph/0304052].

[14]   P. Høyer, J. Neerbek, and Y. Shi: Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica, 34(4):429–448, 2002. Special issue on Quantum Computation and Cryptography. [Algorithmica:25gl9elr5rxr3q6a, arXiv:quant-ph/0102078].

[15]   P. Høyer and R. Špalek: Lower bounds on quantum query complexity. EATCS Bulletin, 87:78–103, October, 2005. [arXiv:quant-ph/0509153].

[16]   S. Laplante, T. Lee, and M. Szegedy: The quantum adversary method and formula size lower bounds. In Proc. of 20th IEEE Complexity, pp. 76–90, 2005. [CCC:10.1109/CCC.2005.29, arXiv:quant-ph/0501057].

[17]   S. Laplante and F. Magniez: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In Proc. of 19th IEEE Complexity, pp. 294–304, 2004. [CCC:10.1109/CCC.2004.1313852, arXiv:quant-ph/0311189].

[18]   M. Li and P. M. B. Vitányi: An Introduction to Kolmogorov Complexity and its Applications. Springer, Berlin, second edition, 1997.

[19]   L. Lovász: Semidefinite programs and combinatorial optimization. http://research.microsoft.com/users/lovasz/semidef.ps, 2000.

[20]   F. Magniez, M. Santha, and M. Szegedy: Quantum algorithms for the triangle problem. In Proc. of 16th ACM-SIAM SODA, pp. 1109–1117, 2005. [SODA:1070432.1070591, arXiv:quant-ph/0310134].

[21]   R. Mathias: The spectral norm of a nonnegative matrix. Linear Algebra and its Applications, 139:269–284, 1990. [10.10160024-3795(90)90403-Y].

[22]   M. A. Nielsen and I. L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[23]   M. Saks and A. Wigderson: Probabilistic Boolean decision trees and the complexity of evaluating games trees. In Proc. of 27th IEEE FOCS, pp. 29–38, 1986.

[24]   M. Santha: On the Monte Carlo decision tree complexity of read-once formulae. Random Structures and Algorithms, 6(1):75–87, 1995.

[25]   M. Snir: Lower bounds on probabilistic decision trees. Theoretical Computer Science, 38:69–82, 1985. [TCS:10.1016/0304-3975(85)90210-5].

[26]   M. Szegedy: On the quantum query complexity of detecting triangles in graphs. quant-ph/0310107, 2003. [arXiv:quant-ph/0310107].

[27]   S. Zhang: On the power of Ambainis’s lower bounds. Theoretical Computer Science, 339(2–3):241–256, 2005. Earlier version in ICALP’04. [TCS:10.1016/j.tcs.2005.01.019, ICALP:gm2ff6wpc0q39v3x, arXiv:quant-ph/0311060].