{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:12:13Z","timestamp":1783746733047,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T00:00:00Z","timestamp":1783900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,13]]},"DOI":"10.1145\/3806645.3816165","type":"proceedings-article","created":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T04:21:11Z","timestamp":1783743671000},"page":"722-730","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Bit-Parallel Swap Matching"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5937-5796","authenticated-orcid":false,"given":"Simone","family":"Faro","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Catania, Catania, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4722-9542","authenticated-orcid":false,"given":"Francesco Pio","family":"Marino","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Catania, Catania, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8840-6157","authenticated-orcid":false,"given":"Arianna","family":"Pavone","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Universit\u00e0 di Palermo, Palermo, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8355-1121","authenticated-orcid":false,"given":"Simone","family":"Spina","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Catania, Catania, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7312-5002","authenticated-orcid":false,"given":"Caterina","family":"Viola","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Catania, Catania, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,13]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","unstructured":"Pritom Ahmed Costas\u00a0S. Iliopoulos A.\u00a0S. M.\u00a0Sohidull Islam and Mohammad\u00a0Sohel Rahman. 2014. The swap matching problem revisited. Theor. Comput. Sci. 557 (2014) 34\u201349. 10.1016\/j.tcs.2014.08.009","DOI":"10.1016\/j.tcs.2014.08.009"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646103"},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"publisher","unstructured":"Amihood Amir Yonatan Aumann Gad\u00a0M. Landau Moshe Lewenstein and Noa Lewenstein. 2000. Pattern Matching with Swaps. J. Algorithms 37 2 (2000) 247\u2013266. 10.1006\/jagm.2000.1120","DOI":"10.1006\/jagm.2000.1120"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"publisher","unstructured":"Ricardo\u00a0A. Baeza-Yates and Gaston\u00a0H. Gonnet. 1992. A New Approach to Text Searching. Commun. ACM 35 10 (1992) 74\u201382. 10.1145\/135239.135243","DOI":"10.1145\/135239.135243"},{"key":"e_1_3_3_1_6_2","unstructured":"V\u00e1clav Blazej Ondrej Such\u00fd and Tom\u00e1s Valla. 2016. A Simpler Bit-parallel Algorithm for Swap Matching. CoRR abs\/1606.04763 (2016). http:\/\/arxiv.org\/abs\/1606.04763"},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10217-2_24"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"publisher","unstructured":"Matteo Campanelli Domenico Cantone Simone Faro and Emanuele Giaquinta. 2012. Pattern Matching with Swaps in Practice. Int. J. Found. Comput. Sci. 23 2 (2012) 323\u2013342. 10.1142\/S0129054112400151","DOI":"10.1142\/S0129054112400151"},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95891-8_25"},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"publisher","unstructured":"Domenico Cantone Simone Faro and Emanuele Giaquinta. 2012. A compact representation of nondeterministic (suffix) automata for the bit-parallel approach. Inf. Comput. 213 (2012) 3\u201312. 10.1016\/j.ic.2011.03.006","DOI":"10.1016\/j.ic.2011.03.006"},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38100-3_9"},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"publisher","unstructured":"Domenico Cantone Simone Faro Arianna Pavone and Caterina Viola. 2026. Quantum algorithms for longest common and palindromic substrings in the circuit model. Theor. Comput. Sci. 1065 (2026) 115716. 10.1016\/J.TCS.2025.115716","DOI":"10.1016\/J.TCS.2025.115716"},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"publisher","unstructured":"Simone Faro and Thierry Lecroq. 2013. The exact online string matching problem: A review of the most recent results. ACM Comput. Surv. 45 2 (2013) 13:1\u201313:42. 10.1145\/2431211.2431212","DOI":"10.1145\/2431211.2431212"},{"key":"e_1_3_3_1_15_2","first-page":"148","volume-title":"Prague Stringology Conference 2020, Prague, Czech Republic, August 31 - September 2, 2020","author":"Faro Simone","year":"2020","unstructured":"Simone Faro and Francesco\u00a0Pio Marino. 2020. Reducing Time and Space in Indexed String Matching by Characters Distance Text Sampling. In Prague Stringology Conference 2020, Prague, Czech Republic, August 31 - September 2, 2020, Jan Holub and Jan Zd\u00e1rek (Eds.). Czech Technical University in Prague, Faculty of Information Technology, Department of Theoretical Computer Science, 148\u2013159. http:\/\/www.stringology.org\/event\/2020\/p13.html"},{"key":"e_1_3_3_1_16_2","doi-asserted-by":"publisher","unstructured":"Simone Faro Francesco\u00a0Pio Marino and Arianna Pavone. 2020. Efficient Online String Matching Based on Characters Distance Text Sampling. Algorithmica 82 11 (2020) 3390\u20133412. 10.1007\/S00453-020-00732-4","DOI":"10.1007\/S00453-020-00732-4"},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"publisher","unstructured":"Simone Faro and Arianna Pavone. 2018. An Efficient Skip-Search Approach to Swap Matching. Comput. J. 61 9 (2018) 1351\u20131360. 10.1093\/comjnl\/bxx123","DOI":"10.1093\/comjnl\/bxx123"},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-97-2340-9_21"},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"publisher","unstructured":"Simone Faro Arianna Pavone and Caterina Viola. 2025. Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism. CoRR abs\/2503.05596 (2025). 10.48550\/ARXIV.2503.05596 arXiv:https:\/\/arXiv.org\/abs\/2503.05596","DOI":"10.48550\/ARXIV.2503.05596"},{"key":"e_1_3_3_1_20_2","volume-title":"Fast algorithms for string matching with and without swaps","author":"Fredriksson Kimmo","year":"2000","unstructured":"Kimmo Fredriksson. 2000. Fast algorithms for string matching with and without swaps. Technical Report. Unpublished manuscript, http:\/\/www.cs.uef.fi\/\u00a0fredriks\/pub\/papers\/sm-w-swaps.pdf."},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"publisher","unstructured":"Kimmo Fredriksson and Emanuele Giaquinta. 2014. On a compact encoding of the swap automaton. Inf. Process. Lett. 114 7 (2014) 392\u2013396. 10.1016\/j.ipl.2014.01.004","DOI":"10.1016\/j.ipl.2014.01.004"},{"key":"e_1_3_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. 2017. Quantum Pattern Matching Fast on Average. Algorithmica 77 1 (2017) 16\u201339. 10.1007\/s00453-015-0060-4","DOI":"10.1007\/s00453-015-0060-4"},{"key":"e_1_3_3_1_24_2","doi-asserted-by":"publisher","unstructured":"Pradeep Niroula and Yunseong Nam. 2021. A quantum algorithm for string matching. npj Quantum Information 7 Article number 37 (2021). 10.1038\/s41534-021-00369-3","DOI":"10.1038\/s41534-021-00369-3"}],"event":{"name":"HPDC '26: 35th International Symposium on High-Performance Parallel and Distributed Computing","location":"Cleveland USA","acronym":"HPDC '26","sponsor":["SIGHPC ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing","SIGARCH ACM Special Interest Group on Computer Architecture"]},"container-title":["Proceedings of the 35th International Symposium on High-Performance Parallel and Distributed Computing"],"original-title":[],"deposited":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T04:22:11Z","timestamp":1783743731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3806645.3816165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,13]]},"references-count":23,"alternative-id":["10.1145\/3806645.3816165","10.1145\/3806645"],"URL":"https:\/\/doi.org\/10.1145\/3806645.3816165","relation":{},"subject":[],"published":{"date-parts":[[2026,7,13]]},"assertion":[{"value":"2026-07-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}