Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer

Abstract

Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem (i.e., at least as hard as any problem in the nondeterministic polynomial-time (NP) class). Given validity of the exponential time hypothesis, its computational complexity was proven to be no less than $2^{N^{2/3}}$, where $N$ is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with $N\le 5627$. We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as $2^{N/\beta }$ with $\beta \approx 10^3$. Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, $\beta$ can be increased even further. This suggests that, for $N<{\beta }^3$, annealing devices provide most efficient way to find an exact ground state.

7 pages, 7 figures

References in corpus (32)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Parallel Tempering: Theory, Applications, and New Perspectives
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Annealing and Analog Quantum Computation
• Mathematical Foundation of Quantum Annealing
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Quantum Annealing: An Overview
• Reverse annealing for the fully connected $p$-spin model
• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• Prime factorization using quantum annealing and computational algebraic geometry
• Nature of the spin-glass phase at experimental length scales
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Computational complexity of spin-glass three-dimensional (3D) Ising model
• Replica symmetry breaking in and around six dimensions
• Quantum speedup of branch-and-bound algorithms
• Quantum annealing simulation of out-of-equilibrium magnetization in a spin-chain compound
• The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Mean-Field Approximate Optimization Algorithm
• Low Energy Excitations in Spin Glasses from Exact Ground States
• Many-body localization enables iterative quantum optimization
• The droplet-scaling versus replica symmetry breaking debate in spin glasses revisited
• Finite-Dimensional Spin Glasses: States, Excitations, and Interfaces
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Quantum Annealing with chaotic driver Hamiltonians
• Physics of the Edwards-Anderson Spin Glass in Dimensions $d=3,\dots ,8$ from Heuristic Ground State Optimization

Cited by in corpus (3)

• Tricritical Kibble-Zurek scaling in Rydberg atom ladders
• Quantum-inspired dynamical models on quantum and classical annealers
• Quantum sequel of neural network training