A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search

by Andris Ambainis

Theory of Computing, Volume 6(1), pp. 1-25, 2010

Bibliography with links to cited articles

[1]   S. Aaronson: Limitations of quantum advice and one-way communication. Theory of Computing, 1:1–28, 2005. Conference version in CCC’2004. [ToC:v001/a001, arXiv:quant-ph/0402095].

[2]   S. Aaronson and Y. Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. [JACM:1008731.1008735].

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

[4]   A. Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220–238, 2006. Conference version in FOCS’03. [JCSS:10.1016/j.jcss.2005.06.006, FOCS:10.1109/SFCS.2003.1238197, arXiv:quant-ph/0305028].

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

[6]   A. Ambainis, R. Špalek, and R. de Wolf: A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. In Proc. 38th STOC, pp. 618–633. ACM Press, 2006. [STOC:10.1145/1132516.1132604].

[7]   A. Ambainis, R. Špalek, and R. de Wolf: Quantum direct product theorems for symmetric functions and time-space tradeoffs. Algorithmica, 55(3):422–461, 2009.

[8]   H. Barnum, M. Saks, and M. Szegedy: Quantum decision trees and semidefinite programming. In Proc. 18th IEEE Conf. on Comput. Complex. (CCC’03), pp. 179–193. IEEE Press, 2003. [CCC:10.1109/CCC.2003.1214419].

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

[10]   E. Bernstein and U. Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. [SICOMP:10.1137/S0097539796300921].

[11]   G. Brassard, P. Høyer, and A. Tapp: Quantum counting. In Proc. 25th Intern. Conf. Automata, Languages and Programming (ICALP’98), volume 1443 of LNCS, pp. 820–831. Springer, 1998. [ICALP:ap2mrf08d8gcqppe, arXiv:quant-ph/9805082].

[12]   H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci., 288:21–43, 2002. [TCS:10.1016/S0304-3975(01)00144-X].

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

[14]   P. Høyer, T. Lee, and R. Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [STOC:10.1145/1250790.1250867].

[15]   P. Hoyer, J. Neerbek, and Y. Shi: Quantum lower bounds of ordered searching, sorting and element distinctness. Algorithmica, 34:429–448, 2002. Conference version at ICALP’01. [Algorithmica:25gl9elr5rxr3q6a, arXiv:quant-ph/0102078].

[16]   H. Klauck, R. Špalek, and R. de Wolf: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput., 36(5):1472–1493, 2007. Conference version at FOCS’04. [SICOMP:10.1137/05063235X, FOCS:10.1109/FOCS.2004.52, arXiv:quant-ph/0402123].

[17]   D. Knuth: Combinatorial matrices. In Selected Papers on Discrete Mathematics, CSLI Lecture Notes, no. 106. University of Chicago Press, 2003.

[18]   S. Laplante and F. Magniez: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. SIAM J. Comput., 38(1):46–62, 2008. Conference version at CCC’04. [SICOMP:10.1137/050639090, CCC:10.1109/CCC.2004.1313852, arXiv:quant-ph/0311189].

[19]   F. Magniez, M. Santha, and M. Szegedy: Quantum algorithms for the triangle problem. SIAM J. Comput., 37(2):413–424, 2007. Conference version at SODA’05. [SICOMP:10.1137/050643684, arXiv:quant-ph/0310134].

[20]   A. Nayak: Optimal lower bounds for quantum automata and random access codes. In Proc. 40th FOCS, pp. 369–377. IEEE Press, 1999. [FOCS:10.1109/SFFCS.1999.814608, arXiv:quant-ph/9904093].

[21]   B. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean functionnote. Quant-ph, arXiv:0904.2759, 2009. [arXiv:0904.2759].

[22]   R. Špalek: The multiplicative quantum adversary. In Proc. 23rd IEEE Conf. on Comput. Complex., pp. 237–248. IEEE Press, 2008. [CCC:10.1109/CCC.2008.9].

[23]   R. Špalek and M. Szegedy: All quantum adversary methods are equivalent. Theory of Computing, 2(1):1–18, 2006. Conference version at ICALP’05. [ToC:v002/a001, arXiv:quant-ph/0409116].

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