Commuting2qGateGrouper pass #8034

1ucian0 · 2022-05-09T21:37:45Z

The pass Commuting2qGateGrouper groups the commuting multi-qubit gates into Commuting2qBlock.

from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import CommutationAnalysis
from qiskit.transpiler.passes.routing import Commuting2qGateGrouper

from qiskit.circuit.library import TwoLocal

circuit = TwoLocal(5, "ry", "cz", entanglement='pairwise').decompose()
print(circuit.draw('text', fold=-1))

passmanager = PassManager()
passmanager.append([Commuting2qGateGrouper()])
result = passmanager.run(circuit)
print(result.draw('text', fold=-1))

     ┌──────────┐   ┌──────────┐               ┌───────────┐                ┌───────────┐             
q_0: ┤ Ry(θ[0]) ├─■─┤ Ry(θ[5]) ├─────────────■─┤ Ry(θ[10]) ├──────────────■─┤ Ry(θ[15]) ├─────────────
     ├──────────┤ │ └──────────┘┌──────────┐ │ └───────────┘┌───────────┐ │ └───────────┘┌───────────┐
q_1: ┤ Ry(θ[1]) ├─■──────■──────┤ Ry(θ[6]) ├─■───────■──────┤ Ry(θ[11]) ├─■───────■──────┤ Ry(θ[16]) ├
     ├──────────┤        │      ├──────────┤         │      ├───────────┤         │      ├───────────┤
q_2: ┤ Ry(θ[2]) ├─■──────■──────┤ Ry(θ[7]) ├─■───────■──────┤ Ry(θ[12]) ├─■───────■──────┤ Ry(θ[17]) ├
     ├──────────┤ │             ├──────────┤ │              ├───────────┤ │              ├───────────┤
q_3: ┤ Ry(θ[3]) ├─■──────■──────┤ Ry(θ[8]) ├─■───────■──────┤ Ry(θ[13]) ├─■───────■──────┤ Ry(θ[18]) ├
     ├──────────┤        │      ├──────────┤         │      ├───────────┤         │      ├───────────┤
q_4: ┤ Ry(θ[4]) ├────────■──────┤ Ry(θ[9]) ├─────────■──────┤ Ry(θ[14]) ├─────────■──────┤ Ry(θ[19]) ├
     └──────────┘               └──────────┘                └───────────┘                └───────────┘
     ┌──────────┐┌─────────────────────┐┌──────────┐┌─────────────────────┐┌───────────┐┌─────────────────────┐┌───────────┐
q_0: ┤ Ry(θ[0]) ├┤0                    ├┤ Ry(θ[5]) ├┤0                    ├┤ Ry(θ[10]) ├┤0                    ├┤ Ry(θ[15]) ├
     ├──────────┤│                     │├──────────┤│                     │├───────────┤│                     │├───────────┤
q_1: ┤ Ry(θ[1]) ├┤1                    ├┤ Ry(θ[6]) ├┤1                    ├┤ Ry(θ[11]) ├┤1                    ├┤ Ry(θ[16]) ├
     ├──────────┤│                     │├──────────┤│                     │├───────────┤│                     │├───────────┤
q_2: ┤ Ry(θ[2]) ├┤2 Commuting 2q gates ├┤ Ry(θ[7]) ├┤2 Commuting 2q gates ├┤ Ry(θ[12]) ├┤2 Commuting 2q gates ├┤ Ry(θ[17]) ├
     ├──────────┤│                     │├──────────┤│                     │├───────────┤│                     │├───────────┤
q_3: ┤ Ry(θ[3]) ├┤3                    ├┤ Ry(θ[8]) ├┤3                    ├┤ Ry(θ[13]) ├┤3                    ├┤ Ry(θ[18]) ├
     ├──────────┤│                     │├──────────┤│                     │├───────────┤│                     │├───────────┤
q_4: ┤ Ry(θ[4]) ├┤4                    ├┤ Ry(θ[9]) ├┤4                    ├┤ Ry(θ[14]) ├┤4                    ├┤ Ry(θ[19]) ├
     └──────────┘└─────────────────────┘└──────────┘└─────────────────────┘└───────────┘└─────────────────────┘└───────────┘

