Department of Computer Science, University of Helsinki,
Finlandmassimo.equi@helsinki.fihttps://orcid.org/0000-0001-8609-0040
Department of Computer Science, University of Helsinki,
Finlandarianne.vandegriend@helsinki.fihttps://orcid.org/0000-0001-5946-0958
Department of Computer Science, University of Helsinki,
Finlandveli.makinen@helsinki.fihttps://orcid.org/0000-0003-4454-1493 Massimo
Equi, Arianne Meijer - van de Griend and Veli Mäkinen [500]Theory of
computation Quantum computation theory [500]Theory of computation Parallel
algorithms [500]Theory of computation Pattern matching [500]Theory of
computation Graph algorithms analysis John Q. Open and Joan R. Access 2 42nd
Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December
24–27, 2016 Little Whinging, United Kingdom 42 23

# From Bit-Parallelism to Quantum String Matching for Labelled Graphs

Massimo Equi  Arianne Meijer - van de Griend  Veli Mäkinen

###### Abstract

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 a linear speed-up, with time
complexity $O(|E|+|V|+\sqrt{|P|})$.

###### keywords:

Bit-parallelism, quantum computation, string matching, level DAGs

###### category:

##  1 Introduction

Exact string matching problem is to decide if a pattern string $P$ appears as
a substring of a text string $T$. In the classical models of computation, this
problem can be solved in $O(|P|+|T|)$ time [8]. Different quantum algorithms
for this basic problem have been developed [11, 12, 14], resulting into
different solutions, the best of which finds a match in
$O(\sqrt{|T|}(\log^{2}|T|+\log|P|))$ time [11] with high probability. These
assume the pattern and text are stored in quantum registers, requiring thus
$O(|P|+|T|)$ qubits to function. Moreover, these approaches implicitly assume
that strings of the size of the pattern and the text could fit into a
(quantum) memory word; an assumption that, if dropped, would introduce a
linear dependence with $P$ and $T$ in the time complexity. For example,
Niroula and Nam [11] perform $O(\log(|T|))$ rounds of parallel swaps,
executing $O(|T|)$ swaps in parallel per round.

In the classical models of computation, an analogy for these assumptions is to
assume that the text has been preprocessed for subsequent queries. For
example, one can build a Burrows-Wheeler transform -based index structure for
the text in time $O(|T|)$ [4], assuming $T\in\\{1,2,\ldots,\sigma\\}^{*}$,
where $\sigma\leq|T|$. Then, one can query the pattern from the index in
$O(|P|\log\log\sigma)$ time [4, Theorem 6.2]. In this light, quantum models
can offer only limited benefit over the classical models for exact string
matching.

Motivated by this difficulty in improving linear-time solvable problems using
quantum approaches, let us consider problems known to be solved in quadratic
time. For example, approximate string matching problem is such a problem:
decide if a pattern string $P$ is within edit distance $k$ from a substring of
a text string $T$, where edit distance is the number of single symbol
insertions, deletions, and substitution needed to convert a string to another.
This problem can be solved using _bit-parallelism_ in
$O(\lceil|P|/w\rceil|T|)$ time [9], under the Random Access Memory (RAM) model
with computer word size $w$. A reasonable assumption is that
$w=\Theta(\log|T|)$, so that this model reflects the capacity of classical
computers. Thus, when $|P|=|T|=n$, this bit-parallel algorithm for approximate
string matching takes time at least $\Omega(n^{2-\epsilon})$ for all
$\epsilon>0$, as $\log n=o(n^{\epsilon})$ for all $\epsilon>0$. It is believed
that this quadratic bound cannot be significantly improved, as there is a
matching conditional lower bound saying that if approximate pattern matching
could be solved in time $O(n^{-\epsilon})$ with some $\epsilon>0$, then the
Orthogonal Vector Hypothesis (OVH) and thus the Strong Exponential Time
Hypothesis (SETH) would not hold [2]. As these hypotheses are about classical
models of computation, it is natural to ask if the quadratic barrier could be
broken with quantum computation.

In this quest for breaking the quadratic barrier, we study another problem
with a bit-parallel solution and a conditional lower bound. Consider exact
pattern matching on a graph, that is, consider deciding if a pattern string
$P\in\Sigma^{*}$ equals a labeled path in a graph $G=(V,E)$, where $V$ is the
set of nodes and $E$ is the set of edges. Here we assume the nodes $v$ of the
graph are labeled by $\ell(v)\in\Sigma$ and a path $v_{1}\to v_{2}\to\cdots
v_{t}$, $(v_{i},v_{i+1})\in E$ for $1\leq i<t$, spells string
$\ell(v_{1})\ell(v_{2})\cdots\ell(v_{t})$. There is an OVH lower bound
conditionally refuting an $O(|P||E|^{1-\epsilon}$) or $O(|P|^{1-\epsilon}|E|$)
time solution [6]. This conditional lower bound holds even if graph $G$ is a
_level_ DAG: for every two nodes $v$ and $w$, holds the property that every
path from $v$ to $w$ has the same length. On DAGs, this string matching on
labeled graphs (SMLG) problem can be solved in $O(\lceil|P|/w\rceil|E|)$ time
[13], so the status of this problem is identical to that of approximate
pattern matching on strings. However, the simplicity of the bit-parallel
solution for SMLG on level DAGs enables a connection to quantum computation.
We consider a specific model of quantum computation, the Quantum Random Access
Memory (QRAM) model, in which we have access to “quantum arrays”, and we
assume that integer values like $|P|$, $|V|$ or $|E|$ fit into a (quantum)
memory word. Under this model, we turn the bit-parallel solution into a
quantum algorithm that solves SMLG on level DAGs with high probability in
$O(|E|+|V|+\sqrt{|P|})$ time, breaking through the classical quadratic
conditional lower bound. Observe that in a level DAG the size of pattern is
always smaller than the size of the graph, thus the square-root term is just
to indicate the presence of Grover’s search.

Classical conditional lower bounds are not new to be broken by quantum
computing. For example, the quadratic Orthogonal Vectors problem itself can be
solved in subquadratic time (linear using QRAM) using quantum computing. This
is not the only problem to have a better-than-quadratic solution in the
quantum realm, as explained in this master’s thesis [15]. Nevertheless, to the
best of our knowledge, we are the first to propose a linear time algorithm for
SMLG, even if restricted to a specific class of graphs. Moreover, the
translation of a bit-parallel strategy to a quantum-parallel one is an
original technique, and we are not aware of any other work utilising it.

An earlier work provided a quantum algorithm solving SMLG in time
$O(\sqrt{|V||E|}|P|)$. When the graph is non-sparse, that is
$|V|=O(\sqrt{|E|})$, the time complexity becomes $O(|E|^{\frac{3}{4}}|P|)$,
which is an improvement over classical algorithms. We offer a different kind
of trade-off, limiting ourselves to a special class of graphs, but obtaining a
significantly better time complexity. We also note that, even if no
subquadratic classical algorithm exists for non-sparse graphs, the existing
classical reduction from OV [6] produces a sparse level DAG, for our quantum
algorithm runs in linear time.

As mentioned above, in some previous works [11, 14, 12](and references in
[14]) algorithms have been proposed to solve string matching in plain text in
the QRAM model, under the assumption that the entire text, or at least text
sub-strings of the same length of the pattern, fit into a memory word. We find
this assumption to be too restrictive, as even the classical RAM model does
not adopt it, since in such a model of computation many operations would
become trivial. Instead, our algorithm works without the need for such an
assumption, and has the same time complexity as the previous solutions, if
they are all compared under our QRAM model of computation, This is because,
using our QRAM model, a $O(|P|)$ term would appear in the time complexities of
these previous algorithms.

The paper is structured as follows. We revisit exact pattern matching and
derive a simple quantum algorithm for it, in order to introduce the quantum
machinery. Then we give a brute-force quantum algorithm for SMLG, which we
later improve on level DAGs. This improvement is based on extending the Shift-
And algorithm [3], whose quantum version we extend for level DAGs.

In what follows, we assume the reader is familiar with the basic notions in
quantum computing as covered in textbooks [10].

##  2 Preliminaries

An _alphabet_ $\Sigma$ is a set of _characters_. Throughout the paper we
assume $\Sigma$ is ordered, i.e., for each $a,b\in\Sigma$ we can decide if
$a<b$. A sequence $P\in\Sigma^{n}$ is called a _string_ and its length is
denoted $n=|P|$. We denote integers $i,i+1,\ldots,j$ as interval $[i..j]$ and
represent a string $P$ as an array $P[0..n-1]$, where $P[i]\in\Sigma$ for
$0\leq i\leq n-1$, as in this work all indexes start from $0$. String
$P[i..j]$ is called a _substring_ and string $P[0..i]$ a _prefix_ of $P$. With
bit-vectors discussed next, we use $0$-based indexing.

Let $B$ be a $w$-bit integer interpreted as string $B[0..w-1]$ from alphabet
$\\{0,1\\}$ such that $B=\sum_{i=0}^{w-1}B[i]\cdot 2^{i}$. We call $B$ a _bit-
vector_. Given two bit-vectors $B$ and $C$, we define the following Boolean
operations $A=B\land C$, $O=B\lor C$, and $N=\neg B$ as follows: $A[i]=1$ iff
$B[i]=C[i]=1$, $O[i]=1$ iff $B[i]=1$ or $C[i]=1$, and $N[i]=1$ iff $B[i]=0$.
When bit-vector content is visualized, we list the most significant bit first,
i.e., $B[w-1]B[w-2]\cdots B[0]$. With this in mind, we define the left-shifts
$L=B\ll k$ and right-shifts $R=B\gg k$ as follows: $L[i+k]=B[i]$ and
$R[i]=B[i+k]$. Here values out of the domain of the bit-vectors are assumed to
be $0$. Logarithms are assumed to be in base two: $\log n=\log_{2}n$.

In _directed labelled graph_ (DAG) $G=(V,E,\ell)$, $V$ is the set of nodes,
$E$ is the sets of vertices, and $\ell:V\rightarrow\Sigma$ is a labelling
function that assigns a character of the alphabet to each node. We assume the
nodes to be indexed as $v_{0},v_{1},\ldots v_{n-1}$ in topological order,
where $n=|V|$. For $v_{i}\in V$, $\ell(v_{i})$ is its label. Set of nodes
$in(v_{i})=\\{j\,|\,(v_{j},v_{i})\in E\\}$ contains the indexes of the in-
neighbours of $v_{i}$, and $D_{i}=|in(v_{i})|$ is the in-degree of $v_{i}$.
If, for $0\leq d\leq D_{i}-1$, $v_{k}$ is the $d$-th in-neighbour of $v_{i}$
according to the topological indexing that we defined above, we express this
fact using notation $k=in_{i}(d)$, where
$in_{i}:[0,D_{i}-1]\rightarrow[0,n-1]$.

In this work, we study the problem of _string matching in labelled graphs_ ,
that consists in finding a match for a pattern string $P[1..m]$ in a labelled
graphs $G$ over alphabet $\Sigma$, where $P$ has a _match_ in $G$ if there is
a path $v_{1},\ldots,v_{k}$ such that $P=\ell(v_{1})\cdots\ell(v_{k})$ (we
also say that $P$ _occurs_ in $G$, and that $v_{1},\ldots,v_{k}$ is an
_occurrence_ of $P$). Notice that if $|P|=1$, a classic visit of the graph
solves the problem in linear time, thus we always assume $|P|\geq 2$.

######  Problem 1 (String Matching in Labeled Graphs (SMLG)).

input: A labeled graph $G=(V,E,L)$ and a pattern string $P$, both over an
alphabet $\Sigma$.

output: _True_ if and only if there is at least one occurrence of $P$ in $G$.

##  3 Quantum Notation and Preliminaries

In quantum computing, data is represented in quantum bits (qubits), the
quantum analogue to classical bits. A qubit can be in two states, denoted as
$\ket{0}=$ ($\begin{smallmatrix}1\\\ 0\end{smallmatrix}$) and $\ket{1}=$
($\begin{smallmatrix}0\\\ 1\end{smallmatrix}$) but, unlike a classical bit, it
can also be a linear combination of the two states, a superposition:
$\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$. The complex values $\alpha$ and
$\beta$ are called the amplitudes of $\ket{\psi}$. Measuring a qubit in
superposition will result in either $\ket{0}$ or $\ket{1}$ with probabilities
$|\alpha|^{2}$ and $|\beta|^{2}$, respectively. Note that this notation can
easily be generalised to integer states $\ket{n}$ using the tensor product
between the quantum states of the binary representation on $n$:
$\ket{n}=\bigotimes_{i\in binary(n)}\ket{i}$, and in this case we use the term
_quantum register_. Throughout the paper, we will use notation $\ket{q}_{Q}$
to denote that qubit $Q$ is in state $\ket{q}$. We use lower case letters for
quantum states and capital letters for qubits.

In this work, we mainly use the NOT gate $X$, the controlled NOT $CX$, and the
Toffoli gate $CCX$. We also apply an OR gate, that computes a logical _or_
between two quibits and stores the results in a third quibit. This can easily
be obtained with a simple combination of $X$ gates with a Toffoli gate.

Furthermore, to define some quantum states, we use Kronecker’s delta function
$\delta_{x,y}$, which is $\delta_{x,y}=1$ if $x=y$ and $\delta_{x,y}=0$
otherwise. Given superposition
$\ket{\psi}=\sum_{i=0}^{n-1}\alpha_{i}\ket{i}_{I}\ket{\delta_{c,i}}_{Q}$, the
delta function specifies that qubit $Q$ is in state $\ket{1}$ iff $i=c$, as in
the following example

$\sum_{i=0}^{3}\alpha_{i}\ket{i}_{I}\ket{\delta_{0,i}}_{Q}=\alpha_{0}\ket{0}_{I}\ket{1}_{Q}+\alpha_{1}\ket{1}_{I}\ket{0}_{Q}+\alpha_{2}\ket{2}_{I}\ket{0}_{Q}+\alpha_{3}\ket{3}_{I}\ket{0}_{Q}$

where $I$ is a quantum register of at least two qubits.

We assume to have a _quantum random access memory_ (QRAM) able to use a
quantum register as an index to access classical data. Let
$m_{0},m_{1},\ldots,m_{n-1}$ be the data stored in QRAM $M$. Given quantum
register $I$, the operation that reads data from $M$ into quantum register $Q$
initialized to $\ket{0}$ using $I$ as index is defined as follows [7]:

$\sum_{i=0}^{n-1}\alpha_{i}\ket{i}_{I}\ket{0}_{Q}\xrightarrow{\text{QRAM
read}}\sum_{i=1}^{n}\alpha_{i}\ket{i}_{I}\ket{0\oplus
m_{i}}_{Q}=\sum_{i=1}^{n}\alpha_{i}\ket{i}_{I}\ket{m_{i}}_{Q}.$

Notice that this is a unitary operation, and thus reading the same data into
the same register twice will reset such a register to the value it had before
performing the reading operation. In terms of time complexity, the execution
of the read operation is proportional to the number of qubits in quantum
register $I$. Under the Word-QRAM model with memory-word size $O(\log n)$ for
inputs of size $n$, we can assume to be able to perform a QRAM read operation
in $O(1)$, because $O(\log n)$ qubits are enough for register $I$ to index an
input of size $n$. Indeed, this reflect same assumption of the classical Word-
RAM model, where operations on memory words are assumed to be constant.

##  4 String Matching in Plain Text

A quantum computer, with access to QRAM, can solve the problem of finding an
exact match for a pattern string $P$ into a text string $T$ in time
$O(|P|+\sqrt{|T|})$, with high probability. We explain a simple solution to
this problem. Let $|T|=n$ and $|P|=m$, then $T=t_{0}t_{1}\cdots t_{n-1}$ and
$P=p_{0}p_{1}\cdots p_{m-1}$ are two strings defined over a binary alphabet,
that is $t_{i},p_{j}\in\\{0,1\\}$ for $0\leq i\leq n-1$ and $0\leq j\leq m-1$.
We use qubits $C_{T}$ and $C_{P}$ initialized to $\ket{0}$ to track the
current characters of $T$ and $P$, and we assume to have the text and the
pattern stored in qubits in the following way:

$\ket{0}_{C_{T}}\ket{0}_{C_{P}}\ket{t_{0}}_{T_{0}}\ket{t_{1}}_{T_{1}}\cdots\ket{t_{n-1}}_{T_{n-1}}\ket{p_{0}}_{P_{0}}\ket{p_{1}}_{P_{1}}\cdots\ket{p_{m-1}}_{P_{m-1}}.$

We also use auxiliary qubits $A_{-1},A_{0},A_{1}\cdots A_{m-1}$, and quantum
registers $I$, $J$, and $Q$, all three of $\log n$ qubits. We initialize
$A_{-1}$ and $Q$ to $\ket{1}$, while $A_{0},A_{1}\cdots A_{m-1}$, $I$ and $J$
are all initialized to $\ket{0}$. We prepare quantum register $I$ in an
equally balanced superposition spanning all the text positions, that is
$\ket{0}_{I}\rightarrow 1/\sqrt{n}\sum_{i=0}^{n-1}\ket{i}_{I}$, assuming $n$
to be a power of $2$, without loss of generality. If this is not the case, we
generate a superposition as large as the first power of two greater than $n$,
then standard techniques can be applied to handle the additional substates, as
explained in Appendix A.

Each individual state $\ket{i}$ in the superposition represents a computation
starting at position $i$ in the text. In each of these computations, we scan
$T[i..i+m-1]$ and try to match each character with $P[0..m-1]$, storing the
intermediate results of such comparisons in registers
$A_{0},A_{1},\cdots,A_{m-1}$. More precisely, at iteration $j$, $0\leq j\leq
m-1$, we compute a logical _xor_ between $t_{i+j}$ and $p_{j}$ storing the
result in $C_{P}$ via a $CX$ gate with control $C_{T}$ and target $C_{P}$.
Then, we apply a $X$ gate to $C_{P}$, which now stores
$\ket{\lnot(t_{i+j}\oplus p_{j})}_{C_{P}}=\ket{t_{i+j}=p_{j}}_{C_{P}}$. At
this point, we apply a Toffoli gate with controls $C_{P}$ and $A_{j-1}$,
storing the value in target qubit $A_{j}$. We now reset $C_{T}$ and $C_{P}$ to
$\ket{0}$ by applying to them the same gates again, but in reverse order. As
last step in iteration $j$, we increase both $I$ and $J$ by $1$ by performing
transformation
$\sum_{i=0}^{n-1}\ket{1}_{Q}\ket{i}_{I}\ket{j}_{J}\rightarrow\sum_{i=0}^{n-1}\ket{1}_{Q}\ket{i+1}_{I}\ket{j+1}_{J}$
(this of course requires two separate addition operations), where the addition
is intended to be modulo $2^{n}$. This allows us to read the next character of
the pattern at the next iteration.

After the last iteration, we can run Grover’s operator where the marked items
are represented by $\ket{a_{m-1,i}}_{A_{m-1}}=\ket{1}$, and then measure
register $\ket{I}$ to locate the ending position of a match. Of course, we do
not know the exact number of marked items, and we address this issue by
guessing the number of items and rerunning the whole algorithm a constant
number of times. We illustrate the entire procedure in Algorithm 1.

