Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range

by Andris Ambainis

Theory of Computing, Volume 1(3), pp. 37-46, 2005

Bibliography with links to cited articles

[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. Spalek: 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].

This file has been generated by bibtex2html 1.74