Approximate optimization, sampling, and spin-glass droplet discovery with tensor networks

Marek M. Rams, Masoud Mohseni, Daniel Eppens, Konrad Jałowiecki, and Bartłomiej Gardas
Phys. Rev. E 104, 025308 – Published 23 August 2021

Abstract

We devise a deterministic algorithm to efficiently sample high-quality solutions of certain spin-glass systems that encode hard optimization problems. We employ tensor networks to represent the Gibbs distribution of all possible configurations. Using approximate tensor-network contractions, we are able to efficiently map the low-energy spectrum of some quasi-two-dimensional Hamiltonians. We exploit the local nature of the problems to compute spin-glass droplets geometries, which provides a new form of compression of the low-energy spectrum. It naturally extends to sampling, which otherwise, for exact contraction, is #P-complete. In particular, for one of the hardest known problem-classes devised on chimera graphs known as deceptive cluster loops and for up to 2048 spins, we find on the order of 1010 degenerate ground states in a single run of our algorithm, computing better solutions than have been reported on some hard instances. Our gradient-free approach could provide new insight into the structure of disordered spin-glass complexes, with ramifications both for machine learning and noisy intermediate-scale quantum devices.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
3 More
  • Received 11 June 2020
  • Accepted 23 July 2021

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

©2021 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & Thermodynamics

Authors & Affiliations

Marek M. Rams1,*, Masoud Mohseni2,†, Daniel Eppens2, Konrad Jałowiecki3, and Bartłomiej Gardas4,5,‡

  • 1Jagiellonian University, Institute of Theoretical Physics, Łojasiewicza 11, 30-348 Kraków, Poland
  • 2Google Quantum Artificial Intelligence Lab, Venice, California 90291, USA
  • 3Institute of Physics, University of Silesia, Uniwersytecka 4, 40-007 Katowice, Poland
  • 4Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland
  • 5Jagiellonian University, Marian Smoluchowski Institute of Physics, Łojasiewicza 11, 30-348 Kraków, Poland

  • *marek.rams@uj.edu.pl
  • mohseni@google.com
  • bartek.gardas@gmail.com

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 104, Iss. 2 — August 2021

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 E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×