S. Aaronson and A. Ambainis, The need of structure in quantum speedups, 2009.

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.
DOI : 10.1145/1008731.1008735

D. Aharonov and A. Ta-shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth ACM symposium on Theory of computing , STOC '03, pp.20-29, 2003.
DOI : 10.1145/780542.780546
URL : http://arxiv.org/abs/quant-ph/0301023

A. Ambainis, Quantum Walk Algorithm for Element Distinctness, SIAM Journal on Computing, vol.37, issue.1, pp.210-239, 2007.
DOI : 10.1137/S0097539705447311
URL : http://arxiv.org/abs/quant-ph/0311001

T. Batu, Testing properties of distributions, 2001.

T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld, The Complexity of Approximating the Entropy, SIAM Journal on Computing, vol.35, issue.1, pp.132-150, 2005.
DOI : 10.1137/S0097539702403645

T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld et al., Testing random variables for independence and identity, Proceedings 2001 IEEE International Conference on Cluster Computing, p.442, 2001.
DOI : 10.1109/SFCS.2001.959920

T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White, Testing that distributions are close, Proceedings 41st Annual Symposium on Foundations of Computer Science, p.259, 2000.
DOI : 10.1109/SFCS.2000.892113

T. Batu, R. Kumar, and R. Rubinfeld, Sublinear algorithms for testing monotone and unimodal distributions, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.381-390, 2004.
DOI : 10.1145/1007352.1007414

G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation & Information, volume 305 of Contemporary Mathematics Series Millenium Volume, pp.53-74, 2002.
DOI : 10.1090/conm/305/05215

G. Brassard, P. Høyer, and A. Tapp, Quantum cryptanalysis of hash and claw-free functions, ACM SIGACT News, vol.28, issue.2, pp.14-19, 1997.
DOI : 10.1145/261342.261346

S. Bravyi, A. Harrow, and A. Hassidim, Quantum Algorithms for Testing Properties of Distributions, IEEE Transactions on Information Theory, vol.57, issue.6, 2009.
DOI : 10.1109/TIT.2011.2134250
URL : https://hal.archives-ouvertes.fr/inria-00455782

O. Goldreich and D. Ron, A sublinear bipartiteness tester for bounded degree graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing , STOC '98, pp.289-298, 1998.
DOI : 10.1145/276698.276767

L. Grover and T. Rudolph, How significant are the known collision and element distinctness quantum algorithms? Quant, Inf. & Comp, vol.4, pp.201-206, 2004.

A. Sahai and S. Vadhan, A complete promise problem for statistical zero-knowledge, Proceedings 38th Annual Symposium on Foundations of Computer Science, p.448, 1997.
DOI : 10.1109/SFCS.1997.646133

M. Santha, Quantum Walk Based Search Algorithms, TAMC, pp.31-46, 2008.
DOI : 10.1007/978-3-540-79228-4_3

M. Szegedy, Quantum Speed-Up of Markov Chain Based Algorithms, 45th Annual IEEE Symposium on Foundations of Computer Science, pp.32-41, 2004.
DOI : 10.1109/FOCS.2004.53

P. Valiant, Testing symmetric properties of distributions, STOC '08: Proceedings of the 40th annual ACM symposium on Theory of computing, pp.383-392, 2008.