Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
arXiv:1603.03755 · doi:10.1103/PhysRevA.94.022327
Abstract
Quantum annealing aims to exploit quantum mechanics to speed up the search for the solution to optimization problems. Most problems exhibit complete connectivity between the logical spin variables after they are mapped to the Ising spin Hamiltonian of quantum annealing. To account for hardware constraints of current and future physical quantum annealers, methods enabling the embedding of fully connected graphs of logical spins into a constant-degree graph of physical spins are therefore essential. Here, we compare the recently proposed embedding scheme for quantum annealing with all-to-all connectivity due to Lechner, Hauke and Zoller (LHZ) [Science Advances 1 (2015)] to the commonly used minor embedding (ME) scheme. Using both simulated quantum annealing and parallel tempering simulations, we find that for a set of instances randomly chosen from a class of fully connected, random Ising problems, the ME scheme outperforms the LHZ scheme when using identical simulation parameters, despite the fault tolerance of the latter to weakly correlated spin-flip noise. This result persists even after we introduce several decoding strategies for the LHZ scheme, including a minimum-weight decoding algorithm that results in substantially improved performance over the original LHZ scheme. We explain the better performance of the ME scheme in terms of more efficient spin updates, which allows it to better tolerate the correlated spin-flip errors that arise in our model of quantum annealing. Our results leave open the question of whether the performance of the two embedding schemes can be improved using scheme-specific parameters and new error correction approaches.
arXiv comment17 pages, 19 figures. v2: updated to published version
References in corpus (48)
- Ising formulations of many NP problems
- 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
- Topological quantum memory
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Defining and detecting quantum speedup
- Robustness of adiabatic quantum computation
- Digitized adiabatic quantum computing with a superconducting circuit
- Emergence and Frustration of Magnetic Order with Variable-Range Interactions in a Trapped Ion Quantum Simulator
- Bounds for the adiabatic approximation with applications to quantum computation
- Architectural considerations in the design of a superconducting quantum annealing processor
- Experimental signature of programmable quantum annealing
- Feedback-optimized parallel tempering Monte Carlo
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- A practical heuristic for finding graph minors
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Quantum Optimization of Fully-Connected Spin Glasses
- Error corrected quantum annealing with hundreds of qubits
- Entanglement in a quantum annealing processor
- Quantum versus Classical Annealing of Ising Spin Glasses
- Application of Quantum Annealing to Training of Deep Neural Networks
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Decoherence in adiabatic quantum computation
- Quantum computing and the entanglement frontier
- Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Quantum Annealing Implementation of Job-Shop Scheduling
- Quantum annealing correction for random Ising problems
- Experimental determination of Ramsey numbers
- Reexamining classical and quantum models for the D-Wave One processor
- Quantum Annealing Correction with Minor Embedding
- Gatemon Benchmarking and Two-Qubit Operation
- Decoherence in adiabatic quantum computation
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- 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
- Unraveling Quantum Annealers using Classical Hardness
- Unification and limitations of error suppression techniques for adiabatic quantum computing
- Error suppression and error correction in adiabatic quantum computation I: techniques and challenges
- Experimental quantum annealing: case study involving the graph isomorphism problem
- Algorithm engineering for a quantum annealing platform
- Performance of two different quantum annealing correction codes
- Error correction for encoded quantum annealing
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer
- Constraint Optimization and Statistical Mechanics
Cited by in corpus (21)
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
- Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
- High-accuracy Ising machine using Kerr-nonlinear parametric oscillators with local four-body interactions
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
- Understanding domain-wall encoding theoretically and experimentally
- Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
- Breakdown of the weak coupling limit in quantum annealing
- Parity Quantum Optimization: Encoding Constraints
- Minimal Constraints in the Parity Formulation of Optimization Problems
- Quantum Annealing Machines Based on Semiconductor Nanostructures
- Analysis of the Hopfield Model with Discrete Coupling
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
- Performance of Domain-Wall Encoding for Quantum Annealing
- Four-body coupler for superconducting qubits based on Josephson parametric oscillators
- Generation of all-to-all connections in a two-dimensional qubit array with two-body interactions
- Improving success probability in the LHZ parity embedding by computing with quantum walks
- Practical hybrid decoding scheme for parity-encoded spin systems