Transpiler pass to convert SWAP-CX-SWAP to BridgeGate

[kdk]

What is the expected enhancement?

The bridge gate (definition in https://arxiv.org/pdf/1907.02686.pdf , ref. Fig. 2) allows for an effective CX gate across next-nearest-neighbors and has been shown to improve, in some cases substantially, the two-qubit output depth of routed circuits. With the exception of #1803 , the current in-tree routing passes are not aware of the bridge gate, and so, in some cases, may output a subcircuit like:

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

which could be equivalently replaced with an application of the bridge gate like:

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

with a lower overall cost (four instead of seven two-qubit gates).

It would be beneficial to have a transpiler pass which runs post-routing to find instances where a routing pass inserted a SWAP-CX-SWAP and replaces it with a bridge gate. This allows for all non-bridge aware routing passes to take advantage of the bridge gate, without requiring them to be updated individually. (Doing so may be an interesting future enhancement, as it would allow the heuristics used by the routing passes to calculate the cost of a bridge operation correctly.)

To accomplish this:

• [ ] Add a BridgeGate to qiskit.circuit.library.standard_gates (Can use #5609 as an example of adding a gate to the standard library)
• [ ] Add a transpiler pass SwapCXSwapToBridge which identifies cases where a circuit contains a SWAP-CX-SWAP and replaces it with the equivalent BridgeGate.

N.B. That this optimization can be applied even if the middle CX gate is in the reversed direction, or has adjacent single qubit gates, but these can be added separately after the initial implementation.

[1ucian0]

It would be great if the pass can be applied to the commutation graph.

For example:

        ┌───┐┌───┐                   ┌────────┐┌───┐               
q_0: ───┤ X ├┤ H ├───        q_0: ───┤        ├┤ H ├─────          
        └─┬─┘└───┘                   │        │└───┘┌───┐          
q_1: ─X───■────■───X─    =>  q_1: ───┤ bridge ├─────┤ X ├          
      │      ┌─┴─┐ │                 │        │     └─┬─┘          
q_2: ─X──────┤ X ├─X─        q_2: ───┤        ├───────■──          
             └───┘                   └────────┘                    

(I'm not even sure if this is possible)

[boschmitt]

In the the new version of tweedledum that will become a hard dependency for Qiskit-terra(#6588), there is some experimental passes that can handle these sort of optimization through coupling-constrained linear resynthesis:

from qiskit.circuit import QuantumCircuit, QuantumRegister
from qiskit.dagcircuit.dagcircuit import DAGCircuit
from qiskit.circuit.library.standard_gates import CXGate, SwapGate
from qiskit.converters import circuit_to_dag, dag_to_circuit
from tweedledum.target import Device
from tweedledum.qiskit.passes.optimization import SteinerResynth
circuit = QuantumCircuit(3)
circuit.append(SwapGate(), [0, 1])
circuit.append(CXGate(), [1, 2])
circuit.append(SwapGate(), [0, 1])
print(circuit)
device = Device.path(3)
opt_pass = SteinerResynth(device)
opt_circuit = opt_pass.run(circuit_to_dag(circuit))
print(dag_to_circuit(opt_circuit))

q_0: ─X───────X─
      │       │ 
q_1: ─X───■───X─
        ┌─┴─┐   
q_2: ───┤ X ├───
        └───┘   
q0_0: ───────■─────────■──
           ┌─┴─┐     ┌─┴─┐
q0_1: ──■──┤ X ├──■──┤ X ├
      ┌─┴─┐└───┘┌─┴─┐└───┘
q0_2: ┤ X ├─────┤ X ├─────
      └───┘     └───┘     

I can also handle @1ucian0 example:

             ┌───┐   
q_0: ─X──────┤ X ├─X─
      │      └─┬─┘ │ 
q_1: ─X───■────■───X─
        ┌─┴─┐┌───┐   
q_2: ───┤ X ├┤ H ├───
        └───┘└───┘   

q0_0: ───────■────────────
           ┌─┴─┐          
q0_1: ──■──┤ X ├──■───────
      ┌─┴─┐└───┘┌─┴─┐┌───┐
q0_2: ┤ X ├─────┤ X ├┤ H ├
      └───┘     └───┘└───┘

But if it won't be able to commute through "non-linear" gates (ex: ZGate):

                  ┌───┐   
q_0: ─X───────────┤ X ├─X─
      │      ┌───┐└─┬─┘ │ 
q_1: ─X───■──┤ Z ├──■───X─
        ┌─┴─┐├───┤        
q_2: ───┤ X ├┤ H ├────────
        └───┘└───┘        
                        ┌───┐
q0_0: ─X─────────────■──┤ X ├
       │      ┌───┐┌─┴─┐└─┬─┘
q0_1: ─X───■──┤ Z ├┤ X ├──■──
         ┌─┴─┐├───┤└───┘     
q0_2: ───┤ X ├┤ H ├──────────
         └───┘└───┘