Presentation
Layout-Aware Embedding for Quantum Annealing Processors
Event Type
Research Paper
AI/Machine Learning/Deep Learning
Autonomous Driving
TimeTuesday, June 18th8:30am - 9am
LocationAnalog 1, 2
DescriptionDue to the physical limit in connectivity between qubits in Quantum Annealing
Processors (QAPs), when sampling from a problem formulated as an Ising graph
model, it is necessary to embed the problem onto the physical
lattice of qubits. A valid mapping of the problem nodes into qubits
often requires qubit chains to ensure connectivity.
We introduce the concept of layout-awareness for embedding; wherein
information about the layout of the input and target graphs is used to guide
the allocation of qubits to each problem node. We then evaluate the consequent
impact on the sampling distribution obtained from D-Wave's QAP, and provide a
set of tools to assist developers in targeting QAP architectures using
layout-awareness. We quantify the results from a layout-agnostic and a
layout-aware embedding algorithm on (a) the success rate and time at finding
valid embeddings, (b) the metrics of the resulting chains and interactions, and
(c) the energy profile of the annealing samples. The latter results are obtained
by running experiments on a D-Wave Quantum Annealer, and are directly related to
the ability of the device to solve complex problems.
Our technique effectively reduces the search space, which improves the time and
success rate of the embedding algorithm and/or finds mappings that result in
lower energy samples from the QAP. Together, these contributions are an important
step towards an understanding of how near-future Computer-Aided Design (CAD) tools
can work in concert with quantum computing technologies to solve previously
intractable problems.
Processors (QAPs), when sampling from a problem formulated as an Ising graph
model, it is necessary to embed the problem onto the physical
lattice of qubits. A valid mapping of the problem nodes into qubits
often requires qubit chains to ensure connectivity.
We introduce the concept of layout-awareness for embedding; wherein
information about the layout of the input and target graphs is used to guide
the allocation of qubits to each problem node. We then evaluate the consequent
impact on the sampling distribution obtained from D-Wave's QAP, and provide a
set of tools to assist developers in targeting QAP architectures using
layout-awareness. We quantify the results from a layout-agnostic and a
layout-aware embedding algorithm on (a) the success rate and time at finding
valid embeddings, (b) the metrics of the resulting chains and interactions, and
(c) the energy profile of the annealing samples. The latter results are obtained
by running experiments on a D-Wave Quantum Annealer, and are directly related to
the ability of the device to solve complex problems.
Our technique effectively reduces the search space, which improves the time and
success rate of the embedding algorithm and/or finds mappings that result in
lower energy samples from the QAP. Together, these contributions are an important
step towards an understanding of how near-future Computer-Aided Design (CAD) tools
can work in concert with quantum computing technologies to solve previously
intractable problems.
