We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.
We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.
We present a quantum variational algorithm based on a novel circuit that generates all permutations that can be spanned by one- and two-qubits permutation gates. The construction of the circuits follows from group-theoretical results, most importantly the Bruhat decomposition of the group generated by the cx gates. These circuits require a number of qubits that scale logarithmically with the permutation dimension, and are therefore employable in near-term applications. We further augment the circuits with ancilla qubits to enlarge their span, and with these we build ansatze to tackle permutation-based optimization problems such as quadratic assignment problems, and graph isomorphisms. The resulting quantum algorithm, QuPer, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with 256 variables, requiring 20 qubits.
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on n vertices drawn from the Erdős--Rényi distribution G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most k edge edits.
We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2logn/ε), where ε parameterizes the approximation threshold. We complement this with an Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model.
We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.
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 Lv(e) unique in v. Jiang and Bunke showed that the subgraph isomorphism problem H⊆G for such graphs can be solved in time 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 m pattern matches in time O(P)P+3/2⋅∣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⋅δlogδ⋅∣V(G)∣+O(m).
The Noisy Intermediate-Scale Quantum (NISQ) era of technology in which we currently find ourselves is defined by non-universality, susceptibility to errors and noise, and a search for useful applications. While demonstrations of practical quantum advantage remain elusive in this era, it provides space to develop and analyze the advantages and limitations of systems and their ability to solve problems. In this work, we critically assess a proposed quantum algorithm for the graph isomorphism problem, implemented on a photonic quantum device. Inspired by the nature of this quantum algorithm, we formulate a necessary condition for the isomorphism of graphs encoded in Gaussian boson samplers and a classical algorithm to test for it. Our classical algorithm makes use of efficiently computable statistical properties of a quantum sampling system to show a pair of graphs fail to meet our necessary condition and thus cannot be isomorphic. We analyze our algorithm in the context of the inspiring, sampler-based quantum algorithm of Bràdler et. al., the classical color refinement algorithm, and the state-of-the-art quasi-polynomial Babai algorithm.
Graph isomorphism, the problem of determining whether two graphs are structurally identical despite potentially differing node labels and edge orientations, is a fundamental problem in computer science and theoretical mathematics. This paper investigates the potential for quantum algorithms, specifically leveraging Grover's algorithm, to improve the efficiency of graph isomorphism testing. We explore the theoretical complexity of this problem on a quantum computer, analyzing the impact of graph structure and algorithm parameters. The core claim is that determining graph isomorphism remains a computationally challenging problem, even with quantum acceleration. We delve into the limitations imposed by the problem's inherent complexity and the practical hurdles involved in implementing quantum algorithms for this task. The analysis focuses on the search space reduction offered by Grover's algorithm and its interaction with the graph's topology. We examine the factors that contribute to the algorithm's effectiveness, including graph size, connectivity, and the number of possible graph configurations. Ultimately, this work contributes to a deeper understanding of the computational challenges associated with graph isomorphism and provides insights into the potential and limitations of quantum computing in tackling this problem.
The noisy intermediate-scale quantum (NISQ) computer significantly advances quantum computing technology. Due to the physical connectivity constraints of the NISQ device, its induced qubit mapping problem becomes more challenging. Recent works employ heuristics to achieve promising outcomes. However, they are limited to using only one type of center for graph matching, and their exhaustive traversal of the coupling graph results in high computation time. This paper strategically generates specific subgraphs during the initial mapping stage to reduce the solution space for the coupling graph. Then, we employ a bidirectional graph isomorphism search to improve initial mapping. In the main mapping stage, we develop an efficient search algorithm to minimize the number of inserted gates. Experimental results show that our method significantly outperforms the state-of-the-art work in reducing the number of inserted CNOT gates by 13.22% and the runtime by 19.61%.