[1]   Scott Aaronson: Quantum lower bound for the collision problem. In Proc. 34th STOC, pp. 635–642. ACM Press, 2002. [doi:10.1145/509907.509999]

[2]   Scott Aaronson: BQP and the polynomial hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. See expanded version in ECCC 2009. [doi:10.1145/1806689.1806711]

[3]   Scott Aaronson and Andris Ambainis: The need for structure in quantum speedups. In Proc. 2nd Innovations in Computer Science Conference (ICS’11), pp. 338–352, 2011. (Tsinghua). [arXiv:0911.0996]

[4]   Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. Preliminary versions by Aaronson in STOC’02 (item [1]) and by Shi in FOCS’02. [doi:10.1145/1008731.1008735]

[5]   Dorit Aharonov, Vaughan Jones, and Zeph Landau: A polynomial quantum algorithm for approximating the jones polynomial. Algorithmica, 55(3):395–421, 2009. Preliminary version in STOC’06. [doi:10.1007/s00453-008-9168-0]

[6]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci., 64(4):750–767, 2002. Preliminary version in STOC’00. [doi:10.1006/jcss.2002.1826]

[7]   Andris Ambainis and Ronald de Wolf: Average-case quantum query complexity. Journal of Physics A: Mathematical and General, 34(35):6741, 2001. Preliminary version in STACS’00. [doi:10.1088/0305-4470/34/35/302, arXiv:quant-ph/9904079]

[8]   Arturs Bačkurs and Mohammad Bavarian: On the sum of L₁ influences. In Proc. 29th IEEE Conf. on Computational Complexity (CCC’14). IEEE Comp. Soc. Press, 2014. ECCC 2014. [doi:10.1109/CCC.2014.21, arXiv:1302.4625]

[9]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in FOCS’98. [doi:10.1145/502090.502097]

[10]   Jonathan Niel de Beaudrap, Richard Cleve, and John Watrous: Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449–461, 2002. [doi:10.1007/s00453-002-0978-1]

[11]   Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [doi:10.1137/S0097539796300933]

[12]   Ethan Bernstein and Umesh V. Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]

[13]   Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In S. J. Lomonaco and H. E. Brandt, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics Series. Amer. Math. Soc., 2002. [doi:10.1090/conm/305, arXiv:quant-ph/0005055]

[14]   Gilles Brassard, Peter Høyer, and Alain Tapp: Quantum cryptanalysis of hash and claw free functions. ACM SIGACT News, 28(2):14–19, 1997. [doi:10.1145/261342.261346, arXiv:quant-ph/9705002]

[15]   Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]

[16]   Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig: Quantum property testing. SIAM J. Comput., 37(5):1387–1400, 2008. Preliminary version in SODA’03. [doi:10.1137/S0097539704442416]

[17]   Wim van Dam, Sean Hallgren, and Lawrence Ip: Quantum algorithms for some hidden shift problems. SIAM J. Comput., 36(3):763–778, 2006. Preliminary version in SODA’03. [doi:10.1137/S009753970343141X]

[18]   David Deutsch and Richard Jozsa: Rapid solution of problems by quantum computation. Proc. Roy. Soc. A, 439(1907):553–558, 1992. [doi:10.1098/rspa.1992.0167]

[19]   Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell: On the Fourier tails of bounded functions over the discrete cube. Israel J. Math., 160(1):389–412, 2007. Preliminary version in STOC’06. [doi:10.1007/s11856-007-0068-9]

[20]   Lance Fortnow and John D. Rogers: Complexity limitations on quantum computation. J. Comput. Sys. Sci., 59(2):240–252, 1999. Preliminary version in CCC’98. [doi:10.1006/jcss.1999.1651, arXiv:cs/9811023]

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

[22]   Aram Harrow, Avinatan Hassidim, and Seth Lloyd: Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett., 15, 2009. [doi:10.1103/PhysRevLett.103.150502, arXiv:0811.3171]

[23]   Edith Hemaspaandra, Lane A. Hemaspaandra, and Marius Zimand: Almost-everywhere superiority for quantum polynomial time. Inform. and Comput., 175(2):171–181, 2002. [doi:10.1006/inco.2001.3110, arXiv:quant-ph/9910033]

[24]   Jeff Kahn, Michael E. Saks, and Clifford D. Smyth: A dual version of Reimer’s inequality and a proof of Rudich’s conjecture. In Proc. 15th IEEE Conf. on Computational Complexity (CCC’00), pp. 98–103. IEEE Comp. Soc. Press, 2000. [doi:10.1109/CCC.2000.856739]

[25]   Gatis Midrijanis: A polynomial quantum query lower bound for the set equality problem. In Proc. 31th Internat. Colloq. on Automata, Languages and Programming (ICALP’04), pp. 996–1005. Springer, 2004. [doi:10.1007/978-3-540-27836-8_83]

[26]   Ashley Montanaro: Some applications of hypercontractive inequalities in quantum information theory. J. Math. Phys., 53(12), 2012. [doi:10.1063/1.4769269, arXiv:1208.0161]

[27]   Ryan O’Donnell, Michael E. Saks, Oded Schramm, and Rocco A. Servedio: Every decision tree has an influential variable. In Proc. 46th FOCS, pp. 31–39. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.34, arXiv:cs/0508071]

[28]   Ryan O’Donnell and Rocco A. Servedio: New degree bounds for polynomial threshold functions. Combinatorica, 30(3):327–358, 2010. Preliminary version in STOC’03. [doi:10.1007/s00493-010-2173-3]

[29]   Yaoyun Shi: Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables. Inform. Proc. Lett., 75(1-2):79–83, 2000. [doi:10.1016/S0020-0190(00)00069-7, arXiv:quant-ph/9904107]

[30]   Peter W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. Preliminary version in FOCS’94. [doi:10.1137/S0097539795293172]

[31]   Daniel R. Simon: On the power of quantum computation. SIAM J. Comput., 26(5):1474–1483, 1997. Preliminary version at FOCS’94. [doi:10.1137/S0097539796298637]

[32]   Clifford D. Smyth: Reimer’s inequality and Tardos’ conjecture. In Proc. 34th STOC, pp. 218–221. ACM Press, 2002. [doi:10.1145/509907.509942]

[33]   Henry Yuen: A quantum lower bound for distinguishing random functions from random permutations. Quantum Information & Computation, 14(13 & 14), 2014. QIC-online. [arXiv:1310.2885]

[34]   Mark Zhandry: A note on the quantum collision and set equality problems. 2013. [arXiv:1312.1027]