{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T18:27:38Z","timestamp":1790360858307,"version":"4.1.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T00:00:00Z","timestamp":1088640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>\n                    Given a function\n                    <jats:italic>f<\/jats:italic>\n                    as an oracle, the collision problem is to find two distinct indexes\n                    <jats:italic>i<\/jats:italic>\n                    and\n                    <jats:italic>j<\/jats:italic>\n                    such that\n                    <jats:italic>f<\/jats:italic>\n                    (\n                    <jats:italic>i<\/jats:italic>\n                    ) =\n                    <jats:italic>f<\/jats:italic>\n                    (\n                    <jats:italic>j<\/jats:italic>\n                    ), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an\n                    <jats:italic>r<\/jats:italic>\n                    -to-one function must evaluate the function \u03a9((\n                    <jats:italic>n<\/jats:italic>\n                    \/\n                    <jats:italic>r<\/jats:italic>\n                    )\n                    <jats:sup>1\/3<\/jats:sup>\n                    ) times, where\n                    <jats:italic>n<\/jats:italic>\n                    is the size of the domain and\n                    <jats:italic>r<\/jats:italic>\n                    |\n                    <jats:italic>n<\/jats:italic>\n                    . This matches an upper bound of Brassard, H\u00f8yer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of \u03a9(\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>2\/3<\/jats:sup>\n                    ) queries for the element distinctness problem, which is to determine whether\n                    <jats:italic>n<\/jats:italic>\n                    integers are all distinct. The best previous lower bound was \u03a9(\u221a\n                    <jats:italic>n<\/jats:italic>\n                    ) queries.\n                  <\/jats:p>","DOI":"10.1145\/1008731.1008735","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T12:39:33Z","timestamp":1090327173000},"page":"595-605","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":167,"title":["Quantum lower bounds for the collision and the element distinctness problems"],"prefix":"10.1145","volume":"51","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[{"name":"University of California, Berkeley, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yaoyun","family":"Shi","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC-02)","author":"Aaronson S.","year":"2002"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing (Portland, Ore.), ACM","author":"Ambainis A.","year":"2000"},{"key":"e_1_2_1_3_1","unstructured":"Ambainis A. 2003a. Quantum lower bounds for collision and element distinctness with small range. Pre-print: quant-ph\/0305179.  Ambainis A. 2003a. Quantum lower bounds for collision and element distinctness with small range. Pre-print: quant-ph\/0305179."},{"key":"e_1_2_1_4_1","unstructured":"Ambainis A. 2003b. Quantum walk algorithm for element distinctness. Pre-print: quant-ph\/0311001.  Ambainis A. 2003b. Quantum walk algorithm for element distinctness. Pre-print: quant-ph\/0311001."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 352--361","author":"Beals R.","year":"1998"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 15th Annual ACM Symposium on the Theory of Computing","author":"Ben-Or M.","year":"1983"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_2_1_8_1","volume-title":"Lecture Notes in Computer Science","volume":"1380","author":"Brassard G."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of 16th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Buhrman H.","year":"2001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"DeVore R. A. and Lorentz G. G. 1993. Constructive approximation. Springer-Verlag Berlin Germany.  DeVore R. A. and Lorentz G. G. 1993. Constructive approximation. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-662-02888-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","article-title":"A lower bound of 1\/2n2 on linear search programs for the knapsack problem","volume":"16","author":"Dobkin D.","year":"1978","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of 33rd Annual ACM Symposium on Theory of Computing. ACM","author":"Grigni M."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","author":"Grigoriev D."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 28th Annual ACM, Symposium on the Theory of Computing","author":"Grover L. K.","year":"1996"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s00453-002-0976-3","article-title":"Quantum complexities of ordered searching, sorting, and element distinctness","volume":"34","author":"H\u00f8yer P.","year":"2002","journal-title":"Algorithmica"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 35th ACM Symposium on Theory of Computing. ACM","author":"Klauck H.","year":"2003"},{"key":"e_1_2_1_17_1","unstructured":"Kutin S. 2003. A quantum lower bound for the collision problem. Pre-print: quant-ph\/0304162.  Kutin S. 2003. A quantum lower bound for the collision problem. Pre-print: quant-ph\/0304162."},{"key":"e_1_2_1_18_1","unstructured":"Minsky M. and Papert S. 1969. Perceptrons. MIT Press Cambridge Mass.  Minsky M. and Papert S. 1969. Perceptrons. MIT Press Cambridge Mass."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria","author":"Nisan N."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria","author":"Paturi R.","year":"1992"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 43st Symposium on Foundations of Computer Science (FOCS)","author":"Shi Y.","year":"2002"},{"key":"e_1_2_1_22_1","unstructured":"Shi Y. 2004. Approximating linear restrictions of Boolean functions. Manuscript.  Shi Y. 2004. Approximating linear restrictions of Boolean functions. Manuscript."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","article-title":"Lower bounds for algebraic decision trees","volume":"3","author":"Steele J. M.","year":"1982","journal-title":"J. Algorithms"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 41st Symposium on Foundations of Computer Science (FOCS) (Redondo Beach, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 537--546","author":"Watrous J.","year":"2000"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008731.1008735","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1008731.1008735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:41:08Z","timestamp":1750268468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008731.1008735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1008731.1008735"],"URL":"https:\/\/doi.org\/10.1145\/1008731.1008735","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}