Simulated-quantum-annealing comparison between all-to-all connectivity schemes

Tameem Albash, Walter Vinci, and Daniel A. Lidar
Phys. Rev. A 94, 022327 – Published 22 August 2016

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 by Lechner, Hauke, and Zoller (LHZ) [Sci. Adv. 1, e1500838 (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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
12 More
  • Received 24 March 2016
  • Revised 10 April 2016

DOI:https://doi.org/10.1103/PhysRevA.94.022327

©2016 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Authors & Affiliations

Tameem Albash1,2,3, Walter Vinci1,2,4, and Daniel A. Lidar1,2,4,5

  • 1Department of Physics and Astronomy, University of Southern California, Los Angeles, California 90089, USA
  • 2Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
  • 3Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
  • 4Department of Electrical Engineering, University of Southern California, Los Angeles, California 90089, USA
  • 5Department of Chemistry, University of Southern California, Los Angeles, California 90089, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 94, Iss. 2 — August 2016

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×