The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
| Autor: | Mondada, Luca, Andrés-Martínez, Pablo |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\delta$ of the patterns : $O(N)^{N + 1/2} \cdot \delta \log \delta \cdot |V(G)| + O(m)$. Comment: The main bound of thm 1 is asymptotically very close to previous work, significantly reducing the novelty and motivation for this work. A new approach to this problem is presented in 2402.13065 |
| Databáze: | arXiv |
| Externí odkaz: |
|