Testing is needed

qiskit-bot · 2022-05-09T21:37:47Z

Thank you for opening a new pull request.

Before your PR can be merged it will first need to pass continuous integration tests and be reviewed. Sometimes the review process can be slow, so please be patient.

While you're waiting, please feel free to review other open PRs. While only a subset of people are authorized to approve pull requests for merging, everyone is encouraged to review open pull requests. Doing reviews helps reduce the burden on the core team and helps make the project's code better for everyone.

One or more of the the following people are requested to review this:

@Qiskit/terra-core

coveralls · 2022-05-09T22:10:44Z

Pull Request Test Coverage Report for Build 2423044318

76 of 77 (98.7%) changed or added relevant lines in 5 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage increased (+0.02%) to 84.408%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/transpiler/passes/routing/commuting_2q_gate_routing/commuting_2q_gate_grouper.py	66	67	98.51%

Totals
Change from base Build 2409841148:	0.02%
Covered Lines:	54635
Relevant Lines:	64727

💛 - Coveralls

ajavadia · 2022-05-10T02:46:20Z

this is fine but at some point we should really do the generic things described here: #5775

Because all these things that we collect can be described by some condition on the gates inspected, to see whether they should be placed in the bucket or not. Here the condition is being a 2-qubit gate and commuting with the block, in #7361 the condition is being a linear gate (cx, swap, etc.), in Collect2qBlocks the condition is being a 2-qubit gate. Soon we will need to collect all cliffords. etc.

1ucian0 · 2022-05-10T10:41:41Z

we should really do the generic things described here: #5775

I agree, at least with the general principle. However, that seems to be a bigger project than this one.

eggerdj · 2022-05-25T14:16:54Z

Some preliminary testing from my end. First comment is that this plays nicely with the commuting gate router. For instance:

from qiskit.transpiler import PassManager, CouplingMap, Layout
from qiskit.transpiler.passes import CommutationAnalysis
from qiskit.transpiler.passes.routing.swap_strategies import Commuting2qGateGrouper, SwapStrategy
from qiskit.transpiler.passes import FullAncillaAllocation
from qiskit.transpiler.passes import EnlargeWithAncilla
from qiskit.transpiler.passes import ApplyLayout
from qiskit.transpiler.passes import SetLayout
from qiskit.transpiler.passes import Commuting2qGateRouter
from qiskit.circuit.library import TwoLocal

circuit = TwoLocal(5, "ry", "cz", entanglement='full', reps=2).decompose()
circuit.draw('mpl', fold=-1)

swap_strat = SwapStrategy.from_line([0, 1, 2, 3, 4])
backend_cmap = CouplingMap(couplinglist=[(0, 1), (1, 2), (1, 3), (3, 4), (4, 5), (5, 6)])
initial_layout = Layout.from_intlist([0, 1, 3, 4, 5], *circuit.qregs)

passmanager = PassManager(
    [
        CommutationAnalysis(), 
        Commuting2qGateGrouper(),
        Commuting2qGateRouter(swap_strat),
        SetLayout(initial_layout),
        FullAncillaAllocation(backend_cmap),
        EnlargeWithAncilla(),
        ApplyLayout(),
    ]
)

result = passmanager.run(circuit)
result.draw('mpl', fold=-1)

transpiles this

into this

eggerdj · 2022-05-25T14:24:23Z

This also looks good:

from qiskit import QuantumCircuit
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import CommutationAnalysis
from qiskit.transpiler.passes.routing.swap_strategies import Commuting2qGateGrouper

circ = QuantumCircuit(8)
circ.cz(0, 1)
circ.cz(2, 3)
circ.cz(0, 2)
circ.cz(1, 3)
circ.cz(0, 3)

circ.cz(5, 6)
circ.cz(6, 7)
circ.cz(5, 7)
print(circ.draw("text"))

passmanager = PassManager(
    [
        CommutationAnalysis(), 
        Commuting2qGateGrouper(),
    ]
)

print(passmanager.run(circ).draw("text"))

results in

q_0: ─■──■─────■─
      │  │     │ 
q_1: ─■──┼──■──┼─
         │  │  │ 
