Obstacles to quantum annealing in a planar embedding of XORSAT

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.

References in corpus (19)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Continuous Quantum Phase Transitions
• Quantum annealing with more than one hundred qubits
• QuSpin: a Python Package for Dynamics and Exact Diagonalisation of Quantum Many Body Systems part I: spin chains
• Anderson localization casts clouds over adiabatic quantum optimization
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Stochastic series expansion method for quantum Ising models with arbitrary interactions
• Ashkin-Teller criticality and pseudo first-order behavior in a frustrated Ising model on the square lattice
• Simplest random K-satisfiability problem
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• First-order transitions and the performance of quantum algorithms in random optimization problems
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Quasi-adiabatic quantum Monte Carlo algorithm for quantum evolution in imaginary time
• Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• Singular ferromagnetic susceptibility of the transverse-field Ising antiferromagnet on the triangular lattice
• Quantum Vertex Model for Reversible Classical Computing

Cited by in corpus (4)

• QuSpin: a Python Package for Dynamics and Exact Diagonalisation of Quantum Many Body Systems. Part II: bosons, fermions and higher spins
• Tensor Network Rewriting Strategies for Satisfiability and Counting
• Boundary conditions dependence of the phase transition in the quantum Newman-Moore model
• Tensor networks for $p$-spin models