A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
arXiv:1805.09510 · doi:10.1103/PhysRevApplied.10.054004
Abstract
There are many factors that influence the design of quantum annealing processing units. Here we address the issue of improving quantum annealing processing unit designs from the point of view of the critical behavior of spin glasses. It has been argued [Phys. Rev. X 4, 021008 (2014)] that among the most difficult Ising spin-glass ground-state problems are those related to lattices which exhibit a finite-temperature spin-glass transition. Here, we show that adding small-world couplers between qubits (spins) to the native quasi-planar quantum processing unit graph results in a topology where a disordered Ising system can undergo a finite-temperature spin-glass transition, even when an Ising spin glass on the quasi-planar native graph does not display a transition into a glassy phase at any finite temperature. To ensure that these systems can be engineered with current fabrication techniques, using large-scale Monte Carlo simulations we demonstrate that highly-constrained systems restricted to a few fabrication layers and with fixed coupler angles can also exhibit a finite-temperature spin-glass transition. This indicates that these systems might be mean-field-like, which also means that embedding highly-nonplanar problems might be simplified when compared to the underlying native topology. Our results are illustrated using the quasi-planar Chimera topology currently used in the D-Wave Systems Inc. quantum annealing machines, as well as standard two-dimensional square lattices. The presented approach can be generalized to other topologies.
arXiv comment12 pages, 13 figures, interactive 3D versions of some figures in the ancillary material
References in corpus (33)
- Statistical mechanics of complex networks
- The diameter of the world wide web
- 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
- Adiabatic Quantum Computing
- Quantum Annealing and Analog Quantum Computation
- Detecting arbitrary quantum errors via stabilizer measurements on a sublattice of the surface code
- Mathematical Foundation of Quantum Annealing
- Architectural considerations in the design of a superconducting quantum annealing processor
- What is the Computational Value of Finite Range Tunneling?
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum Optimization of Fully-Connected Spin Glasses
- Monte Carlo Simulations of Spin Glasses at Low Temperatures
- Probing for quantum speedup in spin glass problems with planted solutions
- Ising model in small-world networks
- Bootstrap percolation on the random graph
- Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Error Threshold for Color Codes and Random 3-Body Ising Models
- Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
- Probing the Almeida-Thouless line away from the mean-field model
- Stiffness of the Edwards-Anderson Model in all Dimensions
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Comment on "Ising model on a small world network"
- Behavior of Ising Spin Glasses in a Magnetic Field
- Mean-Field and Anomalous Behavior on a Small-World Network
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Mean Field Dynamical Exponents in Finite-Dimensional Ising Spin Glass
- Lower-Critical Spin-Glass Dimension from 23 Sequenced Hierarchical Models
- Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
- Scaling and universality in glass transition
- Critical Properties of an Ising Model with Dilute Long-range Interactions
Cited by in corpus (5)
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Exploring Quantum Annealing Architectures: A Spin Glass Perspective
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- Absence of small-world effects at the quantum level and stability of the quantum critical point
- Fluctuations and Persistence in Quantum Diffusion on Regular Lattices