{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T17:05:34Z","timestamp":1768583134980,"version":"3.49.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-2129139"],"award-info":[{"award-number":["CCF-2129139"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"\n Longest common substring (LCS)<\/jats:italic>\n is an important text processing problem, which has recently been investigated in the quantum query model. The decision version of this problem,\n LCS with threshold<\/jats:italic>\n \n \\(d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , asks whether two length-\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n input strings have a common substring of length\n \n \\(d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The two extreme cases,\n \n \\(d=1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(d=n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , correspond, respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case\n \n \\(1\\ll d\\ll n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n was not fully understood. We show that the complexity of LCS with threshold\n \n \\(d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n smoothly interpolates between the two extreme cases up to\n \n \\(n^{o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n factors:\n \n \n \u2014<\/jats:label>\n \n LCS with threshold\n \n \\(d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n has a quantum algorithm in\n \n \\(n^{2\/3+o(1)}\/d^{1\/6}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n query complexity and time complexity, and requires at least\n \n \\(\\Omega(n^{2\/3}\/d^{1\/6})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n quantum query complexity.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n \n Our result improves upon previous upper bounds\n \n \\(\\widetilde{O}(\\min\\{n\/d^{1\/2},n^{2\/3}\\})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful\n String Synchronizing Set<\/jats:italic>\n technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples\n \n \\(n\/\\tau^{1-o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n synchronizing positions in the string depending on their length-\n \n \\(\\Theta(\\tau)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n contexts, and each synchronizing position can be reported by a quantum algorithm in\n \n \\(\\widetilde{O}(\\tau^{1\/2+o(1)})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. As another application of our quantum string synchronizing set, we study the\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -mismatch Matching<\/jats:italic>\n problem, which asks if the pattern has an occurrence in the text with at most\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n Hamming mismatches. Using a structural result of Charalampopoulos et al. (FOCS 2020), we obtain:\n \n \n \u2014<\/jats:label>\n \n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -mismatch matching has a quantum algorithm with\n \n \\(k^{3\/4}n^{1\/2+o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n query complexity and\n \n \\(\\widetilde{O}(kn^{1\/2})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time complexity. We also observe a non-matching quantum query lower bound of\n \n \\(\\Omega(\\sqrt{kn})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1145\/3672395","type":"journal-article","created":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T13:42:57Z","timestamp":1718026977000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Quantum Speed-Ups for String Synchronizing Sets, Longest Common Substring, and\n k<\/i>\n -mismatch Matching"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5264-1772","authenticated-orcid":false,"given":"Ce","family":"Jin","sequence":"first","affiliation":[{"name":"MIT, Cambridge, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7028-2595","authenticated-orcid":false,"given":"Jakob","family":"Nogler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.16"},{"key":"e_1_3_4_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00061"},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01092-x"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2019.25"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-2776-5_2"},{"key":"e_1_3_4_8_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a003"},{"key":"e_1_3_4_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447311"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9219-1"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.8"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.6"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00744-0"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00097-X"},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2020.5"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456807"},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-019-09317-z"},{"key":"e_1_3_4_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_4_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.69"},{"key":"e_1_3_4_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.31"},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2021.19"},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44888-8_5"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2018.23"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.27"},{"key":"e_1_3_4_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.30"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"e_1_3_4_31_1","unstructured":"Andrew M. Childs Robin Kothari Matt Kovacs-Deak Aarthi Sundaram and Daochen Wang. 2022. Quantum Divide and Conquer. arXiv:2210.06419. Retrieved from https:\/\/arxiv.org\/abs\/2210.06419"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch142"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.26"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59042-0_72"},{"key":"e_1_3_4_35_1","unstructured":"Christoph Durr and Peter H \\(\\phi\\) yer. 1996. A Quantum Algorithm for Finding the Minimum. arXiv:quant-ph\/9607014. Retrieved from https:\/\/arxiv.org\/abs\/quant-ph\/9607014"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646102"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.2307\/2034009"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/8307.8309"},{"key":"e_1_3_4_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01066-z"},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60044-2_36"},{"key":"e_1_3_4_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.62"},{"key":"e_1_3_4_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.118"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1131"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316368"},{"key":"e_1_3_4_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00097"},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520061"},{"key":"e_1_3_4_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch187"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.36"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90178-7"},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/214438.214445"},{"key":"e_1_3_4_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/090745854"},{"key":"e_1_3_4_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129758"},{"key":"e_1_3_4_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055097"},{"key":"e_1_3_4_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00010-8"},{"key":"e_1_3_4_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38905-4_22"},{"key":"e_1_3_4_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220002"},{"key":"e_1_3_4_58_1","unstructured":"Qisheng Wang. 2022. A Note on Quantum Divide and Conquer for Minimal String Rotation. arXiv:2210.09149. Retrieved from https:\/\/arxiv.org\/abs\/2210.09149"},{"key":"e_1_3_4_59_1","unstructured":"Qisheng Wang and Mingsheng Ying. 2020. Quantum Algorithm for Lexicographically Minimal String Rotation. arXiv:2012.09376."},{"key":"e_1_3_4_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3672395","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3672395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:57:49Z","timestamp":1750294669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3672395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3672395"],"URL":"https:\/\/doi.org\/10.1145\/3672395","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"assertion":[{"value":"2023-09-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}