Adiabatic quantum programming: Minor embedding with hard faults

Christine Klymko, Blair D. Sullivan, Travis S. Humble

Research output: Contribution to journalArticlepeer-review

68 Scopus citations

Abstract

Adiabatic quantum programming defines the time-dependent mapping of a quantum algorithm into an underlying hardware or logical fabric. An essential step is embedding problem-specific information into the quantum logical fabric. We present algorithms for embedding arbitrary instances of the adiabatic quantum optimization algorithm into a square lattice of specialized unit cells. These methods extend with fabric growth while scaling linearly in time and quadratically in footprint. We also provide methods for handling hard faults in the logical fabric without invoking approximations to the original problem and illustrate their versatility through numerical studies of embeddability versus fault rates in square lattices of complete bipartite unit cells. The studies show that these algorithms are more resilient to faulty fabrics than naive embedding approaches, a feature which should prove useful in benchmarking the adiabatic quantum optimization algorithm on existing faulty hardware.

Original languageEnglish
Pages (from-to)709-729
Number of pages21
JournalQuantum Information Processing
Volume13
Issue number3
DOIs
StatePublished - Mar 2014

Funding

Acknowledgments This work was supported by the Lockheed Martin Corporation under Contract No. NFE-11-03394. The authors thank Greg Tallant (Lockheed) for technical interchange and Daniel Pack (ORNL) for help preparing Fig. 2. This manuscript has been authored by a contractor of the U.S. Government under Contract No. DE-AC05-00OR22725. Accordingly, the U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes.

Keywords

  • Adiabatic quantum optimization
  • Fault-tolerant computing
  • Graph embedding
  • Quantum computing

Fingerprint

Dive into the research topics of 'Adiabatic quantum programming: Minor embedding with hard faults'. Together they form a unique fingerprint.

Cite this