ASAP rescheduler

Header: tweedledum/algorithms/transformation/asap_reschedule.hpp

template<typename Circuit>
Circuit tweedledum::asap_reschedule(Circuit const &original)

As soon as possible (ASAP) rescheduler.

In tweedledum, the DAG circuit representations are always topologically sorted. The topological order, however, is not guaranteed to be layered. Meaning that when topologically visiting operations, you might visit a node of the second layer before visiting all nodes of the first layer. For example:

                             ┌───┐
                 >───●───────┤ 4 ├    visiting order: [1] [2] [3] [4] [5]
                     │       └───┘    layer:           1   2   3   2   1
                   ┌─┴─┐┌───┐┌───┐
                 >─┤ 1 ├┤ 2 ├┤ 3 ├
                   └───┘└───┘└───┘
                             ┌───┐
                 >───────────┤ 5 ├
                             └───┘

The nodes are numbered as they appear in the underlying DAG data structure. Nodes will be visited in this order when using foreach_node or foreach_op methods. Observer that node five is visited last, but it is on the first layer.

This algorithm will move operations closer to inputs, hence guaranteeing that all nodes of the same layer are visited before visiting the nodes of the next layer. Applying to the example we obtain:

                        ┌───┐
                 >───●──┤ 4 ├─────    visiting order: [1] [5] [2] [4] [3]
                     │  └───┘         layer:           1   1   2   2   3
                   ┌─┴─┐┌───┐┌───┐
                 >─┤ 1 ├┤ 2 ├┤ 3 ├
                   └───┘└───┘└───┘
                   ┌───┐
                 >─┤ 5 ├──────────
                   └───┘

NOTE: The node_ids are not preserved.

Return

A new rescheduled (leyered) circuit.

Parameters

• original: The original quantum circuit (will not be modified).