Skip to main content

tk_pg_greedy_synth/synthesis/
greedy.rs

1use super::ParallelMode;
2use crate::backend::{
3    CostKernel, ExpandedSparseWeightedSum, GreedyCostBackend, GroupedWeightedSum, ScalarBackend,
4    WeightedSumStrategy,
5};
6#[cfg(feature = "unstable_simd")]
7use crate::backend::{ExpandedSimdWeightedSum, SimdBackend};
8use crate::packed_pg_slice::PackedBackend;
9use crate::reducer::Reducer;
10use std::cmp::max;
11use tk_pg_core::{Op, PGPass, PauliGraph};
12
13const DEFAULT_WINDOW_SIZE: usize = 1280;
14const MINIMUM_POOL_SIZE: usize = 1000;
15const TQE_SAMPLE_FRACTION: f64 = 0.1;
16const MINIMUM_TOP_UP_SIZE: usize = 200;
17const GROUPED_WEIGHTED_SUM_MIN_OPS_PER_SET: usize = 64;
18
19#[derive(Clone, Copy)]
20struct GreedySynthConfig {
21    window_size: Option<usize>,
22    pool_size: Option<usize>,
23    top_up_size: Option<usize>,
24    enable_progress: bool,
25    seed: u64,
26    parallel_mode: ParallelMode,
27}
28
29impl Default for GreedySynthConfig {
30    fn default() -> Self {
31        Self {
32            window_size: None,
33            pool_size: None,
34            top_up_size: None,
35            enable_progress: false,
36            seed: 0,
37            parallel_mode: ParallelMode::Auto,
38        }
39    }
40}
41
42/// Returns the average size of nonempty Pauli-op sets.
43fn average_ops_per_set(pg: &PauliGraph) -> usize {
44    let mut ops: usize = 0;
45    let mut op_sets = 0;
46    let mut current_set_has_op = false;
47
48    for op in pg.get_ops() {
49        match op {
50            Op::SetBoundary => {
51                op_sets += usize::from(current_set_has_op);
52                current_set_has_op = false;
53            }
54            Op::Rotation { .. } | Op::Reset { .. } | Op::Measure { .. } => {
55                ops += 1;
56                current_set_has_op = true;
57            }
58            _ => {}
59        }
60    }
61    op_sets += usize::from(current_set_has_op);
62
63    ops.checked_div(op_sets).unwrap_or(0)
64}
65
66fn resolve_sizes(
67    n_qubits: usize,
68    window_size: Option<usize>,
69    pool_size: Option<usize>,
70    top_up_size: Option<usize>,
71) -> (usize, usize, usize) {
72    let window_size = window_size.unwrap_or(DEFAULT_WINDOW_SIZE);
73    let pool_size = pool_size.unwrap_or(max(
74        MINIMUM_POOL_SIZE,
75        ((n_qubits * n_qubits) as f64 * (2.0 * TQE_SAMPLE_FRACTION)) as usize,
76    ));
77    let top_up_size = top_up_size.unwrap_or(max(MINIMUM_TOP_UP_SIZE, pool_size / n_qubits));
78    (window_size, pool_size, top_up_size)
79}
80
81/// Transforms a Pauli graph using the specified backend, the default weighted
82/// sum strategy and the given synthesis configuration.
83///
84/// Grouped weighting replaces expanded weighting when nonempty rotation sets
85/// contain an average of at least 64 rotations. This inherited tuning heuristic
86/// should only change with representative benchmarks and an output quality
87/// comparison.
88fn transform_with_backend<P, W>(
89    pg: &PauliGraph,
90    config: GreedySynthConfig,
91    packed_backend: P,
92    expanded_weighted_sum: W,
93) -> PauliGraph
94where
95    P: PackedBackend + CostKernel + Copy + Sync,
96    W: WeightedSumStrategy,
97{
98    assert!(
99        config.window_size.is_none_or(|size| size > 0),
100        "window size must be positive"
101    );
102    assert!(
103        config.pool_size.is_none_or(|size| size > 0),
104        "pool size must be positive"
105    );
106    assert!(
107        config.top_up_size.is_none_or(|size| size > 0),
108        "top-up size must be positive"
109    );
110    if pg.get_n_qubits() == 0 {
111        if !pg.get_ops().is_empty() {
112            panic!("GreedySynthPass expects a graph with 0 qubits to have no operations.");
113        }
114        return PauliGraph::new(0);
115    }
116    if pg.get_ops().is_empty() {
117        return PauliGraph::new(pg.get_n_qubits());
118    }
119
120    let (window_size, pool_size, top_up_size) = resolve_sizes(
121        pg.get_n_qubits(),
122        config.window_size,
123        config.pool_size,
124        config.top_up_size,
125    );
126    if average_ops_per_set(pg) >= GROUPED_WEIGHTED_SUM_MIN_OPS_PER_SET {
127        Reducer::new(
128            packed_backend,
129            GreedyCostBackend::new(packed_backend, GroupedWeightedSum::default()),
130            window_size,
131            pool_size,
132            top_up_size,
133            config.seed,
134            config.parallel_mode,
135            config.enable_progress,
136        )
137        .reduce(pg)
138    } else {
139        Reducer::new(
140            packed_backend,
141            GreedyCostBackend::new(packed_backend, expanded_weighted_sum),
142            window_size,
143            pool_size,
144            top_up_size,
145            config.seed,
146            config.parallel_mode,
147            config.enable_progress,
148        )
149        .reduce(pg)
150    }
151}
152
153macro_rules! impl_pass_configuration {
154    ($pass:ty, $constructor_summary:literal) => {
155        impl $pass {
156            #[doc = $constructor_summary]
157            pub fn new() -> Self {
158                Self {
159                    config: GreedySynthConfig::default(),
160                }
161            }
162
163            /// Sets the lookahead window size for packed operations.
164            ///
165            /// The default is 1280. The value must be positive.
166            pub fn with_window_size(mut self, size: usize) -> Self {
167                self.config.window_size = Some(size);
168                self
169            }
170
171            /// Sets the number of candidates sampled after frontier progress.
172            ///
173            /// The default depends on the input and is at least 1000. The value
174            /// must be positive.
175            pub fn with_pool_size(mut self, size: usize) -> Self {
176                self.config.pool_size = Some(size);
177                self
178            }
179
180            /// Sets the number of candidates added when the frontier has not
181            /// progressed.
182            ///
183            /// The default depends on the input and is at least 200. The value
184            /// must be positive.
185            pub fn with_top_up_size(mut self, size: usize) -> Self {
186                self.config.top_up_size = Some(size);
187                self
188            }
189
190            /// Enables or disables terminal progress reporting.
191            ///
192            /// Progress reporting is disabled by default.
193            pub fn with_progress(mut self, enable: bool) -> Self {
194                self.config.enable_progress = enable;
195                self
196            }
197
198            /// Sets the seed for candidate sampling.
199            ///
200            /// The default seed is zero.
201            pub fn with_seed(mut self, seed: u64) -> Self {
202                self.config.seed = seed;
203                self
204            }
205
206            /// Selects the parallelization policy for candidate costing.
207            ///
208            /// The default is [`ParallelMode::Auto`].
209            pub fn with_parallel_mode(mut self, mode: ParallelMode) -> Self {
210                self.config.parallel_mode = mode;
211                self
212            }
213        }
214
215        impl Default for $pass {
216            fn default() -> Self {
217                Self::new()
218            }
219        }
220    };
221}
222
223/// Greedily synthesizes a canonical Pauli graph with scalar packed kernels.
224///
225/// The pass expects the output of `CanonicalFormPass` followed by
226/// `GroupCommutingOpsPass`. Output contains Clifford gates on individual
227/// qubits, Pauli rotations, measurements, resets, black boxes and TQE gates.
228///
229pub struct GreedySynthPass {
230    config: GreedySynthConfig,
231}
232
233impl_pass_configuration!(
234    GreedySynthPass,
235    "Creates a scalar synthesis pass with sizes chosen automatically."
236);
237
238impl PGPass for GreedySynthPass {
239    fn transform(&self, pg: &PauliGraph) -> PauliGraph {
240        transform_with_backend(
241            pg,
242            self.config,
243            ScalarBackend,
244            ExpandedSparseWeightedSum::default(),
245        )
246    }
247}
248
249/// Greedily synthesizes a canonical Pauli graph with portable SIMD kernels.
250#[cfg(feature = "unstable_simd")]
251pub struct GreedySynthSimdPass {
252    config: GreedySynthConfig,
253}
254
255#[cfg(feature = "unstable_simd")]
256impl_pass_configuration!(
257    GreedySynthSimdPass,
258    "Creates a SIMD synthesis pass with sizes chosen automatically."
259);
260
261#[cfg(feature = "unstable_simd")]
262impl PGPass for GreedySynthSimdPass {
263    fn transform(&self, pg: &PauliGraph) -> PauliGraph {
264        transform_with_backend(
265            pg,
266            self.config,
267            SimdBackend,
268            ExpandedSimdWeightedSum::default(),
269        )
270    }
271}