, If y > x we always answer "no" the query "F (x) = y ?

, most one i such that x ? y ? H i . If there is no such i, we answer "no" to the collision query. If there is such an i, we can test with at most 2 calls to f whether i = i 0 . If i = i 0 , we answer

, If there is no i such that x < N/p i , we may therefore answer "no". Otherwise, let i 1 be the biggest such i. Then the answer is "yes, p.0

. Références,

S. Aaronson and Y. Shi, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM, vol.51, issue.4, pp.595-605, 2004.

A. Ambainis, A better lower bound for quantum algorithms searching an ordered list, FOCS '99 : Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.352, 1999.
DOI : 10.1109/sffcs.1999.814606
URL : http://arxiv.org/pdf/quant-ph/9902053.pdf

A. Ambainis, Quantum lower bounds by quantum arguments, J. Comput. Syst. Sci, vol.64, issue.4, pp.750-767, 2002.
DOI : 10.1145/335305.335394
URL : http://arxiv.org/pdf/quant-ph/0002066

R. Beals, Quantum computation of Fourier transforms over symmetric groups, Proceedings of the 29th Annual ACM Symposium on the Theory of Computation (STOC), pp.48-53, 1997.
DOI : 10.1145/258533.258548

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. Wolf, Quantum lower bounds by polynomials, J. ACM, vol.48, issue.4, pp.778-797, 2001.
DOI : 10.1109/sfcs.1998.743485
URL : http://arxiv.org/pdf/quant-ph/9802049

G. Brassard and P. Høyer, An exact quantum polynomial-time algorithm for Simon's problem, Israel Symposium on Theory of Computing Systems, pp.12-23, 1997.
DOI : 10.1109/istcs.1997.595153
URL : http://arxiv.org/pdf/quant-ph/9704027

L. R. Hales, The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem, 2002.

M. Hirvensalo, Quantum Computing (Natural Computing Series). SpringerVerlag, 2001.

P. Høyer, Conjugated operators in quantum algorithms, Phys. Rev. A, vol.59, pp.3280-3289, 1999.

R. Jozsa, Quantum algorithms and the Fourier transform, Proc. R. Soc. of London A, vol.454, 1998.

P. Koiran, V. Nesme, and N. Portier, A quantum lower bound for the query complexity of Simon's problem

G. Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, 2003.
DOI : 10.1137/s0097539703436345
URL : http://arxiv.org/pdf/quant-ph/0302112

H. Kurzweil and B. Stellmacher, The Theory of Finite Groups, An Introduction. Universitext, 2004.

S. Kutin, Quantum lower bound for the collision problem, 2003.

A. Michael, I. L. Nielsen, and . Chuang, Quantum computation and quantum information, 2000.

N. Nisan and M. Szegedy, On the degree of boolean functions as real polynomials, Comput. Complex, vol.4, issue.4, pp.301-313, 1994.

R. Paturi, On the degree of polynomials that approximate symmetric boolean functions (preliminary version), STOC '92 : Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp.468-474, 1992.

P. Philipps, Bornes inférieures en calcul quantique : Méthode par adversaire vs. méthode des polynômes. Rapport de stage de DEA, effectué au LRI sous la direction de Frédéric Magniez, 2003.

W. Peter and . Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput, vol.26, issue.5, pp.1484-1509, 1997.

D. R. Simon, On the power of quantum computation, SIAM Journal on Computing, vol.26, issue.5, pp.1474-1483, 1997.