The graph isomorphism problem
Graph isomorphism is a classic problem in computer science that has no known efficient solution. There is some optimism that there exists an efficient quantum algorithm, but so far no provably effective one has been found. Sean Shiau, Sue Coppersmith and I constructed a quantum algorithm based on a random walk of two interacting particles that distinguishes all the difficult test cases that we could check, including many pairs of large strongly regular graphs. This leads to a conjectured algorithm.
Shiueyuan Shiau, Robert Joynt, and S.N. Coppersmith, Quantum Information and Computation 5, 492 (2005)
PhysicallyMotivated Dynamical Algorithms
for the Graph Isomorphism Promblem
