The layout problem as a Max-SAT problem

[1ucian0]

Abstract

The PR https://github.com/Qiskit/qiskit-terra/pull/3043 introduced the idea of solving the mapping problem (convert the circuit to run in a real device the coupling map) as a CSP. There are probably other similar approaches to, for example, minimize the amount of required swaps.

Description

The mapping problem can be explained by the following example. Imagine a device with the following coupling map:

[0]-[1]-[2]

That means that the device allows to entanglement between the qubits [0]/[1] and [1]/[2]. Now, let's take the following circuit (those gate that are not CX are ignored for the goal of this explanation):

q0 --.--.--
     |  |
q1 --+--|--
        |
q2 -----+--

The idea is to map the circuit into the coupling map. q0 needs to be connected in the coupling map with q1 and q2 so the circuit can execute in the given hardware. For that we have to modified the circuit inserting as few gates as possible. How to do it is what we called the mapping problem. The problem is two-folded: The layout selection and the swapper algorithm.

Layout selection

The presented circuit can allocate the virtual qubits (q0, q1, q2) in specific physical qubits ([0], [1], [2]). For example if we choose the following layout q1->[0], q0->[1], and q2->[2] the connections between q0/q1 and q0/q2 exist in the coupling map and no further modification is need.

However, what if the following CX is added:

q0[1] --.--.----
        |  |
q1[0] --+--|--.--
           |  |
q2[2] -----+--+--

Now q1/q2 needs to exist in the coupling map. Using the defined layout, that means that the edge [0]/[2] is required, which is not the case in coupling map [0]-[1]-[2]. This circuit needs to be modified by a swapper:

The swapper

A swapper is an algorithm that introduce swap gates. This allows to cross cables. The flow from the upper cable continues in the lower one after the swap:

>--X--     >--\ /--
   |    =      X
 --X-->     --/ \-->

In the last circuit example, the swapper should be inserted a before the last CX:

q0[1] --.--.--X--.-- [0]
        |  |  |  |
q1[0] --+--|--X--|-- [1]
           |     |
q2[2] -----+-----+-- [2]

After the swap, the intermediate layout is q0->[0], q1->[0], and q2->[2]. Because the swap, the control that was in q1 now was moved to q0.

The project

It's relatively simple to create algorithms to select a layout or swappers that simply solved the problem. However, it is hard to do it efficiently. Swap gates are particularly expensive and introduced errors in the result. It is key to do it smartly.

In PR Qiskit/qiskit-terra#3043, the author used python-constraint to do layout selection, using backtracking. While fast, the approach is limited, because either works or not i.e. it chooses a layout if possible or gives up and no layout is selected. There is no middle ground. Without being an expert, the author suspects that integer programming can be used as a best effort (connects as much as CXs as possible before running the swapper).

Maybe the swapper itself can be model as an optimization problem.

Members

• Hartwig Bauer
• Bruno Schmitt
• Lukas Burgholzer
• Qiskit Coach: @1ucian0 - Slack @luciano

Deliverable

Transpiler pass(es)

GitHub repo

tbd

[1ucian0]

https://developers.google.com/optimization/mip/integer_opt_cp

[itoko]

This paper would be interesting for this project members.

Depth-Optimal Quantum Circuit Placement for Arbitrary Topologies https://arxiv.org/abs/1703.08540

It provides MIP formulation of the mapping problem (objective is minimization of circuit depth, though) under given fixed layers.

[boschmitt]

I would be interested in this if not killed. Bruno Schmitt, Computer Scientist (:

[burgholzer]

I'm in, Lukas Burgholzer, CS

[HartwigB]

I'm in, Hartwig Bauer, CS

[boschmitt]

Code in https://github.com/boschmitt/qiskit-terra

Two branches (different approaches):

• maxSAT_layout
• burgholzer

[burgholzer]

final_presentation.pptx