Summary

This PR aims to start a discussion on the proper interface for the extended BlockCollector class and for the transpiler passes that can work with either DAGCircuit or DAGDependency.

Extended BlockCollector interface

The existing BlockCollector class allows to greedily collect maximal blocks of nodes matching a given filter function. This serves to collect blocks of linear gates, blocks of Clifford gates, blocks of 1-qubit gates, blocks of 2-qubits gates, and so on. In addition, BlockCollector can exploit commutativity between gates by using the DAGDependency representation of the circuit.

However, this does not encompass use-cases where the decision of whether to add an eligible node to the current block should depend both on the node and on the current block. Furthermore, we may want the collected blocks to carry more information that just the list of nodes contained in the block.

Consider the use-case of collecting and reimplementing "star-shaped" subcircuits (see PR #11387). Deciding whether a given 2-qubit gate can be added to the current "star" depends on whether the star's center qubit has already been chosen and whether this center qubit is part of the node's qubits.

Or consider the use-case of collecting blocks of nodes all controlled by the same set of qubits. Deciding whether a node can be added to the current block depends on whether this node is also controlled by the same qubits as the other nodes in the block.

This PR proposes the following extension of the BlockCollector interface. There is a new abstract class called Block; previous block collection strategies work with the DefaultBlock subclass; collecting blocks from a DAGCircuit/DAGDependency returns a list of these blocks (rather than a list of lists of nodes); yet the change is backward compatible with the help of an additional argument output_nodes.

As an example, a StarBlock used to collect star-shaped subcircuits contained the list of nodes in the block, the "center" node of the star, and the number of 2-qubit gates in the block.

Star to linear prerouting pass

This PR includes a specific example of the star-to-line prerouting pass: the relevant code is copied/adapted from PR #11387. However, an additional effort is taken to make both pieces of collecting star-shaped subcircuits and rewriting star-shaped subcircuits work with either DAGCircuit and DAGDependency. This is greatly simplified by the new DAG-dependency interface proposed in PR #11705, and for this reason this PR is implemented on top of #11705.

One question is whether we can somehow make the block rewriting part of the pass to be more generic, i.e. eventually requiring less code duplication between this and other similar passed. One possibility is to first "collapse" detected star-shaped subcircuits into new special gates (the same way as Clifford gates are collapsed into a single Clifford), but I am not convinced this extra translation would make the code simpler or easier to use.

Suggestions are welcome!