Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
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