[RFC] Unrolling

[1ucian0]

The problem

There is a need to support unrolling to a broader set of gate basis (see #3086). Additionally, supporting multiple decompositions are growing (see #3067).

Use cases

Our unrolling mechanism should support the following situations:

• UC1 "circular" decompositions: should be able to handle situations like CX -> Rxx -> CX.
• UC2 Decomposition to unitary: If the basis supports unitary and there is no further possible decomposition for a gate that is not in the basis, the gate should be transformed to unitary.
• UC3 Consider the cost of synthesis: The unitary -> U transformation is particularly expensive. While it should be possible, unrolling should consider that cost.
• UC4 A user should be able to add a new possible decomposition for a gate or to choose which decomposition should be used.

Optional features

It would be nice to also support the following situations:

• OF1 @chriseclectic requires some gates to be reduced to unitary, even when they are in the basis. Currently, this is solved with labels.

basis: [h, unitary]
--[h]--[h]--   =>  --[unitary]--[h]--

[chriseclectic]

In terms of synthesis you may also want to choose between different algorithms or input a custom one. Simple example for single qubit unitaries is you could synthesis to u3, u1+x90, rx+ry or rx+rz gates.

[1ucian0]

from @chriseclectic in #3146 (comment) :

In terms of synthesis you may also want to choose between different algorithms or input a custom one.

May I add it as optional? Or do you think is a "must to have"?

[1ucian0]

Proposal: multiple prioritized decompositions

Supporting multiple possible decomposition per gate might allow to signal the unroller on how to unroll each gate until the basis gate set is reached. The decompositions are sorted by preference. ie, in cx: [{h, cz}, {rxx}, {unitary}], cx will be decomposed as {h, cz} before trying {rxx}.

Consider the coming examples using the following decomposition rules:

cx: [{h, cz}, {rxx}, {unitary}]
rxx: [{cx}, {unitary}]
cz: [{h, cx}, {unitary}]
h: [{u}, {unitary}]
u: [{unitary}]
unitary: [{u}]  # via synthesis

cuasi-implementation:

def decompose(gate, basis, visited=None):
    if gate in basis:
        return [gate]

    if visited is None:
        visited = set()

    if gate in visited:
        return [None]  # No decomposition was found on this branch

    visited.add(gate)  #avoids inf loops

    decompositions = decompositions_db[gate]
    for decomposition in decompositions:
        candidate = []
        for subgate in decomposition:
            candidate.append(decompose(subgate, basis, visited))
        if None not in candidate:  # is it a valid decomposition?
            return candidate  # once a valid decomposition is found, return it.
    return None  # no decomposition was found

for gate in circuit:
    circuit.replace(gate, decompose(gate, basis))  #replaces gate with its decomposition

• The visited set avoids infinite recursion (UC1).
• If a particular gate instance prefers a particular decomposition over another one, it needs to reorder its decompositions property to express the new priority order (UC4 OF1)
• By default, unitary is the lowest priority for all the gates (except unitary) (UC2)
• Synthesis is only considered (by default) if the circuit has a unitary and the basis has u (UC3).

To implement this proposal:

• .definition can be removed.
• decompositions is a list of DAGs.
• DAGs should provide a way to know "its basis" i.e. the gates that are used in the DAG.
• A mechanism to rearrange and add decompositions is needed.

Problems:

• When there are more than one possible decompositions, it's not defined which is prefered. For example, cx can be decomposed to the basis {rxx, u} as cx->[h, cz]->[[u], [u]] or cx->rxx. This can be fixed by first constructing the decomposition tree and then analyzing it to search for the shortest path (to improve the efficiency of the unroller) or the shortest result (to improve the depth of the resulting circuit).

Footnotes:
[1] Since order of the gates and repetition can be ignored to the purpose of the problem, the examples are in terms of set. However, this does not implies that the possible implementation should.

[kdk]

I think that moving away from Instruction.definition toward a library of equivalence is a step in the right direction.

Opinions:

• Equivalent gate decompositions should be unordered. Before knowing the circuit and target basis, It will be difficult to know how to choose a good order. This can be left either to the unroller to search for or user to specify.
• The decision to select one or preferentially order decompositions should live outside of the Gate class. This way we can avoid shared global state for cases where a user wants to unroll a circuit more than once, using different decomposition strategies.

Questions:

• unitary and synthesis: Do we have a good idea of the use cases where users want to use unitary gates? Currently, oneQ and twoQ unitaries will be synthesized by default via .definition so it can be somewhat confusing to think about what the expected output will be. I wonder if the use cases are narrow enough that we can ask users to specify explicitly when they want to send a given gate as a unitary.

• Variable-arity gates (e.g. global MS from Add global Molmer-Sorenson gate #3149): Some gates are defined over a variable number of q/cbits (even without broadcasting.) If a gate can have variable shape, how do we record its definition?

[kdk]

@mtreinish raised a good question in #1435:

If we build to a library of equivalent DAGs, how can we make sure that users or passes don't inadvertently modify them and alter their behavior in subsequent circuits?

[1ucian0]

Equivalent gate decompositions should be unordered. Before knowing the circuit and target basis, It will be difficult to know how to choose a good order. This can be left either to the unroller to search for or user to specify.

Would be fair to say that they should be ordered at unrolling-time? I think would be easier to have a "default" order that can be modified. But I'm also okey with having them without any priority and set that priority immediately before unrolling (I'm not sure how the API would look like)

The decision to select one or preferentially order decompositions should live outside of the Gate class. This way we can avoid shared global state for cases where a user wants to unroll a circuit more than once, using different decomposition strategies.

you mean transpile different circuits with different unrolling strategies? Like unrolling differently circuit1 and circuit2 in transpiler([circuit1, circuit2])?

unitary and synthesis: Do we have a good idea of the use cases where users want to use unitary gates? Currently, oneQ and twoQ unitaries will be synthesized by default via .definition so it can be somewhat confusing to think about what the expected output will be. I wonder if the use cases are narrow enough that we can ask users to specify explicitly when they want to send a given gate as a unitary.

Sure.. it could be. In general, unrolling should be "lazy" ie no call until that unroll is necessary.

Variable-arity gates (e.g. global MS from #3149): Some gates are defined over a variable number of q/cbits (even without broadcasting.) If a gate can have variable shape, how do we record its definition?

I think this is also solvable by having callables as decompositions, which is consistent with the synthesis situation. What do you think? I can modify the proposal to "decompositions is a list of callables that return a DAG".

[shaimach]

IMHO, gate mapping is an arbitrary directed graph: one may specify multiple decompositions per gate, and loops are allowed.

The backend defines the set of physically implemented gates (or in case of a simulator, all of them), which then allows the graph to be transformed into a DAG via Breadth-first search (BFS) from the physical gates.

This way we separate gate mappings from the physical basis set.