Port built-in synthesis algorithms to rust

[mtreinish]

What should we add?

Right now in Qiskit we have a synthesis library that provides numerous methods for synthesizing various high level objects into circuits. As part of our effort to migrate more of Qiskit's code into rust for better runtime performance and efficiency we need to look at migrating these functions to Rust.

Until we have an implementation complete for #12205 the full path for this will be potentially limited. But we can work on this in parallel to #12205 and return a "circuit sequence" like we currently do in 2q unitary synthesis and 1q unitary synthesis (we likely can reuse TwoQubitGateSequence from 2q synthesis for >2q circuits as long as it's composed of just standard library gates) and then construct the circuit or dag in python space until we finish #12205.

This will potentially be a blocker for #12211 as we can't leverage a rust implementation of the pass fully if we need to call out to python to perform the synthesis.

The current list of synthesis methods are:

Tasks

Beta Give feedback

1. Port synth_permutation_depth_lnn_kms to Rust #12224
   Rust performance synthesis +3
   
2. Port synth_permutation_basic to Rust #12225
   Rust performance synthesis +3
   
3. Port synth_permutation_acg to Rust #12226
   Rust performance synthesis +3
   
4. Port synth_cnot_count_full_pmh to Rust #12227
   Rust performance synthesis +3
   
5. Port synth_cnot_depth_line_kms to Rust #12228
   Rust performance synthesis +3
   
6. Port synth_cz_depth_line_mr to Rust #12229
   Rust performance synthesis +3
7. Port synth_cnot_phase_aam to Rust #12230
   Rust performance synthesis +3
   
8. Port synth_cx_cz_depth_line_my to Rust #12231
   Rust performance synthesis +3
9. Port synth_clifford_full to Rust #12232
   Rust performance synthesis +3
10. Port synth_clifford_ag to Rust #12233
    Rust performance synthesis +3
11. Port synth_clifford_bm to Rust #12234
    Rust performance synthesis +3
    
12. Port synth_clifford_greedy to Rust #12235
    Rust performance synthesis +3
    
13. Port synth_clifford_layers to Rust #12236
    Rust performance synthesis +3
14. Port synth_clifford_depth_lnn to Rust #12237
    Rust performance synthesis +3
15. Port synth_cnotdihedral_full to Rust #12238
    Rust performance synthesis +3
16. Port synth_cnotdihedral_two_qubits to Rust #12239
    Rust performance synthesis +3
17. Port synth_cnotdihedral_general to Rust #12240
    Rust performance synthesis +3
18. Port synth_stabilizer_layers to Rust #12241
    Rust performance synthesis +3
19. Port synth_stabilizer_depth_lnn to Rust #12242
    Rust performance synthesis +3
20. Port synth_circuit_from_stabilizers to Rust #12243
    Rust performance synthesis +3
21. Port SolovayKitaevDecomposition to Rust #12244
    Rust performance synthesis +3
22. Port synth_qft_line to Rust #12245
    Rust performance synthesis +3
23. Port qs_decomposition to Rust #12213
    Rust performance synthesis +3
24. aqc? (this one might not be necessary or too difficult for the scope of this issue and isn't critical).
25. Port XXDecomposer to Rust #12005
    Rust performance synthesis +3
    
26. Port TwoQubitWeylDecomposition to Rust #12008
    Rust performance synthesis +3
    
27. Port TwoQubitBasisDecomposition to Rust #12004
    Rust performance synthesis +3
    
28. Oxidize parameter calculation for OneQubitEulerDecomposer #9185
    Changelog: None Rust mod: quantum info performance +4
29. Move binary linear matrices utils to rust #12330
    Rust performance synthesis +3
    
30. Port TwoQubitControlledUDecomposer to rust #12907
    Rust performance synthesis +3