Routing is applied to 2-qubit custom gates that don't need routing

[chriseclectic]

Environment

• Qiskit Terra version: 0.21
• Python version: 3.9
• Operating system: MacOS

What is happening?

When using custom gates which should transpile to separable single qubit gates, the transpiler is appling routing passes to these which results in the insertion of lots of swap/cx gates in a circuit that shouldn't be there.

How can we reproduce the issue?

Here is a minimal example:

Define a custom N-qubit gate with a definition in terms of 1-qubit gates:

class BadGate(Gate):
    
    def __init__(self, num_qubits: int):
        super().__init__("bad", num_qubits, [])
    
    def _define(self):
        qr = QuantumRegister(self.num_qubits, 'q')
        qc = QuantumCircuit(qr)
        for q in qr:
            qc._append(XGate(), [q], [])
        self.definition = qc

Apply this gate across 2-qubits not in coupling map and transpile

qc = QuantumCircuit(3)
qc.append(BadGate(2), [0, 2])

coupling_map = [[0, 1], [1, 0], [1, 2], [2, 1]]
tqc = transpile(qc, basis_gates=['x', 'cx'], coupling_map=coupling_map, initial_layout=range(3))

Produces the following circuit:

         ┌───┐               
q_0 -> 0 ┤ X ├───────────────
         ├───┤     ┌───┐┌───┐
q_1 -> 1 ┤ X ├──■──┤ X ├┤ X ├
         └─┬─┘┌─┴─┐└─┬─┘└───┘
q_2 -> 2 ──■──┤ X ├──■───────
              └───┘          

If "cx" isn't include in the basis gates above a transpiler error will be raised about being unable to map swaps to give basis.

If initial layout is not included, it will remap the qubist that dont need remapping (but avoid adding swaps). This has a separate bug of adding an additional qubit to the circuit that is not even in the coupling map (returns 4-qubit circuit for this example)

tqc = transpile(qc, basis_gates=['x', 'cx'], coupling_map=coupling_map)
                    
ancilla_0 -> 0 ─────
               ┌───┐
      q_0 -> 1 ┤ X ├
               ├───┤
      q_2 -> 2 ┤ X ├
               └───┘
      q_1 -> 3 ─────

Importantly this only happens if the custom gate is 2-qubit, if its a 3+ qubit gates, routing seems to be skipped and things behave as expected:

qc = QuantumCircuit(3)
qc.append(BadGate(3), [0, 1, 2])
tqc = transpile(qc, basis_gates=['x'],
    coupling_map=coupling_map, initial_layout=range(3))

produces

         ┌───┐
q_0 -> 0 ┤ X ├
         ├───┤
q_1 -> 1 ┤ X ├
         ├───┤
q_2 -> 2 ┤ X ├
         └───┘

What should happen?

Running the above 2-qubit example should return the circuit equivalent to qc.decompose() , Eg

     ┌───┐
q_0: ┤ X ├
     └───┘
q_1: ─────
     ┌───┐
q_2: ┤ X ├
     └───┘

Any suggestions?

I would expect that this requires that unrolling to intended final basis gates needs to happen before any routing is done, but currently it seems routing is done on any opaque 2-qubit gate regardless of its definition and whether it is in basis gates or not.

[jakelishman]

There's an advantage to doing the basis translation later, in that then the layout and routing passes have to do less work (because there's fewer gates in the circuit). Doing the basis translation too early may also get in the way of high-level synthesis routines.

Perhaps a sensible compromise is to replace the Unroll3qOrMore pass with one that also splits custom instructions (by an unrolling or translation approach) into subinstructions that act on separate qubits - the DAG methods for determining the partition already exist.

The reason it is the way it is now is because none of the layout/routing algorithms can cope with 3q gates really (and the old coupling map assumed that notl native 3q could exist), so they needed to be unrolled prior.

[chriseclectic]

I'll add that this bug directly applies to the build in PauliGate which is of this form (which is close to how I found the bug). The above example can be replaced with

qc = QuantumCircuit(3)
qc.pauli('XX', [0, 2])

[jakelishman]

Yeah, the mechanism is fairly clear from how our layout/routing passes work, I think - there's an assumption built in that any object that appears to operate on 2 qubits necessarily requires coupling between the two. It's hard to untangle that right now, but a rework of the (role taken by the) Unroll3qOrMore pass like I was talking about above should hopefully get us around these problems in the near term.

[mtreinish]

This has almost been fixed by the Split2QUnitaries pass https://docs.quantum.ibm.com/api/qiskit/qiskit.transpiler.passes.Split2QUnitaries which should decompose the 2 qubit gate into two single qubit unitaries (after it's been collected into a 2q block). Although that pass only runs at optimizations levels 2 and 3 but I think this is ok because the output is still valid, just not as optimized (which is kind of what optimization levels are for).

However running the reproduce script with level 2 locally on 1.2.1 is still inserting a swap because it's not collecting BadGate into a unitary because there is only a single gate in the block. The consolidation pass doesn't thing it's worth substituting BadGate for a UnitaryGate because there is only a single gate. It actually would have worked before #13095 but that was necessary because the pass was causing issues with incomplete single qubit basis gates. There are options on the ConsolidateBlocks pass to force it to do this consolidation but using them may have side effects which we'll need to test.