GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
minestarks/circuit-folding

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/source/compiler/qsc_circuit/src

source/compiler/qsc_circuit/src/circuit.rs

2048lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7use core::panic;
8use log::warn;
9use rustc_hash::{FxHashMap, FxHashSet};
10use serde::{Deserialize, Serialize};
11use std::slice::from_ref;
12use std::{cmp::max, hash::Hasher};
13use std::{
14 fmt::{Display, Write},
15 hash::Hash,
16 ops::Not,
17 vec,
18};
19
20/// Current format version.
21pub const CURRENT_VERSION: usize = 1;
22
23/// Representation of a quantum circuit group.
24#[derive(Clone, Serialize, Deserialize, Default, Debug)]
25pub struct CircuitGroup {
26 pub circuits: Vec<Circuit>,
27 pub version: usize,
28}
29
30impl Display for CircuitGroup {
31 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
32 for circuit in &self.circuits {
33 writeln!(f, "{circuit}")?;
34 }
35 Ok(())
36 }
37}
38
39/// Representation of a quantum circuit.
40#[derive(Clone, Serialize, Deserialize, Default, Debug)]
41pub struct Circuit {
42 pub qubits: Vec<Qubit>,
43 #[serde(rename = "componentGrid")]
44 pub component_grid: ComponentGrid,
45}
46
47impl Circuit {
48 #[must_use]
49 pub fn display_basic(&self) -> impl Display {
50 CircuitDisplay {
51 circuit: self,
52 render_locations: false,
53 render_groups: false,
54 }
55 }
56
57 #[must_use]
58 pub fn display_with_groups(&self) -> impl Display {
59 // Groups rendered only in tests since the current line rendering
60 // doesn't look good enough to be user-facing.
61 CircuitDisplay {
62 circuit: self,
63 render_locations: true,
64 render_groups: true,
65 }
66 }
67}
68
69impl Display for Circuit {
70 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71 write!(
72 f,
73 "{}",
74 CircuitDisplay {
75 circuit: self,
76 render_locations: true,
77 render_groups: true,
78 }
79 )
80 }
81}
82
83/// Type alias for a grid of components.
84pub type ComponentGrid = Vec<ComponentColumn>;
85
86/// Representation of a column in the component grid.
87#[derive(Clone, Serialize, Deserialize, Default, Debug)]
88pub struct ComponentColumn {
89 pub components: Vec<Component>,
90}
91
92/// Union type for components.
93pub type Component = Operation;
94
95/// Union type for operations.
96#[derive(Clone, Serialize, Deserialize, Debug)]
97#[serde(tag = "kind")]
98pub enum Operation {
99 #[serde(rename = "measurement")]
100 Measurement(Measurement),
101 #[serde(rename = "unitary")]
102 Unitary(Unitary),
103 #[serde(rename = "ket")]
104 Ket(Ket),
105}
106
107impl Operation {
108 /// Returns the gate name of the operation.
109 #[must_use]
110 pub fn gate(&self) -> String {
111 match self {
112 Operation::Measurement(m) => m.gate.clone(),
113 Operation::Unitary(u) => u.gate.clone(),
114 #[allow(clippy::unicode_not_nfc)]
115 Operation::Ket(k) => format!("|{}〉", k.gate),
116 }
117 }
118
119 pub fn gate_mut(&mut self) -> &mut String {
120 match self {
121 Self::Measurement(measurement) => &mut measurement.gate,
122 Self::Unitary(unitary) => &mut unitary.gate,
123 Self::Ket(ket) => &mut ket.gate,
124 }
125 }
126
127 /// Returns the arguments for the operation.
128 #[must_use]
129 pub fn args(&self) -> Vec<String> {
130 match self {
131 Operation::Measurement(m) => m.args.clone(),
132 Operation::Unitary(u) => u.args.clone(),
133 Operation::Ket(k) => k.args.clone(),
134 }
135 }
136
137 pub fn args_mut(&mut self) -> &mut Vec<String> {
138 match self {
139 Self::Measurement(measurement) => &mut measurement.args,
140 Self::Unitary(unitary) => &mut unitary.args,
141 Self::Ket(ket) => &mut ket.args,
142 }
143 }
144
145 #[must_use]
146 pub fn source_location(&self) -> Option<&SourceLocation> {
147 match self {
148 Self::Measurement(measurement) => measurement.metadata.as_ref(),
149 Self::Unitary(unitary) => unitary.metadata.as_ref(),
150 Self::Ket(ket) => ket.metadata.as_ref(),
151 }
152 .and_then(|m| m.source.as_ref())
153 }
154
155 #[must_use]
156 pub fn source_location_mut(&mut self) -> &mut Option<SourceLocation> {
157 let md = match self {
158 Self::Measurement(measurement) => &mut measurement.metadata,
159 Self::Unitary(unitary) => &mut unitary.metadata,
160 Self::Ket(ket) => &mut ket.metadata,
161 };
162
163 if md.is_none() {
164 md.replace(Metadata {
165 source: None,
166 scope_location: None,
167 });
168 }
169
170 if let Some(md) = md {
171 &mut md.source
172 } else {
173 unreachable!()
174 }
175 }
176
177 #[must_use]
178 pub fn scope_location_mut(&mut self) -> &mut Option<SourceLocation> {
179 let md = match self {
180 Self::Measurement(measurement) => &mut measurement.metadata,
181 Self::Unitary(unitary) => &mut unitary.metadata,
182 Self::Ket(ket) => &mut ket.metadata,
183 };
184
185 if md.is_none() {
186 md.replace(Metadata {
187 source: None,
188 scope_location: None,
189 });
190 }
191
192 if let Some(md) = md {
193 &mut md.scope_location
194 } else {
195 unreachable!()
196 }
197 }
198
199 /// Returns the children for the operation.
200 #[must_use]
201 pub fn children(&self) -> &ComponentGrid {
202 match self {
203 Operation::Measurement(m) => &m.children,
204 Operation::Unitary(u) => &u.children,
205 Operation::Ket(k) => &k.children,
206 }
207 }
208
209 /// Returns the children for the operation.
210 #[must_use]
211 pub fn children_mut(&mut self) -> &mut ComponentGrid {
212 match self {
213 Operation::Measurement(m) => &mut m.children,
214 Operation::Unitary(u) => &mut u.children,
215 Operation::Ket(k) => &mut k.children,
216 }
217 }
218
219 #[must_use]
220 pub fn targets_mut(&mut self) -> &mut Vec<Register> {
221 match self {
222 Operation::Measurement(m) => &mut m.qubits,
223 Operation::Unitary(u) => &mut u.targets,
224 Operation::Ket(k) => &mut k.targets,
225 }
226 }
227 /// Returns if the operation is a controlled operation.
228 #[must_use]
229 pub fn is_controlled(&self) -> bool {
230 match self {
231 Operation::Measurement(_) | Operation::Ket(_) => false,
232 Operation::Unitary(u) => !u.controls.is_empty(),
233 }
234 }
235
236 /// Returns if the operation is a measurement operation.
237 #[must_use]
238 pub fn is_measurement(&self) -> bool {
239 match self {
240 Operation::Measurement(_) => true,
241 Operation::Unitary(_) | Operation::Ket(_) => false,
242 }
243 }
244
245 /// Returns if the operation is an adjoint operation.
246 #[must_use]
247 pub fn is_adjoint(&self) -> bool {
248 match self {
249 Operation::Measurement(_) | Operation::Ket(_) => false,
250 Operation::Unitary(u) => u.is_adjoint,
251 }
252 }
253}
254
255/// Representation of a measurement operation.
256#[derive(Clone, Serialize, Deserialize, Default, Debug)]
257pub struct Measurement {
258 pub gate: String,
259 #[serde(skip_serializing_if = "Vec::is_empty")]
260 #[serde(default)]
261 pub args: Vec<String>,
262 #[serde(skip_serializing_if = "Vec::is_empty")]
263 #[serde(default)]
264 pub children: ComponentGrid,
265 pub qubits: Vec<Register>,
266 pub results: Vec<Register>,
267 #[serde(skip_serializing_if = "Option::is_none")]
268 pub metadata: Option<Metadata>,
269}
270
271/// Representation of a unitary operation.
272#[derive(Clone, Serialize, Deserialize, Default, Debug)]
273pub struct Unitary {
274 pub gate: String,
275 #[serde(skip_serializing_if = "Vec::is_empty")]
276 #[serde(default)]
277 pub args: Vec<String>,
278 #[serde(skip_serializing_if = "Vec::is_empty")]
279 #[serde(default)]
280 pub children: ComponentGrid,
281 pub targets: Vec<Register>,
282 #[serde(skip_serializing_if = "Vec::is_empty")]
283 #[serde(default)]
284 pub controls: Vec<Register>,
285 #[serde(rename = "isAdjoint")]
286 #[serde(skip_serializing_if = "Not::not")]
287 #[serde(default)]
288 pub is_adjoint: bool,
289 #[serde(skip_serializing_if = "Option::is_none")]
290 pub metadata: Option<Metadata>,
291}
292
293/// Representation of a gate that will set the target to a specific state.
294#[derive(Clone, Serialize, Deserialize, Default, Debug)]
295pub struct Ket {
296 pub gate: String,
297 #[serde(skip_serializing_if = "Vec::is_empty")]
298 #[serde(default)]
299 pub args: Vec<String>,
300 #[serde(skip_serializing_if = "Vec::is_empty")]
301 #[serde(default)]
302 pub children: ComponentGrid,
303 pub targets: Vec<Register>,
304 #[serde(skip_serializing_if = "Option::is_none")]
305 pub metadata: Option<Metadata>,
306}
307
308#[derive(Serialize, Deserialize, Debug, Eq, Hash, PartialEq, Clone)]
309pub struct Register {
310 pub qubit: usize,
311 #[serde(skip_serializing_if = "Option::is_none")]
312 pub result: Option<usize>,
313}
314
315impl Register {
316 #[must_use]
317 pub fn quantum(qubit_id: usize) -> Self {
318 Self {
319 qubit: qubit_id,
320 result: None,
321 }
322 }
323
324 #[must_use]
325 pub fn classical(qubit_id: usize, result_id: usize) -> Self {
326 Self {
327 qubit: qubit_id,
328 result: Some(result_id),
329 }
330 }
331
332 #[must_use]
333 pub fn is_classical(&self) -> bool {
334 self.result.is_some()
335 }
336}
337
338#[derive(Clone, Serialize, Deserialize, Debug)]
339pub struct Qubit {
340 pub id: usize,
341 #[serde(rename = "numResults")]
342 #[serde(default)]
343 pub num_results: usize,
344 #[serde(skip_serializing_if = "Vec::is_empty")]
345 #[serde(default)]
346 pub declarations: Vec<SourceLocation>,
347}
348
349#[derive(Clone, Serialize, Deserialize, Debug)]
350#[serde(rename_all = "camelCase")]
351/// The schema of `Metadata` may change and its contents
352/// are never meant to be persisted in a .qsc file.
353pub struct Metadata {
354 #[serde(skip_serializing_if = "Option::is_none")]
355 /// The location in the source code that this operation originated from.
356 pub source: Option<SourceLocation>,
357 #[serde(skip_serializing_if = "Option::is_none")]
358 /// Only populated if this operation represents a scope group.
359 pub scope_location: Option<SourceLocation>,
360}
361
362#[derive(Clone, Serialize, Deserialize, Debug)]
363pub struct SourceLocation {
364 pub file: String,
365 pub line: u32,
366 pub column: u32,
367}
368
369impl Display for SourceLocation {
370 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
371 write!(f, "{}:{}:{}", self.file, self.line, self.column)
372 }
373}
374
375/// First by column, then by row.
376type ObjectsByColumnAndRow = FxHashMap<usize, FxHashMap<i16, CircuitObject>>;
377
378struct RowBuilder {
379 wire: Wire,
380 max_depth_above_axis: u8,
381 current_top_offset: u8,
382 current_bottom_offset: u8,
383 max_depth_below_axis: u8,
384 objects: ObjectsByColumnAndRow,
385 next_column: usize,
386 render_locations: bool,
387}
388
389#[derive(Clone)]
390enum Wire {
391 None, // TODO: abolish
392 Qubit { label: String },
393 Classical { start_column: Option<usize> },
394}
395
396#[derive(Debug, Clone)]
397enum CircuitObject {
398 Blank, // TODO: blank is silly, get rid of it
399 Wire,
400 WireStart,
401 Vertical,
402 VerticalDashed,
403 Horizontal,
404 TopLeftCorner,
405 TopRightCorner,
406 BottomLeftCorner,
407 BottomRightCorner,
408 Object(String),
409 GroupLabel(String),
410}
411
412impl RowBuilder {
413 fn add_object_to_row_wire(&mut self, column: usize, object: &str) {
414 self.add_to_row_wire(column, CircuitObject::Object(object.to_string()));
415 }
416
417 fn increment_current_top_offset(&mut self) {
418 self.current_top_offset += 1;
419 self.max_depth_above_axis = max(self.max_depth_above_axis, self.current_top_offset + 1);
420 }
421
422 fn increment_current_bottom_offset(&mut self) {
423 self.current_bottom_offset += 1;
424 self.max_depth_below_axis = max(self.max_depth_below_axis, self.current_bottom_offset + 1);
425 }
426
427 fn decrement_current_top_offset(&mut self) {
428 if self.current_top_offset > 0 {
429 self.current_top_offset -= 1;
430 }
431 }
432
433 fn decrement_current_bottom_offset(&mut self) {
434 if self.current_bottom_offset > 0 {
435 self.current_bottom_offset -= 1;
436 }
437 }
438
439 fn add_measurement(&mut self, column: usize, source: Option<&SourceLocation>) {
440 let mut gate_label = String::from("M");
441 if self.render_locations
442 && let Some(loc) = source
443 {
444 let _ = write!(&mut gate_label, "@{loc}");
445 }
446 self.add_to_row_wire(column, CircuitObject::Object(gate_label.clone()));
447 }
448
449 fn add_gate(&mut self, column: usize, operation: &Operation) {
450 let gate_label = self.operation_label(operation);
451
452 self.add_object(column, gate_label.as_str());
453 }
454
455 fn add_object(&mut self, column: usize, object: &str) {
456 self.add_to_row_wire(column, CircuitObject::Object(object.to_string()));
457 }
458
459 fn operation_label(&self, operation: &Operation) -> String {
460 let mut gate_label = String::new();
461 gate_label.push_str(&operation.gate());
462 if operation.is_adjoint() {
463 gate_label.push('\'');
464 }
465
466 if !operation.args().is_empty() {
467 let args = operation.args().join(", ");
468 let _ = write!(&mut gate_label, "({args})");
469 }
470
471 if self.render_locations
472 && let Some(loc) = operation.source_location()
473 {
474 let _ = write!(&mut gate_label, "@{loc}");
475 }
476
477 gate_label
478 }
479
480 fn start_classical(&mut self, column: usize) {
481 self.add_to_row_wire(column, CircuitObject::WireStart);
482 if let Wire::Classical { start_column } = &mut self.wire {
483 start_column.replace(column);
484 }
485 }
486
487 fn add_to_row_wire(&mut self, column: usize, circuit_object: CircuitObject) {
488 let row_row = self.objects.entry(column).or_default();
489 row_row.insert(0, circuit_object);
490 self.next_column = column + 1;
491 }
492
493 fn add_to_current_top(&mut self, column: usize, obj: CircuitObject) {
494 let row_row = self.objects.entry(column).or_default();
495 row_row.insert(i16::from(self.current_top_offset), obj);
496 self.next_column = column + 1;
497 }
498
499 fn add_to_current_bottom(&mut self, column: usize, obj: CircuitObject) {
500 let row_row = self.objects.entry(column).or_default();
501 row_row.insert(-i16::from(self.current_bottom_offset), obj);
502 self.next_column = column + 1;
503 }
504
505 fn expand_rows(mut self) -> Vec<Row> {
506 for column_objects in self.objects.values_mut() {
507 // Do the wire row (row 0)
508 if let Some(object) = column_objects.get(&0) {
509 // If we encountered a vertical, we need to fill in the rest of the column
510 if matches!(object, CircuitObject::Vertical) {
511 for r in 0..self.max_depth_above_axis {
512 column_objects.insert(i16::from(r), CircuitObject::Vertical);
513 }
514 for r in 0..self.max_depth_below_axis {
515 column_objects.insert(-i16::from(r), CircuitObject::Vertical);
516 }
517 }
518 }
519
520 let mut top_corner_height = None;
521 let mut bottom_corner_height = None;
522 // Do the rows above zero
523 for height_offset_from_top in 1..self.max_depth_above_axis {
524 if let Some(object) = column_objects.get(&i16::from(height_offset_from_top)) {
525 // if we encountered a box corner, we need to fill in the rest of the column
526 if matches!(
527 object,
528 CircuitObject::TopLeftCorner | CircuitObject::TopRightCorner
529 ) {
530 top_corner_height.replace(height_offset_from_top);
531 }
532 }
533 }
534
535 // Do the rows below zero
536 for height_offset_from_bottom in 1..self.max_depth_below_axis {
537 if let Some(object) = column_objects.get(&-i16::from(height_offset_from_bottom)) {
538 // if we encountered a box corner, we need to fill in the rest of the column
539 if matches!(
540 object,
541 CircuitObject::BottomLeftCorner | CircuitObject::BottomRightCorner
542 ) {
543 bottom_corner_height.replace(height_offset_from_bottom);
544 }
545 }
546 }
547
548 if let Some(top_corner_height) = top_corner_height {
549 for r in (top_corner_height + 1)..self.max_depth_above_axis {
550 column_objects.insert(i16::from(r), CircuitObject::Vertical);
551 }
552 // Do zero as well
553 column_objects.insert(0, CircuitObject::Vertical);
554
555 if bottom_corner_height.is_none() {
556 // Do the rows below zero
557 for r in 1..self.max_depth_below_axis {
558 column_objects.insert(-i16::from(r), CircuitObject::Vertical);
559 }
560 }
561 }
562
563 if let Some(bottom_corner_height) = bottom_corner_height {
564 for r in bottom_corner_height + 1..self.max_depth_below_axis {
565 column_objects.insert(-i16::from(r), CircuitObject::Vertical);
566 }
567 // Do zero as well
568 column_objects.insert(0, CircuitObject::Vertical);
569
570 if top_corner_height.is_none() {
571 // Do the rows above zero
572 for r in 1..self.max_depth_above_axis {
573 column_objects.insert(i16::from(r), CircuitObject::Vertical);
574 }
575 }
576 }
577 }
578
579 let mut top_rows = Vec::new();
580 // Do the rows above zero
581 for height_offset_from_top in 1..self.max_depth_above_axis {
582 let mut row_objects = FxHashMap::default();
583 for (column, column_objects) in &mut self.objects {
584 if let Some(object) = column_objects.remove(&i16::from(height_offset_from_top)) {
585 row_objects.insert(*column, object);
586 }
587 }
588 top_rows.push(Row {
589 wire: Wire::None,
590 objects: row_objects,
591 });
592 }
593
594 // Do the wire row (row 0)
595 let idx = 0;
596 let mut row_objects = FxHashMap::default();
597 for (column, column_objects) in &mut self.objects {
598 if let Some(object) = column_objects.remove(&idx) {
599 row_objects.insert(*column, object);
600 }
601 }
602 let mid_row = Row {
603 wire: self.wire,
604 objects: row_objects,
605 };
606
607 let mut bottom_rows = vec![];
608 // Do the rows below zero
609 for height_offset_from_bottom in 1..self.max_depth_below_axis {
610 let mut row_objects = FxHashMap::default();
611 for (column, column_objects) in &mut self.objects {
612 if let Some(object) = column_objects.remove(&-i16::from(height_offset_from_bottom))
613 {
614 row_objects.insert(*column, object);
615 }
616 }
617 bottom_rows.push(Row {
618 wire: Wire::None,
619 objects: row_objects,
620 });
621 }
622
623 let mut rows = vec![];
624 rows.extend(top_rows);
625 rows.push(mid_row);
626
627 bottom_rows.reverse();
628 rows.extend(bottom_rows);
629
630 rows
631 }
632}
633
634type ObjectsByColumn = FxHashMap<usize, CircuitObject>;
635
636struct Row {
637 wire: Wire,
638 objects: ObjectsByColumn,
639}
640
641impl Row {
642 fn fmt(&self, f: &mut std::fmt::Formatter<'_>, columns: &[Column]) -> std::fmt::Result {
643 // Temporary string so we can trim whitespace at the end
644 let mut s = String::new();
645 match &self.wire {
646 Wire::None => {
647 for (column_index, column) in columns.iter().enumerate() {
648 let obj = self.objects.get(&column_index);
649 s.write_str(&column.fmt_object(obj))?;
650 }
651 }
652 Wire::Qubit { label } => {
653 s.write_str(&columns[0].fmt_qubit_label(label))?;
654 for (column_index, column) in columns.iter().enumerate().skip(1) {
655 let obj = self.objects.get(&column_index);
656
657 s.write_str(&column.fmt_object_on_qubit_wire(obj))?;
658 }
659 }
660 Wire::Classical { start_column } => {
661 for (column_index, column) in columns.iter().enumerate() {
662 let obj = self.objects.get(&column_index);
663
664 if let Some(start) = *start_column
665 && column_index > start
666 {
667 s.write_str(&column.fmt_object_on_classical_wire(obj))?;
668 } else {
669 s.write_str(&column.fmt_object(obj))?;
670 }
671 }
672 }
673 }
674 writeln!(f, "{}", s.trim_end())?;
675 Ok(())
676 }
677}
678
679const MIN_COLUMN_WIDTH: usize = 7;
680
681const QUBIT_WIRE: [char; 3] = ['─', '─', '─']; // "───────"
682const CLASSICAL_WIRE: [char; 3] = ['═', '═', '═']; // "═══════"
683const QUBIT_WIRE_CROSS: [char; 3] = ['─', '┼', '─']; // "───┼───"
684const CLASSICAL_WIRE_CROSS: [char; 3] = ['═', '╪', '═']; // "═══╪═══"
685const CLASSICAL_WIRE_START: [char; 3] = [' ', '╘', '═']; // " ╘═══"
686const QUBIT_WIRE_DASHED_CROSS: [char; 3] = ['─', '┆', '─']; // "───┆───"
687const CLASSICAL_WIRE_DASHED_CROSS: [char; 3] = ['═', '┆', '═']; // "═══┆═══"
688const VERTICAL_DASHED: [char; 3] = [' ', '┆', ' ']; // " ┆ "
689const VERTICAL: [char; 3] = [' ', '│', ' ']; // " │ "
690const BLANK: [char; 3] = [' ', ' ', ' ']; // " "
691const TOP_LEFT_CORNER: [char; 3] = [' ', '┌', '─']; // " ┌───"
692const TOP_RIGHT_CORNER: [char; 3] = ['─', '┐', ' ']; // "───┐ "
693const BOTTOM_LEFT_CORNER: [char; 3] = [' ', '└', '─']; // " └───"
694const BOTTOM_RIGHT_CORNER: [char; 3] = ['─', '┘', ' ']; // "───┘ "
695
696struct Column {
697 column_width: usize,
698}
699
700impl Column {
701 fn new(column_width: usize) -> Self {
702 // Column widths should be odd numbers for this struct to work well
703 let odd_column_width = column_width | 1;
704 Self {
705 column_width: odd_column_width,
706 }
707 }
708
709 /// "q_0 "
710 #[allow(clippy::doc_markdown)]
711 fn fmt_qubit_label(&self, label: &str) -> String {
712 let column_width = self.column_width;
713 let s = format!("{label:<column_width$}");
714 s
715 }
716
717 /// "── A ──"
718 fn fmt_on_qubit_wire(&self, obj: &str) -> String {
719 let column_width = self.column_width;
720 format!("{:─^column_width$}", format!(" {obj} "))
721 }
722
723 /// "══ A ══"
724 fn fmt_on_classical_wire(&self, obj: &str) -> String {
725 let column_width = self.column_width;
726 format!("{:═^column_width$}", format!(" {obj} "))
727 }
728
729 /// " A "
730 fn fmt_on_blank(&self, obj: &str) -> String {
731 let column_width = self.column_width;
732 format!("{: ^column_width$}", format!(" {obj} "))
733 }
734
735 fn expand_template(&self, template: &[char; 3]) -> String {
736 let half_width = self.column_width / 2;
737 let left = template[0].to_string().repeat(half_width);
738 let right = template[2].to_string().repeat(half_width);
739
740 format!("{left}{}{right}", template[1])
741 }
742
743 fn fmt_object_on_classical_wire(&self, circuit_object: Option<&CircuitObject>) -> String {
744 let circuit_object = circuit_object.unwrap_or(&CircuitObject::Wire);
745
746 if let CircuitObject::Object(label) = circuit_object {
747 return self.fmt_on_classical_wire(label.as_str());
748 }
749
750 let template = match circuit_object {
751 CircuitObject::Wire => CLASSICAL_WIRE,
752 CircuitObject::Vertical => CLASSICAL_WIRE_CROSS,
753 CircuitObject::WireStart => CLASSICAL_WIRE_START,
754 CircuitObject::VerticalDashed => CLASSICAL_WIRE_DASHED_CROSS,
755 o @ (CircuitObject::Blank
756 | CircuitObject::TopLeftCorner
757 | CircuitObject::TopRightCorner
758 | CircuitObject::BottomLeftCorner
759 | CircuitObject::BottomRightCorner
760 | CircuitObject::Horizontal
761 | CircuitObject::GroupLabel(_)) => {
762 unreachable!("unexpected object on blank row: {o:?}")
763 }
764 CircuitObject::Object(_) => unreachable!("case should have been handled earlier"),
765 };
766
767 self.expand_template(&template)
768 }
769
770 fn fmt_object_on_qubit_wire(&self, circuit_object: Option<&CircuitObject>) -> String {
771 let circuit_object = circuit_object.unwrap_or(&CircuitObject::Wire);
772 if let CircuitObject::Object(label) = circuit_object {
773 return self.fmt_on_qubit_wire(label.as_str());
774 }
775
776 let template = match circuit_object {
777 CircuitObject::Wire => QUBIT_WIRE,
778 CircuitObject::Vertical => QUBIT_WIRE_CROSS,
779 CircuitObject::VerticalDashed => QUBIT_WIRE_DASHED_CROSS,
780 CircuitObject::WireStart
781 | CircuitObject::Blank
782 | CircuitObject::TopLeftCorner
783 | CircuitObject::TopRightCorner
784 | CircuitObject::BottomLeftCorner
785 | CircuitObject::BottomRightCorner
786 | CircuitObject::Horizontal
787 | CircuitObject::Object(_)
788 | CircuitObject::GroupLabel(_) => unreachable!(),
789 };
790
791 self.expand_template(&template)
792 }
793
794 fn fmt_object(&self, circuit_object: Option<&CircuitObject>) -> String {
795 let circuit_object = circuit_object.unwrap_or(&CircuitObject::Blank);
796 if let CircuitObject::Object(label) = circuit_object {
797 return self.fmt_on_blank(label.as_str());
798 }
799
800 if let CircuitObject::GroupLabel(label) = circuit_object {
801 // Technically we're not on a qubit wire, but here we're
802 // repurposing the qubit wire line character for the horizontal box line
803 return self.fmt_on_qubit_wire(label.as_str());
804 }
805
806 let template = match circuit_object {
807 CircuitObject::WireStart => CLASSICAL_WIRE_START,
808 CircuitObject::Blank => BLANK,
809 CircuitObject::Vertical => VERTICAL,
810 CircuitObject::VerticalDashed => VERTICAL_DASHED,
811 CircuitObject::TopLeftCorner => TOP_LEFT_CORNER,
812 CircuitObject::TopRightCorner => TOP_RIGHT_CORNER,
813 CircuitObject::Horizontal => QUBIT_WIRE,
814 CircuitObject::BottomLeftCorner => BOTTOM_LEFT_CORNER,
815 CircuitObject::BottomRightCorner => BOTTOM_RIGHT_CORNER,
816 o @ CircuitObject::Wire => {
817 unreachable!("unexpected object on blank row: {o:?}")
818 }
819 CircuitObject::Object(_) | CircuitObject::GroupLabel(_) => {
820 unreachable!("case should have been handled earlier")
821 }
822 };
823
824 self.expand_template(&template)
825 }
826}
827
828struct CircuitDisplay<'a> {
829 circuit: &'a Circuit,
830 render_locations: bool,
831 render_groups: bool,
832}
833
834impl Display for CircuitDisplay<'_> {
835 /// Formats the circuit into a diagram.
836 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
837 // Identify qubits that require gap rows
838 let qubits_with_gap_row_below = self.identify_qubits_with_gap_rows();
839
840 // Initialize rows for qubits and classical wires
841 let (mut rows, register_to_row) = self.initialize_rows(&qubits_with_gap_row_below);
842
843 // Add operations to the diagram
844 self.add_grid(1, &self.circuit.component_grid, &mut rows, &register_to_row);
845
846 // Finalize the diagram by extending wires and formatting columns
847 let columns = finalize_columns(&rows);
848
849 // Draw the diagram
850 for row in rows {
851 let subrows = row.expand_rows();
852 for subrow in subrows {
853 subrow.fmt(f, &columns)?;
854 }
855 }
856
857 Ok(())
858 }
859}
860
861type Rows = (Vec<RowBuilder>, FxHashMap<(usize, Option<usize>), usize>);
862
863impl CircuitDisplay<'_> {
864 /// Identifies qubits that require gap rows for multi-qubit operations.
865 fn identify_qubits_with_gap_rows(&self) -> FxHashSet<usize> {
866 // Keep track of which qubits have the qubit after them in the same multi-qubit operation,
867 // because those qubits need to get a gap row below them.
868 let mut qubits_with_gap_row_below = FxHashSet::default();
869
870 for col in &self.circuit.component_grid {
871 for op in &col.components {
872 if !op.children().is_empty() {
873 continue;
874 }
875 let targets = match op {
876 Operation::Measurement(m) => &m.qubits,
877 Operation::Unitary(u) => &u.targets,
878 Operation::Ket(k) => &k.targets,
879 };
880 for target in targets {
881 let qubit = target.qubit;
882
883 if qubits_with_gap_row_below.contains(&qubit) {
884 continue;
885 }
886
887 let next_qubit = qubit + 1;
888
889 // Check if the next qubit is also in this operation.
890 if targets.iter().any(|t| t.qubit == next_qubit) {
891 qubits_with_gap_row_below.insert(qubit);
892 }
893 }
894 }
895 }
896 qubits_with_gap_row_below
897 }
898
899 /// Initializes rows for qubits and classical wires.
900 fn initialize_rows(&self, qubits_with_gap_row_below: &FxHashSet<usize>) -> Rows {
901 // Maintain a mapping from from Registers in the Circuit schema
902 // to row in the diagram
903 let mut register_to_row = FxHashMap::default();
904
905 let mut rows = vec![];
906 for q in &self.circuit.qubits {
907 let mut label = format!("q_{}", q.id);
908 if self.render_locations {
909 let mut first = true;
910 for loc in &q.declarations {
911 if first {
912 label.push('@');
913 first = false;
914 } else {
915 label.push_str(", ");
916 }
917 let _ = write!(&mut label, "{loc}");
918 }
919 }
920
921 rows.push(RowBuilder {
922 wire: Wire::Qubit { label },
923 max_depth_above_axis: 1,
924 max_depth_below_axis: 0,
925 current_top_offset: 0,
926 current_bottom_offset: 0,
927 objects: FxHashMap::default(),
928 next_column: 1,
929 render_locations: self.render_locations,
930 });
931
932 // associate this qubit register with this row
933 register_to_row.insert((q.id, None), rows.len() - 1);
934
935 for i in 0..q.num_results {
936 rows.push(RowBuilder {
937 wire: Wire::Classical { start_column: None },
938 max_depth_above_axis: 1,
939 max_depth_below_axis: 0,
940 current_top_offset: 0,
941 current_bottom_offset: 0,
942 objects: FxHashMap::default(),
943 next_column: 1,
944 render_locations: self.render_locations,
945 });
946
947 // associate this result register with this row
948 register_to_row.insert((q.id, Some(i)), rows.len() - 1);
949 }
950
951 let qubit_bottom_padding = q.num_results;
952
953 // If this qubit has no result wires, but it is in a multi-qubit operation with
954 // the next qubit, we add an empty row to make room for the vertical connector.
955 if qubits_with_gap_row_below.contains(&q.id) && qubit_bottom_padding == 0 {
956 rows.push(RowBuilder {
957 wire: Wire::None,
958 max_depth_above_axis: 1,
959 current_top_offset: 0,
960 current_bottom_offset: 0,
961 max_depth_below_axis: 0,
962 objects: FxHashMap::default(),
963 next_column: 1,
964 render_locations: self.render_locations,
965 });
966 }
967 }
968
969 (rows, register_to_row)
970 }
971
972 fn add_grid(
973 &self,
974 start_column: usize,
975 component_grid: &ComponentGrid,
976 rows: &mut [RowBuilder],
977 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
978 ) -> usize {
979 let mut curr_column = start_column;
980 for column_operations in component_grid {
981 let offset = self.add_column(rows, register_to_row, curr_column, column_operations);
982 curr_column += offset;
983 }
984 curr_column - start_column
985 }
986
987 fn add_column(
988 &self,
989 rows: &mut [RowBuilder],
990 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
991 column: usize,
992 col: &ComponentColumn,
993 ) -> usize {
994 let mut col_width = 0;
995 for op in &col.components {
996 let target_rows = get_row_indexes(op, register_to_row, true);
997 let control_rows = get_row_indexes(op, register_to_row, false);
998
999 let mut all_rows = target_rows.clone();
1000 all_rows.extend(control_rows.iter());
1001 all_rows.sort_unstable();
1002
1003 // We'll need to know the entire range of rows for this operation so we can
1004 // figure out the starting column and also so we can draw any
1005 // vertical lines that cross wires.
1006 let (begin, end) = all_rows.split_first().map_or((0, 0), |(first, tail)| {
1007 (*first, tail.last().unwrap_or(first) + 1)
1008 });
1009
1010 if op.children().is_empty() {
1011 add_operation_to_rows(op, rows, &target_rows, &control_rows, column, begin, end);
1012 col_width = max(col_width, 1);
1013 } else {
1014 let offset = self.add_boxed_group(rows, register_to_row, column, op, op.children());
1015 col_width = max(col_width, offset);
1016 }
1017 }
1018
1019 for column in column..(column + col_width) {
1020 for r in &mut *rows {
1021 if r.current_top_offset > 0 {
1022 for o in 1..=r.current_top_offset {
1023 r.objects
1024 .entry(column)
1025 .or_default()
1026 .entry(i16::from(o))
1027 .or_insert(CircuitObject::Horizontal);
1028 }
1029 }
1030
1031 if r.current_bottom_offset > 0 {
1032 for o in 1..=r.current_bottom_offset {
1033 r.objects
1034 .entry(column)
1035 .or_default()
1036 .entry(-i16::from(o))
1037 .or_insert(CircuitObject::Horizontal);
1038 }
1039 }
1040 }
1041 }
1042 col_width
1043 }
1044
1045 fn add_boxed_group(
1046 &self,
1047 rows: &mut [RowBuilder],
1048 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
1049 column: usize,
1050 op: &Operation,
1051 children: &Vec<ComponentColumn>,
1052 ) -> usize {
1053 assert!(
1054 !op.children().is_empty(),
1055 "must only be called for an operation with children"
1056 );
1057 // TODO: draw control lines
1058 // assert!(
1059 // !op.is_controlled(),
1060 // "rendering controlled boxes not supported"
1061 // );
1062 assert!(
1063 !op.is_measurement(),
1064 "rendering measurement boxes not supported"
1065 );
1066
1067 let mut all_registers = registers(op, true);
1068 all_registers.extend(registers(op, false));
1069
1070 let mut offset = 0;
1071 if self.render_groups {
1072 add_box_start(op, rows, &all_registers, register_to_row, column);
1073 offset += 1;
1074 }
1075
1076 offset += self.add_grid(column + offset, children, rows, register_to_row);
1077
1078 if self.render_groups {
1079 add_box_end(op, rows, &all_registers, register_to_row, column + offset);
1080 offset += 1;
1081 }
1082 offset
1083 }
1084}
1085
1086/// Adds a single operation to the rows.
1087fn add_operation_to_rows(
1088 operation: &Operation,
1089 rows: &mut [RowBuilder],
1090 targets: &[usize],
1091 controls: &[usize],
1092 column: usize,
1093 begin: usize,
1094 end: usize,
1095) {
1096 for i in targets {
1097 let row = &mut rows[*i];
1098 if matches!(row.wire, Wire::Classical { .. })
1099 && matches!(operation, Operation::Measurement(_))
1100 {
1101 row.start_classical(column);
1102 } else {
1103 row.add_gate(column, operation);
1104 }
1105 }
1106
1107 if operation.is_controlled() || operation.is_measurement() {
1108 for i in controls {
1109 let row = &mut rows[*i];
1110 if matches!(row.wire, Wire::Qubit { .. }) && operation.is_measurement() {
1111 row.add_measurement(column, operation.source_location());
1112 } else {
1113 row.add_object_to_row_wire(column, "●");
1114 }
1115 }
1116
1117 // If we have a control wire, draw vertical lines spanning all
1118 // control and target wires and crossing any in between
1119 // (vertical lines may overlap if there are multiple controls/targets,
1120 // this is ok in practice)
1121 #[allow(clippy::needless_range_loop)]
1122 for i in begin..end {
1123 let row = &mut rows[i];
1124 let existing = row
1125 .objects
1126 .get(&column)
1127 .cloned()
1128 .unwrap_or_default()
1129 .remove(&0);
1130 if let Some(existing) = existing {
1131 // TODO: this definitely doesn't work
1132 if let CircuitObject::Object(_) = existing {
1133 if i == begin {
1134 for sr in 1..=row.current_bottom_offset {
1135 // add vertical to subrows below axis
1136 let row_row = row.objects.entry(column).or_default();
1137 row_row.insert(-i16::from(sr), CircuitObject::Vertical);
1138 }
1139 } else if i == end - 1 {
1140 for sr in 1..=row.current_top_offset {
1141 // add vertical to subrows above axis
1142 let row_row = row.objects.entry(column).or_default();
1143 row_row.insert(i16::from(sr), CircuitObject::Vertical);
1144 }
1145 } else {
1146 // crossing wire, leave as is
1147 }
1148 }
1149 } else {
1150 row.add_to_row_wire(column, CircuitObject::Vertical);
1151 }
1152 }
1153 } else {
1154 // No control wire. Draw dashed vertical lines to connect
1155 // target wires if there are multiple targets
1156 for row in &mut rows[begin..end] {
1157 if !row.objects.contains_key(&column) {
1158 row.add_to_row_wire(column, CircuitObject::VerticalDashed);
1159 }
1160 }
1161 }
1162}
1163
1164fn add_box_start(
1165 operation: &Operation,
1166 rows: &mut [RowBuilder],
1167 registers: &[Register],
1168 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
1169 column: usize,
1170) {
1171 let mut registers = registers.to_vec();
1172 registers.sort_unstable_by_key(|r| (r.qubit, r.result));
1173
1174 // Split into groups of consecutive registers
1175 let mut groups: Vec<Vec<Register>> = vec![];
1176 let mut current_group: Vec<Register> = vec![];
1177 for reg in &registers {
1178 if let Some(last_reg) = current_group.last() {
1179 if reg.qubit == last_reg.qubit || reg.qubit == last_reg.qubit + 1 {
1180 current_group.push(reg.clone());
1181 } else {
1182 groups.push(current_group);
1183 current_group = vec![reg.clone()];
1184 }
1185 } else {
1186 current_group.push(reg.clone());
1187 }
1188 }
1189 if !current_group.is_empty() {
1190 groups.push(current_group);
1191 }
1192
1193 if groups.len() > 1 {
1194 for group in &groups {
1195 add_box_start(operation, rows, group, register_to_row, column);
1196 }
1197 // add dashed vertical lines between groups
1198 for i in 0..(groups.len() - 1) {
1199 let last_reg_of_group = groups[i]
1200 .last()
1201 .expect("group must have at least one register");
1202 let next_reg_of_group = groups[i + 1]
1203 .first()
1204 .expect("group must have at least one register");
1205 let last_row = *register_to_row
1206 .get(&(last_reg_of_group.qubit, last_reg_of_group.result))
1207 .expect("register must map to a row");
1208 let next_row = *register_to_row
1209 .get(&(next_reg_of_group.qubit, next_reg_of_group.result))
1210 .expect("register must map to a row");
1211 for row in &mut rows[(last_row + 1)..next_row] {
1212 // TODO: should this be column + 1?
1213 row.add_to_row_wire(column + 1, CircuitObject::VerticalDashed);
1214 }
1215 }
1216 return;
1217 }
1218
1219 // Handle single group
1220
1221 let first_register = registers
1222 .first()
1223 .expect("there should at least be one register in group");
1224 let last_register = registers
1225 .last()
1226 .expect("there should at least be one register in group");
1227
1228 let first_row = *register_to_row
1229 .get(&(first_register.qubit, first_register.result))
1230 .expect("register must map to a row");
1231
1232 let last_row = *register_to_row
1233 .get(&(last_register.qubit, last_register.result))
1234 .expect("register must map to a row");
1235
1236 // Add the vertical line for the box start
1237 rows[first_row].increment_current_top_offset();
1238 rows[last_row].increment_current_bottom_offset();
1239 add_vertical_box_border(rows, column, first_row, last_row, true);
1240
1241 // Add label to the top
1242 let label = group_label(operation);
1243 rows[first_row].add_to_current_top(column + 1, CircuitObject::GroupLabel(label));
1244}
1245
1246fn add_vertical_box_border(
1247 rows: &mut [RowBuilder],
1248 column: usize,
1249 first_row: usize,
1250 last_row: usize,
1251 is_start: bool,
1252) {
1253 let top = if is_start {
1254 CircuitObject::TopLeftCorner
1255 } else {
1256 CircuitObject::TopRightCorner
1257 };
1258 let bottom = if is_start {
1259 CircuitObject::BottomLeftCorner
1260 } else {
1261 CircuitObject::BottomRightCorner
1262 };
1263 rows[first_row].add_to_current_top(column, top);
1264 let second_from_top = first_row.saturating_add(1);
1265 let second_from_bottom = last_row.saturating_sub(1);
1266 if second_from_bottom >= second_from_top {
1267 for row in &mut rows[second_from_top..=second_from_bottom] {
1268 row.add_to_row_wire(column, CircuitObject::Vertical);
1269 }
1270 }
1271 rows[last_row].add_to_current_bottom(column, bottom);
1272}
1273
1274fn group_label(operation: &Operation) -> String {
1275 let mut gate_label = String::new();
1276 gate_label.push('[');
1277 gate_label.push_str(&operation.gate());
1278 if operation.is_adjoint() {
1279 gate_label.push('\'');
1280 }
1281 let args = operation.args();
1282
1283 if !args.is_empty() {
1284 let args = args.join(", ");
1285 let _ = write!(&mut gate_label, "({args})");
1286 }
1287
1288 if let Some(loc) = operation.source_location() {
1289 let _ = write!(&mut gate_label, "@{loc}");
1290 }
1291
1292 gate_label.push(']');
1293 gate_label
1294}
1295
1296fn add_box_end(
1297 operation: &Operation,
1298 rows: &mut [RowBuilder],
1299 registers: &[Register],
1300 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
1301 column: usize,
1302) {
1303 assert!(
1304 !operation.children().is_empty(),
1305 "must only be called for an operation with children"
1306 );
1307
1308 let mut registers = registers.to_vec();
1309 registers.sort_unstable_by_key(|r| (r.qubit, r.result));
1310
1311 // Split into groups of consecutive registers
1312 let mut groups: Vec<Vec<Register>> = vec![];
1313 let mut current_group: Vec<Register> = vec![];
1314 for reg in &registers {
1315 if let Some(last_reg) = current_group.last() {
1316 if reg.qubit == last_reg.qubit || reg.qubit == last_reg.qubit + 1 {
1317 current_group.push(reg.clone());
1318 } else {
1319 groups.push(current_group);
1320 current_group = vec![reg.clone()];
1321 }
1322 } else {
1323 current_group.push(reg.clone());
1324 }
1325 }
1326 if !current_group.is_empty() {
1327 groups.push(current_group);
1328 }
1329
1330 if groups.len() > 1 {
1331 for group in &groups {
1332 add_box_end(operation, rows, group, register_to_row, column);
1333 }
1334 return;
1335 }
1336
1337 let first = *register_to_row
1338 .get(&(
1339 registers
1340 .first()
1341 .expect("registers should not be empty")
1342 .qubit,
1343 registers
1344 .first()
1345 .expect("registers should not be empty")
1346 .result,
1347 ))
1348 .expect("register must map to a row");
1349 let last = *register_to_row
1350 .get(&(
1351 registers
1352 .last()
1353 .expect("registers should not be empty")
1354 .qubit,
1355 registers
1356 .last()
1357 .expect("registers should not be empty")
1358 .result,
1359 ))
1360 .expect("register must map to a row");
1361
1362 // Add the vertical line for the box start
1363 add_vertical_box_border(rows, column, first, last, false);
1364
1365 rows[first].decrement_current_top_offset();
1366 rows[last].decrement_current_bottom_offset();
1367}
1368
1369/// Finalizes the columns by calculating their widths.
1370fn finalize_columns(rows: &[RowBuilder]) -> Vec<Column> {
1371 // Find the end column for the whole circuit so that
1372 // all qubit wires will extend until the end
1373 let end_column = rows
1374 .iter()
1375 .max_by_key(|r| r.next_column)
1376 .map_or(1, |r| r.next_column);
1377
1378 let longest_qubit_label = rows
1379 .iter()
1380 .map(|r| {
1381 if let Wire::Qubit { label } = &r.wire {
1382 label.len() + 1
1383 } else {
1384 0
1385 }
1386 })
1387 .chain(std::iter::once(MIN_COLUMN_WIDTH))
1388 .max()
1389 .unwrap_or_default();
1390
1391 // To be able to fit long-named operations, we calculate the required width for each column,
1392 // based on the maximum length needed for gates, where a gate X is printed as "- X -".
1393 std::iter::once(longest_qubit_label)
1394 .chain((1..end_column).map(|column| {
1395 rows.iter()
1396 .filter_map(|row| row.objects.get(&column))
1397 .flat_map(|row_row| row_row.values())
1398 .filter_map(|object| match object {
1399 CircuitObject::Object(string) | CircuitObject::GroupLabel(string) => {
1400 Some(string.len() + 4)
1401 }
1402 _ => None,
1403 })
1404 .chain(std::iter::once(MIN_COLUMN_WIDTH))
1405 .max()
1406 .expect("Column width should be at least 1")
1407 }))
1408 .map(Column::new)
1409 .collect()
1410}
1411
1412/// Gets the row indexes for the targets or controls of an operation.
1413fn get_row_indexes(
1414 operation: &Operation,
1415 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
1416 is_target: bool,
1417) -> Vec<usize> {
1418 let registers = registers(operation, is_target);
1419
1420 registers
1421 .into_iter()
1422 .filter_map(|reg| {
1423 let reg = (reg.qubit, reg.result);
1424 register_to_row.get(&reg).copied()
1425 })
1426 .collect()
1427}
1428
1429fn registers(operation: &Operation, is_target: bool) -> Vec<Register> {
1430 match operation {
1431 Operation::Measurement(m) => {
1432 if is_target {
1433 m.results.clone()
1434 } else {
1435 m.qubits.clone()
1436 }
1437 }
1438 Operation::Unitary(u) => {
1439 if is_target {
1440 u.targets.clone()
1441 } else {
1442 u.controls.clone()
1443 }
1444 }
1445 Operation::Ket(k) => {
1446 if is_target {
1447 k.targets.clone()
1448 } else {
1449 vec![]
1450 }
1451 }
1452 }
1453}
1454
1455/// Converts a list of operations into a 2D grid of operations in col-row format.
1456/// Operations will be left-justified as much as possible in the resulting grid.
1457/// Children operations are recursively converted into a grid.
1458///
1459/// # Arguments
1460///
1461/// * `operations` - A vector of operations to be converted.
1462/// * `num_qubits` - The number of qubits in the circuit.
1463///
1464/// # Returns
1465///
1466/// A component grid representing the operations.
1467#[must_use]
1468pub fn operation_list_to_grid(
1469 operations: Vec<Operation>,
1470 qubits: &[Qubit],
1471 loop_detection: bool,
1472) -> ComponentGrid {
1473 let operations = if loop_detection {
1474 collapse_repetition(operations)
1475 } else {
1476 operations
1477 };
1478
1479 operation_list_to_grid_inner(operations, qubits)
1480}
1481
1482fn collapse_repetition(mut operations: Vec<Operation>) -> Vec<Operation> {
1483 for op in &mut operations {
1484 if !op.children().is_empty() {
1485 assert_eq!(
1486 op.children().len(),
1487 1,
1488 "children should be a single list at this point"
1489 );
1490 let mut first = op.children_mut().remove(0);
1491 first.components = collapse_repetition(first.components);
1492 op.children_mut().push(first);
1493 }
1494 }
1495 collapse_repetition_base(operations)
1496}
1497
1498fn operation_list_to_grid_inner(
1499 mut operations: Vec<Operation>,
1500 qubits: &[Qubit],
1501) -> Vec<ComponentColumn> {
1502 for op in &mut operations {
1503 // The children data structure is a grid, so checking if it is
1504 // length 1 is actually checking if it has a single column,
1505 // or in other words, we are checking if its children are in a single list.
1506 // If the operation has children in a single list, it needs to be converted to a grid.
1507 // If it was already converted to a grid, but the grid was still a single list,
1508 // then doing it again won't effect anything.
1509 if op.children().len() == 1 {
1510 match op {
1511 Operation::Measurement(m) => {
1512 let child_vec = m.children.remove(0).components; // owns
1513 m.children = operation_list_to_grid_inner(child_vec, qubits);
1514 }
1515 Operation::Unitary(u) => {
1516 let child_vec = u.children.remove(0).components;
1517 u.children = operation_list_to_grid_inner(child_vec, qubits);
1518 }
1519 Operation::Ket(k) => {
1520 let child_vec = k.children.remove(0).components;
1521 k.children = operation_list_to_grid_inner(child_vec, qubits);
1522 }
1523 }
1524 }
1525 }
1526
1527 // Convert the operations into a component grid
1528 operation_list_to_grid_base(operations, qubits)
1529}
1530
1531#[derive(Debug)]
1532struct RowInfo {
1533 register: Register,
1534 next_available_column: usize,
1535}
1536
1537fn get_row_for_register(register: &Register, rows: &[RowInfo]) -> usize {
1538 rows.iter()
1539 .position(|r| r.register == *register)
1540 .unwrap_or_else(|| panic!("register {register:?} not found in rows {rows:?}"))
1541}
1542
1543fn operation_list_to_grid_base(
1544 operations: Vec<Operation>,
1545 qubits: &[Qubit],
1546) -> Vec<ComponentColumn> {
1547 let mut rows = vec![];
1548 for q in qubits {
1549 rows.push(RowInfo {
1550 register: Register::quantum(q.id),
1551 next_available_column: 0,
1552 });
1553 for i in 0..q.num_results {
1554 rows.push(RowInfo {
1555 register: Register::classical(q.id, i),
1556 next_available_column: 0,
1557 });
1558 }
1559 }
1560
1561 let mut columns: Vec<ComponentColumn> = vec![];
1562
1563 for op in operations {
1564 // get the entire range that this operation spans
1565 let targets = match &op {
1566 Operation::Measurement(m) => &m.qubits,
1567 Operation::Unitary(u) => &u.targets,
1568 Operation::Ket(k) => &k.targets,
1569 };
1570 let controls = match &op {
1571 Operation::Measurement(m) => &m.results,
1572 Operation::Unitary(u) => &u.controls,
1573 Operation::Ket(_) => &vec![],
1574 };
1575 let mut all_rows = targets
1576 .iter()
1577 .chain(controls.iter())
1578 .map(|r| get_row_for_register(r, &rows))
1579 .collect::<Vec<_>>();
1580 all_rows.sort_unstable();
1581 let (begin, end) = all_rows.split_first().map_or((0, 0), |(first, tail)| {
1582 (*first, tail.last().unwrap_or(first) + 1)
1583 });
1584 // find the earliest column that all rows in this range are available
1585 let column = rows[begin..end]
1586 .iter()
1587 .map(|r| r.next_available_column)
1588 .max()
1589 .unwrap_or(0);
1590 // assign this operation to that column
1591 // and update the rows to mark them as occupied until the next column
1592 for r in &mut rows[begin..end] {
1593 r.next_available_column = column + 1;
1594 }
1595 if columns.len() <= column {
1596 columns.resize_with(column + 1, || ComponentColumn { components: vec![] });
1597 }
1598 columns[column].components.push(op);
1599 }
1600
1601 columns
1602}
1603
1604fn make_repeated_parent(base: &Operation, count: usize) -> Operation {
1605 debug_assert!(count > 1);
1606 let mut parent = base.clone();
1607 let mut children = vec![];
1608 let mut tail_children = vec![];
1609
1610 for i in 0..count {
1611 if i == 0 {
1612 children.push(base.clone());
1613 } else {
1614 tail_children.push(base.clone());
1615 }
1616 }
1617
1618 if !tail_children.is_empty() {
1619 let mut tail = base.clone();
1620 *tail.children_mut() = vec![ComponentColumn {
1621 components: tail_children,
1622 }];
1623 *tail.gate_mut() = format!("{}(×{})", tail.gate(), count - 1);
1624 if let Operation::Unitary(u) = &mut tail {
1625 // Merge targets and controls into targets; clear controls
1626 u.targets = merge_unitary_registers(from_ref(base));
1627 u.controls.clear();
1628 } else {
1629 warn!("merging targets/controls is only implemented for unitaries");
1630 }
1631
1632 children.push(tail);
1633 }
1634
1635 let child_columns: ComponentGrid = vec![ComponentColumn {
1636 components: children,
1637 }];
1638 match &mut parent {
1639 Operation::Measurement(m) => {
1640 warn!("collapsing repeated measurements may not be correct");
1641 m.children = child_columns;
1642 m.gate = format!("{}(×{})", m.gate, count);
1643 }
1644 Operation::Unitary(u) => {
1645 u.children = child_columns;
1646 u.gate = format!("{}(×{})", u.gate, count);
1647 // Merge targets and controls into targets; clear controls
1648 let mut seen: FxHashSet<(usize, Option<usize>)> = FxHashSet::default();
1649 let mut merged: Vec<Register> = Vec::new();
1650 for r in u.targets.iter().chain(u.controls.iter()) {
1651 let key = (r.qubit, r.result);
1652 if seen.insert(key) {
1653 merged.push(r.clone());
1654 }
1655 }
1656 u.targets = merged;
1657 u.controls.clear();
1658 }
1659 Operation::Ket(k) => {
1660 warn!("collapsing repeated kets may not be correct");
1661 k.children = child_columns;
1662 k.gate = format!("{}(×{})", k.gate, count);
1663 }
1664 }
1665 parent
1666}
1667
1668/// Counts how many times a motif repeats starting at a given position.
1669fn count_motif_repeats(hashes: &[u64], start_pos: usize, motif_len: usize) -> usize {
1670 let len = hashes.len();
1671 let mut repeats = 1usize;
1672
1673 'outer: loop {
1674 let start_next = start_pos + repeats * motif_len;
1675 let end_next = start_next + motif_len;
1676 if end_next > len {
1677 break;
1678 }
1679 for k in 0..motif_len {
1680 if hashes[start_pos + k] != hashes[start_next + k] {
1681 break 'outer;
1682 }
1683 }
1684 repeats += 1;
1685 }
1686
1687 repeats
1688}
1689
1690/// Finds the best repeating motif starting at a given position.
1691fn find_best_motif(hashes: &[u64], start_pos: usize) -> (usize, usize) {
1692 let len = hashes.len();
1693 let remaining = len - start_pos;
1694 let mut best_motif_len = 1usize;
1695 let mut best_repeats = 1usize;
1696 let max_motif_len = (remaining / 2).max(1);
1697
1698 for motif_len in 1..=max_motif_len {
1699 if motif_len * 2 > remaining {
1700 break;
1701 }
1702
1703 let repeats = count_motif_repeats(hashes, start_pos, motif_len);
1704
1705 if repeats > 1 {
1706 let total = repeats * motif_len;
1707 let best_total = best_repeats * best_motif_len;
1708 if total > best_total || (total == best_total && motif_len < best_motif_len) {
1709 best_motif_len = motif_len;
1710 best_repeats = repeats;
1711 }
1712 }
1713 }
1714
1715 (best_motif_len, best_repeats)
1716}
1717
1718/// Creates a label for a complex motif by joining gate names and truncating if necessary.
1719fn create_motif_label(operations: &[Operation], motif_len: usize) -> String {
1720 let motif_gates: Vec<String> = operations[..motif_len]
1721 .iter()
1722 .map(|op| match op {
1723 Operation::Measurement(m) => m.gate.clone(),
1724 Operation::Unitary(u) => u.gate.clone(),
1725 Operation::Ket(k) => k.gate.clone(),
1726 })
1727 .collect();
1728
1729 let mut label_prefix = motif_gates.join(" ");
1730 if label_prefix.chars().count() > 5 {
1731 let truncated: String = label_prefix.chars().take(5).collect();
1732 label_prefix = format!("{truncated}...");
1733 }
1734 label_prefix
1735}
1736
1737/// Merges targets and controls from repeated unitary operations.
1738fn merge_unitary_registers(repeated_slice: &[Operation]) -> Vec<Register> {
1739 let mut seen: FxHashSet<(usize, Option<usize>)> = FxHashSet::default();
1740 let mut merged = Vec::new();
1741
1742 for op in repeated_slice {
1743 if let Operation::Unitary(child) = op {
1744 for r in child.targets.iter().chain(child.controls.iter()) {
1745 let key = (r.qubit, r.result);
1746 if seen.insert(key) {
1747 merged.push(r.clone());
1748 }
1749 }
1750 }
1751 }
1752
1753 merged
1754}
1755
1756/// Merges targets from repeated ket operations.
1757fn merge_ket_targets(repeated_slice: &[Operation]) -> Vec<Register> {
1758 let mut tgt_seen: FxHashSet<(usize, Option<usize>)> = FxHashSet::default();
1759 let mut new_targets = Vec::new();
1760
1761 for op in repeated_slice {
1762 if let Operation::Ket(child) = op {
1763 for r in &child.targets {
1764 let key = (r.qubit, r.result);
1765 if tgt_seen.insert(key) {
1766 new_targets.push(r.clone());
1767 }
1768 }
1769 }
1770 }
1771
1772 new_targets
1773}
1774
1775/// Creates a parent operation for a complex motif (length > 1).
1776fn make_complex_motif_parent(
1777 base: &Operation,
1778 repeated_slice: &[Operation],
1779 motif_len: usize,
1780 repeats: usize,
1781) -> Operation {
1782 let label_prefix = create_motif_label(repeated_slice, motif_len);
1783 let mut children = Vec::with_capacity(repeats * motif_len);
1784 let mut tail_children = vec![];
1785
1786 for (i, op) in repeated_slice.iter().enumerate() {
1787 if i < motif_len {
1788 children.push(op.clone());
1789 } else {
1790 tail_children.push(op.clone());
1791 }
1792 }
1793
1794 if !tail_children.is_empty() {
1795 let mut tail = base.clone();
1796 *tail.children_mut() = vec![ComponentColumn {
1797 components: tail_children,
1798 }];
1799 *tail.gate_mut() = format!("{}(×{})", tail.gate(), repeats - 1);
1800 if let Operation::Unitary(u) = &mut tail {
1801 // Merge targets and controls into targets; clear controls
1802 u.targets = merge_unitary_registers(repeated_slice);
1803 u.controls.clear();
1804 } else {
1805 warn!("collapsing repeated measurements/kets may not be correct");
1806 }
1807
1808 children.push(tail);
1809 }
1810
1811 let mut parent = base.clone();
1812 match &mut parent {
1813 Operation::Measurement(m) => {
1814 m.children = vec![ComponentColumn {
1815 components: children,
1816 }];
1817 m.gate = format!("{label_prefix}(×{repeats})");
1818 }
1819 Operation::Unitary(u) => {
1820 u.children = vec![ComponentColumn {
1821 components: children,
1822 }];
1823 u.gate = format!("{label_prefix}(×{repeats})");
1824 u.targets = merge_unitary_registers(repeated_slice);
1825 u.controls.clear();
1826 }
1827 Operation::Ket(k) => {
1828 k.children = vec![ComponentColumn {
1829 components: children,
1830 }];
1831 k.gate = format!("{label_prefix}(×{repeats})");
1832 k.targets = merge_ket_targets(repeated_slice);
1833 }
1834 }
1835
1836 parent
1837}
1838
1839#[allow(clippy::needless_pass_by_value)]
1840fn collapse_repetition_base(operations: Vec<Operation>) -> Vec<Operation> {
1841 // Extended: detect repeating motifs of length > 1 as well (e.g. A B A B A B -> (A B)(3)).
1842 // Strategy: scan list; for each start index find longest total repeated sequence comprising
1843 // repeats (>1) of a motif whose operations are all the same variant type. Prefer the match
1844 // with the greatest total collapsed length; tie-breaker smaller motif length.
1845 let len = operations.len();
1846 let hashes = operations.iter().map(hash_operation).collect::<Vec<u64>>();
1847 let mut i = 0;
1848 let mut result: Vec<Operation> = Vec::new();
1849
1850 while i < len {
1851 let (best_motif_len, best_repeats) = find_best_motif(&hashes, i);
1852
1853 if best_repeats > 1 {
1854 let base = &operations[i];
1855 let parent = if best_motif_len == 1 {
1856 make_repeated_parent(base, best_repeats)
1857 } else {
1858 let repeated_slice = &operations[i..i + best_repeats * best_motif_len];
1859 make_complex_motif_parent(base, repeated_slice, best_motif_len, best_repeats)
1860 };
1861
1862 result.push(parent);
1863 i += best_repeats * best_motif_len;
1864 } else {
1865 // No pattern; push single op
1866 result.push(operations[i].clone());
1867 i += 1;
1868 }
1869 }
1870
1871 result
1872}
1873
1874fn hash_operation(op: &Operation) -> u64 {
1875 let args = op.args();
1876 let non_metadata_args = args
1877 .iter()
1878 .filter(|arg| !arg.starts_with("metadata="))
1879 .collect::<Vec<_>>();
1880
1881 let more = match op {
1882 Operation::Measurement(measurement) => {
1883 ("m", measurement.qubits.clone(), measurement.results.clone())
1884 }
1885 Operation::Unitary(unitary) => ("u", unitary.controls.clone(), unitary.targets.clone()),
1886 Operation::Ket(ket) => ("k", vec![], ket.targets.clone()),
1887 };
1888 let data = (
1889 op.gate(),
1890 op.is_adjoint(),
1891 op.is_controlled(),
1892 op.is_measurement(),
1893 non_metadata_args,
1894 op.children()
1895 .iter()
1896 .map(|child| {
1897 child
1898 .components
1899 .iter()
1900 .map(hash_operation)
1901 .collect::<Vec<_>>()
1902 })
1903 .collect::<Vec<_>>(),
1904 more,
1905 );
1906 // standard hash
1907 let mut hasher = std::collections::hash_map::DefaultHasher::new();
1908 data.hash(&mut hasher);
1909 hasher.finish()
1910}
1911
1912/// Groups qubits into a single register. Collapses operations accordingly.
1913#[must_use]
1914pub fn group_qubits(
1915 operations: Vec<Operation>,
1916 qubits: Vec<Qubit>,
1917 qubit_ids_to_group: &[usize],
1918) -> (Vec<Operation>, Vec<Qubit>) {
1919 let (qubit_map, new_qubits) = get_qubit_map(qubits, qubit_ids_to_group);
1920
1921 assert!(qubit_map.values().collect::<FxHashSet<_>>().len() == 1);
1922
1923 let new_operations = operations
1924 .into_iter()
1925 .map(|op| map_operation(qubit_ids_to_group, &qubit_map, op))
1926 .collect::<Vec<_>>();
1927
1928 (new_operations, new_qubits)
1929}
1930
1931fn map_operation(
1932 qubit_ids_to_group: &[usize],
1933 qubit_map: &FxHashMap<usize, usize>,
1934 mut op: Operation,
1935) -> Operation {
1936 for child_column in op.children_mut() {
1937 let children = &mut child_column.components;
1938 for child in children {
1939 *child = map_operation(qubit_ids_to_group, qubit_map, child.clone());
1940 }
1941 }
1942
1943 let mut remapped_controls = vec![];
1944 let mut remapped_targets = vec![];
1945 let gate = match &mut op {
1946 Operation::Measurement(m) => {
1947 m.qubits = map_to_group(qubit_map, &mut remapped_controls, &m.qubits);
1948 m.results = map_to_group(qubit_map, &mut remapped_targets, &m.results);
1949 &mut m.gate
1950 }
1951 Operation::Unitary(u) => {
1952 u.targets = map_to_group(qubit_map, &mut remapped_targets, &u.targets);
1953 u.controls = map_to_group(qubit_map, &mut remapped_controls, &u.controls);
1954
1955 if !remapped_controls.is_empty() && !remapped_targets.is_empty() {
1956 let new_id = qubit_map
1957 .values()
1958 .next()
1959 .copied()
1960 .expect("should be present");
1961 // remove from controls if it is also a target
1962 u.controls.retain(|r| r.qubit != new_id);
1963 u.gate = format!("C{}", u.gate);
1964 }
1965 &mut u.gate
1966 }
1967 Operation::Ket(k) => {
1968 k.targets = map_to_group(qubit_map, &mut remapped_targets, &k.targets);
1969 &mut k.gate
1970 }
1971 };
1972
1973 if !remapped_controls.is_empty() || !remapped_targets.is_empty() {
1974 let remapped_qubit_idxs =
1975 remapped_qubit_indices(qubit_ids_to_group, &remapped_controls, &remapped_targets);
1976 *gate = format!("{gate} (q{remapped_qubit_idxs:?})");
1977 }
1978
1979 op
1980}
1981
1982fn map_to_group(
1983 qubit_map: &FxHashMap<usize, usize>,
1984 remapped_qubits: &mut Vec<usize>,
1985 registers: &[Register],
1986) -> Vec<Register> {
1987 registers
1988 .iter()
1989 .map(|r| {
1990 let new_id = qubit_map.get(&r.qubit);
1991 if let Some(new_id) = new_id {
1992 remapped_qubits.push(r.qubit);
1993 Register {
1994 qubit: *new_id,
1995 result: r.result,
1996 }
1997 } else {
1998 r.clone()
1999 }
2000 })
2001 .collect()
2002}
2003
2004fn get_qubit_map(
2005 qubits: Vec<Qubit>,
2006 qubit_ids_to_group: &[usize],
2007) -> (FxHashMap<usize, usize>, Vec<Qubit>) {
2008 let mut qubit_map = FxHashMap::default();
2009 let mut group_idx: Option<usize> = None;
2010 let mut new_qubits: Vec<Qubit> = vec![];
2011 for q in qubits {
2012 if qubit_ids_to_group.contains(&q.id) {
2013 if let Some(group_idx) = group_idx {
2014 qubit_map.insert(q.id, group_idx);
2015 new_qubits[group_idx].num_results += q.num_results;
2016 new_qubits[group_idx].declarations.extend(q.declarations);
2017 } else {
2018 group_idx = Some(new_qubits.len());
2019 qubit_map.insert(q.id, new_qubits.len());
2020 new_qubits.push(Qubit {
2021 id: q.id, // Use the first qubit's ID as the group ID
2022 num_results: q.num_results,
2023 declarations: q.declarations.clone(),
2024 });
2025 }
2026 } else {
2027 new_qubits.push(q.clone());
2028 }
2029 }
2030 (qubit_map, new_qubits)
2031}
2032
2033fn remapped_qubit_indices(
2034 qubit_ids_to_group: &[usize],
2035 remapped_controls: &[usize],
2036 remapped_targets: &[usize],
2037) -> Vec<usize> {
2038 remapped_controls
2039 .iter()
2040 .chain(remapped_targets.iter())
2041 .map(|id| {
2042 qubit_ids_to_group
2043 .iter()
2044 .position(|&x| x == *id)
2045 .expect("should be present")
2046 })
2047 .collect::<Vec<_>>()
2048}