2026-07-26T04:38:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17963 2024-03-06T11:00:44Z ddc:004 open_access

From Bit-Parallelism to Quantum String Matching for Labelled Graphs Equi, Massimo Meijer-van de Griend, Arianne Mäkinen, Veli Bit-parallelism quantum computation string matching level DAGs Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor w, where w is the computer word size. A classic example is computing the edit distance of two strings of length n, which can be solved in O(n²/w) time. In a reasonable classical model of computation, one can assume w = Θ(log n), and obtaining significantly better speed-ups is unlikely in the light of conditional lower bounds obtained for such problems. In this paper, we study the connection of bit-parallelism to quantum computation, aiming to see if a bit-parallel algorithm could be converted to a quantum algorithm with better than logarithmic speed-up. We focus on string matching in labeled graphs, the problem of finding an exact occurrence of a string as the label of a path in a graph. This problem admits a quadratic conditional lower bound under a very restricted class of graphs (Equi et al. ICALP 2019), stating that no algorithm in the classical model of computation can solve the problem in time O(|P||E|^(1-ε)) or O(|P|^(1-ε)|E|). We show that a simple bit-parallel algorithm on such restricted family of graphs (level DAGs) can indeed be converted into a realistic quantum algorithm that attains subquadratic time complexity O(|E|√|P|). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Massimo Equi and Arianne Meijer-van de Griend and Veli Mäkinen 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.9 urn:nbn:de:0030-drops-179637 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode