Quantum annealing correction with minor embedding

Walter Vinci, Tameem Albash, Gerardo Paz-Silva, Itay Hen, and Daniel A. Lidar
Phys. Rev. A 92, 042310 – Published 9 October 2015

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 two-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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
22 More
  • Received 13 July 2015

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

©2015 American Physical Society

Authors & Affiliations

Walter Vinci1,2,3, Tameem Albash2,3,4, Gerardo Paz-Silva5,6, Itay Hen3,4, and Daniel A. Lidar1,2,3,7

  • 1Department of Electrical Engineering, University of Southern California, Los Angeles, California 90089, USA
  • 2Department of Physics and Astronomy, University of Southern California, Los Angeles, California 90089, USA
  • 3Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
  • 4Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
  • 5Centre for Quantum Computation and Communication Technology (Australian Research Council), Griffith University, Brisbane, Queensland 4111, Australia
  • 6Centre for Quantum Dynamics, Griffith University, Brisbane, Queensland 4111, Australia
  • 7Department 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. 92, Iss. 4 — October 2015

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
×