Physics – Quantum Physics
Scientific paper
2003-12-20
Quantum Information and Computation,Vol 5, No. 6,(2005) 492-506
Physics
Quantum Physics
17 pages, 5 figures, 1 table, with additions and corrections included
Scientific paper
We investigate classical and quantum physics-based algorithms for solving the graph isomorphism problem. Our work integrates and extends previous work by Gudkov et al. (cond-mat/0209112) and by Rudolph (quant-ph/0206068). Gudkov et al. propose an algorithm intended to solve the graph isomorphism problem in polynomial time by mimicking a classical dynamical many-particle process. We show that this algorithm fails to distinguish pairs of non-isomorphic strongly regular graphs, thus providing an infinite class of counterexamples. We also show that the simplest quantum generalization of the algorithm also fails. However, by combining Gudkov et al.'s algorithm with a construction proposed by Rudoph in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested (with up to 29 vertices).
Coppersmith Susan N.
Joynt Robert
Shiau Shiue-Yuan
No associations
LandOfFree
Physically-motivated dynamical algorithms for the graph isomorphism problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Physically-motivated dynamical algorithms for the graph isomorphism problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Physically-motivated dynamical algorithms for the graph isomorphism problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-657004