Quantum Annealing Correction with Minor Embedding
arXiv:1507.02658 · doi:10.1103/PhysRevA.92.042310
Abstract
Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a 2-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with "planted" (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems, but also when minor embedding is used to extend the connectivity of physical devices.
arXiv comment34 pages, 28 figures
References in corpus (47)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
- Quantum annealing with more than one hundred qubits
- 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
- Robustness of adiabatic quantum computation
- Experimental signature of programmable quantum annealing
- Quantum Adiabatic Markovian Master Equations
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Quantum Error Correction
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Fault-tolerant quantum computation with long-range correlated noise
- Adiabatic Quantum Computation in Open Systems
- 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
- Quantum Speedup by Quantum Annealing
- A scalable control system for a superconducting adiabatic quantum optimization processor
- Decoherence in adiabatic quantum computation
- Error correcting codes for adiabatic quantum computation
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Towards Fault Tolerant Adiabatic Quantum Computation
- Tunable Quantum Tunneling of Magnetic Domain Walls
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- A scalable readout system for a superconducting adiabatic quantum optimization system
- Thermally assisted adiabatic quantum computation
- Quantum annealing correction for random Ising problems
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Reexamining classical and quantum models for the D-Wave One processor
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Error suppression and error correction in adiabatic quantum computation I: techniques and challenges
- Adiabatic quantum optimization with the wrong Hamiltonian
- Unification and limitations of error suppression techniques for adiabatic quantum computing
- Error suppression and error correction in adiabatic quantum computation II: non-equilibrium dynamics
- High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
- Quantum and Classical in Adiabatic Computation
- Quantum error suppression with commuting Hamiltonians: Two-local is too local
- A family of [[6k, 2k, 2]] codes for practical, scalable adiabatic quantum computation
- The Stability of Quantum Concatenated Code Hamiltonians
- When Diabatic Trumps Adiabatic in Quantum Optimization
- Why now is the right time to study quantum computing
Cited by in corpus (62)
- Perspectives of quantum annealing: Methods and implementations
- What is the Computational Value of Finite Range Tunneling?
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- A NASA Perspective on Quantum Computing: Opportunities and Challenges
- Quantum Annealing for Constrained Optimization
- Benchmarking Quantum Annealing Controls with Portfolio Optimization
- Weighted p-bits for FPGA implementation of probabilistic circuits
- Temperature scaling law for quantum annealing optimizers
- Driver Hamiltonians for constrained optimization in quantum annealing
- Nested Quantum Annealing Correction
- Uncertain fate of fair sampling in quantum annealing
- Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Scaling overhead of embedding optimization problems in quantum annealing
- Quantum annealing correction at finite temperature: ferromagnetic -spin models
- Analog Errors in Ising Machines
- Performance of two different quantum annealing correction codes
- An energetic perspective on rapid quenches in quantum annealing
- Mean Field Analysis of Quantum Annealing Correction
- Constrained quantum annealing of graph coloring
- Improved Boltzmann machines with error corrected quantum annealing
- Boosting quantum annealer performance via sample persistence
- Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
- Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
- Nested Quantum Annealing Correction at Finite Temperature: -spin models
- Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
- Evidence for Temperature Chaos in Spin Glasses
- Improving performance of logical qubits by parameter tuning and topology compensation
- Error suppression in adiabatic quantum computing with qubit ensembles
- Fair sampling of ground-state configurations of binary optimization problems
- Retrieving the ground state of spin glasses using thermal noise: Performance of quantum annealing at finite temperatures
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Parity Quantum Optimization: Encoding Constraints
- Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
- Patch-planting spin-glass solution for benchmarking
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
- 4-clique Network Minor Embedding for Quantum Annealers
- Site and bond percolation thresholds in -based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
- Quantum annealing speedup of embedded problems via suppression of Griffiths singularities
- Quantum annealing with a nonvanishing final value of the transverse field
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- Quantum walk on a chimera graph
- Graph minor embedding can affect sampling degenerate ground states using quantum annealing
- Demonstration of error-suppressed quantum annealing via boundary cancellation
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing---Abridged Version
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Mapping State Transition Susceptibility in Quantum Annealing
- Decoding quantum error correction with Ising model hardware
- Using copies to improve precision in continuous-time quantum computing
- Minor Embedding for Quantum Annealing with Reinforcement Learning
- Benchmarking Embedded Chain Breaking in Quantum Annealing
- A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer
- Analog Errors in Quantum Annealing: Doom and Hope
- Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
- Frustration-enhanced quantum annealing correction models with additional inter-replica interactions
- Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
- Structural Comparison of Error Mitigation Methods for Ising Machines: Penalty-Spin Model versus Stacked Model
- Multi-tasking through quantum annealing