dorsal/arxiv
View SchemaPhysically-motivated dynamical algorithms for the graph isomorphism problem
| Authors | Shiue-yuan Shiau, Robert Joynt, S. N. Coppersmith |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0312170 |
| URL | https://arxiv.org/abs/quant-ph/0312170 |
| Journal | Quantum Information and Computation,Vol 5, No. 6,(2005) 492-506 |
Abstract
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).
{
"annotation_id": "19a7c306-344a-407e-b03f-18ec39adc689",
"date_created": "2026-03-02T18:02:02.667000Z",
"date_modified": "2026-03-02T18:02:02.667000Z",
"file_hash": "ac05f13dacda39436bb1b99a6cb9dd8b6d4b504b6e3c523adc2b20b9954cd890",
"private": false,
"record": {
"abstract": "We investigate classical and quantum physics-based algorithms for solving the\ngraph isomorphism problem. Our work integrates and extends previous work by\nGudkov et al. (cond-mat/0209112) and by Rudolph (quant-ph/0206068). Gudkov et\nal. propose an algorithm intended to solve the graph isomorphism problem in\npolynomial time by mimicking a classical dynamical many-particle process. We\nshow that this algorithm fails to distinguish pairs of non-isomorphic strongly\nregular graphs, thus providing an infinite class of counterexamples. We also\nshow that the simplest quantum generalization of the algorithm also fails.\nHowever, by combining Gudkov et al.\u0027s algorithm with a construction proposed by\nRudoph in which one examines a graph describing the dynamics of two particles\non the original graph, we find an algorithm that successfully distinguishes all\npairs of non-isomorphic strongly regular graphs that we tested (with up to 29\nvertices).",
"arxiv_id": "quant-ph/0312170",
"authors": [
"Shiue-yuan Shiau",
"Robert Joynt",
"S. N. Coppersmith"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information and Computation,Vol 5, No. 6,(2005) 492-506",
"title": "Physically-motivated dynamical algorithms for the graph isomorphism problem",
"url": "https://arxiv.org/abs/quant-ph/0312170"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0ed92ac3-3ad7-4b6b-9c5c-004f8b49a1a8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}