Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
Authors:
Preprint
Abstract
Quantum annealing aims to exploit quantum mechanics to speed up 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.Keywords
All Related Versions
This publication has 49 references indexed in Scilit:
- Computational multiqubit tunnelling in programmable quantum annealersNature Communications, 2016
- Performance of two different quantum annealing correction codesQuantum Information Processing, 2015
- Adiabatic quantum programming: minor embedding with hard faultsQuantum Information Processing, 2013
- Thermally assisted quantum annealing of a 16-qubit problemNature Communications, 2013
- Quantum annealing with manufactured spinsNature, 2011
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph designQuantum Information Processing, 2010
- Minor-embedding in adiabatic quantum computation: I. The parameter setting problemQuantum Information Processing, 2008
- Quantum coherence and entanglement with ultracold atoms in optical latticesNature, 2008
- Counting models for 2SAT and 3SAT formulaeTheoretical Computer Science, 2005
- Spin-glass models as error-correcting codesNature, 1989