tk_pg_greedy_synth/synthesis/
greedy.rs1use 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
42fn 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
81fn 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 pub fn with_window_size(mut self, size: usize) -> Self {
167 self.config.window_size = Some(size);
168 self
169 }
170
171 pub fn with_pool_size(mut self, size: usize) -> Self {
176 self.config.pool_size = Some(size);
177 self
178 }
179
180 pub fn with_top_up_size(mut self, size: usize) -> Self {
186 self.config.top_up_size = Some(size);
187 self
188 }
189
190 pub fn with_progress(mut self, enable: bool) -> Self {
194 self.config.enable_progress = enable;
195 self
196 }
197
198 pub fn with_seed(mut self, seed: u64) -> Self {
202 self.config.seed = seed;
203 self
204 }
205
206 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
223pub 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#[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}