Title: Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework,
Abstract: Adiabatic quantum computing has evolved in recent years from a theoretical
field into an immensely practical area, a change partially sparked by D-Wave
System's quantum annealing hardware. These multimillion-dollar quantum
annealers offer the potential to solve optimization problems millions of times
faster than classical heuristics, prompting researchers at Google, NASA and
Lockheed Martin to study how these computers can be applied to complex
real-world problems such as NASA rover missions. Unfortunately, compiling
(embedding) an optimization problem into the annealing hardware is itself a
difficult optimization problem and a major bottleneck currently preventing
widespread adoption. Additionally, while finding a single embedding is
difficult, no generalized method is known for tuning embeddings to use minimal
hardware resources. To address these barriers, we introduce a graph-theoretic
framework for developing structured embedding algorithms. Using this framework,
we introduce a biclique virtual hardware layer to provide a simplified
interface to the physical hardware. Additionally, we exploit bipartite
structure in quantum programs using odd cycle transversal (OCT) decompositions.
By coupling an OCT-based embedding algorithm with new, generalized reduction
methods, we develop a new baseline for embedding a wide range of optimization
problems into fault-free D-Wave annealing hardware. To encourage the reuse and
extension of these techniques, we provide an implementation of the framework
and embedding algorithms.