dorsal/arxiv
View SchemaOn the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
| Authors | Daniel A. Lidar |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0309064 |
| URL | https://arxiv.org/abs/quant-ph/0309064 |
| DOI | 10.1088/1367-2630/6/1/167 |
| Journal | New J. Phys. 6 (2004) 167 |
Abstract
It is shown that the canonical problem of classical statistical thermodynamics, the computation of the partition function, is in the case of +/-J Ising spin glasses a particular instance of certain simple sums known as quadratically signed weight enumerators (QWGTs). On the other hand it is known that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating QWGTs. This suggests a connection between the partition function estimation problem for spin glasses and quantum computation. This connection extends to knots and graph theory via the equivalence of the Kauffman polynomial and the partition function for the Potts model.
{
"annotation_id": "43b44e9a-3cb1-4fb8-9c6c-ef33021da64c",
"date_created": "2026-03-02T18:02:02.725000Z",
"date_modified": "2026-03-02T18:02:02.725000Z",
"file_hash": "504b886aa12077124bd5318c9687d400e5ba7a6899574653ea37330b2e39a473",
"private": false,
"record": {
"abstract": "It is shown that the canonical problem of classical statistical\nthermodynamics, the computation of the partition function, is in the case of\n+/-J Ising spin glasses a particular instance of certain simple sums known as\nquadratically signed weight enumerators (QWGTs). On the other hand it is known\nthat quantum computing is polynomially equivalent to classical probabilistic\ncomputing with an oracle for estimating QWGTs. This suggests a connection\nbetween the partition function estimation problem for spin glasses and quantum\ncomputation. This connection extends to knots and graph theory via the\nequivalence of the Kauffman polynomial and the partition function for the Potts\nmodel.",
"arxiv_id": "quant-ph/0309064",
"authors": [
"Daniel A. Lidar"
],
"categories": [
"quant-ph",
"cond-mat",
"math-ph",
"math.MP"
],
"doi": "10.1088/1367-2630/6/1/167",
"journal_ref": "New J. Phys. 6 (2004) 167",
"title": "On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants",
"url": "https://arxiv.org/abs/quant-ph/0309064"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "00a7d20b-6c0d-43f0-8a91-2d2c5c21eccd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}