GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
iadavis/pipeline-issue-debugging

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

1266lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7use rustc_hash::{FxHashMap, FxHashSet};
8use serde::{Deserialize, Serialize};
9use std::{
10 cmp::max,
11 fmt::{Display, Write},
12 hash::Hash,
13 ops::Not,
14 vec,
15};
16
17/// Current format version.
18pub const CURRENT_VERSION: usize = 1;
19
20/// Representation of a quantum circuit group.
21#[derive(Clone, Serialize, Deserialize, Default, Debug)]
22pub struct CircuitGroup {
23 pub circuits: Vec<Circuit>,
24 pub version: usize,
25}
26
27impl Display for CircuitGroup {
28 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
29 for circuit in &self.circuits {
30 writeln!(f, "{circuit}")?;
31 }
32 Ok(())
33 }
34}
35
36/// Representation of a quantum circuit.
37#[derive(Clone, Serialize, Deserialize, Default, Debug)]
38pub struct Circuit {
39 pub qubits: Vec<Qubit>,
40 #[serde(rename = "componentGrid")]
41 pub component_grid: ComponentGrid,
42}
43
44impl Circuit {
45 #[must_use]
46 pub fn display_no_locations(&self) -> impl Display {
47 CircuitDisplay {
48 circuit: self,
49 render_locations: false,
50 render_groups: false,
51 }
52 }
53
54 #[must_use]
55 pub fn display_with_groups(&self) -> impl Display {
56 // Groups rendered only in tests since the current line rendering
57 // doesn't look good enough to be user-facing.
58 CircuitDisplay {
59 circuit: self,
60 render_locations: true,
61 render_groups: true,
62 }
63 }
64}
65
66impl Display for Circuit {
67 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68 write!(
69 f,
70 "{}",
71 CircuitDisplay {
72 circuit: self,
73 render_locations: true,
74 render_groups: false,
75 }
76 )
77 }
78}
79
80/// Type alias for a grid of components.
81pub type ComponentGrid = Vec<ComponentColumn>;
82
83/// Representation of a column in the component grid.
84#[derive(Clone, Serialize, Deserialize, Default, Debug)]
85pub struct ComponentColumn {
86 pub components: Vec<Component>,
87}
88
89/// Union type for components.
90pub type Component = Operation;
91
92/// Union type for operations.
93#[derive(Clone, Serialize, Deserialize, Debug)]
94#[serde(tag = "kind")]
95pub enum Operation {
96 #[serde(rename = "measurement")]
97 Measurement(Measurement),
98 #[serde(rename = "unitary")]
99 Unitary(Unitary),
100 #[serde(rename = "ket")]
101 Ket(Ket),
102}
103
104impl Operation {
105 /// Returns the gate name of the operation.
106 #[must_use]
107 pub fn gate(&self) -> String {
108 match self {
109 Operation::Measurement(m) => m.gate.clone(),
110 Operation::Unitary(u) => u.gate.clone(),
111 #[allow(clippy::unicode_not_nfc)]
112 Operation::Ket(k) => format!("|{}〉", k.gate),
113 }
114 }
115
116 pub fn gate_mut(&mut self) -> &mut String {
117 match self {
118 Self::Measurement(measurement) => &mut measurement.gate,
119 Self::Unitary(unitary) => &mut unitary.gate,
120 Self::Ket(ket) => &mut ket.gate,
121 }
122 }
123
124 /// Returns the arguments for the operation.
125 #[must_use]
126 pub fn args(&self) -> Vec<String> {
127 match self {
128 Operation::Measurement(m) => m.args.clone(),
129 Operation::Unitary(u) => u.args.clone(),
130 Operation::Ket(k) => k.args.clone(),
131 }
132 }
133
134 pub fn args_mut(&mut self) -> &mut Vec<String> {
135 match self {
136 Self::Measurement(measurement) => &mut measurement.args,
137 Self::Unitary(unitary) => &mut unitary.args,
138 Self::Ket(ket) => &mut ket.args,
139 }
140 }
141
142 #[must_use]
143 pub fn source_location(&self) -> Option<&SourceLocation> {
144 match self {
145 Self::Measurement(measurement) => measurement.metadata.as_ref(),
146 Self::Unitary(unitary) => unitary.metadata.as_ref(),
147 Self::Ket(ket) => ket.metadata.as_ref(),
148 }
149 .and_then(|m| m.source.as_ref())
150 }
151
152 #[must_use]
153 pub fn source_location_mut(&mut self) -> &mut Option<SourceLocation> {
154 let md = match self {
155 Self::Measurement(measurement) => &mut measurement.metadata,
156 Self::Unitary(unitary) => &mut unitary.metadata,
157 Self::Ket(ket) => &mut ket.metadata,
158 };
159
160 if md.is_none() {
161 md.replace(Metadata {
162 source: None,
163 scope_location: None,
164 });
165 }
166
167 if let Some(md) = md {
168 &mut md.source
169 } else {
170 unreachable!()
171 }
172 }
173
174 #[must_use]
175 pub fn scope_location_mut(&mut self) -> &mut Option<SourceLocation> {
176 let md = match self {
177 Self::Measurement(measurement) => &mut measurement.metadata,
178 Self::Unitary(unitary) => &mut unitary.metadata,
179 Self::Ket(ket) => &mut ket.metadata,
180 };
181
182 if md.is_none() {
183 md.replace(Metadata {
184 source: None,
185 scope_location: None,
186 });
187 }
188
189 if let Some(md) = md {
190 &mut md.scope_location
191 } else {
192 unreachable!()
193 }
194 }
195
196 /// Returns the children for the operation.
197 #[must_use]
198 pub fn children(&self) -> &ComponentGrid {
199 match self {
200 Operation::Measurement(m) => &m.children,
201 Operation::Unitary(u) => &u.children,
202 Operation::Ket(k) => &k.children,
203 }
204 }
205
206 /// Returns the children for the operation.
207 #[must_use]
208 pub fn children_mut(&mut self) -> &mut ComponentGrid {
209 match self {
210 Operation::Measurement(m) => &mut m.children,
211 Operation::Unitary(u) => &mut u.children,
212 Operation::Ket(k) => &mut k.children,
213 }
214 }
215
216 #[must_use]
217 pub fn targets_mut(&mut self) -> &mut Vec<Register> {
218 match self {
219 Operation::Measurement(m) => &mut m.qubits,
220 Operation::Unitary(u) => &mut u.targets,
221 Operation::Ket(k) => &mut k.targets,
222 }
223 }
224 /// Returns if the operation is a controlled operation.
225 #[must_use]
226 pub fn is_controlled(&self) -> bool {
227 match self {
228 Operation::Measurement(_) | Operation::Ket(_) => false,
229 Operation::Unitary(u) => !u.controls.is_empty(),
230 }
231 }
232
233 /// Returns if the operation is a measurement operation.
234 #[must_use]
235 pub fn is_measurement(&self) -> bool {
236 match self {
237 Operation::Measurement(_) => true,
238 Operation::Unitary(_) | Operation::Ket(_) => false,
239 }
240 }
241
242 /// Returns if the operation is an adjoint operation.
243 #[must_use]
244 pub fn is_adjoint(&self) -> bool {
245 match self {
246 Operation::Measurement(_) | Operation::Ket(_) => false,
247 Operation::Unitary(u) => u.is_adjoint,
248 }
249 }
250}
251
252/// Representation of a measurement operation.
253#[derive(Clone, Serialize, Deserialize, Default, Debug)]
254pub struct Measurement {
255 pub gate: String,
256 #[serde(skip_serializing_if = "Vec::is_empty")]
257 #[serde(default)]
258 pub args: Vec<String>,
259 #[serde(skip_serializing_if = "Vec::is_empty")]
260 #[serde(default)]
261 pub children: ComponentGrid,
262 pub qubits: Vec<Register>,
263 pub results: Vec<Register>,
264 #[serde(skip_serializing_if = "Option::is_none")]
265 pub metadata: Option<Metadata>,
266}
267
268/// Representation of a unitary operation.
269#[derive(Clone, Serialize, Deserialize, Default, Debug)]
270pub struct Unitary {
271 pub gate: String,
272 #[serde(skip_serializing_if = "Vec::is_empty")]
273 #[serde(default)]
274 pub args: Vec<String>,
275 #[serde(skip_serializing_if = "Vec::is_empty")]
276 #[serde(default)]
277 pub children: ComponentGrid,
278 pub targets: Vec<Register>,
279 #[serde(skip_serializing_if = "Vec::is_empty")]
280 #[serde(default)]
281 pub controls: Vec<Register>,
282 #[serde(rename = "isAdjoint")]
283 #[serde(skip_serializing_if = "Not::not")]
284 #[serde(default)]
285 pub is_adjoint: bool,
286 #[serde(skip_serializing_if = "Option::is_none")]
287 pub metadata: Option<Metadata>,
288}
289
290/// Representation of a gate that will set the target to a specific state.
291#[derive(Clone, Serialize, Deserialize, Default, Debug)]
292pub struct Ket {
293 pub gate: String,
294 #[serde(skip_serializing_if = "Vec::is_empty")]
295 #[serde(default)]
296 pub args: Vec<String>,
297 #[serde(skip_serializing_if = "Vec::is_empty")]
298 #[serde(default)]
299 pub children: ComponentGrid,
300 pub targets: Vec<Register>,
301 #[serde(skip_serializing_if = "Option::is_none")]
302 pub metadata: Option<Metadata>,
303}
304
305#[derive(Serialize, Deserialize, Debug, Eq, Hash, PartialEq, Clone)]
306pub struct Register {
307 pub qubit: usize,
308 #[serde(skip_serializing_if = "Option::is_none")]
309 pub result: Option<usize>,
310}
311
312impl Register {
313 #[must_use]
314 pub fn quantum(qubit_id: usize) -> Self {
315 Self {
316 qubit: qubit_id,
317 result: None,
318 }
319 }
320
321 #[must_use]
322 pub fn classical(qubit_id: usize, result_id: usize) -> Self {
323 Self {
324 qubit: qubit_id,
325 result: Some(result_id),
326 }
327 }
328
329 #[must_use]
330 pub fn is_classical(&self) -> bool {
331 self.result.is_some()
332 }
333}
334
335#[derive(Clone, Serialize, Deserialize, Debug)]
336pub struct Qubit {
337 pub id: usize,
338 #[serde(rename = "numResults")]
339 #[serde(default)]
340 pub num_results: usize,
341 #[serde(skip_serializing_if = "Vec::is_empty")]
342 #[serde(default)]
343 pub declarations: Vec<SourceLocation>,
344}
345
346#[derive(Clone, Serialize, Deserialize, Debug)]
347#[serde(rename_all = "camelCase")]
348/// The schema of `Metadata` may change and its contents
349/// are never meant to be persisted in a .qsc file.
350pub struct Metadata {
351 #[serde(skip_serializing_if = "Option::is_none")]
352 /// The location in the source code that this operation originated from.
353 pub source: Option<SourceLocation>,
354 #[serde(skip_serializing_if = "Option::is_none")]
355 /// Only populated if this operation represents a scope group.
356 pub scope_location: Option<SourceLocation>,
357}
358
359#[derive(Clone, Serialize, Deserialize, Debug)]
360pub struct SourceLocation {
361 pub file: String,
362 pub line: u32,
363 pub column: u32,
364}
365
366impl Display for SourceLocation {
367 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
368 write!(f, "{}:{}:{}", self.file, self.line, self.column)
369 }
370}
371
372type ObjectsByColumn = FxHashMap<usize, CircuitObject>;
373
374struct Row {
375 wire: Wire,
376 objects: ObjectsByColumn,
377 next_column: usize,
378 render_locations: bool,
379}
380
381enum Wire {
382 Qubit { label: String },
383 Classical { start_column: Option<usize> },
384}
385
386#[derive(Debug)]
387enum CircuitObject {
388 Blank,
389 Wire,
390 WireCross,
391 WireStart,
392 DashedCross,
393 Vertical,
394 VerticalDashed,
395 Object(String),
396}
397
398impl Row {
399 fn add_object(&mut self, column: usize, object: &str) {
400 self.add(column, CircuitObject::Object(object.to_string()));
401 }
402
403 fn add_measurement(&mut self, column: usize, source: Option<&SourceLocation>) {
404 let mut gate_label = String::from("M");
405 if self.render_locations
406 && let Some(loc) = source
407 {
408 let _ = write!(&mut gate_label, "@{loc}");
409 }
410 self.add(column, CircuitObject::Object(gate_label.clone()));
411 }
412
413 fn add_gate(&mut self, column: usize, operation: &Operation) {
414 let gate_label = self.operation_label(operation);
415
416 self.add_object(column, gate_label.as_str());
417 }
418
419 fn operation_label(&self, operation: &Operation) -> String {
420 let mut gate_label = String::new();
421 gate_label.push_str(&operation.gate());
422 if operation.is_adjoint() {
423 gate_label.push('\'');
424 }
425
426 if !operation.args().is_empty() {
427 let args = operation.args().join(", ");
428 let _ = write!(&mut gate_label, "({args})");
429 }
430
431 if self.render_locations
432 && let Some(loc) = operation.source_location()
433 {
434 let _ = write!(&mut gate_label, "@{loc}");
435 }
436 gate_label
437 }
438
439 fn add_vertical(&mut self, column: usize) {
440 if !self.objects.contains_key(&column) {
441 match self.wire {
442 Wire::Qubit { .. } => self.add(column, CircuitObject::WireCross),
443 Wire::Classical { start_column } => {
444 if start_column.is_some() {
445 self.add(column, CircuitObject::WireCross);
446 } else {
447 self.add(column, CircuitObject::Vertical);
448 }
449 }
450 }
451 }
452 }
453
454 fn add_dashed_vertical(&mut self, column: usize) {
455 if !self.objects.contains_key(&column) {
456 match self.wire {
457 Wire::Qubit { .. } => self.add(column, CircuitObject::DashedCross),
458 Wire::Classical { start_column } => {
459 if start_column.is_some() {
460 self.add(column, CircuitObject::DashedCross);
461 } else {
462 self.add(column, CircuitObject::VerticalDashed);
463 }
464 }
465 }
466 }
467 }
468
469 fn start_classical(&mut self, column: usize) {
470 self.add(column, CircuitObject::WireStart);
471 if let Wire::Classical { start_column } = &mut self.wire {
472 start_column.replace(column);
473 }
474 }
475
476 fn add(&mut self, column: usize, circuit_object: CircuitObject) {
477 self.objects.insert(column, circuit_object);
478 self.next_column = column + 1;
479 }
480
481 fn fmt(&self, f: &mut std::fmt::Formatter<'_>, columns: &[Column]) -> std::fmt::Result {
482 // Temporary string so we can trim whitespace at the end
483 let mut s = String::new();
484 match &self.wire {
485 Wire::Qubit { label } => {
486 s.write_str(&columns[0].fmt_qubit_label(label))?;
487 for (column_index, column) in columns.iter().enumerate().skip(1) {
488 let obj = self.objects.get(&column_index);
489
490 s.write_str(&column.fmt_object_on_qubit_wire(obj))?;
491 }
492 }
493 Wire::Classical { start_column } => {
494 for (column_index, column) in columns.iter().enumerate() {
495 let obj = self.objects.get(&column_index);
496
497 if let Some(start) = *start_column
498 && column_index > start
499 {
500 s.write_str(&column.fmt_object_on_classical_wire(obj))?;
501 } else {
502 s.write_str(&column.fmt_object(obj))?;
503 }
504 }
505 }
506 }
507 writeln!(f, "{}", s.trim_end())?;
508 Ok(())
509 }
510}
511
512const MIN_COLUMN_WIDTH: usize = 7;
513
514const QUBIT_WIRE: [char; 3] = ['─', '─', '─']; // "───────"
515const CLASSICAL_WIRE: [char; 3] = ['═', '═', '═']; // "═══════"
516const QUBIT_WIRE_CROSS: [char; 3] = ['─', '┼', '─']; // "───┼───"
517const CLASSICAL_WIRE_CROSS: [char; 3] = ['═', '╪', '═']; // "═══╪═══"
518const CLASSICAL_WIRE_START: [char; 3] = [' ', '╘', '═']; // " ╘═══"
519const QUBIT_WIRE_DASHED_CROSS: [char; 3] = ['─', '┆', '─']; // "───┆───"
520const CLASSICAL_WIRE_DASHED_CROSS: [char; 3] = ['═', '┆', '═']; // "═══┆═══"
521const VERTICAL_DASHED: [char; 3] = [' ', '┆', ' ']; // " ┆ "
522const VERTICAL: [char; 3] = [' ', '│', ' ']; // " │ "
523const BLANK: [char; 3] = [' ', ' ', ' ']; // " "
524
525struct Column {
526 column_width: usize,
527}
528
529impl Column {
530 fn new(column_width: usize) -> Self {
531 // Column widths should be odd numbers for this struct to work well
532 let odd_column_width = column_width | 1;
533 Self {
534 column_width: odd_column_width,
535 }
536 }
537
538 /// "q_0 "
539 #[allow(clippy::doc_markdown)]
540 fn fmt_qubit_label(&self, label: &str) -> String {
541 let column_width = self.column_width;
542 let s = format!("{label:<column_width$}");
543 s
544 }
545
546 /// "── A ──"
547 fn fmt_on_qubit_wire(&self, obj: &str) -> String {
548 let column_width = self.column_width;
549 format!("{:─^column_width$}", format!(" {obj} "))
550 }
551
552 /// "══ A ══"
553 fn fmt_on_classical_wire(&self, obj: &str) -> String {
554 let column_width = self.column_width;
555 format!("{:═^column_width$}", format!(" {obj} "))
556 }
557
558 /// " A "
559 fn fmt_on_blank(&self, obj: &str) -> String {
560 let column_width = self.column_width;
561 format!("{: ^column_width$}", format!(" {obj} "))
562 }
563
564 fn expand_template(&self, template: &[char; 3]) -> String {
565 let half_width = self.column_width / 2;
566 let left = template[0].to_string().repeat(half_width);
567 let right = template[2].to_string().repeat(half_width);
568
569 format!("{left}{}{right}", template[1])
570 }
571
572 fn fmt_object_on_classical_wire(&self, circuit_object: Option<&CircuitObject>) -> String {
573 let circuit_object = circuit_object.unwrap_or(&CircuitObject::Wire);
574
575 if let CircuitObject::Object(label) = circuit_object {
576 return self.fmt_on_classical_wire(label.as_str());
577 }
578
579 let template = match circuit_object {
580 CircuitObject::Wire => CLASSICAL_WIRE,
581 CircuitObject::WireCross | CircuitObject::Vertical => CLASSICAL_WIRE_CROSS,
582 CircuitObject::WireStart => CLASSICAL_WIRE_START,
583 CircuitObject::DashedCross => CLASSICAL_WIRE_DASHED_CROSS,
584 o @ (CircuitObject::VerticalDashed | CircuitObject::Blank) => {
585 unreachable!("unexpected object on blank row: {o:?}")
586 }
587 CircuitObject::Object(_) => unreachable!("case should have been handled earlier"),
588 };
589
590 self.expand_template(&template)
591 }
592
593 fn fmt_object_on_qubit_wire(&self, circuit_object: Option<&CircuitObject>) -> String {
594 let circuit_object = circuit_object.unwrap_or(&CircuitObject::Wire);
595 if let CircuitObject::Object(label) = circuit_object {
596 return self.fmt_on_qubit_wire(label.as_str());
597 }
598
599 let template = match circuit_object {
600 CircuitObject::Wire => QUBIT_WIRE,
601 CircuitObject::WireCross | CircuitObject::Vertical => QUBIT_WIRE_CROSS,
602 CircuitObject::DashedCross => QUBIT_WIRE_DASHED_CROSS,
603 CircuitObject::WireStart
604 | CircuitObject::VerticalDashed
605 | CircuitObject::Blank
606 | CircuitObject::Object(_) => unreachable!(),
607 };
608
609 self.expand_template(&template)
610 }
611
612 fn fmt_object(&self, circuit_object: Option<&CircuitObject>) -> String {
613 let circuit_object = circuit_object.unwrap_or(&CircuitObject::Blank);
614 if let CircuitObject::Object(label) = circuit_object {
615 return self.fmt_on_blank(label.as_str());
616 }
617
618 let template = match circuit_object {
619 CircuitObject::WireStart => CLASSICAL_WIRE_START,
620 CircuitObject::Blank => BLANK,
621 CircuitObject::Vertical => VERTICAL,
622 CircuitObject::VerticalDashed => VERTICAL_DASHED,
623 o @ (CircuitObject::Wire | CircuitObject::WireCross | CircuitObject::DashedCross) => {
624 unreachable!("unexpected object on blank row: {o:?}")
625 }
626 CircuitObject::Object(_) => {
627 unreachable!("case should have been handled earlier")
628 }
629 };
630
631 self.expand_template(&template)
632 }
633}
634
635struct CircuitDisplay<'a> {
636 circuit: &'a Circuit,
637 render_locations: bool,
638 render_groups: bool,
639}
640
641impl Display for CircuitDisplay<'_> {
642 /// Formats the circuit into a diagram.
643 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
644 let mut rows = vec![];
645
646 // Maintain a mapping from from Registers in the Circuit schema
647 // to row in the diagram
648 let mut register_to_row = FxHashMap::default();
649
650 // Keep track of which qubits have the qubit after them in the same multi-qubit operation,
651 // because those qubits need to get a gap row below them.
652 let mut qubits_with_gap_row_below = FxHashSet::default();
653
654 // Identify qubits that require gap rows
655 self.identify_qubits_with_gap_rows(&mut qubits_with_gap_row_below);
656
657 // Initialize rows for qubits and classical wires
658 self.initialize_rows(&mut rows, &mut register_to_row, &qubits_with_gap_row_below);
659
660 // Add operations to the diagram
661 self.add_grid(1, &self.circuit.component_grid, &mut rows, &register_to_row);
662
663 // Finalize the diagram by extending wires and formatting columns
664 let columns = finalize_columns(&rows);
665
666 // Draw the diagram
667 for row in rows {
668 row.fmt(f, &columns)?;
669 }
670
671 Ok(())
672 }
673}
674
675impl CircuitDisplay<'_> {
676 /// Identifies qubits that require gap rows for multi-qubit operations.
677 fn identify_qubits_with_gap_rows(&self, qubits_with_gap_row_below: &mut FxHashSet<usize>) {
678 for col in &self.circuit.component_grid {
679 Self::add_qubits_with_gap_rows(&col.components, qubits_with_gap_row_below);
680 }
681 }
682
683 fn add_qubits_with_gap_rows(
684 components: &Vec<Operation>,
685 qubits_with_gap_row_below: &mut FxHashSet<usize>,
686 ) {
687 for op in components {
688 if !op.children().is_empty() {
689 for c in op.children() {
690 Self::add_qubits_with_gap_rows(&c.components, qubits_with_gap_row_below);
691 }
692 continue;
693 }
694
695 let targets = match op {
696 Operation::Measurement(m) => &m.qubits,
697 Operation::Unitary(u) => &u.targets,
698 Operation::Ket(k) => &k.targets,
699 };
700 for target in targets {
701 let qubit = target.qubit;
702
703 if qubits_with_gap_row_below.contains(&qubit) {
704 continue;
705 }
706
707 let next_qubit = qubit + 1;
708
709 // Check if the next qubit is also in this operation.
710 if targets.iter().any(|t| t.qubit == next_qubit) {
711 qubits_with_gap_row_below.insert(qubit);
712 }
713 }
714 }
715 }
716
717 /// Initializes rows for qubits and classical wires.
718 fn initialize_rows(
719 &self,
720 rows: &mut Vec<Row>,
721 register_to_row: &mut FxHashMap<(usize, Option<usize>), usize>,
722 qubits_with_gap_row_below: &FxHashSet<usize>,
723 ) {
724 for q in &self.circuit.qubits {
725 let mut label = format!("q_{}", q.id);
726 if self.render_locations {
727 let mut first = true;
728 for loc in &q.declarations {
729 if first {
730 label.push('@');
731 first = false;
732 } else {
733 label.push_str(", ");
734 }
735 let _ = write!(&mut label, "{loc}");
736 }
737 }
738 rows.push(Row {
739 wire: Wire::Qubit { label },
740 objects: FxHashMap::default(),
741 next_column: 1,
742 render_locations: self.render_locations,
743 });
744
745 register_to_row.insert((q.id, None), rows.len() - 1);
746
747 // If this qubit has no children, but it is in a multi-qubit operation with
748 // the next qubit, we add an empty row to make room for the vertical connector.
749 // We can just use a classical wire type for this row since the wire won't actually be rendered.
750 let extra_rows = if qubits_with_gap_row_below.contains(&q.id) {
751 max(1, q.num_results)
752 } else {
753 q.num_results
754 };
755
756 for i in 0..extra_rows {
757 rows.push(Row {
758 wire: Wire::Classical { start_column: None },
759 objects: FxHashMap::default(),
760 next_column: 1,
761 render_locations: self.render_locations,
762 });
763
764 register_to_row.insert((q.id, Some(i)), rows.len() - 1);
765 }
766 }
767 }
768
769 /// Adds operations to the diagram.
770 fn add_grid(
771 &self,
772 start_column: usize,
773 component_grid: &ComponentGrid,
774 rows: &mut [Row],
775 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
776 ) -> usize {
777 let mut curr_column = start_column;
778 for column_operations in component_grid {
779 let offset = self.add_column(rows, register_to_row, curr_column, column_operations);
780 curr_column += offset;
781 }
782 curr_column - start_column
783 }
784
785 fn add_column(
786 &self,
787 rows: &mut [Row],
788 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
789 column: usize,
790 col: &ComponentColumn,
791 ) -> usize {
792 let mut col_width = 0;
793 for op in &col.components {
794 let target_rows = get_row_indexes(op, register_to_row, true);
795 let control_rows = get_row_indexes(op, register_to_row, false);
796
797 let mut all_rows = target_rows.clone();
798 all_rows.extend(control_rows.iter());
799 all_rows.sort_unstable();
800
801 // We'll need to know the entire range of rows for this operation so we can
802 // figure out the starting column and also so we can draw any
803 // vertical lines that cross wires.
804 let (begin, end) = all_rows.split_first().map_or((0, 0), |(first, tail)| {
805 (*first, tail.last().unwrap_or(first) + 1)
806 });
807
808 if op.children().is_empty() {
809 add_operation_to_rows(op, rows, &target_rows, &control_rows, column, begin, end);
810 col_width = max(col_width, 1);
811 } else {
812 let offset = self.add_boxed_group(
813 rows,
814 register_to_row,
815 &all_rows,
816 column,
817 op,
818 op.children(),
819 );
820 col_width = max(col_width, offset);
821 }
822 }
823
824 col_width
825 }
826
827 fn add_boxed_group(
828 &self,
829 rows: &mut [Row],
830 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
831 target_rows: &[usize],
832 column: usize,
833 op: &Operation,
834 children: &Vec<ComponentColumn>,
835 ) -> usize {
836 assert!(
837 !op.children().is_empty(),
838 "must only be called for an operation with children"
839 );
840 assert!(
841 !op.is_controlled(),
842 "rendering controlled boxes not supported"
843 );
844 assert!(
845 !op.is_measurement(),
846 "rendering measurement boxes not supported"
847 );
848
849 let mut offset = 0;
850 if self.render_groups {
851 add_box_start(op, rows, target_rows, column);
852 offset += 1;
853 }
854
855 offset += self.add_grid(column + offset, children, rows, register_to_row);
856
857 if self.render_groups {
858 add_box_end(op, rows, target_rows, column + offset);
859 offset += 1;
860 }
861 offset
862 }
863}
864
865/// Adds a single operation to the rows.
866fn add_operation_to_rows(
867 operation: &Operation,
868 rows: &mut [Row],
869 targets: &[usize],
870 controls: &[usize],
871 column: usize,
872 begin: usize,
873 end: usize,
874) {
875 for i in targets {
876 let row = &mut rows[*i];
877 if matches!(row.wire, Wire::Classical { .. })
878 && matches!(operation, Operation::Measurement(_))
879 {
880 row.start_classical(column);
881 } else {
882 row.add_gate(column, operation);
883 }
884 }
885
886 if operation.is_controlled() || operation.is_measurement() {
887 for i in controls {
888 let row = &mut rows[*i];
889 if matches!(row.wire, Wire::Qubit { .. }) && operation.is_measurement() {
890 row.add_measurement(column, operation.source_location());
891 } else {
892 row.add_object(column, "●");
893 }
894 }
895
896 // If we have a control wire, draw vertical lines spanning all
897 // control and target wires and crossing any in between
898 // (vertical lines may overlap if there are multiple controls/targets,
899 // this is ok in practice)
900 for row in &mut rows[begin..end] {
901 row.add_vertical(column);
902 }
903 } else {
904 // No control wire. Draw dashed vertical lines to connect
905 // target wires if there are multiple targets
906 for row in &mut rows[begin..end] {
907 row.add_dashed_vertical(column);
908 }
909 }
910}
911
912fn add_box_start(operation: &Operation, rows: &mut [Row], target_rows: &[usize], column: usize) {
913 assert!(
914 !operation.children().is_empty(),
915 "must only be called for an operation with children"
916 );
917
918 let mut first = true;
919
920 for i in target_rows {
921 if first {
922 first = false;
923 let label = rows[*i].operation_label(operation);
924 rows[*i].add_object(column, format!("[ [{label}]").as_str());
925 } else {
926 rows[*i].add_object(column, "[");
927 }
928 }
929}
930
931fn add_box_end(operation: &Operation, rows: &mut [Row], target_rows: &[usize], column: usize) {
932 assert!(
933 !operation.children().is_empty(),
934 "must only be called for an operation with children"
935 );
936
937 for i in target_rows {
938 rows[*i].add_object(column, "]");
939 }
940}
941
942/// Finalizes the columns by calculating their widths.
943fn finalize_columns(rows: &[Row]) -> Vec<Column> {
944 // Find the end column for the whole circuit so that
945 // all qubit wires will extend until the end
946 let end_column = rows
947 .iter()
948 .max_by_key(|r| r.next_column)
949 .map_or(1, |r| r.next_column);
950
951 let longest_qubit_label = rows
952 .iter()
953 .map(|r| {
954 if let Wire::Qubit { label } = &r.wire {
955 label.len() + 1
956 } else {
957 0
958 }
959 })
960 .chain(std::iter::once(MIN_COLUMN_WIDTH))
961 .max()
962 .unwrap_or_default();
963
964 // To be able to fit long-named operations, we calculate the required width for each column,
965 // based on the maximum length needed for gates, where a gate X is printed as "- X -".
966 std::iter::once(longest_qubit_label)
967 .chain((1..end_column).map(|column| {
968 rows.iter()
969 .filter_map(|row| row.objects.get(&column))
970 .filter_map(|object| match object {
971 CircuitObject::Object(string) => Some(string.len() + 4),
972 _ => None,
973 })
974 .chain(std::iter::once(MIN_COLUMN_WIDTH))
975 .max()
976 .expect("Column width should be at least 1")
977 }))
978 .map(Column::new)
979 .collect()
980}
981
982/// Gets the row indexes for the targets or controls of an operation.
983fn get_row_indexes(
984 operation: &Operation,
985 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
986 is_target: bool,
987) -> Vec<usize> {
988 let registers = match operation {
989 Operation::Measurement(m) => {
990 if is_target {
991 &m.results
992 } else {
993 &m.qubits
994 }
995 }
996 Operation::Unitary(u) => {
997 if is_target {
998 &u.targets
999 } else {
1000 &u.controls
1001 }
1002 }
1003 Operation::Ket(k) => {
1004 if is_target {
1005 &k.targets
1006 } else {
1007 &vec![]
1008 }
1009 }
1010 };
1011
1012 registers
1013 .iter()
1014 .filter_map(|reg| {
1015 let reg = (reg.qubit, reg.result);
1016 register_to_row.get(&reg).copied()
1017 })
1018 .collect()
1019}
1020
1021/// Converts a list of operations into a 2D grid of operations in col-row format.
1022/// Operations will be left-justified as much as possible in the resulting grid.
1023/// Children operations are recursively converted into a grid.
1024///
1025/// # Arguments
1026///
1027/// * `operations` - A vector of operations to be converted.
1028/// * `num_qubits` - The number of qubits in the circuit.
1029///
1030/// # Returns
1031///
1032/// A component grid representing the operations.
1033#[must_use]
1034pub fn operation_list_to_grid(mut operations: Vec<Operation>, num_qubits: usize) -> ComponentGrid {
1035 for op in &mut operations {
1036 // The children data structure is a grid, so checking if it is
1037 // length 1 is actually checking if it has a single column,
1038 // or in other words, we are checking if its children are in a single list.
1039 // If the operation has children in a single list, it needs to be converted to a grid.
1040 // If it was already converted to a grid, but the grid was still a single list,
1041 // then doing it again won't effect anything.
1042 if op.children().len() == 1 {
1043 match op {
1044 Operation::Measurement(m) => {
1045 m.children =
1046 operation_list_to_grid(m.children.remove(0).components, num_qubits);
1047 }
1048 Operation::Unitary(u) => {
1049 u.children =
1050 operation_list_to_grid(u.children.remove(0).components, num_qubits);
1051 }
1052 Operation::Ket(k) => {
1053 k.children =
1054 operation_list_to_grid(k.children.remove(0).components, num_qubits);
1055 }
1056 }
1057 }
1058 }
1059
1060 // Convert the operations into a component grid
1061 let mut component_grid = vec![];
1062 for col in remove_padding(operation_list_to_padded_array(operations, num_qubits)) {
1063 let column = ComponentColumn { components: col };
1064 component_grid.push(column);
1065 }
1066 component_grid
1067}
1068
1069/// Converts a list of operations into a padded 2D array of operations.
1070///
1071/// # Arguments
1072///
1073/// * `operations` - A vector of operations to be converted.
1074/// * `num_qubits` - The number of qubits in the circuit.
1075///
1076/// # Returns
1077///
1078/// A 2D vector of optional operations padded with `None`.
1079fn operation_list_to_padded_array(
1080 operations: Vec<Operation>,
1081 num_qubits: usize,
1082) -> Vec<Vec<Option<Operation>>> {
1083 if operations.is_empty() {
1084 return vec![];
1085 }
1086
1087 let grouped_ops = group_operations(&operations, num_qubits);
1088 let aligned_ops = transform_to_col_row(align_ops(grouped_ops));
1089
1090 // Need to convert to optional operations so we can
1091 // take operations out without messing up the indexing
1092 let mut operations = operations.into_iter().map(Some).collect::<Vec<_>>();
1093 aligned_ops
1094 .into_iter()
1095 .map(|col| {
1096 col.into_iter()
1097 .map(|op_idx| op_idx.and_then(|idx| operations[idx].take()))
1098 .collect()
1099 })
1100 .collect()
1101}
1102
1103/// Removes padding (`None` values) from a 2D array of operations.
1104///
1105/// # Arguments
1106///
1107/// * `operations` - A 2D vector of optional operations padded with `None`.
1108///
1109/// # Returns
1110///
1111/// A 2D vector of operations without `None` values.
1112fn remove_padding(operations: Vec<Vec<Option<Operation>>>) -> Vec<Vec<Operation>> {
1113 operations
1114 .into_iter()
1115 .map(|col| col.into_iter().flatten().collect())
1116 .collect()
1117}
1118
1119/// Transforms a row-col 2D array into an equivalent col-row 2D array.
1120///
1121/// # Arguments
1122///
1123/// * `aligned_ops` - A 2D vector of optional usize values in row-col format.
1124///
1125/// # Returns
1126///
1127/// A 2D vector of optional usize values in col-row format.
1128fn transform_to_col_row(aligned_ops: Vec<Vec<Option<usize>>>) -> Vec<Vec<Option<usize>>> {
1129 if aligned_ops.is_empty() {
1130 return vec![];
1131 }
1132
1133 let num_rows = aligned_ops.len();
1134 let num_cols = aligned_ops
1135 .iter()
1136 .map(std::vec::Vec::len)
1137 .max()
1138 .unwrap_or(0);
1139
1140 let mut col_row_array = vec![vec![None; num_rows]; num_cols];
1141
1142 for (row, row_data) in aligned_ops.into_iter().enumerate() {
1143 for (col, value) in row_data.into_iter().enumerate() {
1144 col_row_array[col][row] = value;
1145 }
1146 }
1147
1148 col_row_array
1149}
1150
1151/// Groups operations by their respective registers.
1152///
1153/// # Arguments
1154///
1155/// * `operations` - A slice of operations to be grouped.
1156/// * `num_qubits` - The number of qubits in the circuit.
1157///
1158/// # Returns
1159///
1160/// A 2D vector of indices where `groupedOps[i][j]` is the index of the operations
1161/// at register `i` and column `j` (not yet aligned/padded).
1162fn group_operations(operations: &[Operation], num_qubits: usize) -> Vec<Vec<usize>> {
1163 let mut grouped_ops = vec![vec![]; num_qubits];
1164
1165 let max_q_id = match num_qubits {
1166 0 => 0,
1167 _ => num_qubits - 1,
1168 };
1169
1170 for (instr_idx, op) in operations.iter().enumerate() {
1171 let ctrls = match op {
1172 Operation::Measurement(m) => &m.qubits,
1173 Operation::Unitary(u) => &u.controls,
1174 Operation::Ket(_) => &vec![],
1175 };
1176 let targets = match op {
1177 Operation::Measurement(m) => &m.results,
1178 Operation::Unitary(u) => &u.targets,
1179 Operation::Ket(k) => &k.targets,
1180 };
1181 let q_regs: Vec<_> = ctrls
1182 .iter()
1183 .chain(targets)
1184 .filter(|reg| !reg.is_classical())
1185 .collect();
1186 let q_reg_idx_list: Vec<_> = q_regs.iter().map(|reg| reg.qubit).collect();
1187 let cls_controls: Vec<_> = ctrls.iter().filter(|reg| reg.is_classical()).collect();
1188 let is_classically_controlled = !cls_controls.is_empty();
1189
1190 if !is_classically_controlled && q_regs.is_empty() {
1191 continue;
1192 }
1193
1194 let (min_reg_idx, max_reg_idx) = if is_classically_controlled {
1195 (0, max_q_id)
1196 } else {
1197 q_reg_idx_list
1198 .into_iter()
1199 .fold(None, |acc, x| match acc {
1200 None => Some((x, x)),
1201 Some((min, max)) => Some((min.min(x), max.max(x))),
1202 })
1203 .unwrap_or((0, max_q_id))
1204 };
1205
1206 for reg_ops in grouped_ops
1207 .iter_mut()
1208 .take(max_reg_idx + 1)
1209 .skip(min_reg_idx)
1210 {
1211 reg_ops.push(instr_idx);
1212 }
1213 }
1214
1215 grouped_ops
1216}
1217
1218/// Aligns operations by padding registers with `None` to make sure that multiqubit
1219/// gates are in the same column.
1220///
1221/// # Arguments
1222///
1223/// * `ops` - A 2D vector of usize values representing the operations.
1224///
1225/// # Returns
1226///
1227/// A 2D vector of optional usize values representing the aligned operations.
1228fn align_ops(ops: Vec<Vec<usize>>) -> Vec<Vec<Option<usize>>> {
1229 let mut max_num_ops = ops.iter().map(std::vec::Vec::len).max().unwrap_or(0);
1230 let mut col = 0;
1231 let mut padded_ops: Vec<Vec<Option<usize>>> = ops
1232 .into_iter()
1233 .map(|reg_ops| reg_ops.into_iter().map(Some).collect())
1234 .collect();
1235
1236 while col < max_num_ops {
1237 for reg_idx in 0..padded_ops.len() {
1238 if padded_ops[reg_idx].len() <= col {
1239 continue;
1240 }
1241
1242 // Represents the gate at padded_ops[reg_idx][col]
1243 let op_idx = padded_ops[reg_idx][col];
1244
1245 // The vec of where in each register the gate appears
1246 let targets_pos: Vec<_> = padded_ops
1247 .iter()
1248 .map(|reg_ops| reg_ops.iter().position(|&x| x == op_idx))
1249 .collect();
1250 // The maximum column index of the gate in the target registers
1251 let gate_max_col = targets_pos
1252 .iter()
1253 .filter_map(|&pos| pos)
1254 .max()
1255 .unwrap_or(usize::MAX);
1256
1257 if col < gate_max_col {
1258 padded_ops[reg_idx].insert(col, None);
1259 max_num_ops = max_num_ops.max(padded_ops[reg_idx].len());
1260 }
1261 }
1262 col += 1;
1263 }
1264
1265 padded_ops
1266}
1267