A Quantum Observable for the Graph Isomorphism Problem

Abstract

Suppose we are given two graphs on $n$ vertices. We define an observable in the Hilbert space $\Co[(S_n \wr S_2)^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.

5 pages, no figures

References in corpus (1)

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

Cited by in corpus (17)

• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• The Hidden Subgroup Problem - Review and Open Problems
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Optimal measurements for the dihedral hidden subgroup problem
• Complexity Classes of Equivalence Problems Revisited
• A Case for Synthesis of Recursive Quantum Unitary Programs
• Easy and hard functions for the Boolean hidden shift problem
• On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
• Efficient Quantum Algorithm for Identifying Hidden Polynomials
• Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
• Normalizer Circuits and Quantum Computation
• Abelian Hypergroups and Quantum Computation
• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity
• An Improved Query for the Hidden Subgroup Problem
• Approximating uniform quantum channels