{
  "id": "2501.01107",
  "version": "v1",
  "published": "2025-01-02T07:08:13.000Z",
  "updated": "2025-01-02T07:08:13.000Z",
  "title": "On Computational Complexity of 3D Ising Spin Glass: Lessons from D-Wave Annealer",
  "authors": [
    "Hao Zhang",
    "Alex Kamenev"
  ],
  "comment": "9 pages, 6 figures",
  "categories": [
    "cond-mat.dis-nn",
    "quant-ph"
  ],
  "abstract": "Finding an exact ground state of a 3D Ising spin glass is proven to be an NP-hard problem. There is a widespread belief that this statement implies an exponential scaling, $\\sim 2^{N/\\beta}$, of necessary computational efforts (classical or quantum), with the number of spins, $N$. Yet, what is a factor $\\beta$ here and are there any fundamental limits on how large it can be? Here we report results of extensive experimentation with D-Wave 3D annealer with $N\\leq 5627$. We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, characterized by $\\beta\\approx 10^{3}$. We argue that with a further improvement of annealing protocols, post-processing algorithms and device noise reduction, $\\beta$ can be increased even further. We provide a theoretical argumentation for this observation based on statistical analysis of low energy states.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-01-02T07:08:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "3d ising spin glass",
      "computational complexity",
      "d-wave annealer",
      "exact ground state",
      "device noise reduction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}