UW Physics Department Robert Joynt Home Page Curriculum Vitae Robert Joynt Publications Current Research


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.

Shiue-yuan Shiau, Robert Joynt, and S.N. Coppersmith, Quantum Information and Computation 5, 492 (2005)

Physically-Motivated Dynamical Algorithms for the Graph Isomorphism Promblem







Home | Curriculum Vitae | Publications
Research | UW Physics Department