We study a variant of the subgraph isomorphism problem that is of high interest to the quantum computing community. Our results give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously, independently of the number of patterns. After a pre-computation step in which the patterns are compiled into a decision tree, the running time is linear in the size of the input quantum circuit. More generally, we consider connected port graphs, in which every edge $e$ incident to $v$ has a label $L_v(e)$ unique in $v$ . Jiang and Bunke showed that the subgraph isomorphism problem $H \subseteq G$ for such graphs can be solved in time $O(|V(G)| \cdot |V(H)|)$ . We show that if in addition the graphs are directed acyclic, then the subgraph isomorphism problem can be solved for an unbounded number of patterns simultaneously. We enumerate all $m$ pattern matches in time $O(P)^{P+3/2} \cdot |V(G)| + O(m)$ , where $P$ is the number of vertices of the largest pattern. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits $N$ and depth $δ$ of the patterns : $O(N)^{N + 1/2} \cdot δ\log δ\cdot |V(G)| + O(m)$ .We study a variant of the subgraph isomorphism problem that is of high interest to the quantum computing community. Our results give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously, independently of the number of patterns. After a pre-computation step in which the patterns are compiled into a decision tree, the running time is linear in the size of the input quantum circuit. More generally, we consider connected port graphs, in which every edge $e$ incident to $v$ has a label $L_v(e)$ unique in $v$. Jiang and Bunke showed that the subgraph isomorphism problem $H \subseteq G$ for such graphs can be solved in time $O(|V(G)| \cdot |V(H)|)$. We show that if in addition the graphs are directed acyclic, then the subgraph isomorphism problem can be solved for an unbounded number of patterns simultaneously. We enumerate all $m$ pattern matches in time $O(P)^{P+3/2} \cdot |V(G)| + O(m)$, where $P$ is the number of vertices of the largest pattern. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits $N$ and depth $δ$ of the patterns : $O(N)^{N + 1/2} \cdot δ\log δ\cdot |V(G)| + O(m)$.

arXiv:2302.06717Feb 13, 20230 citations

Quantum Query Complexity of Some Graph Problems

Christoph Dürr, Mark Heiligman, Peter Høyer +1 more

Lecture notes in computer scienceJan 1, 200472 citations

Quantum Query Complexity for Some Graph Problems

Aija Bērziņa, Andrej Dubrovsky, Rūsiņš Freivalds +2 more

Lecture notes in computer scienceJan 1, 200438 citations

From Bit-Parallelism to Quantum String Matching for Labelled Graphs

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

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=Θ(\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|\sqrt{|P|})$ .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=Θ(\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|\sqrt{|P|})$.

arXiv:2302.02848Työväentutkimus VuosikirjaJan 1, 20230 citations

Quantum Algorithms for Graph and Algebra Problems

Sebastian Dörn

Recent Advances in Computer Science and CommunicationsJan 9, 20101 citation

Quantum‐based exact pattern matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.

ETRI JournalMay 11, 202113 citations

e

incident to

v

has a label

L_v(e)

unique in

v

. Jiang and Bunke showed that the subgraph isomorphism problem

H \subseteq G

for such graphs can be solved in time

O(|V(G)| \cdot |V(H)|)

. We show that if in addition the graphs are directed acyclic, then the subgraph isomorphism problem can be solved for an unbounded number of patterns simultaneously. We enumerate all

m

pattern matches in time

O(P)^{P+3/2} \cdot |V(G)| + O(m)

, where

P

is the number of vertices of the largest pattern. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits

N

and depth

δ

of the patterns :

O(N)^{N + 1/2} \cdot δ\log δ\cdot |V(G)| + O(m)

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=Θ(\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-ε})

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|\sqrt{|P|})