q_2: ─■──■──┼──┼─
      │     │  │ 
q_3: ─■─────■──■─
                 
q_4: ────────────
                 
q_5: ─■─────■────
      │     │    
q_6: ─■──■──┼────
         │  │    
q_7: ────■──■────
                 
     ┌─────────────────────┐
q_0: ┤0                    ├
     │                     │
q_1: ┤1                    ├
     │  Commuting 2q gates │
q_2: ┤2                    ├
     │                     │
q_3: ┤3                    ├
     └─────────────────────┘
q_4: ───────────────────────
     ┌─────────────────────┐
q_5: ┤0                    ├
     │                     │
q_6: ┤1 Commuting 2q gates ├
     │                     │
q_7: ┤2                    ├
     └─────────────────────┘

…s into Commuting2qBlock.

ajavadia · 2022-06-16T16:08:17Z

The second example posted by @eggerdj highlights that this is not quite grouping the commuting 2-qubit gates (because the top gates and bottom gates also commute). Rather it is grouping 2q gates that commute and act on contiguous qubits. This should be in the docstrings.

ajavadia · 2022-06-16T16:09:42Z

I agree, at least with the general principle. However, that seems to be a bigger project than this one.

Only slightly bigger. But it simplifies the transpiler quite a lot and prevents a bunch of ad-hoc passes that keep creeping in. I just saw another pass today that groups 2-qubit clifford gates.

mtreinish · 2022-06-22T13:40:23Z

releasenotes/notes/swap-strategies-3ab013ca60f02b36.yaml

-    made of commuting two-qubit terms. Here, a swap strategy is specified by the class
-    :class:`.SwapStrategy`. Swap strategies need to be tailored to the coupling map and, ideally,
-    the circuit for the best results.
+ - |


You need a release note for the new DAGCircuit method too since that's a new feature on that interface

mtreinish · 2022-06-22T13:41:31Z

qiskit/transpiler/passes/routing/commuting_2q_gate_routing/commuting_2q_gate_grouper.py

+
+
+class Commuting2qGateGrouper(TransformationPass):
+    """A pass that collapses 2-qubit gates that commute into :class:`.Commuting2qBlock`."""


You should update the docstring here to add the clarification that @ajavadia asked for in #8034 (comment)

mtreinish · 2022-06-22T13:43:54Z

qiskit/transpiler/passes/routing/commuting_2q_gate_routing/commuting_2q_gate_grouper.py

+        new_dag = dag.copy_empty_like()
+
+        for nd in dag.layered_topological_op_nodes():
+            if nd in self._done_nodes:


Why is this instance level? Isn't it per dag? What happens if this pass is run twice couldn't this accidentally eval true because of leftover instance state?

mtreinish · 2022-06-22T13:49:43Z

qiskit/transpiler/passes/routing/commuting_2q_gate_routing/commuting_2q_gate_grouper.py

+            else:
+                commuting_op_set = self._commutes_with(nd)
+                used_qarg = {qarg for node in commuting_op_set for qarg in node.qargs}
+                used_carg = {carg for node in commuting_op_set for carg in node.cargs}
+                new_dag.apply_operation_back(
+                    Commuting2qBlock(commuting_op_set),
+                    [qbit for qbit in dag.qubits if qbit in used_qarg],
+                    [cbit for cbit in dag.clbits if cbit in used_carg],
+                )


I'm a bit confused here, what happens if there is a 2q gate that's not in a commuting set? Like if you have a standalone swap on 2 qubits won't this collapse that into a Commuting2qBlock of a gate? That doesn't seem desirable. For example:

from qiskit.circuit import QuantumCircuit from qiskit.transpiler import PassManager, CouplingMap from qiskit.transpiler.passes import Commuting2qGateGrouper circ = QuantumCircuit(4) circ.cx(0, 1) circ.cx(1, 2) cmap = CouplingMap([[0, 1], [1, 2], [1, 3], [3, 4]]) cmap.make_symmetric() passmanager = PassManager([Commuting2qGateGrouper()]) res = passmanager.run(circ) print(res)

outputs:

