Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Computational Methods in Sciences and Engineering

A method to generate quantum circuits for 2D pattern matching problem

Shi Cheng

Published Apr 24, 2026• 0 citations
Publisher
DOI
10.66113/jcmse.26s2002

Related papers

A Pattern Matching Based Framework for Quantum Circuit Rewriting

Hui Jiang, Dian-Kang Li, Yuxin Deng +1 more

Journal of Computer Science and Technology•Nov 1, 2024•2 citations

A Pattern Matching-Based Framework for Quantum Circuit Rewriting

Hui Jiang, Diankang Li, Yuxin Deng +1 more

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.06684•Jun 14, 2022•2 citations

An Efficient Method for Quantum Circuit Placement Problem on a 2-D Grid

Atsushi Matsuo, Shigeru Yamashita

Lecture notes in computer science•Jan 1, 2019•18 citations

Algorithms for Quantum Computers

Jamie Smith, Michele Mosca

arXiv:1001.0767•Springer eBooks•Jan 1, 2012•27 citations

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)$.

arXiv:2302.06717•Feb 13, 2023•2 citations

Pattern Recognition in Quantum Computation

Vasil Dinev Penchev

•May 18, 2020•0 citations
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 GIBMG_{IBM}GIBM​ gate set to the GSurG_{Sur}GSur​ gate set. Compared with the existing tool PaF, QRewriting obtains an improvement of reducing depths (resp. gate counts) by 29\% (resp. 14\%).
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 eee incident to vvv has a label Lv(e)L_v(e)Lv​(e) unique in vvv. Jiang and Bunke showed that the subgraph isomorphism problem H⊆GH \subseteq GH⊆G for such graphs can be solved in time O(∣V(G)∣⋅∣V(H)∣)O(|V(G)| \cdot |V(H)|)O(∣V(G)∣⋅∣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 mmm pattern matches in time O(P)P+3/2⋅∣V(G)∣+O(m)O(P)^{P+3/2} \cdot |V(G)| + O(m)O(P)P+3/2⋅∣V(G)∣+O(m), where PPP 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 NNN and depth δδδ of the patterns : O(N)N+1/2⋅δlog⁡δ⋅∣V(G)∣+O(m)O(N)^{N + 1/2} \cdot δ\log δ\cdot |V(G)| + O(m)O(N)N+1/2⋅δlogδ⋅∣V(G)∣+O(m).