Support control flow in CommutationAnalysis and CommutativeCancellation

[jakelishman]

What should we add?

Part of #9417.

These two passes likely come as a pair, but this issue can be split in two if the discovery phase finds that that is preferable.

Details

The commutation analysis and cancellation is the main addition to the optimisation loop at transpiler optimisation level 2. This currently doesn't support control-flow, mostly because the CommutationAnalysis pass doesn't have a way of passing the information about nested blocks through to CommutativeCancellation in the property set. To solve this, we need to:

• come up with a way to pass the information between the two transpiler passes
• make CommutationAnalysis recurse through control-flow blocks, generating this analysis
• have CommutativeCancellation be able to interpret the new information, and enter control-flow blocks to effect it.

This shouldn't be too difficult, beyond finding a data format; commutation relations can't span control-flow blocks, so a fairly simple recursive structure and visitor should be fine. When designing the data format, we may want to consider related work on DAGCircuit.collect_runs, since the collection and exchange of information is largely the same. See #9425.

It is possible that a control-flow block could commute blockwise with another, or with non-controlled operations. For the purposes of this initial support, we do not need to support recognising these cases, but it will be a goal in the future. Please note on closure of this issue whether this was achieved or not.

[mtreinish]

The first step for this is being implemented by #9143

[jlapeyre]

It looks like modifying CommutationAnalysis might not be useful at the moment. Even if we modified it to support control flow ops in some sense, we have no use for it. See #9143 (comment)

In fact, I think @ewinston 's approach might also work well for #9426 as well.

EDIT: It does work. See

• Support control flow in ConsolidateBlocks #10355

[mtreinish]

This was implemented by: #9143 it superseded the need for the commutation analysis pass to be updated