The algorithm is correct because, after each iteration of the _for_ loop, we
correctly keep track of the positions of the text that are active matches for
the current prefix of the pattern.

######  Lemma 4.1.

After iteration $j$ of the $for$ loop of Algorithm 1, let qubits $I$ and
$A_{j}$ be in superpostion $\sum_{i=0}^{n-1}\ket{i}_{I}\ket{a_{j,i}}_{A_{j}}$.
Then, $\ket{a_{j,i}}_{A_{j}}=\ket{1}$ if and only if $T[i..i+j]=P[0..j]$,
where $0\leq j\leq m-1$ and $0\leq i\leq n-1$.

######  Proof 4.2.

At iteration $0$, after applying gates $CX$ and $X$, $C_{P}$ stores
$\ket{\lnot(T[i]\oplus P[0])}_{C_{P}}$ and $A_{-1}$ stores $\ket{1}_{A_{-1}}$,
thus the Toffoli gate simply copies value $\lnot(T[i]\oplus P[0])$ to $A_{0}$.
Because we are working with a binary alphabet, $\lnot(T[i]\oplus P[0])$ equals
$T[i]=P[0]$, and thus we obtain superposition
$\sum_{i=0}^{n-1}\ket{i}_{I}\ket{T[i]=P[0]}_{A_{0}}$.

At iteration $j$, we assume by induction that register $A_{j-1}$ stores
$\ket{a_{j-1,i}}_{A_{j-1}}=\ket{1}$ if and only if $T[i\ldots i+j-1]=P[0\ldots
j-1]$. Gates $CX$ and $X$ compute $\lnot(T[i+j]\oplus P[j])$ storing it in
$C_{P}$. We then apply the Toffoli gate with controls $C_{P}$ and $A_{j-1}$,
and target $A_{j}$, obtaining superposition
$\sum_{i=0}^{n-1}\ket{i}_{I}\ket{a_{j-1,i}\land T[i+j]=P[j]}_{A_{j}}$. Thus,
$\ket{a_{j,i}}_{A_{j}}=\ket{a_{j-1,i}\land T[i+j]=P[j]}_{A_{j}}$ is $\ket{1}$
if and only if $T[i..i+j]=P[0..j]$.

As mentioned above, we have to be careful in running Grover’s search algorithm
at the end of Algorithm 1. We defer these details to the full proof of Theorem
5.5 given in the appendix. For now, we assume that we are able to retrieve
with arbitrarily high probability $1-(7/8)^{c}$ a marked substate representing
a match. Combining this with Lemma 4.1, we obtain the claimed result.

######  Theorem 4.3.

Given a text string $T$, pattern string $P$ and integer $c>0$, Algorithm 1
finds a match for $P$ in $T$ in time $O(c(|P|+\sqrt{|T|}))$, which is linear
if $c$ is constant. If there is no match, the algorithm returns a negative
answer with probability $p=1$. If there is at least one match, the algorithm
returns the index of the last position of a match with probability
$p>1-(7/8)^{c}$.

######  Proof 4.4.

For the correctness, consider Lemma 4.1 where $j=m=|P|$, which is the number
of times we run the _for_ loop. In this case,
$\ket{a_{|P|,i}}_{A_{|P|}}=\ket{1}$ if and only if
$T[i..i+|P|-1]=P[0..|P|-1]$. Thus, measuring these substates yields a correct
solutions. The details of how to perform such a measurement respecting the
time complexity and probability of success are deferred to the full proof of
Theorem 5.5 in the appendix.

Input: Text $T$ stored as
$\ket{t_{0}}_{T_{0}}\ket{t_{1}}_{T_{1}}\cdots\ket{t_{n-1}}_{T_{n-1}}$, pattern
string $P$ stored as
$\ket{p_{0}}_{P_{0}}\ket{p_{1}}_{P_{1}}\cdots\ket{p_{m-1}}_{P_{m-1}}$, integer
$c$

Output: A position $idx$ of $T$ where a match for $P$ ends, if any

1

2for  _$c$ times_ do

3 Initialize quantum registers $A_{-1},A_{0},A_{1}\cdots A_{m-1}$ as
$\ket{0}_{A_{0}}\ket{0}_{A_{1}}\ket{0}_{A_{m-1}}$;

4

5 Initialize quantum register $A_{-1}$ as $\ket{1}_{A_{-1}}$;

6

7 Initialize quantum register $Q$ as $\ket{1}_{I}$;

8 Initialize quantum register $I$ as $\ket{0}_{I}$;

9 Initialize quantum register $J$ as $\ket{0}_{J}$;

10

// Apply $H^{\otimes\log n}$ to register $I$

11 $\ket{0}_{I}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{i}_{I}$;

12

13 for  _$m$ times_ do

// Read $T[i]$ in $C_{T}$ and $P[j]$ in $C_{P}$ using registers $I$ and $J$ as
indexes

14
$\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{i}_{I}\ket{j}_{J}\ket{0}_{C_{T}}\ket{0}_{C_{P}}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{i}_{I}\ket{j}_{J}\ket{t_{i}}_{C_{T}}\ket{p_{j}}_{C_{P}}$;

15

// Apply $CX$ with control $C_{T}$ and target $C_{P}$

16
$\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}}_{C_{T}}\ket{p_{j}}_{C_{P}}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}}_{C_{T}}\ket{t_{i}\oplus
p_{j}}_{C_{P}}$;

17

// Apply $X$ to $C_{P}$

18 $\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}\oplus
p_{j}}_{C_{P}}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{\lnot(t_{i}\oplus
p_{j})}_{C_{P}}=\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}=p_{j}}_{C_{P}}$;

19

// Apply Toffoli with controls $C_{P}$ and $A_{j-1}$, and target $A_{j}$

20
$\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}=p_{j}}_{C_{P}}\ket{a_{j-1}}_{A_{j-1}}\ket{0}_{A_{j}}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}=p_{j}}_{C_{P}}\ket{a_{j-1}}_{A_{j-1}}\ket{(t_{i}=p_{j})\land
a_{j-1}}_{A_{j}}$;

21

// Reset $C_{T}$ and $C_{P}$ to $\ket{0}$ via uncomputation

22 $\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{\lnot(t_{i}\oplus
p_{j})}_{C_{P}}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}\oplus
p_{j}}_{C_{P}}$;

23

24 $\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}}_{C_{T}}\ket{t_{i}\oplus
p_{j}}_{C_{P}}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{t_{i}}_{C_{T}}\ket{p_{j}}_{C_{P}}$;

25
$\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{i}_{I}\ket{j}_{J}\ket{t_{i}}_{C_{T}}\ket{p_{j}}_{C_{P}}\rightarrow$
$\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{i}_{I}\ket{j}_{J}\ket{t_{i}\oplus
t_{i}}_{C_{T}}\ket{p_{j}\oplus
p_{j}}_{C_{P}}=\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{i}_{I}\ket{j}_{J}\ket{0}_{C_{T}}\ket{0}_{C_{P}}$;

26

// Increment indexes $I$ and $J$

27
$\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{1}_{Q}\ket{i}_{I}\ket{j}_{J}\rightarrow\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{n-1}\ket{1}_{Q}\ket{i\oplus
1}_{I}\ket{j+1}_{J}$;

28

29

30 Choose $K\in[0,|P|]$ uniformly at random;

31 Run Grover’s iterate operator the optimal number of times assuming to have
$K$ solutions, with the marked elements being those such that
$\ket{r_{n-1,j}}_{R_{n-1}}=\ket{1}$;

32 Measure $R_{n-1}$ into classical register $R_{cl}$;

33 if  _$R_{cl}=1$_ then

34 return _$yes$_

35

return _$no$_

Algorithm 1 An algorithm for solving exact string matching in plain text that,
using QRAM, achieves $O(|P|+\sqrt{|T|})$ time complexity. The details of how
to handle Grover’s search at the end are given in Theorem TODO. Figure 1: An
example of the evolution of the superposition after one iteration of Algorithm
1. The first arrow represents the application a $CX$ gate with control $T_{1}$
and target $P_{1}$, and the application of a $X$ gate on $P_{1}$. The second
arrow represents the application of a Toffoli gate with controls $P_{1}$ and
$A_{0}$, and target $A_{1}$. Intuitively, in the first step we are checking
that $T[i+j]=P[j]$; in the second step we combine the result of this check
with the contribution of the previous iteration(s). Characters $A$ and $B$ are
to be considered binary values.

##  5 String Matching in Labeled Graphs

###  5.1 Quantum Brute-force Algorithm for SMLG

In SMLG we are given pattern string $P$ with characters in alphabet $\Sigma$
and a node-labeled graph $G=(V,E)$, with labelling function
$\ell:V\rightarrow\Sigma$. We are asked to find a path (or, actually, a walk)
$\pi=v_{1},v_{2},\ldots,v_{|P|}$ in $G$ such that
$\ell(v_{1})\circ\ell(v_{2})\circ\ldots\circ\ell(v_{|P|})=P$, where $\circ$
denotes string concatenation.

One could try to obtain a quantum algorithm for SMLG by generalizing the idea
we presented for plain text. The idea would be to list all possible paths of
length $|P|$ in the graph, and then mark those ones that are actual matches
for $P$. Unfortunately, the superposition would be as large as there are paths
of length $|P|$, and thus the overall time complexity would be
$O(|P|+\sqrt{|V|^{|P|}})$. Moreover, an adjacency matrix would be needed to
check the existence of edges between nodes in constant time, yielding a space
complexity of $O(|V|^{2})$ qubits. We conclude that more involved techniques
are needed.

###  5.2 The Classical Shift-And Algorithm

