% ACR    4/12/05 Added ref for Shor with e-print field.

@article{AS04,
author = {Scott Aaronson and Yaoyun Shi},
title = "Quantum lower bounds for the collision and the element distinctness problems",
journal = {Journal of the ACM},
volume = 51,
number = 4,
pages = "595-605",
year = 2004,
note = "Based on~\cite{Shi01} and~\cite{Aar02}",
eprint = "jacm:1008735",
}

@article{Amb03-lower,
author = {Andris Ambainis},
title = "Quantum lower bounds for collision and element distinctness with small range",
journal = "Theory of Computing",
year = 2005,
volume = 1,
number = 3,
note = {To appear},
eprint = {toc:v001/a003, arxiv:quant-ph/0305179}
}

@InProceedings{Amb03-upper,
author = {Andris Ambainis},
title = "Quantum walk algorithm for element distinctness",
booktitle = "Proc. of the 45th IEEE FOCS",
pages = {22--31},
year = 2004,
eprint = {focs:10.1109/FOCS.2004.54, quant-ph/0311001},
}

@InProceedings{Aar02,
author = {Scott Aaronson},
title = {Quantum lower bound for the collision problem},
booktitle = "Proc. of the 34th ACM STOC",
year = 2002,
pages = "635-642",
eprint = {stoc:509907.509999, arxiv:quant-ph/0111102}
}

@InProceedings{Shi01,
author = {Yaoyun Shi},
title = {Quantum lower bounds for the collision and the element
distinctness problems},
booktitle = "Proc. of the 43th IEEE FOCS",
year = 2002,
pages = "513-519",
eprint = {focs:10.1109/SFCS.2002.1181975, arxiv:quant-ph/0112086},
}

@article{Shor,
author = "Peter~W. Shor",
title = "Polynomial-time algorithms for prime factorization and
discrete logarithms on a quantum computer",
journal = sicomp,
year = 1997,
volume = 26,
number = 5,
pages = "1484-1509",
eprint = {sicomp:29317}
}

@InProceedings{BBCMdW,
author = {Bob Beals and Harry Buhrman and Richard Cleve and Michele Mosca and Ronald de Wolf},
title = "Quantum lower bounds by polynomials",
booktitle = "Proc. of the 39th IEEE FOCS",
Year = 1998,
pages = "352-361",
eprint = {focs:10.1109/SFCS.1998.743485, arxiv:quant-ph/9802049}
}

@InProceedings{Pat92,
author = {Ramamohan Paturi},
title = "On the degree of polynomials that approximate symmetric boolean functions",
booktitle = "Proc. of the 24th ACM STOC",
year = 1992,
pages = "468-474",
eprint = "stoc:129758"
}

@article{NS92,
author = "Noam Nisan and M{\'a}ri{\'o} Szegedy",
title = "On the degree of Boolean functions as real polynomials",
journal = "Computational Complexity",
volume = 4,
pages = "301-313",
year = 1994,
eprint = {stoc:129757}
}

@InBook{BHT97,
author = "Gilles Brassard and Peter H{\o}yer and Alain Tapp",
title = "Quantum Cryptanalysis of Hash and Claw-Free Functions",
booktitle = "3rd Latin American Theoretical Informatics Symposium (LATIN '98)",
series = "Lecture Notes in CS",
volume = 1380,
publisher = "Springer-Verlag",
pages = "163-169",
year = 1998,
eprint = {latin:11bhjthw46dxl2qa, arxiv:quant-ph/9805082} 
}

@InProceedings{G96,
Author = "Lov~K. Grover",
Title = "A fast quantum mechanical algorithm for database search",
booktitle = "Proc. of the 28th ACM STOC",
Year = 1996,
Pages = "212-219",
eprint = {stoc:237814.237866, arxiv:quant-ph/9605043}
}