S. Aaronson, Lower bounds for local search by quantum arguments, Proc. STOC, pp.465-474, 2004.

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 new quantum lower bound method, with an application to strong direct product theorem for quantum search

A. Ambainis, Quantum lower bounds by quantum arguments, J. Comput. Syst. Sci, vol.64, issue.4, pp.750-767, 2002.

A. Ambainis, Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range, Theory of Computing, vol.1, issue.3, pp.37-46, 2005.

Z. Bar-yossef, R. Kumar, and D. Sivakumar, Sampling Algorithms: lower bounds and applications, Proc. STOC, pp.266-275, 2001.

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. De-wolf, Quantum lower bounds by polynomials, Journal of the ACM, vol.48, issue.4, pp.778-797, 2001.

A. Bogdanov and L. Trevisan, Lower bounds for testing bipartiteness in dense graphs, Proc. 19th IEEE Annual Conference on Computational Complexity (CCC'04, 2004.

B. Bollobás, Extremal Graph Theory, 2004.

P. J. Cameron, Permutation groups, vol.45, 1999.

S. Fenner, F. Green, S. Homer, and Y. Zhang, Bounds on the power of constant-depth quantum circuits, Proc. 15th International Symposium on on Fundamentals of Computation Theory (FCT 2005), vol.3623, pp.44-55, 2005.

K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen, Hidden translation and orbit coset in quantum computing, STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003.

K. Friedl, G. Ivanyos, M. Santha, and Y. Verhoeven, On the black-box complexity of Sperner's lemma, Proc. 15th International Symposium on on Fundamentals of Computation Theory (FCT 2005), vol.3623, pp.245-257, 2005.

O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties. Random Structures and Algorithms, vol.23, pp.23-57, 2003.

P. Koiran, V. Nesme, and N. Portier, A quantum lower bound for the query complexity of Simon's problem, Proc. ICALP 2005, vol.3580, pp.1287-1298, 2005.

P. Koiran, V. Nesme, and N. Portier, The quantum query complexity of the abelian hidden subgroup problem, 2005.
URL : https://hal.archives-ouvertes.fr/hal-02101788

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

S. Kutin, Quantum lower bound for the collision problem with small range. Theory of Computing, vol.1, pp.29-36, 2005.

S. Laplante and F. Magniez, Lower bounds for randomized and quantum query complexity using kolmogorov arguments, Proc. 19th IEEE Annual Conference on Computational Complexity (CCC'04, 2004.

N. Nisan, CREW PRAMs and decision trees, SIAM J. Comput, vol.20, issue.6, pp.999-1007, 1991.

A. L. Rosenberg, On the time required to check properties of graphs: A problem, pp.15-16, 1973.

D. R. Simon, On the power of quantum computation, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp.116-123, 1994.

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

R. Spalek and M. Szegedy, All quantum adversary methods are equivalent, Proc. ICALP 2005, vol.3580, pp.1299-1311, 2005.