  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^2/w)$ time. In a reasonable classical model of computation,
one can assume $w=\Theta(\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-\epsilon})$ or
$O(|P|^{1-\epsilon}|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|\sqrt{|P|})$.