We first introduce the classical _shift-and_ algorithm for matching a pattern
against a text and generalize it to work on graphs. Then, we show how the bit-
vector data structure of that algorithm can be represented as a superposition
of a logaritmic number of qubits. This approach allows us to achieve better
performances than the brute force algorithm.

In the shift-and algorithm, we use bit vector $B$ of the same length of
pattern $P$ to represent which of its prefixes are matching the text during
the computation. Assuming integer-alphabet $\Sigma$, we also initialize
bidimensional array $M$ of size $|P|\times|\Sigma|$ so that
$M[j][\mathtt{c}]=1$ if and only if $P[j]=\mathtt{c}$, and
$M[j][\mathtt{c}]=0$ otherwise. The algorithm starts by initializing vector
$B$ to zero and array $M$ as specified above. Then, we scan whole text $T$
performing the next three operations for each $T[i]$, $i\in[0,n-1]$:

  1. 1.

$B\leftarrow B+1$;

  2. 2.

$B\leftarrow B\land B[\mathtt{T[i]}]$;

  3. 3.

if $B[m-1]=1$, return _yes_ ;

  4. 4.

$B\leftarrow B<<1$.

Operation 1 sets the least significant bit of $B$ to $1$, which is needed to
test $P[1]$ against $T[i]$. Operation 2 computes a bit-wise _and_ between $B$
and the column of $M$ corresponding to character $T[i]$. Remember that
$M[j][T[i]]=1$ means $P[j]=T[i]$, thus this operation leaves each bit $B[j]$
set to $1$ if and only if it was already set to $1$ before this step and the
the $j$-th character of the pattern matches the current character of the text.
At this point, if bit $B[m-1]$ is set to 1 we have found a match for $P$, and
Operation 3 will return _yes_. For the other positions, if bit $B[j]$ is set
to $1$, then we know that prefix $P[1\ldots j]$ matches
$T[i-j+1\leavevmode\nobreak\ \ldots\leavevmode\nobreak\ i]$, and Operation 4
shift the bits in $B$ by one position, so that in the next iteration we will
check whether $P[j+1]$ matches $T[i+1]$.

In labeled DAG $G=(V,E)$, each node $v_{i}\in V$ has a single-character label
$\ell(v_{i})$. We generalize the shift-and algorithm to labeled DAGs by
computing a bit-vector $B_{i}$ for each node $v\in V$, initializing them to
zero. Consider a DFS visit of DAG $G$. When visiting node $v_{i}$, each bit-
vector $B_{k}$ of its in-neighbour $v_{k}\in in(v_{i})$ represents a set of
prefixes of $P$ matching a path in the graph ending at $v_{k}$. Thus, we merge
all of this information together by taking the bit-wise _or_ of all of the in-
neighbours of $v_{i}$, that is we replace Operation 1 with $B_{i}\leftarrow
1+\bigvee_{v_{k}\in in(v_{i})}B_{k}$. Operations 2, 3 and 4 are performed as
before. An example of the state of the data structures at a generic iteration
$i$ is shown in Figure 2, and the body of the iteration now is:

  1. 1.

$B_{i}\leftarrow 1+\bigvee_{v_{k}\in in(v)}B_{k}$;

  2. 2.

$B_{i}\leftarrow B_{i}\land M[\mathtt{T[i]}]$;

  3. 3.

if $B_{i}[m-1]=1$, return _yes_ ;

  4. 4.

$B_{i}\leftarrow B_{i}<<1$.

###  5.3 Quantum Bit-Parallel Algorithm for Level DAGs

We make the classic techniques work in a quantum setting for a special class
of DAGs, which we call _level_ DAGs. A level DAG is a DAG such that, for every
two nodes $v$ and $w$, every path from $v$ to $w$ has the same length, as for
the DAG in Figure 2. We also note that _degenerate strings_ [1] can be
represented as level DAGs.

Figure 2: The adaptation of the classical algorithm for matching pattern $P$
in _level_ DAG $G$. Each bit-vector $D_{v}$ represent the result after the
merging of the bit-vectors of the in-neighbours of $v$ and before the
shifting.

We use a function representing in-neighbours:

$in_{i}(d)=\text{index of the }d\text{-th in-neighbour}\text{ of }v_{i}$

Our approach aims to represent each bit vector $B_{i}$ with a single qubit
$V_{i}$ set up in a proper superposition, and translate the bit-wise
operations to parallel operations across such superposition. In the algorithm,
we use the following qubits and quantum registers. Quantum registers $I$ and
$J$ store the index of a node and the position in the pattern, respectively.
Qubit $V_{i}$ represents, in superposition, the bit-vector of the node
$v_{i}$, and qubit $E_{i,d}$ stores the contribution of edge
$(v_{in_{i}(d)},v_{i})\in E$ in the update of qubit $V_{i}$, for, $0\leq i\leq
n-1$, $0\leq d\leq D_{i}-1$ and $D_{i}=indeg(v_{i})$. Quantum register $C$
stores label $\ell(v_{i})$ of the node in the current iteration, and is used
to fetch the content of the corresponding matrix column, which we will store
in qubit $M$. Occurrences of the pattern encountered during the execution of
the algorithm are stored in qubit $R_{i}$. Qubits $V_{i}^{\prime}$ and
$R_{i}^{\prime}$ are auxiliary qubits used to store intermidiate results, and
we also use auxiliary qubits $A$ and $B$ and auxiliary quantum register $Q$ to
implement necessary operations. Moreover, we assume to have access to QRAM.

####  5.3.1 The algorithm

Assume all the quantum registers and qubits to be initialized to $\ket{0}$,
except $Q$ initialized to $\ket{1}$. The algorithm starts by setting quantum
register J in a balanced superposition, by applying the Hadamard gate on each
one of its qubits. Then, we initialize qubits $A$ so that
$\ket{a_{j}}_{A}=\ket{1}$ for $j=0$, and $\ket{a_{j}}_{A}=\ket{0}$ otherwise.
We do the same with qubit $B$, with the difference that
$\ket{b_{j}}_{A}=\ket{1}$ for $j=m-1$, and $\ket{b_{j}}_{A}=\ket{0}$
otherwise. We can do these operations with two applications of a generalized
Toffoli gate, using register $J$ as control and qubits $A$ and then $B$ as
targets. In the case of qubit $A$, we first apply an $X$ gate to every qubit
of register $J$, we then apply the Toffoli gate, and finally we undo the
applications of the $X$ gate. The generalised Toffoli has a cost proportional
to the number of qubits in $J$, that is logarithmic in the size of the input,
and because this is an operation between a single quantum register and a
qubit, we can assume it to be constant in the Word-QRAM model. We then
initialize the qubits representing the bit-vectors of the nodes at level $0$.
This is done with the same operations described below for the main loop, the
only difference being that these nodes do not have in-neighbours and thus we
can simplify some operations. Specifically, we load each entry of the
character matrix in superposition and we use it and qubit $A$ as controls of a
Toffoli gate which thus flips to $\ket{1}$ sub-state $\ket{v_{i,j}}_{V_{i}}$
if $P[0]$ matches $\ell(v_{i})$.

The rest of the algorithm maintains almost the same overall structure, with
the exception of one necessary adaptation. In a DAG of $L$ levels where
$L_{l}$ is the set of nodes at level $l$, for $0\leq l\leq L-1$, we iterate
over them one at the time, and for each level we process its nodes one after
the other. As we will better explain later, we wait before applying the
quantum equivalent of the shift operation once we scanned the whole level, not
after processing every node. The overall idea is to translate the classical
bit-parallel operations into analogous quantum operations that work across the
superposition. This translation of bit-parallelism to superposition
parallelism is the core of our technique, and we now describe how to apply it
to each operation. The pseudocode of the entire procedure is given in
Algorithm 2, where all the arithmetic operations are to be considere modulo
$2^{|P|}$. We only omit the pseudocode for procedures SourceNodesInit(),
IncreaseI() and IncreaseJ(), which is to be found in Appendix B. We also
assume $|P|$ to be a power of two. If this is not the case, we generate a
superposition as larger as the first power of two greater than $|P|$, then
standard techniques can be used to handle the additional substates, as
explained in Appendix A.

We present a technique to always reduce to this case in the appendix.

Operation 1 (line 2) can be broken down into two simpler operations: computing
the bit-wise $or$ and adding $1$. In our translation to quantum computing,
each sub-state of superposition
$\sum_{j=0}^{m-1}\ket{j}_{J}\ket{v_{i,j}}_{V_{i}}$ represents an entry of the
classical bit-vector used in the Shift-And algorithm. Thus, what was a bit-
wise $or$ is now easily translated into the application of few quantum gates.
Notice that, to compute the logical $or$ between two generic qubits $P$ and
$Q$ and store the result in qubit $R$, we can follow De Morgan’s rules and
apply an $X$ gate to both $P$ and $Q$, apply a Toffoli gate with controls $P$
and $Q$ and target $R$, apply an $X$ gate to $R$, and finally apply an $X$
gate to $P$ and $Q$ again to restore their initial values. In our case, at
iteration $i$, we use qubit $E_{i,d}$ to store the $or$ computed among in-
neighbours $v_{in_{i}(0)},\ldots,v_{in_{i}(d)}$ of node $v_{i}$, and we
compute it in the following way. Let

$\sum_{j=0}^{m-1}\ket{j}_{J}\ket{v_{in_{i}(0),j}}_{V_{in_{i}(d-1)}}\ket{v_{in_{i}(1),j}}_{V_{in_{i}(1)}}\cdots\ket{v_{in_{i}(d-1),j}}_{V_{in_{i}(D_{i}-1)}}\ket{e_{i,d-1,j}}_{E_{i,d-1}}$

be such that

