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

Dilina Perera, Firas Hamze, Jack Raymond, Martin Weigel, Helmut G. Katzgraber

Research output: Contribution to journalArticle

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 multi-dimensional 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.
Original languageEnglish
Pages (from-to)(In-Press)
JournalPhysical Review E
Volume(In-Press)
Publication statusAccepted/In press - 5 Feb 2020

Fingerprint

tiles
Spin Glass
Tile
Hardness
spin glass
hardness
planting
Annealing
Ground State
annealing
ground state
Thermodynamic Properties
simulated annealing
Square Lattice
Simulated Annealing
Parameter Space
Subgraph
Partitioning
Phase Space
Tuning

Bibliographical note

12 pages, 14 figures, 1 table, loads of love

Keywords

  • cond-mat.dis-nn
  • quant-ph

Cite this

Perera, D., Hamze, F., Raymond, J., Weigel, M., & Katzgraber, H. G. (Accepted/In press). Computational hardness of spin-glass problems with tile-planted solutions. Physical Review E, (In-Press), (In-Press).

Computational hardness of spin-glass problems with tile-planted solutions. / Perera, Dilina; Hamze, Firas; Raymond, Jack; Weigel, Martin; Katzgraber, Helmut G.

In: Physical Review E, Vol. (In-Press), 05.02.2020, p. (In-Press).

Research output: Contribution to journalArticle

Perera, D, Hamze, F, Raymond, J, Weigel, M & Katzgraber, HG 2020, 'Computational hardness of spin-glass problems with tile-planted solutions' Physical Review E, vol. (In-Press), pp. (In-Press).
Perera D, Hamze F, Raymond J, Weigel M, Katzgraber HG. Computational hardness of spin-glass problems with tile-planted solutions. Physical Review E. 2020 Feb 5;(In-Press):(In-Press).
Perera, Dilina ; Hamze, Firas ; Raymond, Jack ; Weigel, Martin ; Katzgraber, Helmut G. / Computational hardness of spin-glass problems with tile-planted solutions. In: Physical Review E. 2020 ; Vol. (In-Press). pp. (In-Press).
@article{3933969f444b47e385caf056cc0647cd,
title = "Computational hardness of spin-glass problems with tile-planted solutions",
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 multi-dimensional 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.",
keywords = "cond-mat.dis-nn, quant-ph",
author = "Dilina Perera and Firas Hamze and Jack Raymond and Martin Weigel and Katzgraber, {Helmut G.}",
note = "12 pages, 14 figures, 1 table, loads of love",
year = "2020",
month = "2",
day = "5",
language = "English",
volume = "(In-Press)",
pages = "(In--Press)",
journal = "Physical Review E",
issn = "1539-3755",
publisher = "APS",

}

TY - JOUR

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

AU - Perera, Dilina

AU - Hamze, Firas

AU - Raymond, Jack

AU - Weigel, Martin

AU - Katzgraber, Helmut G.

N1 - 12 pages, 14 figures, 1 table, loads of love

PY - 2020/2/5

Y1 - 2020/2/5

N2 - 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 multi-dimensional 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.

AB - 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 multi-dimensional 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.

KW - cond-mat.dis-nn

KW - quant-ph

M3 - Article

VL - (In-Press)

SP - (In-Press)

JO - Physical Review E

JF - Physical Review E

SN - 1539-3755

ER -