Quantum Optimization of Fully-Connected Spin Glasses

Abstract

The Sherrington-Kirkpatrick model with random $\pm 1$ couplings is programmed on the D-Wave Two annealer featuring 509 qubits interacting on a Chimera-type graph. The performance of the optimizer compares and correlates to simulated annealing. When considering the effect of the static noise, which degrades the performance of the annealer, one can estimate an improvement on the comparative scaling of the two methods in favor of the D-Wave machine. The optimal choice of parameters of the embedding on the Chimera graph is shown to be associated to the emergence of the spin-glass critical temperature of the embedded problem.

includes supplemental material

References in corpus (9)

• Defining and detecting quantum speedup
• Mathematical Foundation of Quantum Annealing
• Architectural considerations in the design of a superconducting quantum annealing processor
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• A case study in programming a quantum annealer for hard operational planning problems
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Bayesian Network Structure Learning Using Quantum Annealing
• How to test the "quantumness" of a quantum computer?

Cited by in corpus (122)

• 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?
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• Open source software in quantum computing
• Application of Quantum Annealing to Training of Deep Neural Networks
• Quantum annealing versus classical machine learning applied to a simplified computational biology problem
• Probing for quantum speedup in spin glass problems with planted solutions
• Quantum Annealing: An Overview
• Searching for quantum speedup in quasistatic quantum annealers
• Application of Quantum Annealing to Nurse Scheduling Problem
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Beyond-classical computation in quantum simulation
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Quantum annealing correction for random Ising problems
• Robust quantum optimizer with full connectivity
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Quantum Annealing Correction with Minor Embedding
• Bayesian Network Structure Learning Using Quantum Annealing
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Benchmarking a quantum annealing processor with the time-to-target metric
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• Multivariable Optimization: Quantum Annealing & Computation
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• A deceptive step towards quantum speedup detection
• Genome assembly using quantum and quantum-inspired annealing
• Reverse quantum annealing of the $p$-spin model with relaxation
• Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
• Global warming: Temperature estimation in annealers
• Nested Quantum Annealing Correction
• Quantum machine learning and quantum biomimetics: A perspective
• Uncertain fate of fair sampling in quantum annealing
• Maximum-Entropy Inference with a Programmable Annealer
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Scaling overhead of embedding optimization problems in quantum annealing
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• Algorithm engineering for a quantum annealing platform
• Analog Errors in Ising Machines
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Mean Field Analysis of Quantum Annealing Correction
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Practical engineering of hard spin-glass instances
• Charged particle tracking with quantum annealing-inspired optimization
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Degeneracy, degree, and heavy tails in quantum annealing
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Open system quantum annealing in mean field models with exponential degeneracy
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Equation Planting: A Tool for Benchmarking Ising Machines
• Quantum adiabatic machine learning with zooming
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Optimally Stopped Optimization
• Ferromagnetically shifting the power of pausing
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Error suppression in adiabatic quantum computing with qubit ensembles
• Breakdown of the weak coupling limit in quantum annealing
• Improving performance of logical qubits by parameter tuning and topology compensation
• Impacts of Noise and Structure on Quantum Information Encoded in a Quantum Memory
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Perils of Embedding for Sampling Problems
• Fair sampling of ground-state configurations of binary optimization problems
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Fast clique minor generation in Chimera qubit connectivity graphs
• Patch-planting spin-glass solution for benchmarking
• Phase transition of Frustrated Ising model via D-wave Quantum Annealing Machine
• Advanced unembedding techniques for quantum annealers
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Disorder-assisted graph coloring on quantum annealers
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
• Realization of Heisenberg models of spin systems with polar molecules in pendular states
• Advantage of pausing: parameter setting for quantum annealers
• Scalable Connectivity for Ising Machines: Dense to Sparse
• 4-clique Network Minor Embedding for Quantum Annealers
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• Quantum annealing speedup of embedded problems via suppression of Griffiths singularities
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
• Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
• Dynamic Asset Allocation with Expected Shortfall via Quantum Annealing
• Quantum-assisted finite-element design optimization
• Two-dimensional Parallel Tempering for Constrained Optimization
• Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
• Unraveling Reverse Annealing: A Study of D-Wave Quantum Annealers
• QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting
• Applications of Quantum Annealing in Statistics
• Quantum walk on a chimera graph
• A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem
• Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All
• Analysis of a Programmable Quantum Annealer as a Random Number Generator
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Mapping State Transition Susceptibility in Quantum Annealing
• Optimization via Quantum Preconditioning
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
• Threshold theorem in isolated quantum dynamics with stochastic control errors
• Minor embedding with Stuart-Landau oscillator networks
• Ultrastrong capacitive coupling of flux qubits
• Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
• Benchmarking Embedded Chain Breaking in Quantum Annealing
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Calculating Nash Equilibrium on Quantum Annealers
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
• Minimizing minor embedding energy: an application in quantum annealing
• Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• Quantum algorithm for the classification of Supersymmetric top quark events
• Hybrid Real-Imaginary Time Evolution for Low-Depth Hamiltonian Simulation in Quantum Optimization
• Approximate Approximation on a Quantum Annealer