[1]   Scott Aaronson: Personal communication, 2014.

[2]   Scott Aaronson, Shalev Ben-David, and Robin Kothari: Separations in query complexity using cheat sheets. In Proc. 48th STOC, pp. 863–876. ACM Press, 2016. [doi:10.1145/2897518.2897644, arXiv:1511.01937]

[3]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Preliminary version in STOC’00. [doi:10.1006/jcss.2002.1826, arXiv:quant-ph/0002066]

[4]   Andris Ambainis: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210–239, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447311, arXiv:quant-ph/0311001]

[5]   Andris Ambainis and Robert Špalek: Quantum algorithms for matching and network flows. In Proc. 23rd Symp. Theoretical Aspects of Comp. Sci. (STACS’06), volume 3884 of LNCS, pp. 172–183. Springer, 2006. [doi:10.1007/11672142_13, arXiv:quant-ph/0508205]

[6]   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, arXiv:quant-ph/9802049]

[7]   Aleksandrs Belovs: Span programs for functions with constant-sized 1-certificates: extended abstract. In Proc. 44th STOC, pp. 77–84. ACM Press, 2012. [doi:10.1145/2213977.2213985, arXiv:1105.4024]

[8]   Shalev Ben-David: A super-Grover separation between randomized and quantum query complexities. Electron. Colloq. on Comput. Complex. (ECCC), 2015. ECCC. [arXiv:1506.08106]

[9]   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, arXiv:quant-ph/9701001]

[10]   Claude Berge: Two theorems in graph theory. Proc. Nat. Acad. Sci. U.S.A., 43(9):842–844, 1957. [doi:10.1073/pnas.43.9.842]

[11]   Aija Berzina, Andrej Dubrovsky, Rusins Freivalds, Lelde Lace, and Oksana Scegulnaja: Quantum query complexity for some graph problems. In Proc. 30th Conf. Current Trends Theory and Pract. Comput. Sci. (SOFSEM’04), volume 2932 of LNCS, pp. 140–150. Springer, 2004. [doi:10.1007/978-3-540-24618-3_11]

[12]   Rajendra Bhatia: Matrix Analysis. Springer, 1997. [doi:10.1007/978-1-4612-0653-8]

[13]   Aharon Brodutch, Daniel Nagaj, Or Sattath, and Dominique Unruh: An adaptive attack on Wiesner’s quantum money. Quantum Inf. Comput., 16(11&12):1048–1070, 2016. [arXiv:1404.1507]

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

[15]   Andrew Childs: The adversary method, 2013. Available at author’s website.

[16]   Stephen A. Cook, Cynthia Dwork, and Rüdiger Reischuk: Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput., 15(1):87–97, 1986. [doi:10.1137/0215006]

[17]   Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms (3. ed.). MIT Press, 2009. Available at publisher’s website.

[18]   Yefim A. Dinitz: Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady, 11(5):1277–1280, 1970. Available at author’s website.

[19]   Sebastian Dörn: Quantum algorithms for matching problems. Theory Comput. Syst., 45(3):613–628, 2009. [doi:10.1007/s00224-008-9118-x]

[20]   Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla: Quantum query complexity of some graph problems. SIAM J. Comput., 35(6):1310–1328, 2006. Preliminary version in ICALP’04. [doi:10.1137/050644719, arXiv:quant-ph/0401091]

[21]   Christoph Dürr and Peter Høyer: A quantum algorithm for finding the minimum, 1996. [arXiv:quant-ph/9607014]

[22]   Avshalom C. Elitzur and Lev Vaidman: Quantum mechanical interaction-free measurements. Found. Phys., 23(7):987–997, 1993. [doi:10.1007/BF00736012, arXiv:hep-th/9305002]

[23]   Shimon Even and Robert Endre Tarjan: Network flow and testing graph connectivity. SIAM J. Comput., 4(4):507–518, 1975. Preliminary version in STOC’74. [doi:10.1137/0204043]

[24]   Bartholomew Furrow: A panoply of quantum algorithms. Quantum Inf. Comput., 8(8):834–859, 2008. ACM DL. [arXiv:quant-ph/0606127]

[25]   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]

[26]   John E. Hopcroft and Richard M. Karp: An n^5∕2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225–231, 1973. Preliminary version in SWAT’71. [doi:10.1137/0202019]

[27]   Onur Hosten and Paul G. Kwiat: Weak measurements and counterfactual computation, 2006. [arXiv:quant-ph/0612159]

[28]   Onur Hosten, Matthew T. Rakher, Julio T. Barreiro, Nicholas A. Peters, and Paul G. Kwiat: Counterfactual computation revisited, 2006. [arXiv:quant-ph/0607101]

[29]   Onur Hosten, Matthew T. Rakher, Julio T. Barreiro, Nicholas A. Peters, and Paul G. Kwiat: Counterfactual quantum computation through quantum interrogation. Nature, 439:949–952, 2006. [doi:10.1038/nature04523]

[30]   Peter Høyer, Troy Lee, and Robert Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867, arXiv:quant-ph/0611054]

[31]   Stacey Jeffery, Robin Kothari, and Frédéric Magniez: Nested quantum walks with quantum data structures. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1474–1485. ACM Press, 2013. [doi:10.1137/1.9781611973105.106, arXiv:1210.1199]

[32]   Alexander V. Karzanov: O nakhozhdenii maksimal’nogo potoka v setyakh spetsial’nogo vida i nekotorykh prilozheniyakh (“On finding maximum flow in networks of a special kind and in certain applications,” in Russian). In Matematicheskie Voprosy Upravleniya Proizvodstvom (Mathematical Questions of Management), volume 5, pp. 81–94. Moscow State Univ. Press, 1973.

[33]   Shelby Kimmel: Quantum adversary (upper) bound. Chicago J. Theor. Comput. Sci., 2013(4), 2013. Preliminary version in ICALP’12. [doi:10.4086/cjtcs.2013.004, arXiv:1101.0797]

[34]   Robin Kothari: An optimal quantum algorithm for the oracle identification problem. In Proc. 31st Symp. Theoretical Aspects of Comp. Sci. (STACS’14), volume 25 of LIPIcs, pp. 482–493. Schloss Dagstuhl, 2014. [doi:10.4230/LIPIcs.STACS.2014.482, arXiv:1311.7685]

[35]   Paul Kwiat, Harald Weinfurter, Thomas Herzog, Anton Zeilinger, and Mark A. Kasevich: Interaction-free measurement. Phys. Rev. Lett., 74(24):4763–4766, 1995. [doi:10.1103/PhysRevLett.74.4763]

[36]   Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.75, arXiv:1011.3020]

[37]   Cedric Yen-Yu Lin and Han-Hsuan Lin: Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. In Proc. 30th IEEE Conf. on Computational Complexity (CCC’15), pp. 537–566. IEEE Comp. Soc. Press, 2015. [doi:10.4230/LIPIcs.CCC.2015.537, arXiv:1410.0932]

[38]   Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha: Search via quantum walk. SIAM J. Comput., 40(1):142–164, 2011. Preliminary version in STOC’07. [doi:10.1137/090745854, arXiv:quant-ph/0608026]

[39]   Silvio Micali and Vijay V. Vazirani: An O(⋅|E|) algorithm for finding maximum matching in general graphs. In Proc. 21st FOCS, pp. 17–27. IEEE Comp. Soc. Press, 1980. [doi:10.1109/SFCS.1980.12]

[40]   Baidyanath Misra and E. C. George Sudarshan: The Zeno’s paradox in quantum theory. J. Math. Phys., 18(4):756–763, 1977. [doi:10.1063/1.523304]

[41]   Graeme Mitchison and Richard Jozsa: Counterfactual computation. Proc. Royal Soc. A, 457(2009):1175–1194, 2001. [doi:10.1098/rspa.2000.0714, arXiv:quant-ph/9907007]

[42]   Graeme Mitchison and Richard Jozsa: The limits of counterfactual computation, 2006. [arXiv:quant-ph/0606092]

[43]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000.

[44]   Noam Nisan: CREW PRAMs and decision trees. SIAM J. Comput., 20(6):999–1007, 1991. Preliminary version in STOC’89. [doi:10.1137/0220062]

[45]   Tae-Gon Noh: Counterfactual quantum cryptography. Phys. Rev. Lett., 103(23):230501, 2009. [doi:10.1103/PhysRevLett.103.230501, arXiv:0809.3979]

[46]   Oded Regev and Liron Schiff: Impossibility of a quantum speed-up with a faulty oracle. In Proc. 35th Internat. Colloq. on Automata, Languages and Programming (ICALP’08), volume 5125 of LNCS, pp. 773–781. Springer, 2008. [doi:10.1007/978-3-540-70575-8_63, arXiv:1202.1027]

[47]   Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759]

[48]   Ben W. Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011. [doi:10.1137/1.9781611973082.44, arXiv:1005.1601]

[49]   Hatim Salih, Zheng-Hong Li, M. Al-Amri, and M. Suhail Zubairy: Protocol for direct counterfactual quantum communication. Phys. Rev. Lett., 110(17):170502, 2013. [doi:10.1103/PhysRevLett.110.170502, arXiv:1206.2042]

[50]   Mario Szegedy: Quantum speed-up of Markov chain based algorithms. In Proc. 45th FOCS, pp. 32–41. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.53]

[51]   Lev Vaidman: The impossibility of the counterfactual computation for all possible outcomes. Phys. Rev. Lett., 98(16):160403, 2007. [doi:10.1103/PhysRevLett.98.160403, arXiv:quant-ph/0610174]

[52]   Lev Vaidman: Comment on “Protocol for direct counterfactual quantum communication”. Phys. Rev. Lett., 112(20):208901, 2014. [doi:10.1103/PhysRevLett.112.208901, arXiv:1304.6689]

[53]   Stephen Wiesner: Conjugate coding. ACM SIGACT News, 15(1):78–88, 1983. [doi:10.1145/1008908.1008920]

[54]   Shengyu Zhang: On the power of Ambainis lower bounds. Theoret. Comput. Sci., 339(2-3):241–256, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.01.019, arXiv:quant-ph/0311060]