What should we add?

An AnnotatedOperation is a just-yet-another high-level object on a circuit, consisting of the base operation and a list of control, power and inverse modifiers. The handling of all the other high-level objects (e.g., Cliffords, Permutations, MCX gates, HalfAdder gates, etc.) is done using the plugin mechanism, and it makes sense to use the plugin mechanism for annotated operations as well. The idea was initially suggested by @jakelishman and recently discussed in depth with @Cryoris and @ShellyGarion.

There are several benefits of doing the above. First, it unifies and simplifies the HighLevelSynthesis transpiler pass, making it easier to port it to Rust. Second, it allows for introducing different implementation for (especially) control-annotated gates. In particular, this would disentangle the HighLevelSynthesis transpiler pass and the mechanism for synthesizing a controlled-circuit, making it easier to improve the controlled-circuit synthesis code in the future.

On the other hand, the current handling of annotated operations inside the HighLevelSynthesis requires a lot more of additional information than available to other plugins. This is because we first use the full power of HighLevelSynthesis to recursively synthesize the base operation (which itself may have a complex definition containing other high-level and annotated operations), and in particular we need access to qubit_tracker, qubit_context and some other internal HighLevelSynthesis data. So this is also a great time to completely rethink the high-level-synthesis plugin interface (with the extra complication that whatever we do should be backward compatible).

Historically, the run method of a "regular" high-level-synthesis plugin accepted the high-level-object to synthesize, the coupling_map and then later also target (it probably makes sense to deprecate coupling_map as done elsewhere), and the list of qubits over which the high-level-object is defined, with the convention that qubits=None indicates the synthesis runs pre-layout, and while the coupling map is available and can guide the plugin to which synthesis algorithm to choose, the physical locations of the qubits are still not chosen and so we still don't know which pairs of qubits are connected and which are not. In addition each plugin accepts an arbitrary dictionary of plugin-specific options, and we started to use this to pass the number of clean and dirty qubits available to the plugin. However, as mentioned above, synthesizing annotated operations also requires the qubits of the operation, the qubit context (the mapping between the current DAG's qubits and the qubits of the original circuit), the qubit tracker (which qubits in the original circuit and clean or dirty) and other data. I am now fairly convinced that even "regular" plugins may wish to have access to this information. In addition, it should also be a plugin's responsibility to update the lists of clean and dirty ancilla qubits after the plugin is run.

I am planning to open a draft PR shortly, using it as a way to discuss the desired interface.