{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T14:39:41Z","timestamp":1777559981225,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540275800","type":"print"},{"value":"9783540316916","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_104","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"1287-1298","source":"Crossref","is-referenced-by-count":5,"title":["A Quantum Lower Bound for the Query Complexity of Simon\u2019s Problem"],"prefix":"10.1007","author":[{"given":"Pascal","family":"Koiran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Nesme","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natacha","family":"Portier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"104_CR1","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM\u00a051(4), 595\u2013605 (2004)","journal-title":"Journal of the ACM"},{"key":"104_CR2","first-page":"48","volume-title":"Proceedings of the 29th Annual ACM Symposium on the Theory of Computation (STOC)","author":"R. Beals","year":"1997","unstructured":"Beals, R.: Quantum computation of Fourier transforms over symmetric groups. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computation (STOC), pp. 48\u201353. ACM Press, New York (1997)"},{"issue":"4","key":"104_CR3","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R. Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM\u00a048(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"104_CR4","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u03c6yer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem. In: Israel Symposium on Theory of Computing Systems, pp. 12\u201323 (1997)","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"104_CR5","unstructured":"Hales, L.R.: The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem. PhD thesis, UC Berkeley (2002)"},{"key":"104_CR6","volume-title":"Quantum Computing (Natural Computing Series)","author":"M. Hirvensalo","year":"2001","unstructured":"Hirvensalo, M.: Quantum Computing (Natural Computing Series). Springer, Heidelberg (2001)"},{"key":"104_CR7","doi-asserted-by":"publisher","first-page":"3280","DOI":"10.1103\/PhysRevA.59.3280","volume":"59","author":"P. H\u03c6yer","year":"1999","unstructured":"H\u03c6yer, P.: Conjugated operators in quantum algorithms. Phys. Rev. A\u00a059, 3280\u20133289 (1999)","journal-title":"Phys. Rev. A"},{"key":"104_CR8","doi-asserted-by":"crossref","unstructured":"Jozsa, R.: Quantum algorithms and the Fourier transform. Proc. R. Soc. of London A, 454 (1998)","DOI":"10.1098\/rspa.1998.0163"},{"key":"104_CR9","unstructured":"Koiran, P., Nesme, V., Portier, N.: A quantum lower bound for the query complexity of Simon\u2019s problem, \n                    \n                      http:\/\/www.arxiv.org\/pdf\/quant-ph\/0501060"},{"key":"104_CR10","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. Quantum Physics e-Print Archive (2003)"},{"key":"104_CR11","series-title":"Universitext","doi-asserted-by":"crossref","DOI":"10.1007\/b97433","volume-title":"The Theory of Finite Groups, An Introduction","author":"H. Kurzweil","year":"2004","unstructured":"Kurzweil, H., Stellmacher, B.: The Theory of Finite Groups, An Introduction. Universitext. Springer, Heidelberg (2004)"},{"key":"104_CR12","unstructured":"Kutin, S.: Quantum lower bound for the collision problem. quant-ph\/0304162 (2003)"},{"key":"104_CR13","volume-title":"Quantum computation and quantum information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge University Press, Cambridge (2000)"},{"issue":"4","key":"104_CR14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Comput. Complex.\u00a04(4), 301\u2013313 (1994)","journal-title":"Comput. Complex."},{"key":"104_CR15","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In: STOC 1992: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"key":"104_CR16","unstructured":"Philipps, P.: Bornes inf\u00e9rieures en calcul quantique: M\u00e9thode par adversaire vs. m\u00e9thode des polyn\u00f4mes. Rapport de stage de DEA, effectu\u00e9 au LRI sous la direction de Fr\u00e9d\u00e9ric Magniez (2003), \n                    \n                      http:\/\/www.lri.fr\/~magniez\/stages-dea.html"},{"issue":"5","key":"104_CR17","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput.\u00a026(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"104_CR18","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"D.R. Simon","year":"1997","unstructured":"Simon, D.R.: On the power of quantum computation. SIAM Journal on Computing\u00a026(5), 1474\u20131483 (1997)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_104.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:46:51Z","timestamp":1619506011000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11523468_104","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}