$e_{i,d-1,j}=v_{in_{i}(0),j}\lor v_{in_{i}(1),j}\cdots\lor v_{in_{i}(d-1),j}.$

where $D_{i}$ is the number of in-neighbours of node $v_{i}$. We compute the
value of $E_{i,d}$ from $E_{i,d-1}$ and $V_{in_{i}(d)}$ as

$\displaystyle\sum_{j=0}^{m-1}\ket{j}_{J}\ket{v_{in_{i}(d),j}}_{V_{in_{i}(d)}}\ket{e_{i,d-1,j}}_{E_{i,d-1}}\ket{0}_{E_{i,d}}\rightarrow$
$\displaystyle\sum_{j=0}^{m-1}\ket{j}_{J}\ket{v_{in_{i}(d),j}}_{V_{in_{i}(d)}}\ket{e_{i,d-1,j}}_{E_{i,d-1}}\ket{v_{in_{i}(d),j}\lor
e_{i,d-1,j}}_{E_{i,d}}.$

Once we processed the last in-neighbour, $E_{i,D_{i}-1}$ stores the $or$
computed among all in-neighbours.

We implement the classic operation of adding $1$ by computing an $or$ with
qubit $A$ and storing the result in $V^{\prime}_{i}$. Since
$\ket{a_{j}}_{A}=\ket{\delta_{0,j}}$, we obtain
$\ket{0}_{V^{\prime}_{i}}\rightarrow\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}$
where $\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}=\ket{1}$ for $j=0$, while
$\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}=\ket{e_{i,D_{i}-1,j}}$ for $1\leq
j\leq m-1$.

Operation 2 (line 2) is implemented as a Toffoli-gate application with qubits
$M$ and $V^{\prime}_{i}$ as control and $V_{i}$ as target.

$\sum\limits_{j=0}^{m-1}\ket{m_{j,\ell(v_{i})}}_{M}\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}\ket{0}_{V_{i}}\rightarrow\ket{m_{j,\ell(v_{i})}}_{M}\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}\ket{m_{j,\ell(v_{i})}\land
v^{\prime}_{i,j}}_{V_{i}}$

Operation 3 (line 2) is replaced by storing in register $R_{i}$ the presence
of a match ending at node $v_{i}$. This requires an intermediate step in which
we use qubit $B$ to filter the content of $V_{i}$. In fact, qubit $V_{i}$ now
is in state $\ket{v_{i,j}}_{V_{i}}=\ket{1}$ for those values of $j$ such that
$P[0..j]$ has a match ending at $v_{i}$ in the graph, and
$\ket{v_{i,j}}_{V_{i}}=\ket{0}$ otherwise. Since we only care about potential
full matches represented by $\ket{v_{i,m-1}}_{V_{i}}$, we use $B$, which is in
state $\ket{\delta_{m-1,j}}_{B}$, as control qubit of a Toffoli gate, the
other control qubit being $V_{i}$ and the target qubit being $R^{\prime}_{i}$.
Then, using the same technique as before, we compute and $or$ between
$R^{\prime}_{i}$ and $R_{i-1}$, storing the result in $R_{i}$.

$\sum\limits_{j=0}^{m-1}\ket{v_{i,j}}_{V_{i}}\ket{\delta_{m-1,j}}_{B}\ket{0}_{R^{\prime}_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{v_{i,j}}_{V_{i}}\ket{\delta_{m-1,j}}_{B}\ket{v_{i,j}\land\delta_{m-1,j}}_{R^{\prime}_{i}}$

Then, using the same technique as before, we compute and $or$ between
$R^{\prime}_{i}$ and $R_{i-1}$, storing the result in $R_{i}$.

$\displaystyle\sum\limits_{j=0}^{m-1}\ket{v_{i,j}\land\delta_{m-1,j}}_{R^{\prime}_{i}}\ket{r_{i-1,j}}_{R_{i-1}}\ket{0}_{R_{i}}\rightarrow$
$\displaystyle\sum\limits_{j=0}^{m-1}\ket{v_{i,j}\land\delta_{m-1,j}}_{R^{\prime}_{i}}\ket{r_{i-1,j}}_{R_{i-1}}\ket{(v_{i,j}\land\delta_{m-1,j})\lor
r_{i-1,j}}_{R_{i}}$

After this operation, $\ket{r_{i,m-1}}_{R_{i}}$ is turned to $\ket{1}$ if
there is a full match of $P$ ending at $v_{i}$, otherwise
$\ket{r_{i,m-1}}_{R_{i}}$ is left unaltered.

Operation 4 (line 2) consists in shifting all bits of the classical bit-vector
by one position. In the quantum setting, we can perform this operation by
adding $1$ to index register $J$ and then reorganising the sum:
$\ket{1}_{C_{\texttt{1}}}\ket{j}_{J}\rightarrow\ket{1}_{C_{\texttt{1}}}\ket{j+1}_{J}$.
Notice that this changes value $\ket{j}_{J}$ in every term of the
superposition to $\ket{j+1}_{j}$. This can be interpreted as “shifting” value
$k_{j}$ of generic register $K$ from $\ket{j}_{J}\ket{k_{j}}_{K}$ to
$\ket{j+1}_{J}\ket{k_{j}}_{K}$. Because this operation acts on every quantum
register and qubit in this way, we have to reset qubits $A$ and $B$ to
$\ket{0}$ before performing this operation and reinitialize their values
afterwards, so that we prevent their values to be shifted. For the same
reason, we also have to wait until having processed the whole level, otherwise
we would shift the values of all the nodes at the previous level and
compromise the computation.

As last step of the algorithm, we run Grover’s search that uses as oracle
function an identity function returning the value of register $R$. Thus, if
there $\ket{r_{i,j}}_{R_{i}}=\ket{1}$ for at least one value of $j$ in $0\leq
j\leq m-1$, then the measurement at the end of the search will return
$R_{i}=\ket{1}$ with high probability. Otherwise, if for every $j$ holds that
$\ket{r_{i,j}}_{R_{i}}=\ket{0}$, than the measurement of Grover’s search will
yield $R_{i}=\ket{0}$. Algorithm 2 shows the entire procedure.

1

Input: Graph $G$, pattern $P$, and constant $c$.

Output: Returns $yes$ if $P$ occurs in $G$, otherwise $no$.

2 for  _$c$ times_ do

3 Initialize quantum register $Q$ to $\ket{1}$;

4 Initialize quantum registers
$I,J,A,B,C,M,V_{i},V^{\prime}_{i},R_{i},R^{\prime}_{i},E_{i,d}\,$ to $\ket{0}$
where $i\in[0,n-1]$ and $d\in[0,\delta_{i}-1]$;

5

// Apply Hadamard to $J$

6 $\ket{0}_{J}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}$;

7

8
SourceNodesInit(_$I,J,A,C,V_{0},\ldots,V_{n-1},V^{\prime}_{0},\ldots,V^{\prime}_{n-1}$_);

9 IncreaseJ(_$J,A,B$_);

// $L$ is the number of levels

10 for  _$l\in[1,L-1]$_ do // scan every level

11 for  _$|L_{l}|$ times_ do // scan every node in the level

12 OperationOne(_$l,I,C,M,E_{i,0},\ldots,E_{i,D_{i}-1},V^{\prime}_{i}$_);

13 OperationTwo(_$M,V^{\prime}_{i},V_{i}$_);

// Invariant 1 holds here

14 OperationThree(_$B,V_{i},R^{\prime}_{i},R_{i}$_);

15 IncreaseI(_$I,M,C$_);

16

17 OperationFour(_$J,A,B$_);

// Invariant 2 holds here

18

19

20 Choose $K\in[0,|P|]$ uniformly at random;

21 Run Grover’s iterate operator the optimal number of times assuming to have
$K$ solutions, with the marked elements being those such that
$\ket{r_{n-1,j}}_{R_{n-1}}=\ket{1}$;

22 Measure $R_{n-1}$ into classical register $R_{cl}$;

23 if  _$R_{cl}=1$_ then

24 return _$yes$_

25

return _$no$_

Algorithm 2 Algorithm for testing whether pattern string $P$ has a match in
level DAG $G$, running in $O(|E|+\sqrt{|P|})$ time.

1

2

3Function
_OperationOne(_$l,I,C,M,E_{i,0},\ldots,E_{i,D_{i}-1},V^{\prime}_{i}$_)_:

4 for  _$|L_{l}|$ times_ do // scan every node in the level

// scan every node in $in(v_{i})$

5
$\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{0}_{C}\rightarrow\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{\ell(v_{i})}_{C};$
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{0}_{M}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{m_{\ell(v_{i}),j}}_{M}$;

6

$k\leftarrow in_{i}(0)$;

// Classical operation

7
$\sum\limits_{j=0}^{m-1}\ket{v_{k,j}}_{V_{k}}\ket{0}_{E_{i,0}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{v_{k,j}}_{V_{k}}\ket{v_{k,j}}_{E_{i,0}}$;

8

9 for  _$d\in[1,D_{i}-1]$_ do // scan every node in $in(v_{i})$

10

$k\leftarrow in_{i}(d)$;

// Classical operation

// Add the contribution of the current in-neighbour

11
$\sum\limits_{j=0}^{m-1}\ket{v_{k,j}}_{V_{k}}\ket{e_{i,d-1,j}}_{E_{i,d-1}}\ket{0}_{E_{i,d}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{v_{k,j}}_{V_{k}}\ket{e_{i,d-1,j}}_{E_{i,d-1}}\ket{e_{i,d-1,j}\lor
v_{k,j}}_{E_{i,d}}$;

12

// Turn to $\ket{1}$ the substate corresponding to $j=0$

13 $\sum\limits_{j=0}^{m-1}\ket{\delta_{0,j}}_{A}\ket{e_{i,D_{i}-1,j}\lor
v_{k,j}}_{E_{i,D_{i}-1}}\ket{0}_{V^{\prime}_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{\delta_{0,j}}_{A}\ket{e_{i,D_{i}-1,j}\lor
v_{k,j}}_{E_{i,D_{i}-1}}\ket{e_{i,D_{i}-1,j}\lor
v_{k,j}\lor\delta_{0,j}}_{V^{\prime}_{i}}$;

14

15

16
Function  _OperationTwo(_$M,V^{\prime}_{i},V_{i}$_)_:

// Compute the $and$ with the column of the matrix

17
$\sum\limits_{j=0}^{m-1}\ket{m_{\ell(v_{i}),j}}_{M}\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}\ket{0}_{V_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{m_{\ell(v_{i}),j}}_{M}\ket{v^{\prime}_{i,j}}_{V^{\prime}_{i}}\ket{m_{\ell(v_{i}),j}\land
v^{\prime}_{i,j}}_{V_{i}}$;

18

19
Function  _OperationThree(_$B,V_{i},R^{\prime}_{i},R_{i}$_)_:

// Set $\ket{r_{i,m-1}}_{R_{i}}=\ket{1}$ if there is a match ending at $v_{i}$

// Apply Toffoli on $V_{i}$, $B$ and $R^{\prime}_{i}$

20
$\sum\limits_{j=0}^{m-1}\ket{v_{i,j}}_{V_{i}}\ket{\delta_{m-1,j}}_{B}\ket{0}_{R^{\prime}_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{v_{i,j}}_{V_{i}}\ket{\delta_{m-1,j}}_{B}\ket{v_{i,j}\land\delta_{m-1,j}}_{R^{\prime}_{i}}$;

21

// Apply logic $or$ on $R^{\prime}_{i}$, $R_{i-1}$ and $R_{i}$

22
$\sum\limits_{j=0}^{m-1}\ket{v_{i,j}\land\delta_{m-1,j}}_{R^{\prime}_{i}}\ket{r_{i-1,j}}_{R_{i-1}}\ket{0}_{R_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{v_{i,j}\land\delta_{m-1,j}}_{R^{\prime}_{i}}\ket{r_{i-1,j}}_{R_{i-1}}\ket{(v_{i,j}\land\delta_{m-1,j})\lor
r_{i-1,j}}_{R_{i}}$;

23

1

2

3Function  _OperationFour(_$J,A,B$_)_:

4 IncreaseJ(_$J,A,B$_);

5

6

To prove the correctness of Algorithm 2, we formalise the key properties in
the following lemmas. We start by ensuring that the shift operation provides
the desired result.

Let $l$ and $y$ be the total number of times that we started the execution of
the middle _for_ -loop (lines 2-2) and of the outer _for_ -loop (lines 2-2),
respectively. That is, $y=x+\sum_{\lambda=1}^{l-1}|L_{\lambda}|$ for $l\geq
2$, where $x\in[0,|L_{l}|]$ is the number of times that we started the
execution of the middle _for_ -loop during the $l$-th iteration of the outer
_for_ -loop. Notice that $y=0$ when $l=0$, and $y=x$ when $l=1$.

######  Lemma 5.1 (_Invariant 1_).

During the $l$-th execution of the outer _for_ -loop (lines 2-2) and the
$y$-th execution of the middle _for_ -loop (lines 2-2) of Algorithm 2, but
before the $y$-th execution of OperationThree() (line 2), _Invariant 1_ holds:
for every qubit $V_{i}$ such that $i\in L_{l}$ and $i\leq t$, we have substate
$\ket{v_{i,j}}_{V_{i}}=\ket{1}$ if and only if there exists a path in $G$
ending at $v_{i}$ and matching $P[0,j]$, where $t=|L_{0}|+x-1$ is the index of
the last node $v_{t}$ Algorithm 2 visited so far.

######  Proof 5.2.

We proceed by strong induction on $y$, defined as above.

Base case, $y=0$. In this case, we executed the initialization but we have not
run yet neither the outer nor the middle _for_ -loop. Thus, $l=0$,
$t=|L_{0}|-1$, and qubits $V_{i}$ such that $i\in L_{0}$ and $i\leq t$ are
those with in-degree zero, which are initialized by function
SourceNodesInit(). For each such $i$, given that $J$ is in state
$\sum_{j=0}^{m-1}\ket{j}_{J}$, function SourceNodesInit() first loads
character $\ell(v_{i})$ in register $C$ and matrix entry $m_{\ell(v_{i}),j}$
in register $M$, in superposition. Then, with regard to $t$, it performs
transformation

$\sum\limits_{j=0}^{m-1}\ket{m_{\ell(v_{i}),j}}_{M}\ket{\delta_{0,j}}_{A}\ket{0}_{V_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{m_{\ell(v_{i}),j}}_{M}\ket{\delta_{0,j}}_{A}\ket{m_{\ell(v_{i}),j}\land\delta_{0,j}}_{V_{i}},$

where, by definition, $v_{t,j}=m_{\ell(v_{i}),j}\land\delta_{0,j}$. Thus,
$\ket{v_{t,j}}=\ket{0}$ for every $j\neq 0$ because of $\delta_{0,j}$, and
$\ket{v_{t,j}}_{V_{i}}=\ket{m_{\ell(v_{i}),j}}_{V_{i}}$ for $j=0$, which in
turn means that $\ket{v_{t,0}}_{V_{i}}=\ket{1}$ if and only if
$P[0,0]=\ell(v_{i})$.

Inductive case, $y\geq 1$. We further divide our analysis in two sub-cases.

First sub-case, $x=|L_{l}|$. In this case, $y$ is the last iteration of the
inner _for_ -loop during the $l$-th iteration of the outer _for_ -loop. We
assume the inductive hypothesis to hold after the execution of OperationTwo().
We execute OperationThree() and IncreaseI(), which do not change the state of
any $V_{z}$, for any $z\in[0,|V|-1]$. Now, we have to perform OperationFour()
(line 2) before starting iteration $y+1$ of the middle _for_ -loop, which will
start iteration $l+1$ of the outer _for_ -loop. Assuming the inductive
hypothesis, the application of OperationFour() makes every $V_{z}$ with $z\in
L_{l}$ such that
$\ket{j^{\prime}}_{J}\ket{v_{z,j}}_{V_{z}}=\ket{j^{\prime}}\ket{1}$, where
$j^{\prime}=j+1$, if and only if there is a match for $P[0,j]$ in $G$ ending
at $v_{z}$, otherwise
$\ket{j^{\prime}}_{J}\ket{v_{z,j}}_{V_{z}}=\ket{j^{\prime}}\ket{0}$. Then, we
start iteration $y+1$ ($l+1$). Notice that we update $V_{i}$ if and only if
$i\in L_{l+1}$ and, in any previous iteration of the middle _for_ -loop, this
could have never been the case, thus every $\ket{v_{i,j}}_{V_{i}}$, $i\in
L_{l+1}$, is currently set to $\ket{0}$. The same holds for every
$V^{\prime}_{i}$. The _for_ -loop inside OperationOne() computes a logic $or$
between all the qubits representing all the in-neighbours of $v_{i}$. Indeed,
before running this _for_ -loop, we have
$\ket{j^{\prime}}_{J}\ket{v_{in_{i}(0),j}}_{E_{i,0}}$. After one iteration, we
have $\ket{j^{\prime}}\ket{v_{in_{i}(0),j}\lor v_{in_{i}(1),j}}_{E_{i,1}}$.
After two iteration, we have $\ket{j^{\prime}}\ket{v_{in_{i}(0),j}\lor
v_{in_{i}(1),j}\lor v_{in_{i}(2),j}}_{E_{i,2}}$. After $D_{i}-1$ iterations,
we have $\ket{j^{\prime}}\ket{e_{i,D_{i}-1,j^{\prime}}}_{E_{i,D_{i}-1}}$,
where

$e_{i,D_{i}-1,j^{\prime}}=\bigvee_{d=0}^{D_{i}-1}v_{in_{i}(d),j}.$

We store an intermediate result in $V^{\prime}_{i}$,
$\ket{v^{\prime}_{i,j^{\prime}}}_{V^{\prime}_{i}}$, where
$v^{\prime}_{i,j^{\prime}}=e_{i,D_{i}-1,j^{\prime}}$ except for
$j^{\prime}=0$, because we make sure that
$\ket{v^{\prime}_{i,0}}_{V^{\prime}_{i}}=\ket{1}$ thanks to the $or$ operation
with qubit $A$, which stores $\ket{\delta_{0,j^{\prime}}}_{A}$. Now we compute
the logical $and$ with the entry of the matrix, as in the base case, obtaining
$\ket{v_{i,j^{\prime}}}_{V_{i}}$, where

$v_{i,j^{\prime}}=m_{\ell(v_{i}),j^{\prime}}\land(\delta_{0,j^{\prime}}\lor\bigvee_{d=0}^{D_{i}-1}v_{in_{i}(d),j}).$

Applying the inductive hypothesis, this translates to

$\displaystyle v_{i,j+1}$
$\displaystyle=(P[j+1]=\ell(v_{i}))\land\left((j+1=0)\lor\bigvee_{d=0}^{D_{i}-1}P[0..j]\text{
has a match ending at }v_{in_{i}(d)}\right)$ $\displaystyle=P[0..j+1]\text{
has a match ending at }v_{i}$

Thus, the statement of the lemma holds for $y+1$.

Second sub-case, $x<|L_{l}|$. The reasoning is analogous to the previous case,
the only difference being that $j$ does not increase and thus we have to look
back by $x+1$ iterations, when $j$ was increased the last time. This requires
to assume that the inductive hypothesis was holding for iteration $y-x$, that
is correct because, by strong induction, we assume the inductive hypothesis to
hold for every $y^{\prime}\leq y$ while proving the statement for $y+1$.

######  Lemma 5.3 (_Invariant 2_).

After line 2 of Algorithm 2, _Invariant 2_ holds: if there exists at least one
match for $P$ in $G$ ending at some $v_{i}$ such that $i\leq t$, then there
exists at least one $j$, $0\leq j\leq m-1$, such that
$\ket{r_{t,j}}_{R_{i}}=\ket{1}$, where $v_{t}$ is the last node we visited in
Algorithm 2 before line 2.

######  Proof 5.4.

We proceed by induction on the number $l$ of times that we run the _for_ -loop
at lines 2-2.

Base case, $l=0$. In this case, nodes $v_{t}$ such that $t\in L_{l^{\prime}}$,
$l^{\prime}\leq 0$ are those with in-degree zero, while the _for_ -loop at
lines 2-2 has never run. Since we are visiting only single-node paths and we
are assuming that pattern $P$ has length at least two, there can be no match
for $P$ ending at these nodes. Correctly, $\ket{r_{i,j}}_{R_{i}}=\ket{0}$ for
every $0\leq j\leq m-1$.

Inductive case, $1\leq l\leq L-1$. By inductive hypothesis, we assume the
statement of the lemma to be true right after running iteration $l$ of the
_for_ -loop at lines 2-2, and thus right before executing IncreaseJ() at line
2. After the execution of IncreaseJ(), the new state is
$\sum_{j=0}^{m-1}\ket{j^{\prime}}_{J}\ket{r_{i,j}}_{R_{i}}$, where
$j^{\prime}=j+1$ and $v_{i}$ is the last node visited so far. Then, we start
iteration $l+1$, processing $i^{\prime}\in L_{l+1}$, $i^{\prime}=t+1$. We
execute OperationOne() OperationTwo(), which do not affect register
$R_{i^{\prime}}$. Then we run the operations at lines 2-2, obtaining
$\ket{r_{i^{\prime},j^{\prime}}}_{R_{i}}$ where
$r_{i^{\prime},j^{\prime}}=(v_{i^{\prime},j^{\prime}}\land\delta_{m-1,j^{\prime}})\lor
r_{t,j}$. Let us consider the first time we run the middle _for_ -loop during
iteration $l+1$ of the outer _for_ -loop. If $P$ has a match ending at some
$v_{z}$, $z<i^{\prime}$, the inductive hypothesis guarantees $r_{t,j}=1$ for
some $j$. Otherwise, if $P$ does not have any such match, then $r_{t,j}=0$ for
all $j$. In this second case, if $P$ has a match ending at $v_{i^{\prime}}$,
we know by Lemma 5.1 that $v_{i^{\prime},m-1}=1$. This, combined with the fact
that $\delta_{m-1,m-1}=1$, correctly implies that $r_{i^{\prime},m-1}=1$,
proving the statement for this specific $i^{\prime}$ and $j^{\prime}=m-1$. If
$P$ has no match ending at $v_{i^{\prime}}$, then $v_{i^{\prime},m-1}=0$, and
$r_{i^{\prime},j^{\prime}}=0$ for all $j^{\prime}$, which must be the case
when no match has been found yet. To conclude the proof, notice that the same
reasoning applies for the subsequent iterations of the middle _for_ -loop by
using every time the previous instance of this reasoning in place of the
inductive hypothesis. That is, we use $r_{i^{\prime},j^{\prime}}$ when proving
the statement for $r_{i^{\prime}+1,j^{\prime}}$ and so on, until we prove the
statement for $r_{t^{\prime},j^{\prime}}$, where $v_{t^{\prime}}$ is the last
node with index in $L_{l+1}$. At this point, we exit the middle _for_ -loop
and the statement of the lemma is proven for $l+1$.

The correctness of the algorithm follows from the previous lemma combined with
few additional observations.

######  Theorem 5.5.

Given pattern string $P$ of length at least $2$ and level DAG $G$, Algorithm 2
returns the right answer for the SMLG problem on $P$ and $G$ with probability
$p>1-(7/8)^{c}$, for any given integer $c$.

######  Proof 5.6.

After running the outer _for_ -loop of Algorithm 2 $L-1$ times, we exit such a
loop, and we know we have visited all the nodes (nodes in $L_{0}$ where
visited during the initialization). If we consider Lemma 5.3 applied in the
case of $t=n-1$, we are considering all the nodes, which means that if $P$ has
no match ending in $G$, then no substate of register $R_{n-1}$ is such that
$\ket{r_{n-1,j}}_{R_{n-1}}=\ket{1}$, for any $j$. Instead, if $P$ has a match
in $G$, then at least one substate of $R_{n-1}$ is such that
$\ket{r_{n-1,j}}_{R_{n-1}}=\ket{1}$, for some $j$.

We use standard techniques that consist in rerunning the algorithm a constant
number of times to boost the probability of success and achieve the desired
one. The appendix provide a more detailed analysis.

Finally, the time complexity of our algorithm is linear in the size of the
graph.

######  Theorem 5.7.

The time complexity of Algorithm 2 is $O(|E|+|V|+\sqrt{|P|})$ in the QRAM
model, and the space complexity is $O(|E|+|V|)$.

######  Proof 5.8.

The algorithm uses $|V|$ qubits $V_{i}$, and the same amount of qubits
$V^{\prime}_{i}$, $R_{i}$, $R^{\prime}_{i}$; qubits $E_{i,d}$ are a total of
$|E|$ qubits, and the rest are a constant number of qubits and registers.
Thus, the space complexity is $O(|E|+|V|)$.

With the _for_ -loop in function SourceNodesInit(), the algorithm visits the
nodes in $L_{0}$, which are at most $O(|V|)$. The iteration conditions at
lines 2 and 2 make the algorithm visit every node. For each such iteration, we
perform a constant number of operations except for the _for_ -loop in
OperationOne(). This _for_ -loop visits all the in-neighbours of a node, each
time performing a constant number of operations, and
$\sum_{i=0}^{|V|-1}|in(i)|=|E|$. All of the aforementioned operations can be
implemented with a constant number of quantum-gate applications, each
affecting a constant number of qubits ($3$ at most), or by performing a load
operation from the QRAM, assumed to require constant time. At the end of the
algorithm, after operation DoubleSuperposition(), we run the quantum-counting
procedure on a superposition of $2|P|$ states.

Summing everything up, we spend $O(|V|)$ time for the initialization,
$O(|V|+|E|)$ time in the _for_ -loops, and $O(\sqrt{|P|})$ time for quantum
counting. The total time complexity is thus $O(|E|+|V|+\sqrt{|P|})$.

## References

  * [1] Mai Alzamel, Lorraine A. K. Ayad, Giulia Bernardini, Roberto Grossi, Costas S. Iliopoulos, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone.  Comparing degenerate strings.  Fundam. Informaticae, 175(1-4):41–58, 2020.
  * [2] Arturs Backurs and Piotr Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  SIAM J. Comput., 47(3):1087–1097, 2018.  doi:10.1137/15M1053128.
  * [3] Ricardo A. Baeza-Yates and Gaston H. Gonnet.  A new approach to text searching.  Commun. ACM, 35(10):74–82, 1992.  doi:10.1145/135239.135243.
  * [4] Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, and Veli Mäkinen.  Linear-time string indexing and analysis in small space.  ACM Trans. Algorithms, 16(2), March 2020.  doi:10.1145/3381417.
  * [5] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik: Progress of Physics, 46(4-5):493–505, 1998\.
  * [6] Massimo Equi, Roberto Grossi, Veli Mäkinen, and Alexandru I. Tomescu.  On the complexity of string matching for graphs.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 55:1–55:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [7] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Quantum random access memory.  Physical review letters, 100(16):160501, 2008.
  * [8] Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt.  Fast pattern matching in strings.  SIAM J. Comput., 6(2):323–350, 1977.  doi:10.1137/0206024.
  * [9] Gene Myers.  A fast bit-vector algorithm for approximate string matching based on dynamic programming.  J. ACM, 46(3):395–415, 1999.  doi:10.1145/316542.316550.
  * [10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.  doi:10.1017/CBO9780511976667.
  * [11] Pradeep Niroula and Yunseong Nam.  A quantum algorithm for string matching.  npj Quantum Information, 7(1):1–5, 2021.
  * [12] Hariharan Ramesh and V Vinay.  String matching in o(n+m) quantum time.  Journal of Discrete Algorithms, 1(1):103–110, 2003.  Combinatorial Algorithms.  URL: https://www.sciencedirect.com/science/article/pii/S1570866703000108, doi:https://doi.org/10.1016/S1570-8667(03)00010-8.
  * [13] Mikko Rautiainen, Veli Mäkinen, and Tobias Marschall.  Bit-parallel sequence-to-graph alignment.  Bioinform., 35(19):3599–3607, 2019.  doi:10.1093/bioinformatics/btz162.
  * [14] Kapil Kumar Soni and Ashwini Kumar Malviya.  Design and analysis of pattern matching algorithms based on quram processing.  Arabian Journal for Science and Engineering, 46(4):3829–3851, 2021\.
  * [15] Jorg Van Renterghem.  The implications of breaking the strong exponential time hypothesis on a quantum computer.  PhD thesis, Master’s thesis, Ghent University, 2019. URL: https://lib. ugent. be/fulltxt …, 2019.

##  Appendix A Reductions to the power-of-two case

For string matching in plain text, if $|T|$ is not a power of two, in addition
to quantum register $I$ for indexing, we use also quantum register
$I^{\prime}$, of the same size. Let $x$ be the smallest integer $x$ such that
$|T|<2^{x}<2|T|$. Generate superposition
$\sum\limits_{i^{\prime}=0}^{2^{x}-1}\ket{i^{\prime}}_{I^{\prime}}\ket{0}_{I}$
and compute
$\sum\limits_{i^{\prime}=0}^{2^{x}-1}\ket{i^{\prime}}_{I^{\prime}}\ket{i^{\prime}\,mod\,|T|}_{I}$.
Now run the algorithm using $I$ as normal. This creates some redundant
substates, but does not affect the correctness of the algorithm.

For SMLG in level DAGs, if $|P|$ is not a power of two, we generate a
superposition of size $2^{x}$, where $x$ is the only integer such that
$|P|<2^{x}<2|P|$. Then, it sufficies to assume that every entry that we read
from the QRAM to the additional substates between $|P|$ and $2^{x}$ is always
initialized to $\ket{1}$, because this is the neutral value in a logical _and_
, an thus in the application of the Toffoli gate. Therefore, in these
substates, a qubit $R_{i}$ can and will be set to value $\ket{1}_{R_{i}}$ if
and only if a previous “shift” carried $\ket{1}_{R_{i-1}}$.

Alternatively, if $|P|$ is not a power of two, we can classically reduce the
problem to this case. We add new symbol $\$$ to the alphabet. Then, we pad $P$
with as many $\$$ at the end as needed to reach the next power of two. For
each level in the DAG, we add a new node with label $\$$, and we place an edge
for every node in that level to the new node. We connect all this new nodes in
a chain, and we also add a chain of $|P|$ such nodes after the last level
(they create new levels consisting only of one node). The pattern now can
overflow in these nodes after finding a proper match in the DAG. Finally, we
apply the same binary encoding as in the plain text case, now replacing every
node with a chain of two nodes, sending all the incoming edges to the first
node and making all the outgoing edges leave from the second node. Overall, we
add one new node per level, and one new edge per node, plus $|P|$ additional
nodes and edges after the last level. This takes time $O(|E|+|P|)$.

##  Appendix B Additional pseudo-code

1

2

3Function
_SourceNodesInit(_$I,J,A,C,V_{0},\ldots,V_{n-1},V^{\prime}_{0},\ldots,V^{\prime}_{n-1}$_)_:

4

// Initialize $\ket{a_{j}}_{A}$ so that $a_{j}=1$ if $j=0$, $a_{j}=0$
otherwise

5
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{0}_{A}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\delta_{0,j}}_{A}$;

6

// Initialize $\ket{b_{j}}_{B}$ so that $b_{j}=1$ if $j=m-1$, $b_{j}=0$
otherwise

7
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{0}_{B}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\delta_{m-1,j}}_{B}$;

8

// $L_{0}$ is the set of nodes in level $0$.

9 for  _$|L_{0}|$ times_ do

// Read node label $\ell(v_{i})$ in $C$

10
$\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{0}_{C}\rightarrow\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{\ell(v_{i})}_{C}$;

11

// Read the matrix entries for character $\ell(v_{i})$ in $M$

12
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{0}_{M}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{m_{\ell(v_{i}),j}}_{M}$;

13

// Apply Toffoli to qubits $M$, $A$ and $V_{i}$

14
$\sum\limits_{j=0}^{m-1}\ket{m_{\ell(v_{i}),j}}_{M}\ket{\delta_{0,j}}_{A}\ket{0}_{V_{i}}\rightarrow\sum\limits_{j=0}^{m-1}\ket{m_{\ell(v_{i}),j}}_{M}\ket{\delta_{0,j}}_{A}\ket{m_{\ell(v_{i}),j}\land\delta_{0,j}}_{V_{i}}$;

15

// Reset $M$ and $C$

16
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{m_{\ell(v_{i}),j}}_{M}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{m_{\ell(v_{i}),j}\oplus
m_{\ell(v_{i}),j}}_{M}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C_{i}}\ket{0}_{M}$;

17

18
$\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{\ell(v_{i})}_{C}\rightarrow\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{\ell(v_{i})\oplus\ell(v_{i})}_{C}\rightarrow\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{0}_{C}$;

19

// Increase $I$ by one to visit the next node

20
$\sum\limits_{j=0}^{m-1}\ket{1}_{Q}\ket{i}_{I}\rightarrow\sum\limits_{j=0}^{m-1}\ket{1}_{Q}\ket{i+1}_{I}$;

21

22

1

2

3Function  _IncreaseI(_$I,M,C$_)_:

// Reset $M$ and $C$

4
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{m_{\ell(v_{i}),j}}_{M}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C}\ket{m_{\ell(v_{i}),j}\oplus
m_{\ell(v_{i}),j}}_{M}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\ell(v_{i})}_{C_{i}}\ket{0}_{M}$;

5

6
$\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{\ell(v_{i})}_{C}\rightarrow\ket{i}_{I}\ket{\ell(v_{i})\oplus\ell(v_{i})}_{C}\rightarrow\sum\limits_{j=0}^{m-1}\ket{i}_{I}\ket{0}_{C}$;

7

// Increase $I$

8
$\sum\limits_{j=0}^{m-1}\ket{1}_{Q}\ket{i}_{I}\rightarrow\sum\limits_{j=0}^{m-1}\ket{1}_{Q}\ket{i+1}_{I}$;

9

1

2 Function  _IncreaseJ(_$J,A,B$_)_:

// Reset $A$ and $B$

3
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\delta_{0,j}}_{A}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{0}_{A};\,\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\delta_{m-1,j}}_{B}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{0}_{B}$;

4

// Increase $J$

5
$\sum\limits_{j=0}^{m-1}\ket{1}_{Q}\ket{j}_{J}\rightarrow\ket{1}_{Q}\ket{j+1}_{J}$;

6

// Reinitialize $A$ and $B$

7
$\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{0}_{A}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\delta_{0,j}}_{A};\,\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{0}_{B}\rightarrow\sum\limits_{j=0}^{m-1}\ket{j}_{J}\ket{\delta_{m-1,j}}_{B}$;

8

##  Appendix C Full proof of Theorem 5.5.

######  Proof C.1.

After running the outer _for_ -loop of Algorithm 2 $L-1$ times, we exit such a
loop, and we know we have visited all the nodes (nodes in $L_{0}$ where
visited during the initialization). If we consider Lemma 5.3 applied in the
case of $t=n-1$, we are considering all the nodes, which means that if $P$ has
no match ending in $G$, then no substate of register $R_{n-1}$ is such that
$\ket{r_{n-1,j}}_{R_{n-1}}=\ket{1}$, for any $j$. Instead, if $P$ has a match
in $G$, then at least one substate of $R_{n-1}$ is such that
$\ket{r_{n-1,j}}_{R_{n-1}}=\ket{1}$, for some $j$.

The _for_ loop that we run at the end of the algorithm ensures to achieve high
probability of success. The probability of success $p$ in Grover’s search
algorithm is the sinusoidal function $p(K)=\sin^{2}((2K+1)\theta)$ [5], where
$\theta=\sin^{-1}\left(\sqrt{\frac{M}{N}}\right)$, $N$ is the search space,
$M$ is the number of good solutions and $K$ is the number of iterations of the
Grover’s operator. This function has period
$\lambda_{M}\approx\frac{\pi}{2}\sqrt{\frac{N}{M}}-1$. Consider the case
$M=1$. If we choose a random number of iterations $K$ between $1$ and
$\lambda_{1}$, we have $p(K)\geq 1/2$ with probability $1/2$. This is because
half of the material of the function is above the horizontal line of $1/2$.
When $p(K)\geq 1/2$, the probability of measuring a wrong result is
$p_{\text{top}}\leq 1/2$. When $p(K)\geq 1/2$, the probability of measuring a
wrong result is greater than $1/2$, but anyway $p_{\text{bottom}}\leq 1$. If
we run the process $c$ times, the overall probability of failure (measuring a
wrong result) $p_{f}$ is then

$p_{f}=\left(p_{\text{top}}\frac{1}{2}+p_{\text{bottom}}\frac{1}{2}\right)^{c}\leq\left(\frac{1}{2}\frac{1}{2}+1\cdot\frac{1}{2}\right)^{c}=\left(\frac{3}{4}\right)^{c}$

Thus, the probability of success (measuring a correct result) is
$p_{s}=1-(3/4)^{c}$.

In the general case $1<M\leq N$, the period $\lambda_{M}$ of function $p(K)$
is smaller than period $\lambda_{1}$ of the case $M=1$. We can still use the
same random number of iterations $K$ between $1$ and $\lambda_{1}$, as nearly
half of the material of the function $p(K)$ is above the horizontal line of
$1/2$: the worst case is when $\lambda_{M}$ is little over half of
$\lambda_{1}$. In this case we know that $p(K)$ will be sampled uniformly over
half of the range of period $\lambda_{1}$, but the other half may have biased
sampling. Namely, the other half of the function might have more material
below $1/2$ than above. To have a safe estimate, we assume that the
probability of returning the wrong result in the biased case is
$p_{\text{biased}}=1$. That is, if we run the process $c$ times, the overall
probability of failure (measuring a wrong result) $p_{f}$ is then

$p_{f}=\left(p_{\text{biased}}\frac{1}{2}+(p_{\text{top}}\frac{1}{2}+p_{\text{bottom}}\frac{1}{2})\frac{1}{2}\right)^{c}\leq\left(1\cdot\frac{1}{2}+(\frac{1}{2}\frac{1}{2}+1\cdot\frac{1}{2})\frac{1}{2}\right)^{c}=\left(\frac{7}{8}\right)^{c}$

Thus, the probability of success (measuring a correct result) is
$p_{s}=1-(7/8)^{c}$.