{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T03:10:37Z","timestamp":1774321837480,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T00:00:00Z","timestamp":1744329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-20-1-0015"],"award-info":[{"award-number":["W911NF-20-1-0015"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research in Quantum Computing program"},{"name":"National Science Foundation","award":["CCF-1813814 and DMR-1747426"],"award-info":[{"award-number":["CCF-1813814 and DMR-1747426"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size\n            <jats:italic>n<\/jats:italic>\n            into smaller subproblems (say,\n            <jats:italic>a<\/jats:italic>\n            copies of size\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n\/b\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            each), along with some auxiliary work of cost\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(C^{\\mathrm{aux}}(n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , to give a recurrence relation\n            <jats:disp-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\begin{equation*}\nC(n) \\le a \\, C(n\/b) + C^{\\mathrm{aux}}(n)\n\\end{equation*}\\)<\/jats:tex-math>\n            <\/jats:disp-formula>\n            for the classical complexity\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(C(n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation\n            <jats:disp-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\begin{equation*}\nC_Q(n) \\le \\sqrt {a} \\, C_Q(n\/b) + O(C^{\\mathrm{aux}}_Q(n))\n\\end{equation*}\\)<\/jats:tex-math>\n            <\/jats:disp-formula>\n            that characterizes the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing the regular language\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Sigma ^* 2 0^* 2 \\Sigma ^*\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            over the alphabet\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Sigma = \\lbrace 0,1,2\\rbrace\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.\n          <\/jats:p>","DOI":"10.1145\/3723884","type":"journal-article","created":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T11:24:22Z","timestamp":1742210662000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Divide and Conquer"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9903-837X","authenticated-orcid":false,"given":"Andrew","family":"Childs","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6114-943X","authenticated-orcid":false,"given":"Robin","family":"Kothari","sequence":"additional","affiliation":[{"name":"Microsoft Corp, Redmond, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1132-7052","authenticated-orcid":false,"given":"Matt","family":"Kovacs-Deak","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0292-744X","authenticated-orcid":false,"given":"Aarthi","family":"Sundaram","sequence":"additional","affiliation":[{"name":"Microsoft Corp, Redmond, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5472-1207","authenticated-orcid":false,"given":"Daochen","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00061"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.8"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01092-x"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.13"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1090\/s0273-0979-99-00796-x"},{"key":"e_1_3_3_9_2","unstructured":"Jonathan Allcock Jinge Bao Aleksandrs Belovs Troy Lee and Miklos Santha. 2023. On the quantum time complexity of divide and conquer. arxiv:2311.16401 [quant-ph]"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447311"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.8"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.107"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.18"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213985"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.11"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_18"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1008861.1008865"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402780"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.2307\/2003354"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.26"},{"key":"e_1_3_3_27_2","unstructured":"Christoph D\u00fcrr and Peter H\u00f8yer. 1996. A quantum algorithm for finding the minimum. arXiv:quant-ph\/9607014"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.50"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250867"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2022.v018a011"},{"key":"e_1_3_3_35_2","unstructured":"Stacey Jeffery and Galina Pass. 2024. Multidimensional quantum walks recursion and quantum divide & conquer. arxiv:2401.08355 [quant-ph]"},{"key":"e_1_3_3_36_2","first-page":"595","article-title":"Multiplication of multidigit numbers on automata","volume":"7","author":"Karatsuba Anatolij A.","year":"1963","unstructured":"Anatolij A. Karatsuba and Yu. Ofman. 1963. Multiplication of multidigit numbers on automata. Soviet Physics Doklady 7 (1963), 595\u2013596.","journal-title":"Soviet Physics Doklady"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2022.11"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2013.004"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0084-9"},{"key":"e_1_3_3_41_2","unstructured":"Troy Lee Rajat Mittal Ben W. Reichardt and Robert \u0160palek. 2010. An adversary for algorithms. arXiv:1011.3020v1"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.75"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00010-8"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a013"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","unstructured":"Ben W. Reichardt. 2009. Span-program-based quantum algorithm for evaluating unbalanced formulas. arXiv:0907.1622","DOI":"10.1145\/1374376.1374394"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.55"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133080"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00071"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.51"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_3_3_52_2","unstructured":"Qisheng Wang. 2022. A note on quantum divide and conquer for minimal string rotation. arxiv:2210.09149 [quant-ph]"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723884","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723884","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:00Z","timestamp":1750295940000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,11]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3723884"],"URL":"https:\/\/doi.org\/10.1145\/3723884","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,11]]},"assertion":[{"value":"2024-01-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}