Performance of block_order_op_nodes

[samanthavbarron]

What is the expected feature or enhancement?

Scheduling/padding passes which use the block_order_op_nodes function are significantly slower than those that do not. In particular, this block is particularly slow, due to repeated calls of dag.descendants and isinstance.

For tracking purposes, the code referenced in this repository originated in this PR.

The block_order_op_nodes function also exists in the qiskit-ibm-provider repo, so it should be an issue there as well.

In this 20 qubit by 20 depth example:

• transpiling with the standard qiskit scheduling/padding passes takes about 0.5s, whereas
• transpiling with the qiskit-ibm-runtime equivalents takes 13.4s.

The profiling figures below suggest that the difference is due to the block_order_op_nodes function, which is needed for block synchronization.

Running with qiskit-ibm-runtime's passes

Running with qiskit passes

Acceptance criteria

[samanthavbarron]

I've also tried running it on a similar 50q example, the standard qiskit passes took 5s, and the qiskit-ibm-runtime ones have been running for 15m.. ⏳

Edit: It took 25m

[samanthavbarron]

@mtreinish @jakelishman

[samanthavbarron]

For added context and tracking:

The order in which the nodes should be emitted is such that:

• Measures/resets are done ASAP
• Then conditionals are done immediately after
• Then anything else is ALAP

So block_order_op_nodes accomplishes this by yielding from dag.topological_op_nodes() in a way such that it looks ahead at each of the non-meas/cond/reset nodes of to see whether it has descendants that are meas/cond/reset to form the blocks, and the meas/resets should be grouped together whenever possible.