Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
arXiv:1401.1546 · doi:10.1103/PhysRevX.4.021008
Abstract
Recently, a programmable quantum annealing machine has been built that minimizes the cost function of hard optimization problems by adiabatically quenching quantum fluctuations. Tests performed by different research teams have shown that, indeed, the machine seems to exploit quantum effects. However experiments on a class of random-bond instances have not yet demonstrated an advantage over classical optimization algorithms on traditional computer hardware. Here we present evidence as to why this might be the case. These engineered quantum annealing machines effectively operate coupled to a decohering thermal bath. Therefore, we study the finite-temperature critical behavior of the standard benchmark problem used to assess the computational capabilities of these complex machines. We simulate both random-bond Ising models and spin glasses with bimodal and Gaussian disorder on the D-Wave Chimera topology. Our results show that while the worst-case complexity of finding a ground state of an Ising spin glass on the Chimera graph is not polynomial, the finite-temperature phase space is likely rather simple: Spin glasses on Chimera have only a zero-temperature transition. This means that benchmarking optimization methods using spin glasses on the Chimera graph might not be the best benchmark problems to test quantum speedup. We propose alternative benchmarks by embedding potentially harder problems on the Chimera topology. Finally, we also study the (reentrant) disorder-temperature phase diagram of the random-bond Ising model on the Chimera graph and show that a finite-temperature ferromagnetic phase is stable up to 19.85(15)% antiferromagnetic bonds. Beyond this threshold the system only displays a zero-temperature spin-glass phase. Our results therefore show that a careful design of the hardware architecture and benchmark problems is key when building quantum annealing machines.
arXiv comment8 pages, 5 figures, 1 table
References in corpus (28)
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Mathematical Foundation of Quantum Annealing
- Experimental signature of programmable quantum annealing
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- First order phase transition in the Quantum Adiabatic Algorithm
- Monte Carlo Simulations of Spin Glasses at Low Temperatures
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Error Threshold for Color Codes and Random 3-Body Ising Models
- Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- Study of the de Almeida-Thouless line using power-law diluted one-dimensional Ising spin glasses
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Behavior of Ising Spin Glasses in a Magnetic Field
- Zero and low temperature behavior of the two-dimensional Ising spin glass
- Chaos and universality in two-dimensional Ising spin glasses
- Finite size corrections in the Sherrington-Kirkpatrick model
- Simplest model to study reentrance in physical systems
- Error estimation and reduction with cross correlations
- Cross-correlations in scaling analyses of phase transitions
- Correlation Length of the Two-Dimensional Ising Spin Glass with Gaussian Interactions
- A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure
Cited by in corpus (95)
- Defining and detecting quantum speedup
- Perspectives of quantum annealing: Methods and implementations
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Quantum Annealing for Industry Applications: Introduction and Review
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- What is the Computational Value of Finite Range Tunneling?
- Quantum Optimization of Fully-Connected Spin Glasses
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Quantum versus Classical Annealing of Ising Spin Glasses
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Probing for quantum speedup in spin glass problems with planted solutions
- Decoherence in adiabatic quantum computation
- Searching for quantum speedup in quasistatic quantum annealers
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Quantum annealing correction for random Ising problems
- Quantum Annealing Correction with Minor Embedding
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Scaling and diabatic effects in quantum annealing with a D-Wave device
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Benchmarking Quantum Annealing Controls with Portfolio Optimization
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Multivariable Optimization: Quantum Annealing & Computation
- A deceptive step towards quantum speedup detection
- Genome assembly using quantum and quantum-inspired annealing
- Next-Generation Topology of D-Wave Quantum Processors
- Benchmarking Hamiltonian Noise in the D-Wave Quantum Annealer
- Global warming: Temperature estimation in annealers
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
- Uncertain fate of fair sampling in quantum annealing
- Quantum annealing for the number partitioning problem using a tunable spin glass of ions
- Maximum-Entropy Inference with a Programmable Annealer
- Readiness of Quantum Optimization Machines for Industrial Applications
- Finding spin-glass ground states using quantum walks
- Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers
- Reexamination of the evidence for entanglement in the D-Wave processor
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Hybrid quantum annealing for larger-than-QPU lattice-structured problems
- Scaling overhead of embedding optimization problems in quantum annealing
- Predicting quantum advantage by quantum walk with convolutional neural networks
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Algorithm engineering for a quantum annealing platform
- Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
- Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
- Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Evidence against a mean field description of short-range spin glasses revealed through thermal boundary conditions
- Practical engineering of hard spin-glass instances
- From local to global ground states in Ising spin glasses
- High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Open system quantum annealing in mean field models with exponential degeneracy
- Quantum annealing speedup over simulated annealing on random Ising chains
- Degeneracy, degree, and heavy tails in quantum annealing
- Topological wormholes
- A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
- Simulated quantum annealing of double-well and multi-well potentials
- Efficient subgraph-based sampling of Ising-type models with frustration
- Optimally Stopped Optimization
- Adiabatic Quantum Optimization for Associative Memory Recall
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- Search range in experimental quantum annealing
- Fair sampling of ground-state configurations of binary optimization problems
- High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder
- Quantum optics and frontiers of physics: The third quantum revolution
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Dual time scales in simulated annealing of a two-dimensional Ising spin glass
- borealis - A generalized global update algorithm for Boolean optimization problems
- Initial State Encoding via Reverse Quantum Annealing and h-gain Features
- A theory of non-equilibrium local search on random satisfaction problems
- A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
- Site and bond percolation thresholds in -based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
- Erratum: Glassy Chimeras Could Be Blind to Quantum Speedup. . . [Phys. Rev. X 4, 021008 (2014)]
- Influence of long-range interaction on degeneracy of eigenvalues of connection matrix of d-dimensional Ising system
- Classifying Data with Local Hamiltonians
- Quantum walk on a chimera graph
- Load Balancing For High Performance Computing Using Quantum Annealing
- Adding color: Visualization of energy landscapes in spin glasses
- Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
- A thermodynamic approach to optimization in complex quantum systems
- Mapping State Transition Susceptibility in Quantum Annealing
- Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
- Development of research network on Quantum Annealing Computation and Information using Google Scholar data
- Quantum Searches in a Hard 2SAT Ensemble
- Relation of classical non-equilibrium dynamics and quantum annealing
- Benchmarking Embedded Chain Breaking in Quantum Annealing
- Notes on Adiabatic Quantum Computers
- Quantum annealing and condensed matter physics
- Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet