Quantum Algorithms for Approximate Graph Isomorphism Testing

• URL: http://arxiv.org/abs/2603.02656v1
• Date: Tue, 03 Mar 2026 06:43:41 GMT
• Title: Quantum Algorithms for Approximate Graph Isomorphism Testing
• Authors: Prateek P. Kulkarni,
• Abstract summary: We study the quantum query complexity of approximate graph isomorphism testing.<n>We present a quantum algorithm based on MNRS quantum walk search over the product graph $(G,H)$ of the two input graphs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\mathcal{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 $\mathcal{O}(n^{3/2} \log n/\varepsilon)$, where $\varepsilon$ parameterizes the approximation threshold. We complement this with an $Ω(n^2)$ 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.

Related papers

• Symmetric and Antisymmetric Quantum States from Graph Structure and Orientation [0.0]
  We prove that a graph state is fully symmetric under particle permutations if and only if the underlying graph is complete.<n>We show that complete directed graphs endowed with appropriate orientations, for an odd number of qudits generate fully antisymmetric multipartite states.
  arXiv  Detail & Related papers  (2026-01-27T18:12:52Z)
• Combinatorial structures in quantum correlation: A new perspective [1.2078273498134855]
  We introduce a new class of quantum states, called $A_$-graph states.<n>The constructed states are different from the standard graph states arising from stabiliser formalism.<n>We develop a graph-theoretic formulation of a moments-based entanglement detection criterion.
  arXiv  Detail & Related papers  (2025-12-17T18:44:07Z)
• Quadratic Quantum Speedup for Finding Independent Set of a Graph [5.668733678326325]
  A quadratic speedup of the quantum adiabatic algorithm (QAA) for finding independent sets in a graph is proven analytically.<n>In comparison to the best classical algorithm with $O(n2)$ scaling, our quantum algorithm achieves a time complexity of $O(n2)$ for finding a large IS, which reduces to $O(n)$ for identifying a size-2 IS.
  arXiv  Detail & Related papers  (2025-10-30T11:35:47Z)
• Studies of properties of bipartite graphs with quantum programming [0.0]
  Multi-qubit quantum states corresponding to bipartite graphs $G(U,V,E)$ are examined.<n>The entanglement distance of the resulting states is derived analytically for an arbitrary bipartite graph structure.
  arXiv  Detail & Related papers  (2025-07-22T14:49:57Z)
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  This article presents a novel and succinct algorithmic framework via alternating quantum walks. It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs. The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
  arXiv  Detail & Related papers  (2024-07-01T06:09:19Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• Understanding Heterophily for Graph Neural Networks [42.640057865981156]
  We present theoretical understandings of the impacts of different heterophily patterns for Graph Neural Networks (GNNs) We show that the separability gains are determined by the normalized distance of the $l$-powered neighborhood distributions. Experiments on both synthetic and real-world data verify the effectiveness of our theory.
  arXiv  Detail & Related papers  (2024-01-17T11:01:28Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
  Graph Neural Network (GNN) whose output is identical to the graph function? In this paper, we fully answer this question and characterize the class of graph problems that can be represented by GNNs. We show that this condition can be efficiently verified by checking quadratically many constraints.
  arXiv  Detail & Related papers  (2022-02-17T18:54:27Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.