Computational hardness of spin-glass problems with tile-planted solutions

Dilina Perera, Firas Hamze, Jack Raymond, Martin Weigel, and Helmut G. Katzgraber
Phys. Rev. E 101, 023316 – Published 28 February 2020

Abstract

We investigate the computational hardness of spin-glass instances on a square lattice, generated via a recently introduced tunable and scalable approach for planting solutions. The method relies on partitioning the problem graph into edge-disjoint subgraphs and planting frustrated, elementary subproblems that share a common local ground state, which guarantees that the ground state of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the typical hardness of problem classes over a large region of the multidimensional tuning parameter space. Our results show that the problems have a wide range of tunable hardness. Moreover, we observe multiple transitions in the hardness phase space, which we further corroborate using simulated annealing and simulated quantum annealing. By investigating thermodynamic properties of these planted systems, we demonstrate that the harder samples undergo magnetic ordering transitions which are also ultimately responsible for the observed hardness transitions on changing the sample composition.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
14 More
  • Received 24 July 2019
  • Revised 16 January 2020
  • Accepted 5 February 2020

DOI:https://doi.org/10.1103/PhysRevE.101.023316

©2020 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & ThermodynamicsQuantum Information, Science & TechnologyCondensed Matter, Materials & Applied Physics

Authors & Affiliations

Dilina Perera1,*, Firas Hamze2, Jack Raymond2, Martin Weigel3, and Helmut G. Katzgraber4,1,5

  • 1Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
  • 2D-Wave Systems, Inc., 3033 Beta Avenue, Burnaby, British Columbia, Canada V5G 4M9
  • 3Centre for Fluid and Complex Systems, Coventry University, Coventry, CV1 5FB, England
  • 4Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA
  • 5Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA

  • *dilinanp@tamu.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 101, Iss. 2 — February 2020

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×