2023/02/06 by Equi, Massimo, van de Griend, Arianne Meijer -, Mäkinen, Veli
#81P68 #E.1 #E.4 #F.1.3 #F.2.2 #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2302.02848
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(n2/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|)).