The realization of quantum algorithms relies on specific quantum compilations according to the underlying quantum processors. However, there are various ways to physically implement qubits in different physical devices and manipulate those qubits. These differences lead to different communication methods and connection topologies, with each vendor implementing its own set of primitive gates. Therefore, quantum circuits have to be rewritten or transformed in order to be transplanted from one platform to another. We propose a pattern matching-based framework for rewriting quantum circuits, called QRewriting. It takes advantage of a new representation of quantum circuits using symbol sequences. Unlike the traditional way of using directed acyclic graphs, the new representation allows us to easily identify the patterns that appear non-consecutively but reducible. Then, we convert the problem of pattern matching into that of finding distinct subsequences and propose a polynomial-time dynamic programming-based pattern matching and replacement algorithm. We develop a rule library for basic optimizations and use it to rewrite the Arithmetic and Toffoli benchmarks from the $G_{IBM}$ gate set to the $G_{Sur}$ gate set. Compared with the existing tool PaF, QRewriting obtains an improvement of reducing depths (resp. gate counts) by 29\% (resp. 14\%).The realization of quantum algorithms relies on specific quantum compilations according to the underlying quantum processors. However, there are various ways to physically implement qubits in different physical devices and manipulate those qubits. These differences lead to different communication methods and connection topologies, with each vendor implementing its own set of primitive gates. Therefore, quantum circuits have to be rewritten or transformed in order to be transplanted from one platform to another. We propose a pattern matching-based framework for rewriting quantum circuits, called QRewriting. It takes advantage of a new representation of quantum circuits using symbol sequences. Unlike the traditional way of using directed acyclic graphs, the new representation allows us to easily identify the patterns that appear non-consecutively but reducible. Then, we convert the problem of pattern matching into that of finding distinct subsequences and propose a polynomial-time dynamic programming-based pattern matching and replacement algorithm. We develop a rule library for basic optimizations and use it to rewrite the Arithmetic and Toffoli benchmarks from the $G_{IBM}$ gate set to the $G_{Sur}$ gate set. Compared with the existing tool PaF, QRewriting obtains an improvement of reducing depths (resp. gate counts) by 29\% (resp. 14\%).

arXiv:2206.06684Jun 14, 20221 citation

An Efficient Nearest Neighbor Design for 2D Quantum Circuits

Anirban Bhattacharjee, Chandan Bandyopadhyay, Bappaditya Mondal +3 more

Lecture notes in electrical engineeringJul 28, 20191 citation

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits

Luca Mondada, Pablo Andrés-Martínez

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

A Long-algorithm Based Variational Quantum Scheme for Pattern Matching Problem

Lu Liu, Xingyu Wu, Chuan Wang

Grover algorithm is a popular model in quantum computation field and has the advantage of outperforming its classical counterpart in terms of searching speed, hence it has been applied in various domains such as pattern matching. Unfortunately, there are two central issue for this quantum search algorithm, i.e., Grover algorithm, in practical application that firstly it can only achieve a probability nearing 100% rather than exactly, secondly it tends to require a deep quantum circuit. In this work, we propose a Long-algorithm based quantum scheme for pattern matching problem, which can effectively enhance the success probability of quantum pattern matching and mitigate the needs for quantum computing resources. The performance of this scheme is demonstrated numerically, validating our design.Grover algorithm is a popular model in quantum computation field and has the advantage of outperforming its classical counterpart in terms of searching speed, hence it has been applied in various domains such as pattern matching. Unfortunately, there are two central issue for this quantum search algorithm, i.e., Grover algorithm, in practical application that firstly it can only achieve a probability nearing 100% rather than exactly, secondly it tends to require a deep quantum circuit. In this work, we propose a Long-algorithm based quantum scheme for pattern matching problem, which can effectively enhance the success probability of quantum pattern matching and mitigate the needs for quantum computing resources. The performance of this scheme is demonstrated numerically, validating our design.

International Conference on Intelligent Computing and Next Generation Networks (ICNGN)Nov 17, 20230 citations

G_{IBM}

gate set to the

G_{Sur}

gate set. Compared with the existing tool PaF, QRewriting obtains an improvement of reducing depths (resp. gate counts) by 29\% (resp. 14\%).

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)