Faculty Recruiting Support CICS

Graph Minor Embeddings, Circuit Layouts, and Quantum Annealing

10 Apr
Wednesday, 04/10/2019 12:15pm to 1:15pm
Computer Science Building Room 140
Theory Seminar
Speaker: Jamie Tucker-Foltz

Quantum annealing is as a quantum computing technology designed to solve one specific problem: the Ising model optimization problem. To use a quantum annealer, the user needs to translate their problem instance into an Ising model and map its variables to specific qubits. One of the most difficult steps in this translation process involves embedding the graph representing the input as a minor of the graph representing the hardware architecture of the device. The intractability of this minor embedding problem is a bottleneck, limiting the scale of instances that can be optimized on a quantum annealer.

In this talk, I will give a brief overview of quantum annealing, how it is different from more common quantum computing approaches, and how the minor embedding problem naturally arises. I will then discuss the theoretical connection between the minor embedding problem and the VLSI layout problem (which comes from the literature on computer chip / circuit design). This connection suggests that, by leveraging the grid-like structures of common quantum annealing architectures, algorithms for the VLSI layout problem can be adapted to produce more compact minor embeddings. I will present a new algorithm for minor embedding based on this idea, which performs very well empirically. This talk should be very accessible, assuming no prior knowledge of graph minor theory or quantum computing.