Quantum Lower Bound for the Collision Problem with Small Range
by Samuel Kutin
Theory of Computing, Volume 1(2), pp. 29-36, 2005
Bibliography with links to cited articles
| [1] |
Scott Aaronson: Quantum lower bound for the collision problem.
In Proc. of the 34th ACM STOC, pp. 635-642, 2002.
[STOC:509907.509999,
arXiv:quant-ph/0111102]. |
| [2] |
Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and
the element distinctness problems.
Journal of the ACM, 51(4):595-605, 2004.
Based on [10] and [1].
[JACM:1008735]. |
| [3] |
Andris Ambainis: Quantum walk algorithm for element distinctness.
In Proc. of the 45th IEEE FOCS, pp. 22-31, 2004.
[FOCS:10.1109/FOCS.2004.54,
arXiv:quant-ph/0311001]. |
| [4] |
Andris Ambainis: Quantum lower bounds for collision and element
distinctness with small range.
Theory of Computing, 1(3), 2005.
To appear.
[ToC:v001/a003,
arXiv:quant-ph/0305179]. |
| [5] |
Bob Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald
de Wolf: Quantum lower bounds by polynomials.
In Proc. of the 39th IEEE FOCS, pp. 352-361, 1998.
[FOCS:10.1109/SFCS.1998.743485,
arXiv:quant-ph/9802049]. |
| [6] |
Gilles Brassard, Peter Høyer, and Alain Tapp: Quantum
Cryptanalysis of Hash and Claw-Free Functions, volume 1380 of Lecture
Notes in CS, pp. 163-169.
Springer-Verlag, 1998.
[LATIN:11bhjthw46dxl2qa,
arXiv:quant-ph/9805082]. |
| [7] |
Lov K. Grover: A fast quantum mechanical algorithm for database search.
In Proc. of the 28th ACM STOC, pp. 212-219, 1996.
[STOC:237814.237866,
arXiv:quant-ph/9605043]. |
| [8] |
Noam Nisan and Márió Szegedy: On the degree of boolean functions
as real polynomials.
Computational Complexity, 4:301-313, 1994.
[STOC:129757]. |
| [9] |
Ramamohan Paturi: On the degree of polynomials that approximate symmetric
boolean functions.
In Proc. of the 24th ACM STOC, pp. 468-474, 1992.
[STOC:129758]. |
| [10] |
Yaoyun Shi: Quantum lower bounds for the collision and the element
distinctness problems.
In Proc. of the 43th IEEE FOCS, pp. 513-519, 2002.
[FOCS:10.1109/SFCS.2002.1181975,
arXiv:quant-ph/0112086]. |
| [11] |
Peter W. Shor: Polynomial-time algorithms for prime factorization and
discrete logarithms on a quantum computer.
SIAM Journal on Computing, 26(5):1484-1509, 1997.
[SICOMP:29317]. |
This file has been generated by bibtex2html 1.74