Repository: BQSKit/bqskit

Issue:
Synthesized circuits have 2-qubit gates with > 3 CNOTs
In some cases, synthesizing eg a 3-qubit unitary gives a block with 4 or 5 layers of e.g. 
`cx q[1], q[2];`
separated by single-qubit gates.

This seems like an easy type of block to look for, then the number of CNOTs on the same pair of qubits can be limited to no more than 3 in a row.

Discussion:

Patch:
diff --git a/bqskit/passes/search/generators/fourparam.py b/bqskit/passes/search/generators/fourparam.py
index e03e883..f8ca437 100644
--- a/bqskit/passes/search/generators/fourparam.py
+++ b/bqskit/passes/search/generators/fourparam.py
@@ -76,8 +76,13 @@ class FourParamGenerator(LayerGenerator):
         # Generate successors
         successors = []
         for edge in coupling_graph:
+
+            if self.count_outer_cnots(circuit, edge) >= 3:
+                # No need to build circuits with more than 3 cnots in a row
+                continue
+
             successor = circuit.copy()
-            successor.append_gate(CNOTGate(), [edge[0], edge[1]])
+            successor.append_gate(CNOTGate(), edge)
             successor.append_gate(RYGate(), edge[0])
             successor.append_gate(RZGate(), edge[0])
             successor.append_gate(RYGate(), edge[1])
@@ -85,3 +90,35 @@ class FourParamGenerator(LayerGenerator):
             successors.append(successor)
 
         return successors
+
+    def count_outer_cnots(self, circuit: Circuit, edge: tuple[int, int]) -> int:
+        """
+        Count how many uninterrupted 4-param cnot blocks are on `edge`.
+
+        This will count backwards from the right-side of the circuit and stop
+        when a cnot is encountered including other qudits.
+        """
+        rear_point = circuit._rear[edge[0]]
+        num_cx_seen = 0
+
+        while rear_point is not None:
+            rear_points = circuit.prev(rear_point)
+
+            if len(rear_points) == 0:
+                break
+
+            rear_point = rear_points.pop()
+
+            if circuit[rear_point].num_qudits == 1:
+                # Move past single-qubit gates
+                continue
+
+            cx_op = circuit[rear_point]
+
+            if cx_op.location != edge:
+                # If CX is on a different edge stop counting
+                break
+
+            num_cx_seen += 1
+
+        return num_cx_seen


Test patch:
diff --git a/tests/passes/search/generators/test_four_param.py b/tests/passes/search/generators/test_four_param.py
new file mode 100644
index 0000000..c523736
--- /dev/null
+++ b/tests/passes/search/generators/test_four_param.py
@@ -0,0 +1,54 @@
+from __future__ import annotations
+
+from bqskit.ir import Circuit
+from bqskit.ir.gates import CNOTGate
+from bqskit.ir.gates import RXGate
+from bqskit.ir.gates import RYGate
+from bqskit.ir.gates import RZGate
+from bqskit.ir.gates.parameterized.u3 import U3Gate
+from bqskit.passes.search.generators import FourParamGenerator
+
+
+def test_fringe_cnot_count_empty_circuit() -> None:
+    gen = FourParamGenerator()
+    assert gen.count_outer_cnots(Circuit(1), (0, 1)) == 0
+
+
+def test_fringe_cnot_count_2q_circuit() -> None:
+    gen = FourParamGenerator()
+    circuit = Circuit(2)
+    circuit.append_gate(U3Gate(), 0)
+    circuit.append_gate(U3Gate(), 1)
+    for i in range(1, 10):
+        circuit.append_gate(CNOTGate(), (0, 1))
+        circuit.append_gate(RYGate(), 0)
+        circuit.append_gate(RZGate(), 0)
+        circuit.append_gate(RYGate(), 1)
+        circuit.append_gate(RXGate(), 1)
+        assert gen.count_outer_cnots(circuit, (0, 1)) == i
+
+
+def test_fringe_cnot_count_4q_circuit() -> None:
+    gen = FourParamGenerator()
+    circuit = Circuit(4)
+    for i in range(4):
+        circuit.append_gate(U3Gate(), i)
+
+    circuit.append_gate(CNOTGate(), (0, 1))
+    circuit.append_gate(RYGate(), 0)
+    circuit.append_gate(RZGate(), 0)
+    circuit.append_gate(RYGate(), 1)
+    circuit.append_gate(RXGate(), 1)
+    circuit.append_gate(CNOTGate(), (2, 3))
+    circuit.append_gate(RYGate(), 2)
+    circuit.append_gate(RZGate(), 2)
+    circuit.append_gate(RYGate(), 3)
+    circuit.append_gate(RXGate(), 3)
+
+    for i in range(1, 10):
+        circuit.append_gate(CNOTGate(), (1, 2))
+        circuit.append_gate(RYGate(), 1)
+        circuit.append_gate(RZGate(), 1)
+        circuit.append_gate(RYGate(), 2)
+        circuit.append_gate(RXGate(), 2)
+        assert gen.count_outer_cnots(circuit, (1, 2)) == i