A Quantum Observable for the Graph Isomorphism Problem

1999/01/13 by Mark Ettinger, Peter Høyer, Ettinger, Mark +2
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/9901029

5 pages, no figures

arxiv created 1999/01/13 · openalex publication_date 1999/01/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Suppose we are given two graphs on n vertices. We define an observable in the Hilbert space \Co[(S_n \wr S₂)^m] which returns the answer ``yes'' with certainty if the graphs are isomorphic and ``no'' with probability at least 1-n!/2^m if the graphs are not isomorphic. We do not know if this observable is efficiently implementable.

Citations

• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups

Related

• Graph isomorphism: Physical resources, optimization models, and algebraic characterizations
• Quantum invariants for the graph isomorphism problem
• The quantum algorithm for graph isomorphism problem
• On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs