GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
copilot/fix-2145

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_circuit/src

compiler/qsc_circuit/src/circuit.rs

931lines · 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::{cmp, fmt::Display, fmt::Write, ops::Not, vec};
10
11/// Current format version.
12pub const CURRENT_VERSION: usize = 1;
13
14/// Representation of a quantum circuit group.
15#[derive(Clone, Serialize, Deserialize, Default, Debug, PartialEq)]
16pub struct CircuitGroup {
17 pub circuits: Vec<Circuit>,
18 pub version: usize,
19}
20
21impl Display for CircuitGroup {
22 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
23 for circuit in &self.circuits {
24 writeln!(f, "{circuit}")?;
25 }
26 Ok(())
27 }
28}
29
30/// Representation of a quantum circuit.
31#[derive(Clone, Serialize, Deserialize, Default, Debug, PartialEq)]
32pub struct Circuit {
33 pub qubits: Vec<Qubit>,
34 #[serde(rename = "componentGrid")]
35 pub component_grid: ComponentGrid,
36}
37
38/// Type alias for a grid of components.
39pub type ComponentGrid = Vec<ComponentColumn>;
40
41/// Representation of a column in the component grid.
42#[derive(Clone, Serialize, Deserialize, Default, Debug, PartialEq)]
43pub struct ComponentColumn {
44 pub components: Vec<Component>,
45}
46
47/// Union type for components.
48pub type Component = Operation;
49
50/// Union type for operations.
51#[derive(Clone, Serialize, Deserialize, Debug, PartialEq)]
52#[serde(tag = "kind")]
53pub enum Operation {
54 #[serde(rename = "measurement")]
55 Measurement(Measurement),
56 #[serde(rename = "unitary")]
57 Unitary(Unitary),
58 #[serde(rename = "ket")]
59 Ket(Ket),
60}
61
62impl Operation {
63 /// Returns the gate name of the operation.
64 #[must_use]
65 pub fn gate(&self) -> String {
66 match self {
67 Operation::Measurement(m) => m.gate.clone(),
68 Operation::Unitary(u) => u.gate.clone(),
69 #[allow(clippy::unicode_not_nfc)]
70 Operation::Ket(k) => format!("|{}〉", k.gate),
71 }
72 }
73
74 /// Returns the arguments for the operation.
75 #[must_use]
76 pub fn args(&self) -> Vec<String> {
77 match self {
78 Operation::Measurement(m) => m.args.clone(),
79 Operation::Unitary(u) => u.args.clone(),
80 Operation::Ket(k) => k.args.clone(),
81 }
82 }
83
84 /// Returns the children for the operation.
85 #[must_use]
86 pub fn children(&self) -> &ComponentGrid {
87 match self {
88 Operation::Measurement(m) => &m.children,
89 Operation::Unitary(u) => &u.children,
90 Operation::Ket(k) => &k.children,
91 }
92 }
93
94 /// Returns if the operation is a controlled operation.
95 #[must_use]
96 pub fn is_controlled(&self) -> bool {
97 match self {
98 Operation::Measurement(_) | Operation::Ket(_) => false,
99 Operation::Unitary(u) => !u.controls.is_empty(),
100 }
101 }
102
103 /// Returns if the operation is a measurement operation.
104 #[must_use]
105 pub fn is_measurement(&self) -> bool {
106 match self {
107 Operation::Measurement(_) => true,
108 Operation::Unitary(_) | Operation::Ket(_) => false,
109 }
110 }
111
112 /// Returns if the operation is an adjoint operation.
113 #[must_use]
114 pub fn is_adjoint(&self) -> bool {
115 match self {
116 Operation::Measurement(_) | Operation::Ket(_) => false,
117 Operation::Unitary(u) => u.is_adjoint,
118 }
119 }
120}
121
122/// Representation of a measurement operation.
123#[derive(Clone, Serialize, Deserialize, Default, Debug, PartialEq)]
124pub struct Measurement {
125 pub gate: String,
126 #[serde(skip_serializing_if = "Vec::is_empty")]
127 #[serde(default)]
128 pub args: Vec<String>,
129 #[serde(skip_serializing_if = "Vec::is_empty")]
130 #[serde(default)]
131 pub children: ComponentGrid,
132 pub qubits: Vec<Register>,
133 pub results: Vec<Register>,
134}
135
136/// Representation of a unitary operation.
137#[derive(Clone, Serialize, Deserialize, Default, Debug, PartialEq)]
138pub struct Unitary {
139 pub gate: String,
140 #[serde(skip_serializing_if = "Vec::is_empty")]
141 #[serde(default)]
142 pub args: Vec<String>,
143 #[serde(skip_serializing_if = "Vec::is_empty")]
144 #[serde(default)]
145 pub children: ComponentGrid,
146 pub targets: Vec<Register>,
147 #[serde(skip_serializing_if = "Vec::is_empty")]
148 #[serde(default)]
149 pub controls: Vec<Register>,
150 #[serde(rename = "isAdjoint")]
151 #[serde(skip_serializing_if = "Not::not")]
152 #[serde(default)]
153 pub is_adjoint: bool,
154}
155
156/// Representation of a gate that will set the target to a specific state.
157#[derive(Clone, Serialize, Deserialize, Default, Debug, PartialEq)]
158pub struct Ket {
159 pub gate: String,
160 #[serde(skip_serializing_if = "Vec::is_empty")]
161 #[serde(default)]
162 pub args: Vec<String>,
163 #[serde(skip_serializing_if = "Vec::is_empty")]
164 #[serde(default)]
165 pub children: ComponentGrid,
166 pub targets: Vec<Register>,
167}
168
169#[derive(Serialize, Deserialize, Debug, Eq, Hash, PartialEq, Clone)]
170pub struct Register {
171 pub qubit: usize,
172 #[serde(skip_serializing_if = "Option::is_none")]
173 pub result: Option<usize>,
174}
175
176impl Register {
177 pub fn quantum(qubit_id: usize) -> Self {
178 Self {
179 qubit: qubit_id,
180 result: None,
181 }
182 }
183
184 pub fn classical(qubit_id: usize, result_id: usize) -> Self {
185 Self {
186 qubit: qubit_id,
187 result: Some(result_id),
188 }
189 }
190
191 pub fn is_classical(&self) -> bool {
192 self.result.is_some()
193 }
194}
195
196#[derive(PartialEq, Clone, Serialize, Deserialize, Debug)]
197pub struct Qubit {
198 pub id: usize,
199 #[serde(rename = "numResults")]
200 #[serde(default)]
201 pub num_results: usize,
202}
203
204#[derive(Clone, Debug, Copy, Default)]
205pub struct Config {
206 /// Maximum number of operations the builder will add to the circuit
207 pub max_operations: usize,
208}
209
210impl Config {
211 /// Set to the current UI limit + 1 so that it still triggers
212 /// the "this circuit has too many gates" warning in the UI.
213 /// (see npm\qsharp\ux\circuit.tsx)
214 ///
215 /// A more refined way to do this might be to communicate the
216 /// "limit exceeded" state up to the UI somehow.
217 pub const DEFAULT_MAX_OPERATIONS: usize = 10001;
218}
219
220type ObjectsByColumn = FxHashMap<usize, CircuitObject>;
221
222struct Row {
223 wire: Wire,
224 objects: ObjectsByColumn,
225 next_column: usize,
226}
227
228enum Wire {
229 Qubit { q_id: usize },
230 Classical { start_column: Option<usize> },
231}
232
233enum CircuitObject {
234 Blank,
235 Wire,
236 WireCross,
237 WireStart,
238 DashedCross,
239 Vertical,
240 VerticalDashed,
241 Object(String),
242}
243
244impl Row {
245 fn add_object(&mut self, column: usize, object: &str) {
246 self.add(column, CircuitObject::Object(object.to_string()));
247 }
248
249 fn add_gate(&mut self, column: usize, gate: &str, args: &[String], is_adjoint: bool) {
250 let mut gate_label = String::new();
251 gate_label.push_str(gate);
252 if is_adjoint {
253 gate_label.push('\'');
254 }
255
256 if !args.is_empty() {
257 let args = args.join(", ");
258 let _ = write!(&mut gate_label, "({args})");
259 }
260
261 self.add_object(column, gate_label.as_str());
262 }
263
264 fn add_vertical(&mut self, column: usize) {
265 if !self.objects.contains_key(&column) {
266 match self.wire {
267 Wire::Qubit { .. } => self.add(column, CircuitObject::WireCross),
268 Wire::Classical { start_column } => {
269 if start_column.is_some() {
270 self.add(column, CircuitObject::WireCross);
271 } else {
272 self.add(column, CircuitObject::Vertical);
273 }
274 }
275 }
276 }
277 }
278
279 fn add_dashed_vertical(&mut self, column: usize) {
280 if !self.objects.contains_key(&column) {
281 match self.wire {
282 Wire::Qubit { .. } => self.add(column, CircuitObject::DashedCross),
283 Wire::Classical { start_column } => {
284 if start_column.is_some() {
285 self.add(column, CircuitObject::DashedCross);
286 } else {
287 self.add(column, CircuitObject::VerticalDashed);
288 }
289 }
290 }
291 }
292 }
293
294 fn start_classical(&mut self, column: usize) {
295 self.add(column, CircuitObject::WireStart);
296 if let Wire::Classical { start_column } = &mut self.wire {
297 start_column.replace(column);
298 }
299 }
300
301 fn add(&mut self, column: usize, circuit_object: CircuitObject) {
302 self.objects.insert(column, circuit_object);
303 self.next_column = column + 1;
304 }
305
306 fn fmt(&self, f: &mut std::fmt::Formatter<'_>, columns: &[Column]) -> std::fmt::Result {
307 // Temporary string so we can trim whitespace at the end
308 let mut s = String::new();
309 match &self.wire {
310 Wire::Qubit { q_id: label } => {
311 s.write_str(&fmt_qubit_label(*label))?;
312 for (column_index, column) in columns.iter().enumerate().skip(1) {
313 let val = self.objects.get(&column_index);
314 let object = val.unwrap_or(&CircuitObject::Wire);
315
316 s.write_str(&column.fmt_qubit_circuit_object(object))?;
317 }
318 }
319 Wire::Classical { start_column } => {
320 for (column_index, column) in columns.iter().enumerate() {
321 let val = self.objects.get(&column_index);
322
323 let object = match (val, start_column) {
324 (Some(v), _) => v,
325 (None, Some(s)) if column_index > *s => &CircuitObject::Wire,
326 _ => &CircuitObject::Blank,
327 };
328
329 s.write_str(&column.fmt_classical_circuit_object(object))?;
330 }
331 }
332 }
333 writeln!(f, "{}", s.trim_end())?;
334 Ok(())
335 }
336}
337
338const MIN_COLUMN_WIDTH: usize = 7;
339
340const QUBIT_WIRE: [char; 3] = ['─', '─', '─']; // "───────"
341const CLASSICAL_WIRE: [char; 3] = ['═', '═', '═']; // "═══════"
342const QUBIT_WIRE_CROSS: [char; 3] = ['─', '┼', '─']; // "───┼───"
343const CLASSICAL_WIRE_CROSS: [char; 3] = ['═', '╪', '═']; // "═══╪═══"
344const CLASSICAL_WIRE_START: [char; 3] = [' ', '╘', '═']; // " ╘═══"
345const QUBIT_WIRE_DASHED_CROSS: [char; 3] = ['─', '┆', '─']; // "───┆───"
346const CLASSICAL_WIRE_DASHED_CROSS: [char; 3] = ['═', '┆', '═']; // "═══┆═══"
347const VERTICAL_DASHED: [char; 3] = [' ', '┆', ' ']; // " │ "
348const VERTICAL: [char; 3] = [' ', '│', ' ']; // " ┆ "
349const BLANK: [char; 3] = [' ', ' ', ' ']; // " "
350
351/// "q_0 "
352#[allow(clippy::doc_markdown)]
353fn fmt_qubit_label(id: usize) -> String {
354 let rest = MIN_COLUMN_WIDTH - 2;
355 format!("q_{id: <rest$}")
356}
357
358struct Column {
359 column_width: usize,
360}
361
362impl Default for Column {
363 fn default() -> Self {
364 Self {
365 column_width: MIN_COLUMN_WIDTH,
366 }
367 }
368}
369
370impl Column {
371 fn new(column_width: usize) -> Self {
372 // Column widths should be odd numbers for this struct to work well
373 let odd_column_width = column_width | 1;
374 Self {
375 column_width: odd_column_width,
376 }
377 }
378
379 /// "── A ──"
380 fn fmt_on_qubit_wire(&self, obj: &str) -> String {
381 let column_width = self.column_width;
382 format!("{:─^column_width$}", format!(" {obj} "))
383 }
384
385 /// "══ A ══"
386 fn fmt_on_classical_wire(&self, obj: &str) -> String {
387 let column_width = self.column_width;
388 format!("{:═^column_width$}", format!(" {obj} "))
389 }
390
391 fn expand_template(&self, template: &[char; 3]) -> String {
392 let half_width = self.column_width / 2;
393 let left = template[0].to_string().repeat(half_width);
394 let right = template[2].to_string().repeat(half_width);
395
396 format!("{left}{}{right}", template[1])
397 }
398
399 fn fmt_classical_circuit_object(&self, circuit_object: &CircuitObject) -> String {
400 if let CircuitObject::Object(label) = circuit_object {
401 return self.fmt_on_classical_wire(label.as_str());
402 }
403
404 let template = match circuit_object {
405 CircuitObject::Blank => BLANK,
406 CircuitObject::Wire => CLASSICAL_WIRE,
407 CircuitObject::WireCross => CLASSICAL_WIRE_CROSS,
408 CircuitObject::WireStart => CLASSICAL_WIRE_START,
409 CircuitObject::DashedCross => CLASSICAL_WIRE_DASHED_CROSS,
410 CircuitObject::Vertical => VERTICAL,
411 CircuitObject::VerticalDashed => VERTICAL_DASHED,
412 CircuitObject::Object(_) => unreachable!("This case is covered in the early return."),
413 };
414
415 self.expand_template(&template)
416 }
417
418 fn fmt_qubit_circuit_object(&self, circuit_object: &CircuitObject) -> String {
419 if let CircuitObject::Object(label) = circuit_object {
420 return self.fmt_on_qubit_wire(label.as_str());
421 }
422
423 let template = match circuit_object {
424 CircuitObject::WireStart // This should never happen
425 | CircuitObject::Blank => BLANK,
426 CircuitObject::Wire => QUBIT_WIRE,
427 CircuitObject::WireCross => QUBIT_WIRE_CROSS,
428 CircuitObject::DashedCross => QUBIT_WIRE_DASHED_CROSS,
429 CircuitObject::Vertical => VERTICAL,
430 CircuitObject::VerticalDashed => VERTICAL_DASHED,
431 CircuitObject::Object(_) => unreachable!("This case is covered in the early return."),
432 };
433
434 self.expand_template(&template)
435 }
436}
437
438impl Display for Circuit {
439 /// Formats the circuit into a diagram.
440 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
441 let mut rows = vec![];
442
443 // Maintain a mapping from from Registers in the Circuit schema
444 // to row in the diagram
445 let mut register_to_row = FxHashMap::default();
446
447 // Keep track of which qubits have the qubit after them in the same multi-qubit operation,
448 // because those qubits need to get a gap row below them.
449 let mut qubits_with_gap_row_below = FxHashSet::default();
450
451 // Identify qubits that require gap rows
452 self.identify_qubits_with_gap_rows(&mut qubits_with_gap_row_below);
453
454 // Initialize rows for qubits and classical wires
455 self.initialize_rows(&mut rows, &mut register_to_row, &qubits_with_gap_row_below);
456
457 // Add operations to the diagram
458 self.add_operations_to_diagram(&mut rows, &register_to_row);
459
460 // Finalize the diagram by extending wires and formatting columns
461 let columns = finalize_columns(&rows);
462
463 // Draw the diagram
464 for row in rows {
465 row.fmt(f, &columns)?;
466 }
467
468 Ok(())
469 }
470}
471
472impl Circuit {
473 /// Identifies qubits that require gap rows for multi-qubit operations.
474 fn identify_qubits_with_gap_rows(&self, qubits_with_gap_row_below: &mut FxHashSet<usize>) {
475 for col in &self.component_grid {
476 for op in &col.components {
477 let targets = match op {
478 Operation::Measurement(m) => &m.qubits,
479 Operation::Unitary(u) => &u.targets,
480 Operation::Ket(k) => &k.targets,
481 };
482 for target in targets {
483 let qubit = target.qubit;
484
485 if qubits_with_gap_row_below.contains(&qubit) {
486 continue;
487 }
488
489 let next_qubit = qubit + 1;
490
491 // Check if the next qubit is also in this operation.
492 if targets.iter().any(|t| t.qubit == next_qubit) {
493 qubits_with_gap_row_below.insert(qubit);
494 }
495 }
496 }
497 }
498 }
499
500 /// Initializes rows for qubits and classical wires.
501 fn initialize_rows(
502 &self,
503 rows: &mut Vec<Row>,
504 register_to_row: &mut FxHashMap<(usize, Option<usize>), usize>,
505 qubits_with_gap_row_below: &FxHashSet<usize>,
506 ) {
507 for q in &self.qubits {
508 rows.push(Row {
509 wire: Wire::Qubit { q_id: q.id },
510 objects: FxHashMap::default(),
511 next_column: 1,
512 });
513
514 register_to_row.insert((q.id, None), rows.len() - 1);
515
516 // If this qubit has no children, but it is in a multi-qubit operation with
517 // the next qubit, we add an empty row to make room for the vertical connector.
518 // We can just use a classical wire type for this row since the wire won't actually be rendered.
519 let extra_rows = if qubits_with_gap_row_below.contains(&q.id) {
520 cmp::max(1, q.num_results)
521 } else {
522 q.num_results
523 };
524
525 for i in 0..extra_rows {
526 rows.push(Row {
527 wire: Wire::Classical { start_column: None },
528 objects: FxHashMap::default(),
529 next_column: 1,
530 });
531
532 register_to_row.insert((q.id, Some(i)), rows.len() - 1);
533 }
534 }
535 }
536
537 /// Adds operations to the diagram.
538 fn add_operations_to_diagram(
539 &self,
540 rows: &mut [Row],
541 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
542 ) {
543 for (col_index, col) in self.component_grid.iter().enumerate() {
544 for op in &col.components {
545 let targets = get_row_indexes(op, register_to_row, true);
546 let controls = get_row_indexes(op, register_to_row, false);
547
548 let mut all_rows = targets.clone();
549 all_rows.extend(controls.iter());
550 all_rows.sort_unstable();
551
552 // We'll need to know the entire range of rows for this operation so we can
553 // figure out the starting column and also so we can draw any
554 // vertical lines that cross wires.
555 let (begin, end) = all_rows.split_first().map_or((0, 0), |(first, tail)| {
556 (*first, tail.last().unwrap_or(first) + 1)
557 });
558
559 let column = col_index + 1;
560
561 add_operation_to_rows(op, rows, &targets, &controls, column, begin, end);
562 }
563 }
564 }
565}
566
567#[allow(clippy::too_many_arguments)]
568/// Adds a single operation to the rows.
569fn add_operation_to_rows(
570 operation: &Operation,
571 rows: &mut [Row],
572 targets: &[usize],
573 controls: &[usize],
574 column: usize,
575 begin: usize,
576 end: usize,
577) {
578 for i in targets {
579 let row = &mut rows[*i];
580 if matches!(row.wire, Wire::Classical { .. })
581 && matches!(operation, Operation::Measurement(_))
582 {
583 row.start_classical(column);
584 } else {
585 row.add_gate(
586 column,
587 &operation.gate(),
588 &operation.args(),
589 operation.is_adjoint(),
590 );
591 }
592 }
593
594 if operation.is_controlled() || operation.is_measurement() {
595 for i in controls {
596 let row = &mut rows[*i];
597 if matches!(row.wire, Wire::Qubit { .. }) && operation.is_measurement() {
598 row.add_object(column, "M");
599 } else {
600 row.add_object(column, "●");
601 }
602 }
603
604 // If we have a control wire, draw vertical lines spanning all
605 // control and target wires and crossing any in between
606 // (vertical lines may overlap if there are multiple controls/targets,
607 // this is ok in practice)
608 for row in &mut rows[begin..end] {
609 row.add_vertical(column);
610 }
611 } else {
612 // No control wire. Draw dashed vertical lines to connect
613 // target wires if there are multiple targets
614 for row in &mut rows[begin..end] {
615 row.add_dashed_vertical(column);
616 }
617 }
618}
619
620/// Finalizes the columns by calculating their widths.
621fn finalize_columns(rows: &[Row]) -> Vec<Column> {
622 // Find the end column for the whole circuit so that
623 // all qubit wires will extend until the end
624 let end_column = rows
625 .iter()
626 .max_by_key(|r| r.next_column)
627 .map_or(1, |r| r.next_column);
628
629 // To be able to fit long-named operations, we calculate the required width for each column,
630 // based on the maximum length needed for gates, where a gate X is printed as "- X -".
631 (0..end_column)
632 .map(|column| {
633 Column::new(
634 rows.iter()
635 .filter_map(|row| row.objects.get(&column))
636 .filter_map(|object| match object {
637 CircuitObject::Object(string) => Some(string.len() + 4),
638 _ => None,
639 })
640 .chain(std::iter::once(MIN_COLUMN_WIDTH))
641 .max()
642 .expect("Column width should be at least 1"),
643 )
644 })
645 .collect()
646}
647
648/// Gets the row indexes for the targets or controls of an operation.
649fn get_row_indexes(
650 operation: &Operation,
651 register_to_row: &FxHashMap<(usize, Option<usize>), usize>,
652 is_target: bool,
653) -> Vec<usize> {
654 let registers = match operation {
655 Operation::Measurement(m) => {
656 if is_target {
657 &m.results
658 } else {
659 &m.qubits
660 }
661 }
662 Operation::Unitary(u) => {
663 if is_target {
664 &u.targets
665 } else {
666 &u.controls
667 }
668 }
669 Operation::Ket(k) => {
670 if is_target {
671 &k.targets
672 } else {
673 &vec![]
674 }
675 }
676 };
677
678 registers
679 .iter()
680 .filter_map(|reg| {
681 let reg = (reg.qubit, reg.result);
682 register_to_row.get(&reg).copied()
683 })
684 .collect()
685}
686
687/// Converts a list of operations into a 2D grid of operations in col-row format.
688/// Operations will be left-justified as much as possible in the resulting grid.
689/// Children operations are recursively converted into a grid.
690///
691/// # Arguments
692///
693/// * `operations` - A vector of operations to be converted.
694/// * `num_qubits` - The number of qubits in the circuit.
695///
696/// # Returns
697///
698/// A component grid representing the operations.
699pub fn operation_list_to_grid(mut operations: Vec<Operation>, num_qubits: usize) -> ComponentGrid {
700 for op in &mut operations {
701 // The children data structure is a grid, so checking if it is
702 // length 1 is actually checking if it has a single column,
703 // or in other words, we are checking if its children are in a single list.
704 // If the operation has children in a single list, it needs to be converted to a grid.
705 // If it was already converted to a grid, but the grid was still a single list,
706 // then doing it again won't effect anything.
707 if op.children().len() == 1 {
708 match op {
709 Operation::Measurement(m) => {
710 m.children =
711 operation_list_to_grid(m.children.remove(0).components, num_qubits);
712 }
713 Operation::Unitary(u) => {
714 u.children =
715 operation_list_to_grid(u.children.remove(0).components, num_qubits);
716 }
717 Operation::Ket(k) => {
718 k.children =
719 operation_list_to_grid(k.children.remove(0).components, num_qubits);
720 }
721 }
722 }
723 }
724
725 // Convert the operations into a component grid
726 let mut component_grid = vec![];
727 for col in remove_padding(operation_list_to_padded_array(operations, num_qubits)) {
728 let column = ComponentColumn { components: col };
729 component_grid.push(column);
730 }
731 component_grid
732}
733
734/// Converts a list of operations into a padded 2D array of operations.
735///
736/// # Arguments
737///
738/// * `operations` - A vector of operations to be converted.
739/// * `num_qubits` - The number of qubits in the circuit.
740///
741/// # Returns
742///
743/// A 2D vector of optional operations padded with `None`.
744fn operation_list_to_padded_array(
745 operations: Vec<Operation>,
746 num_qubits: usize,
747) -> Vec<Vec<Option<Operation>>> {
748 if operations.is_empty() {
749 return vec![];
750 }
751
752 let grouped_ops = group_operations(&operations, num_qubits);
753 let aligned_ops = transform_to_col_row(align_ops(grouped_ops));
754
755 // Need to convert to optional operations so we can
756 // take operations out without messing up the indexing
757 let mut operations = operations.into_iter().map(Some).collect::<Vec<_>>();
758 aligned_ops
759 .into_iter()
760 .map(|col| {
761 col.into_iter()
762 .map(|op_idx| op_idx.and_then(|idx| operations[idx].take()))
763 .collect()
764 })
765 .collect()
766}
767
768/// Removes padding (`None` values) from a 2D array of operations.
769///
770/// # Arguments
771///
772/// * `operations` - A 2D vector of optional operations padded with `None`.
773///
774/// # Returns
775///
776/// A 2D vector of operations without `None` values.
777fn remove_padding(operations: Vec<Vec<Option<Operation>>>) -> Vec<Vec<Operation>> {
778 operations
779 .into_iter()
780 .map(|col| col.into_iter().flatten().collect())
781 .collect()
782}
783
784/// Transforms a row-col 2D array into an equivalent col-row 2D array.
785///
786/// # Arguments
787///
788/// * `aligned_ops` - A 2D vector of optional usize values in row-col format.
789///
790/// # Returns
791///
792/// A 2D vector of optional usize values in col-row format.
793fn transform_to_col_row(aligned_ops: Vec<Vec<Option<usize>>>) -> Vec<Vec<Option<usize>>> {
794 if aligned_ops.is_empty() {
795 return vec![];
796 }
797
798 let num_rows = aligned_ops.len();
799 let num_cols = aligned_ops
800 .iter()
801 .map(std::vec::Vec::len)
802 .max()
803 .unwrap_or(0);
804
805 let mut col_row_array = vec![vec![None; num_rows]; num_cols];
806
807 for (row, row_data) in aligned_ops.into_iter().enumerate() {
808 for (col, value) in row_data.into_iter().enumerate() {
809 col_row_array[col][row] = value;
810 }
811 }
812
813 col_row_array
814}
815
816/// Groups operations by their respective registers.
817///
818/// # Arguments
819///
820/// * `operations` - A slice of operations to be grouped.
821/// * `num_qubits` - The number of qubits in the circuit.
822///
823/// # Returns
824///
825/// A 2D vector of indices where `groupedOps[i][j]` is the index of the operations
826/// at register `i` and column `j` (not yet aligned/padded).
827fn group_operations(operations: &[Operation], num_qubits: usize) -> Vec<Vec<usize>> {
828 let mut grouped_ops = vec![vec![]; num_qubits];
829
830 let max_q_id = match num_qubits {
831 0 => 0,
832 _ => num_qubits - 1,
833 };
834
835 for (instr_idx, op) in operations.iter().enumerate() {
836 let ctrls = match op {
837 Operation::Measurement(m) => &m.qubits,
838 Operation::Unitary(u) => &u.controls,
839 Operation::Ket(_) => &vec![],
840 };
841 let targets = match op {
842 Operation::Measurement(m) => &m.results,
843 Operation::Unitary(u) => &u.targets,
844 Operation::Ket(k) => &k.targets,
845 };
846 let q_regs: Vec<_> = ctrls
847 .iter()
848 .chain(targets)
849 .filter(|reg| !reg.is_classical())
850 .collect();
851 let q_reg_idx_list: Vec<_> = q_regs.iter().map(|reg| reg.qubit).collect();
852 let cls_controls: Vec<_> = ctrls.iter().filter(|reg| reg.is_classical()).collect();
853 let is_classically_controlled = !cls_controls.is_empty();
854
855 if !is_classically_controlled && q_regs.is_empty() {
856 continue;
857 }
858
859 let (min_reg_idx, max_reg_idx) = if is_classically_controlled {
860 (0, max_q_id)
861 } else {
862 q_reg_idx_list
863 .into_iter()
864 .fold(None, |acc, x| match acc {
865 None => Some((x, x)),
866 Some((min, max)) => Some((min.min(x), max.max(x))),
867 })
868 .unwrap_or((0, max_q_id))
869 };
870
871 for reg_ops in grouped_ops
872 .iter_mut()
873 .take(max_reg_idx + 1)
874 .skip(min_reg_idx)
875 {
876 reg_ops.push(instr_idx);
877 }
878 }
879
880 grouped_ops
881}
882
883/// Aligns operations by padding registers with `None` to make sure that multiqubit
884/// gates are in the same column.
885///
886/// # Arguments
887///
888/// * `ops` - A 2D vector of usize values representing the operations.
889///
890/// # Returns
891///
892/// A 2D vector of optional usize values representing the aligned operations.
893fn align_ops(ops: Vec<Vec<usize>>) -> Vec<Vec<Option<usize>>> {
894 let mut max_num_ops = ops.iter().map(std::vec::Vec::len).max().unwrap_or(0);
895 let mut col = 0;
896 let mut padded_ops: Vec<Vec<Option<usize>>> = ops
897 .into_iter()
898 .map(|reg_ops| reg_ops.into_iter().map(Some).collect())
899 .collect();
900
901 while col < max_num_ops {
902 for reg_idx in 0..padded_ops.len() {
903 if padded_ops[reg_idx].len() <= col {
904 continue;
905 }
906
907 // Represents the gate at padded_ops[reg_idx][col]
908 let op_idx = padded_ops[reg_idx][col];
909
910 // The vec of where in each register the gate appears
911 let targets_pos: Vec<_> = padded_ops
912 .iter()
913 .map(|reg_ops| reg_ops.iter().position(|&x| x == op_idx))
914 .collect();
915 // The maximum column index of the gate in the target registers
916 let gate_max_col = targets_pos
917 .iter()
918 .filter_map(|&pos| pos)
919 .max()
920 .unwrap_or(usize::MAX);
921
922 if col < gate_max_col {
923 padded_ops[reg_idx].insert(col, None);
924 max_num_ops = max_num_ops.max(padded_ops[reg_idx].len());
925 }
926 }
927 col += 1;
928 }
929
930 padded_ops
931}
932