Physically-motivated dynamical algorithms for the graph isomorphism problem

Simple item page
dc.creatorShiau, Shiue-yuan
dc.creatorJoynt, Robert
dc.creatorCoppersmith, S. N.
dc.date2003-12-20
dc.date2004-04-20
dc.date.accessioned2026-07-07T06:34:12Z
dc.date.available2026-07-07T06:34:12Z
dc.descriptionWe 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).
dc.description17 pages, 5 figures, 1 table, with additions and corrections included
dc.identifierhttps://arxiv.org/abs/quant-ph/0312170
dc.identifierhttp://arxiv.org/abs/quant-ph/0312170
dc.identifierQuantum Information and Computation,Vol 5, No. 6,(2005) 492-506
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/99449
dc.subjectQuantum Physics
dc.titlePhysically-motivated dynamical algorithms for the graph isomorphism problem
dc.typetext

Files

Collections

arXiv