{"id":"arxiv/2603.02656","url":"https://arxiv.org/abs/2603.02656","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Algorithms for Approximate Graph Isomorphism Testing","domain":"quant-ph","source":"arxiv","authors":["Prateek P. Kulkarni"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-03","reactions":{}}