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

arXiv:2302.06717

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits

Luca Mondada, Pablo Andrés-Martínez

Published Feb 13, 2023• 2 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.2302.06717

Related papers

Quantum Algorithms for Tree Isomorphism and State Symmetrization

David J. Rosenbaum

The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.

arXiv:1011.4138•Nov 18, 2010•2 citations

Quantum Algorithms and Lower Bounds for Independent Set and Subgraph Isomorphism Problem

Sebastian Doern

The study of the quantum query complexity for some graph problems is an interesting area in quantum computing. Only for a few graph problems there are quantum algorithms and lower bounds known. We present some new quantum query and quantum time algorithms and quantum query complexity bounds for the maximal and maximum independent set problem and the graph and subgraph isomorphism problem.

•Oct 12, 2005•1 citation

Graph isomorphism and adiabatic quantum computing

Frank Gaitan, Lane Clark

In the graph isomorphism (GI) problem two $N$-vertex graphs $G$ and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of $G$ that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then $G$ and ${G}^{\ensuremath{'}}$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph $G$. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.

arXiv:1304.5773•Physical Review A•Feb 28, 2014•51 citations

Two-step approach to scheduling quantum circuits

Gian Giacomo Guerreschi, Jongsoo Park

Abstract As the effort to scale up existing quantum hardware proceeds, it becomes necessary to schedule quantum gates in a way that minimizes the number of operations. There are three constraints that have to be satisfied: the order or dependency of the quantum gates in the specific algorithm, the fact that any qubit may be involved in at most one gate at a time, and the restriction that two-qubit gates are implementable only between connected qubits. The last aspect implies that the compilation depends not only on the algorithm, but also on hardware properties like connectivity. Here we suggest a two-step approach in which logical gates are initially scheduled neglecting connectivity considerations, while routing operations are added at a later step in a way that minimizes their overhead. We rephrase the subtasks of gate scheduling in terms of graph problems like edge-coloring and maximum subgraph isomorphism. While this approach is general, we specialize to a one-dimensional array of qubits to propose a routing scheme that is minimal in the number of exchange operations. As a practical application, we schedule the quantum approximate optimization algorithm in a linear geometry and quantify the reduction in the number of gates and circuit depth that results from increasing the efficacy of the scheduling strategies.

arXiv:1708.00023•Quantum Science and Technology•Jun 26, 2018•85 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

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations
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).
The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.
In the graph isomorphism (GI) problem two NNN-vertex graphs GGG and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of GGG that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then GGG and ${G}^{\ensuremath{'}}$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph GGG. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.
Abstract As the effort to scale up existing quantum hardware proceeds, it becomes necessary to schedule quantum gates in a way that minimizes the number of operations. There are three constraints that have to be satisfied: the order or dependency of the quantum gates in the specific algorithm, the fact that any qubit may be involved in at most one gate at a time, and the restriction that two-qubit gates are implementable only between connected qubits. The last aspect implies that the compilation depends not only on the algorithm, but also on hardware properties like connectivity. Here we suggest a two-step approach in which logical gates are initially scheduled neglecting connectivity considerations, while routing operations are added at a later step in a way that minimizes their overhead. We rephrase the subtasks of gate scheduling in terms of graph problems like edge-coloring and maximum subgraph isomorphism. While this approach is general, we specialize to a one-dimensional array of qubits to propose a routing scheme that is minimal in the number of exchange operations. As a practical application, we schedule the quantum approximate optimization algorithm in a linear geometry and quantify the reduction in the number of gates and circuit depth that results from increasing the efficacy of the scheduling strategies.
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\%).
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.