Obstacles to quantum annealing in a planar embedding of XORSAT

Pranay Patil, Stefanos Kourtis, Claudio Chamon, Eduardo R. Mucciolo, and Andrei E. Ruckenstein
Phys. Rev. B 100, 054435 – Published 23 August 2019

Abstract

We introduce a planar embedding of the k-regular k-XORSAT problem, in which solutions are encoded in the ground state of a classical statistical mechanics model of reversible logic gates arranged on a square grid and acting on bits that represent the Boolean variables of the problem. The special feature of this embedding is that the resulting model lacks a finite-temperature phase transition, thus bypassing the first-order thermodynamic transition known to occur in the random graph representation of XORSAT. In spite of this attractive feature, the thermal relaxation into the ground state displays remarkably slow glassy behavior. The question addressed in this paper is whether this planar embedding can afford an efficient path to solution of k-regular k-XORSAT via quantum adiabatic annealing. We first show that our model bypasses an avoided level crossing and consequent exponentially small gap in the limit of small transverse fields. We then present quantum Monte Carlo results for our embedding of the k-regular k-XORSAT that strongly support a picture in which second-order and first-order transitions develop at a finite transverse field for k=2 and k=3, respectively. This translates into power-law and exponential dependences in the scaling of energy gaps with system size, corresponding to times-to-solution which are, respectively, polynomial and exponential in the number of variables. We conclude that neither classical nor quantum annealing can efficiently solve our reformulation of XORSAT, even though the original problem can be solved in polynomial time by Gaussian elimination.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
3 More
  • Received 9 April 2019
  • Revised 27 June 2019

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

©2019 American Physical Society

Physics Subject Headings (PhySH)

Condensed Matter, Materials & Applied Physics

Authors & Affiliations

Pranay Patil1, Stefanos Kourtis1, Claudio Chamon1, Eduardo R. Mucciolo2, and Andrei E. Ruckenstein1

  • 1Department of Physics, Boston University, 590 Commonwealth Avenue, Boston, Massachusetts 02215, USA
  • 2Department of Physics, University of Central Florida, Orlando, Florida 32816, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 100, Iss. 5 — 1 August 2019

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 B

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×