┌─────────────────────┐ q_0: ┤0 ├─────────────────────── │ Commuting 2q gates │┌─────────────────────┐ q_1: ┤1 ├┤0 ├ └─────────────────────┘│ Commuting 2q gates │ q_2: ───────────────────────┤1 ├ └─────────────────────┘ q_3: ──────────────────────────────────────────────

and each group just contains a single cx gate.

this is a good point. A communitation block with a single gate should not be created. Is that what you say?

Yeah I think that would address it, basically we should leave gates alone if they're not part of a commuting set since wrapping them just to unwrap them adds a bunch of unnecessary overhead.

mtreinish · 2022-06-22T14:38:37Z

qiskit/transpiler/passes/routing/commuting_2q_gate_routing/commuting_2q_gate_grouper.py

+        new_dag = dag.copy_empty_like()
+
+        for nd in dag.layered_topological_op_nodes():


Instead of creating a new dag and iteratively adding all the operations to it like this, did you consider do an in place modification using replace_block_with_op? We do this in consolidate blocks (which seems very similar to this pass): https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/transpiler/passes/optimization/consolidate_blocks.py#L116 I'm not sure which would have better performance but it's worth looking at.

mtreinish · 2022-06-22T14:42:04Z

test/python/transpiler/test_commuting2q_router.py

+from qiskit.test import QiskitTestCase
+
+
+class TestCommuting2qGateGrouperRouting(QiskitTestCase):


I feel like the tests here could be a bit more thorough and targetted to just the new Commuting2qGateGrouper pass's behavior. Like it'd be good to test what the pass does with an empty dag, dags that have no 2q gates, that commuting gates are correctly grouped, etc. having the full path tests are good but I think we should test things in isolation on the new feature here too.

1ucian0 added this to the 0.21 milestone May 28, 2022

1ucian0 marked this pull request as ready for review May 28, 2022 20:06

1ucian0 requested a review from a team as a code owner May 28, 2022 20:06

1ucian0 added 2 commits June 1, 2022 18:36

The pass Commuting2qGateGrouper groups the commuting multi-qubit gate…

935351a

…s into Commuting2qBlock.

missing files

9112225

1ucian0 force-pushed the commutative_2q_analysis branch from bf8521e to 9112225 Compare June 1, 2022 16:38

ShellyGarion modified the milestone: 0.21 Jun 14, 2022

mtreinish self-assigned this Jun 14, 2022

mtreinish reviewed Jun 22, 2022

View reviewed changes

mtreinish modified the milestones: 0.21, 0.22 Jun 23, 2022

alexanderivrii mentioned this pull request Jul 4, 2022

Refactoring commutativity analysis and a new commutative inverse cancellation transpiler pass #8184

Merged

This was referenced Jul 11, 2022

collapsing a chain of gates #5775

Open

[WIP] block collection strategies #8319

Closed

mtreinish removed this from the 0.22 milestone Sep 23, 2022

alexanderivrii mentioned this pull request Nov 2, 2022

Adding CollectAndCollapse transpiler pass #8907

Merged



		class Commuting2qGateGrouper(TransformationPass):
		"""A pass that collapses 2-qubit gates that commute into :class:`.Commuting2qBlock`."""

		new_dag = dag.copy_empty_like()

		for nd in dag.layered_topological_op_nodes():

		from qiskit.test import QiskitTestCase


		class TestCommuting2qGateGrouperRouting(QiskitTestCase):

Commuting2qGateGrouper pass #8034

Are you sure you want to change the base?

Commuting2qGateGrouper pass #8034

Uh oh!

Conversation

1ucian0 commented May 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

qiskit-bot commented May 9, 2022

Uh oh!

coveralls commented May 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 2423044318

💛 - Coveralls

Uh oh!

ajavadia commented May 10, 2022

Uh oh!

1ucian0 commented May 10, 2022

Uh oh!

eggerdj commented May 25, 2022

Uh oh!

eggerdj commented May 25, 2022

Uh oh!

ajavadia commented Jun 16, 2022

Uh oh!

ajavadia commented Jun 16, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

1ucian0 commented May 9, 2022 •

edited

Loading

coveralls commented May 9, 2022 •

edited

Loading