GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billti/num2-sim

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/resource_estimator/src

source/resource_estimator/src/counts.rs

633lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7use num_bigint::BigUint;
8use num_complex::Complex;
9use qsc::{Backend, interpret::Value};
10use rand::{Rng, SeedableRng, rngs::StdRng};
11use rustc_hash::FxHashMap;
12use std::{array, cell::RefCell, f64::consts::PI, fmt::Debug, iter::Sum};
13
14use crate::system::LogicalResourceCounts;
15
16/// Resource counter implementation
17///
18/// This counter tracks all resources while executing a QIR program. It takes
19/// care of qubit management, gate counting, and depth calculation.
20pub struct LogicalCounter {
21 /// Stack of free qubits
22 free_list: Vec<usize>,
23 /// Next free qubit id, in case `free_list` is empty
24 next_free: usize,
25 /// Depth counter
26 max_layer: Vec<usize>,
27 /// Layers
28 layers: Vec<LayerInfo>,
29 /// T-count (excluded in rotation count)
30 t_count: usize,
31 /// Number of Z rotation gates (excluding Cliffords and T gates)
32 r_count: usize,
33 /// CCZ count (does not contribute to T count)
34 ccz_count: usize,
35 /// Number of single-qubit and multiple-qubit measurements
36 m_count: usize,
37 /// Global allocation barrier (when calling global barrier this is advanced
38 /// to allocate new qubits after the barrier)
39 allocation_barrier: usize,
40 /// Caching stack
41 caching_stack: Vec<String>,
42 /// Caching
43 caching_layers: FxHashMap<String, LayerCache>,
44 /// Repeating
45 repeats: Vec<RepeatEntry>,
46 /// Random number generator
47 rnd: RefCell<StdRng>,
48}
49
50impl Default for LogicalCounter {
51 fn default() -> Self {
52 Self {
53 free_list: vec![],
54 next_free: 0,
55 max_layer: vec![],
56 layers: vec![],
57 t_count: 0,
58 r_count: 0,
59 ccz_count: 0,
60 m_count: 0,
61 allocation_barrier: 0,
62 caching_stack: vec![],
63 caching_layers: FxHashMap::default(),
64 repeats: vec![],
65 rnd: RefCell::new(StdRng::seed_from_u64(0)),
66 }
67 }
68}
69
70impl LogicalCounter {
71 #[must_use]
72 pub fn logical_resources(&self) -> LogicalResourceCounts {
73 LogicalResourceCounts {
74 num_qubits: self.next_free as _,
75 t_count: self.t_count as _,
76 rotation_count: self.r_count as _,
77 rotation_depth: self.layers.iter().filter(|layer| layer.r != 0).count() as _,
78 ccz_count: self.ccz_count as _,
79 ccix_count: 0,
80 measurement_count: self.m_count as _,
81 }
82 }
83
84 fn schedule_r(&mut self, q: usize) {
85 let level = self.level_at(q);
86
87 if level == self.layers.len() {
88 self.layers.push(LayerInfo::new_with_r());
89 } else {
90 self.layers[level].r += 1;
91 }
92
93 self.max_layer[q] += 1;
94 }
95
96 fn schedule_t(&mut self, q: usize) {
97 let level = self.level_at(q);
98
99 if level == self.layers.len() {
100 self.layers.push(LayerInfo::new_with_t());
101 } else {
102 self.layers[level].t += 1;
103 }
104
105 self.max_layer[q] += 1;
106 }
107
108 fn schedule_ccz(&mut self, q1: usize, q2: usize, q3: usize) {
109 let d1 = self.level_at(q1);
110 let d2 = self.level_at(q2);
111 let d3 = self.level_at(q3);
112 let max_depth = d1.max(d2).max(d3);
113
114 if max_depth == self.layers.len() {
115 self.layers.push(LayerInfo::new_with_ccz());
116 } else {
117 self.layers[max_depth].ccz += 1;
118 }
119
120 self.max_layer[q1] = max_depth + 1;
121 self.max_layer[q2] = max_depth + 1;
122 self.max_layer[q3] = max_depth + 1;
123 }
124
125 fn schedule_two_qubit_clifford(&mut self, q1: usize, q2: usize) {
126 let d1 = self.level_at(q1);
127 let d2 = self.level_at(q2);
128 let max_depth = d1.max(d2);
129 self.max_layer[q1] = max_depth;
130 self.max_layer[q2] = max_depth;
131 }
132
133 fn level_at(&mut self, q: usize) -> usize {
134 while self.max_layer.len() <= q {
135 self.qubit_allocate();
136 }
137
138 self.max_layer[q]
139 }
140
141 fn global_barrier(&mut self) -> usize {
142 let depth = self.layers.len();
143
144 for layer in &mut self.max_layer {
145 *layer = depth;
146 }
147
148 self.allocation_barrier = depth;
149 depth
150 }
151
152 fn begin_caching(&mut self, name: &str, variant: i64) -> bool {
153 let label = format!("{name}-{variant}");
154
155 if let Some(LayerCache::End {
156 start_depth,
157 end_depth,
158 combined_layer,
159 m_count,
160 }) = self.caching_layers.get(&label)
161 {
162 self.layers.extend_from_within(*start_depth..*end_depth);
163
164 self.t_count += combined_layer.t;
165 self.r_count += combined_layer.r;
166 self.ccz_count += combined_layer.ccz;
167 self.m_count += *m_count;
168
169 false
170 } else {
171 let depth = self.global_barrier();
172
173 self.caching_layers.insert(
174 label.clone(),
175 LayerCache::Begin {
176 start_depth: depth,
177 m_count: self.m_count,
178 },
179 );
180 self.caching_stack.push(label);
181
182 true
183 }
184 }
185
186 fn end_caching(&mut self) -> Result<(), String> {
187 let Some(label) = self.caching_stack.pop() else {
188 return Err("cannot end caching before beginning caching".to_string());
189 };
190
191 let entry = self
192 .caching_layers
193 .remove(&label)
194 .expect("layer caching should always have matching begin and end");
195
196 let LayerCache::Begin {
197 start_depth,
198 m_count,
199 } = entry
200 else {
201 panic!("layer caching should always have matching begin and end");
202 };
203
204 let end_depth = self.layers.len();
205
206 let range = &self.layers[start_depth..end_depth];
207 let sum: LayerInfo = range.iter().sum();
208
209 self.caching_layers.insert(
210 label,
211 LayerCache::End {
212 start_depth,
213 end_depth,
214 combined_layer: sum,
215 m_count: self.m_count - m_count,
216 },
217 );
218
219 self.global_barrier();
220 Ok(())
221 }
222
223 pub fn begin_repeat(&mut self, count: i64) -> Result<(), String> {
224 let start_depth = self.global_barrier();
225
226 self.repeats.push(RepeatEntry {
227 count: count
228 .try_into()
229 .map_err(|_| format!("Estimate count {count} is too large to fit in a usize.",))?,
230 start_depth,
231 m_count: self.m_count,
232 });
233
234 Ok(())
235 }
236
237 #[allow(clippy::similar_names)]
238 pub fn end_repeat(&mut self) {
239 if let Some(RepeatEntry {
240 count,
241 start_depth,
242 m_count,
243 }) = self.repeats.pop()
244 {
245 if count == 0 {
246 return;
247 }
248
249 let end_depth = self.global_barrier();
250
251 let range = &self.layers[start_depth..end_depth];
252 let sum: LayerInfo = range.iter().sum();
253
254 // We skip one iteration, which was already done explicitly between
255 // begin_repeat and end_repeat
256 let r_depth = range.iter().filter(|l| l.r != 0).count();
257 let combined_r_depth = r_depth * (count - 1);
258 let combined_t_count = sum.t * (count - 1);
259 let combined_r_count = sum.r * (count - 1);
260 let combined_ccz_count = sum.ccz * (count - 1);
261 let combined_m_count = (self.m_count - m_count) * (count - 1);
262
263 if r_depth > 0 {
264 let first_layer_r_count = combined_r_count - (combined_r_depth - 1);
265
266 self.layers.push(LayerInfo {
267 ccz: combined_ccz_count,
268 r: first_layer_r_count,
269 t: combined_t_count,
270 });
271 for _ in 1..combined_r_depth {
272 self.layers.push(LayerInfo::new_with_r());
273 }
274 } else {
275 self.layers.push(LayerInfo {
276 ccz: combined_ccz_count,
277 r: combined_r_count,
278 t: combined_t_count,
279 });
280 }
281
282 self.t_count += combined_t_count;
283 self.r_count += combined_r_count;
284 self.ccz_count += combined_ccz_count;
285 self.m_count += combined_m_count;
286
287 self.global_barrier();
288 }
289 }
290
291 fn add_estimate(
292 &mut self,
293 estimates: &[(i64, i64)],
294 layout: i64,
295 qubits: &[usize],
296 ) -> Result<(), String> {
297 if layout != 1 {
298 return Err(
299 "Parameter layout in AccountForEstimates must be 1 for PSSPCLayout.".to_string(),
300 );
301 }
302
303 let mut aux_qubit_count = 0_usize;
304 let mut t_count = 0_usize;
305 let mut r_count = 0_usize;
306 let mut r_depth = 0_usize;
307 let mut ccz_count = 0_usize;
308 let mut m_count = 0_usize;
309 for (kind, count) in estimates {
310 if *count < 0 {
311 return Err(format!("Negative estimate count: {count}"));
312 }
313 let count: usize = (*count)
314 .try_into()
315 .map_err(|_| format!("Estimate count {count} is too large to fit in a usize.",))?;
316 match *kind {
317 0 => aux_qubit_count += count,
318 1 => t_count += count,
319 2 => r_count += count,
320 3 => r_depth += count,
321 4 => ccz_count += count,
322 5 => m_count += count,
323 _ => return Err(format!("Unknown estimate kind: {kind}")),
324 }
325 }
326
327 // Allocate helper qubits
328 let helper_qubits = (0..aux_qubit_count)
329 .map(|_| self.qubit_allocate())
330 .collect::<Vec<_>>();
331
332 // Set barrier among all qubits
333 let all_qubits = qubits.iter().chain(helper_qubits.iter());
334 let max_depth = all_qubits
335 .clone()
336 .map(|q| self.max_layer[*q])
337 .max()
338 .unwrap_or(0);
339 for qubit in all_qubits {
340 self.max_layer[*qubit] = max_depth;
341 }
342
343 // Add up the estimates, dividing up between layers if appropriate.
344 let num_layers = if r_depth == 0 {
345 if r_count != 0 {
346 return Err("Rotation depth of zero must use rotation count zero.".to_string());
347 }
348
349 self.layers.push(LayerInfo {
350 t: t_count,
351 r: r_count,
352 ccz: ccz_count,
353 });
354
355 1
356 } else {
357 if r_depth < (r_count as f64 / qubits.len() as f64).ceil() as usize {
358 return Err(format!(
359 "Rotation depth {r_depth} is too small for rotation count {r_count} and {} qubits.",
360 qubits.len()
361 ));
362 }
363
364 let r_count_per_layer = r_count / r_depth;
365 let extra_count = r_count - (r_count_per_layer * r_depth);
366
367 self.layers.push(LayerInfo {
368 t: t_count,
369 r: r_count_per_layer + extra_count,
370 ccz: ccz_count,
371 });
372
373 for _ in 1..r_depth {
374 self.layers.push(LayerInfo {
375 t: 0,
376 r: r_count_per_layer,
377 ccz: 0,
378 });
379 }
380
381 r_depth
382 };
383
384 self.t_count += t_count;
385 self.r_count += r_count;
386 self.ccz_count += ccz_count;
387 self.m_count += m_count;
388
389 for qubit in qubits {
390 self.max_layer[*qubit] += num_layers;
391 }
392
393 // Release helper qubits
394 for qubit in helper_qubits {
395 self.qubit_release(qubit);
396 }
397
398 Ok(())
399 }
400}
401
402impl Backend for LogicalCounter {
403 type ResultType = bool;
404
405 fn ccx(&mut self, ctl0: usize, ctl1: usize, q: usize) {
406 self.ccz_count += 1;
407 self.schedule_ccz(ctl0, ctl1, q);
408 }
409
410 fn cx(&mut self, ctl: usize, q: usize) {
411 self.schedule_two_qubit_clifford(ctl, q);
412 }
413
414 fn cy(&mut self, ctl: usize, q: usize) {
415 self.schedule_two_qubit_clifford(ctl, q);
416 }
417
418 fn cz(&mut self, ctl: usize, q: usize) {
419 self.schedule_two_qubit_clifford(ctl, q);
420 }
421
422 fn h(&mut self, _q: usize) {}
423
424 fn m(&mut self, _q: usize) -> Self::ResultType {
425 self.m_count += 1;
426
427 self.rnd.borrow_mut().gen_bool(0.5)
428 }
429
430 fn mresetz(&mut self, q: usize) -> Self::ResultType {
431 self.m(q)
432 }
433
434 fn reset(&mut self, _q: usize) {}
435
436 fn rx(&mut self, theta: f64, q: usize) {
437 self.rz(theta, q);
438 }
439
440 fn rxx(&mut self, theta: f64, q0: usize, q1: usize) {
441 self.rzz(theta, q0, q1);
442 }
443
444 fn ry(&mut self, theta: f64, q: usize) {
445 self.rz(theta, q);
446 }
447
448 fn ryy(&mut self, theta: f64, q0: usize, q1: usize) {
449 self.rzz(theta, q0, q1);
450 }
451
452 fn rz(&mut self, theta: f64, q: usize) {
453 let multiple = (theta / (PI / 4.0)).round();
454 if ((multiple * (PI / 4.0)) - theta).abs() <= f64::EPSILON {
455 let multiple = (multiple as i64).rem_euclid(8) as u64;
456 if multiple & 1 == 1 {
457 self.t(q);
458 }
459 } else {
460 self.r_count += 1;
461 self.schedule_r(q);
462 }
463 }
464
465 fn rzz(&mut self, theta: f64, q0: usize, q1: usize) {
466 self.cx(q1, q0);
467 self.rz(theta, q0);
468 self.cx(q1, q0);
469 }
470
471 fn sadj(&mut self, _q: usize) {}
472
473 fn s(&mut self, _q: usize) {}
474
475 fn sx(&mut self, _q: usize) {}
476
477 fn swap(&mut self, q0: usize, q1: usize) {
478 self.schedule_two_qubit_clifford(q0, q1);
479 }
480
481 fn tadj(&mut self, q: usize) {
482 self.t_count += 1;
483 self.schedule_t(q);
484 }
485
486 fn t(&mut self, q: usize) {
487 self.t_count += 1;
488 self.schedule_t(q);
489 }
490
491 fn x(&mut self, _q: usize) {}
492
493 fn y(&mut self, _q: usize) {}
494
495 fn z(&mut self, _q: usize) {}
496
497 fn qubit_allocate(&mut self) -> usize {
498 if let Some(index) = self.free_list.pop() {
499 index
500 } else {
501 let index = self.next_free;
502 self.next_free += 1;
503 self.max_layer.push(self.allocation_barrier);
504 index
505 }
506 }
507
508 fn qubit_release(&mut self, q: usize) -> bool {
509 self.free_list.push(q);
510 true
511 }
512
513 fn qubit_swap_id(&mut self, _q0: usize, _q1: usize) {
514 // This can safely be treated as a no-op, because counts don't care which qubit is operated on,
515 // just how many operations are performed, and relabeling is non-physical.
516 }
517
518 fn capture_quantum_state(&mut self) -> (Vec<(BigUint, Complex<f64>)>, usize) {
519 (Vec::new(), 0)
520 }
521
522 fn qubit_is_zero(&mut self, _q: usize) -> bool {
523 true
524 }
525
526 fn custom_intrinsic(&mut self, name: &str, arg: Value) -> Option<Result<Value, String>> {
527 match name {
528 "BeginEstimateCaching" => {
529 let values = arg.unwrap_tuple();
530 let [cache_name, cache_variant] = array::from_fn(|i| values[i].clone());
531 Some(Ok(Value::Bool(self.begin_caching(
532 &cache_name.unwrap_string(),
533 cache_variant.unwrap_int(),
534 ))))
535 }
536 "EndEstimateCaching" => Some(self.end_caching().map(|()| Value::unit())),
537 "BeginRepeatEstimatesInternal" => {
538 let count = arg.unwrap_int();
539 Some(self.begin_repeat(count).map(|()| Value::unit()))
540 }
541 "EndRepeatEstimatesInternal" => {
542 self.end_repeat();
543 Some(Ok(Value::unit()))
544 }
545 "AccountForEstimatesInternal" => {
546 let values = arg.unwrap_tuple();
547 let [estimates, layout, qubits] = array::from_fn(|i| values[i].clone());
548 let estimates = estimates
549 .unwrap_array()
550 .iter()
551 .map(|v| {
552 let entry = v.clone().unwrap_tuple();
553 let [variant, count] = array::from_fn(|i| entry[i].clone());
554 let variant = variant.unwrap_int();
555 let count = count.unwrap_int();
556 (variant, count)
557 })
558 .collect::<Vec<_>>();
559 let layout = layout.unwrap_int();
560 let qubits = qubits
561 .unwrap_array()
562 .iter()
563 .map(|v| v.clone().unwrap_qubit().deref().0)
564 .collect::<Vec<_>>();
565 Some(
566 self.add_estimate(&estimates, layout, &qubits)
567 .map(|()| Value::unit()),
568 )
569 }
570 "GlobalPhase" | "ConfigurePauliNoise" | "ConfigureQubitLoss" | "ApplyIdleNoise" => {
571 Some(Ok(Value::unit()))
572 }
573 _ => None,
574 }
575 }
576}
577
578#[derive(Default, Debug, Clone, PartialEq, Eq)]
579pub struct LayerInfo {
580 t: usize,
581 r: usize,
582 ccz: usize,
583}
584
585impl LayerInfo {
586 #[must_use]
587 pub fn new_with_t() -> Self {
588 Self { t: 1, r: 0, ccz: 0 }
589 }
590
591 #[must_use]
592 pub fn new_with_r() -> Self {
593 Self { t: 0, r: 1, ccz: 0 }
594 }
595
596 #[must_use]
597 pub fn new_with_ccz() -> Self {
598 Self { t: 0, r: 0, ccz: 1 }
599 }
600}
601
602impl<'a> Sum<&'a LayerInfo> for LayerInfo {
603 fn sum<I: Iterator<Item = &'a LayerInfo>>(iter: I) -> Self {
604 let mut layer = LayerInfo::default();
605
606 for current in iter {
607 layer.t += current.t;
608 layer.r += current.r;
609 layer.ccz += current.ccz;
610 }
611
612 layer
613 }
614}
615
616enum LayerCache {
617 Begin {
618 start_depth: usize,
619 m_count: usize,
620 },
621 End {
622 start_depth: usize,
623 end_depth: usize,
624 combined_layer: LayerInfo,
625 m_count: usize,
626 },
627}
628
629struct RepeatEntry {
630 count: usize,
631 start_depth: usize,
632 m_count: usize,
633}
634