From local to global ground states in Ising spin glasses

Ilia Zintchenko, Matthew B. Hastings, and Matthias Troyer
Phys. Rev. B 91, 024201 – Published 5 January 2015

Abstract

We consider whether it is possible to find ground states of frustrated spin systems by solving them locally. Using spin glass physics and Imry-Ma arguments in addition to numerical benchmarks we quantify the power of such local solution methods and show that for the average low-dimensional spin glass problem outside the spin glass phase the exact ground state can be found in polynomial time. In the second part we present a heuristic, general-purpose hierarchical approach which for spin glasses on chimera graphs and lattices in two and three dimensions outperforms, to our knowledge, any other solver currently around, with significantly better scaling performance than simulated annealing.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
8 More
  • Received 13 August 2014

DOI:https://doi.org/10.1103/PhysRevB.91.024201

©2015 American Physical Society

Authors & Affiliations

Ilia Zintchenko1, Matthew B. Hastings2,3, and Matthias Troyer1

  • 1Theoretische Physik, ETH Zurich, 8093 Zurich, Switzerland
  • 2Station Q, Microsoft Research, Santa Barbara, California 93106-6105, USA
  • 3Quantum Architectures and Computation Group, Microsoft Research, Redmond, Washington 98052, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 91, Iss. 2 — 1 January 2015

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review B

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×