Simulated Quantum Annealing with Two All-to-All Connectivity Schemes

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.

17 pages, 19 figures. v2: updated to published version

References in corpus (18)

• Digitized adiabatic quantum computing with a superconducting circuit
• Bounds for the adiabatic approximation with applications to quantum computation
• Feedback-optimized parallel tempering Monte Carlo
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• A practical heuristic for finding graph minors
• Application of Quantum Annealing to Training of Deep Neural Networks
• 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 correction for random Ising problems
• Reexamining classical and quantum models for the D-Wave One processor
• Gatemon Benchmarking and Two-Qubit Operation
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Algorithm engineering for a quantum annealing platform
• Error correction for encoded quantum annealing
• 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