GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
jan

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/source/npm/qsharp/ux/circuit-vis

source/npm/qsharp/ux/circuit-vis/circuitManipulation.ts

668lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT license.
3
4import { getOperationRegisters } from "../../src/utils.js";
5import { Column, ComponentGrid, Operation, Unitary } from "./circuit.js";
6import { CircuitEvents } from "./events.js";
7import { Register } from "./register.js";
8import {
9 findOperation,
10 findParentArray,
11 findParentOperation,
12 getChildTargets,
13 locationStringToIndexes,
14} from "./utils.js";
15
16/**
17 * Move an operation in the circuit.
18 *
19 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
20 * @param sourceLocation The location string of the source operation.
21 * @param targetLocation The location string of the target position.
22 * @param sourceWire The wire index of the source operation.
23 * @param targetWire The wire index to move the operation to.
24 * @param movingControl Whether the operation is being moved as a control.
25 * @param insertNewColumn Whether to insert a new column when adding the operation.
26 * @returns The moved operation or null if the move was unsuccessful.
27 */
28const moveOperation = (
29 circuitEvents: CircuitEvents,
30 sourceLocation: string,
31 targetLocation: string,
32 sourceWire: number,
33 targetWire: number,
34 movingControl: boolean,
35 insertNewColumn: boolean = false,
36): Operation | null => {
37 const originalOperation = findOperation(
38 circuitEvents.componentGrid,
39 sourceLocation,
40 );
41
42 if (originalOperation == null) return null;
43
44 // Create a deep copy of the source operation
45 const newSourceOperation: Operation = JSON.parse(
46 JSON.stringify(originalOperation),
47 );
48
49 _ensureQubitCount(circuitEvents, targetWire);
50
51 // Update operation's targets and controls
52 _moveY(
53 circuitEvents,
54 newSourceOperation,
55 sourceLocation,
56 sourceWire,
57 targetWire,
58 movingControl,
59 );
60
61 // Move horizontally
62 _moveX(
63 circuitEvents,
64 newSourceOperation,
65 originalOperation,
66 targetLocation,
67 insertNewColumn,
68 );
69
70 const sourceOperationParent = findParentArray(
71 circuitEvents.componentGrid,
72 sourceLocation,
73 );
74 if (sourceOperationParent == null) return null;
75 _removeOp(circuitEvents, originalOperation, sourceOperationParent);
76 removeTrailingUnusedQubits(circuitEvents);
77
78 return newSourceOperation;
79};
80
81/**
82 * Move an operation horizontally.
83 *
84 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
85 * @param sourceOperation The operation to be moved.
86 * @param originalOperation The original source operation to be ignored during the check for existing operations.
87 * @param targetLocation The location string of the target position.
88 * @param insertNewColumn Whether to insert a new column when adding the operation.
89 */
90const _moveX = (
91 circuitEvents: CircuitEvents,
92 sourceOperation: Operation,
93 originalOperation: Operation,
94 targetLocation: string,
95 insertNewColumn: boolean = false,
96) => {
97 const targetOperationParent = findParentArray(
98 circuitEvents.componentGrid,
99 targetLocation,
100 );
101
102 const targetLastIndex = locationStringToIndexes(targetLocation).pop();
103
104 if (targetOperationParent == null || targetLastIndex == null) return;
105
106 // Insert sourceOperation to target last index
107 _addOp(
108 circuitEvents,
109 sourceOperation,
110 targetOperationParent,
111 targetLastIndex,
112 insertNewColumn,
113 originalOperation,
114 );
115};
116
117/**
118 * Move an operation vertically by changing its controls and targets.
119 *
120 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
121 * @param sourceOperation The operation to be moved.
122 * @param sourceLocation The location string of the source operation.
123 * @param sourceWire The wire index of the source operation.
124 * @param targetWire The wire index to move the operation to.
125 * @param movingControl Whether the operation is being moved as a control.
126 */
127const _moveY = (
128 circuitEvents: CircuitEvents,
129 sourceOperation: Operation,
130 sourceLocation: string,
131 sourceWire: number,
132 targetWire: number,
133 movingControl: boolean,
134): void => {
135 // Check if the source operation already has a target or control on the target wire
136 let targets: Register[];
137 switch (sourceOperation.kind) {
138 case "unitary":
139 case "ket":
140 targets = sourceOperation.targets;
141 break;
142 case "measurement":
143 targets = sourceOperation.qubits;
144 break;
145 }
146
147 let controls: Register[];
148 switch (sourceOperation.kind) {
149 case "unitary":
150 controls = sourceOperation.controls || [];
151 break;
152 case "measurement":
153 case "ket":
154 controls = [];
155 break;
156 }
157
158 let likeRegisters: Register[];
159 let unlikeRegisters: Register[];
160 if (movingControl) {
161 likeRegisters = controls;
162 unlikeRegisters = targets;
163 } else {
164 likeRegisters = targets;
165 unlikeRegisters = controls;
166 }
167
168 // If a similar register already exists, don't move the gate
169 if (likeRegisters.find((reg) => reg.qubit === targetWire)) {
170 return;
171 }
172
173 // If a different kind of register already exists, swap the control and target
174 if (unlikeRegisters.find((reg) => reg.qubit === targetWire)) {
175 const index = unlikeRegisters.findIndex((reg) => reg.qubit === targetWire);
176 unlikeRegisters[index].qubit = sourceWire;
177 }
178
179 switch (sourceOperation.kind) {
180 case "unitary":
181 if (movingControl) {
182 sourceOperation.controls?.forEach((control) => {
183 if (control.qubit === sourceWire) {
184 control.qubit = targetWire;
185 }
186 });
187 sourceOperation.controls = sourceOperation.controls?.sort(
188 (a, b) => a.qubit - b.qubit,
189 );
190 } else {
191 sourceOperation.targets = [{ qubit: targetWire }];
192 }
193 break;
194 case "measurement":
195 sourceOperation.qubits = [{ qubit: targetWire }];
196 // The measurement result is updated later in the _updateMeasurementLines function
197 break;
198 case "ket":
199 sourceOperation.targets = [{ qubit: targetWire }];
200 break;
201 }
202
203 // Update parent operation targets
204 const parentOperation = findParentOperation(
205 circuitEvents.componentGrid,
206 sourceLocation,
207 );
208 if (parentOperation) {
209 if (parentOperation.kind === "measurement") {
210 // Note: this is very confusing with measurements. Maybe the right thing to do
211 // will become more apparent if we implement expandable measurements.
212 parentOperation.results = getChildTargets(parentOperation);
213 } else if (
214 parentOperation.kind === "unitary" ||
215 parentOperation.kind === "ket"
216 ) {
217 parentOperation.targets = getChildTargets(parentOperation);
218 }
219 }
220};
221
222/**
223 * Add an operation into the circuit.
224 *
225 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
226 * @param sourceOperation The operation to be added.
227 * @param targetLocation The location string of the target position.
228 * @param targetWire The wire index to add the operation to.
229 * @param insertNewColumn Whether to insert a new column when adding the operation.
230 * @returns The added operation or null if the addition was unsuccessful.
231 */
232const addOperation = (
233 circuitEvents: CircuitEvents,
234 sourceOperation: Operation,
235 targetLocation: string,
236 targetWire: number,
237 insertNewColumn: boolean = false,
238): Operation | null => {
239 const targetOperationParent = findParentArray(
240 circuitEvents.componentGrid,
241 targetLocation,
242 );
243 const targetLastIndex = locationStringToIndexes(targetLocation).pop();
244
245 if (targetOperationParent == null || targetLastIndex == null) return null;
246 // Create a deep copy of the source operation
247 const newSourceOperation: Operation = JSON.parse(
248 JSON.stringify(sourceOperation),
249 );
250
251 if (newSourceOperation.kind === "measurement") {
252 newSourceOperation.qubits = [{ qubit: targetWire }];
253 // The measurement result is updated later in the _updateMeasurementLines function
254 } else if (
255 newSourceOperation.kind === "unitary" ||
256 newSourceOperation.kind === "ket"
257 ) {
258 newSourceOperation.targets = [{ qubit: targetWire }];
259 }
260
261 _ensureQubitCount(circuitEvents, targetWire);
262
263 _addOp(
264 circuitEvents,
265 newSourceOperation,
266 targetOperationParent,
267 targetLastIndex,
268 insertNewColumn,
269 );
270
271 return newSourceOperation;
272};
273
274/**
275 * Remove an operation from the circuit.
276 *
277 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
278 * @param sourceLocation The location string of the operation to be removed.
279 */
280const removeOperation = (
281 circuitEvents: CircuitEvents,
282 sourceLocation: string,
283) => {
284 const sourceOperation = findOperation(
285 circuitEvents.componentGrid,
286 sourceLocation,
287 );
288 const sourceOperationParent = findParentArray(
289 circuitEvents.componentGrid,
290 sourceLocation,
291 );
292
293 if (sourceOperation == null || sourceOperationParent == null) return null;
294
295 _removeOp(circuitEvents, sourceOperation, sourceOperationParent);
296 removeTrailingUnusedQubits(circuitEvents);
297};
298
299/**
300 * Find and remove operations in-place that return `true` for a predicate function.
301 *
302 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
303 * @param pred The predicate function to determine which operations to remove.
304 */
305const findAndRemoveOperations = (
306 circuitEvents: CircuitEvents,
307 pred: (op: Operation) => boolean,
308) => {
309 // Remove operations that are true for the predicate function
310 const inPlaceFilter = (grid: ComponentGrid) => {
311 let i = 0;
312 while (i < grid.length) {
313 let j = 0;
314 while (j < grid[i].components.length) {
315 const op = grid[i].components[j];
316 if (op.children) {
317 inPlaceFilter(op.children);
318 }
319 if (pred(op)) {
320 circuitEvents.decrementQubitUseCountForOp(op);
321 grid[i].components.splice(j, 1);
322 } else {
323 j++;
324 }
325 }
326 if (grid[i].components.length === 0) {
327 grid.splice(i, 1);
328 } else {
329 i++;
330 }
331 }
332 };
333
334 inPlaceFilter(circuitEvents.componentGrid);
335};
336
337/**
338 * Add a control to the specified operation on the given wire index.
339 *
340 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
341 * @param op The unitary operation to which the control will be added.
342 * @param wireIndex The index of the wire where the control will be added.
343 * @returns True if the control was added, false if it already existed.
344 */
345const addControl = (
346 circuitEvents: CircuitEvents,
347 op: Unitary,
348 wireIndex: number,
349): boolean => {
350 if (!op.controls) {
351 op.controls = [];
352 }
353 const existingControl = op.controls.find(
354 (control) => control.qubit === wireIndex,
355 );
356 if (!existingControl) {
357 op.controls.push({ qubit: wireIndex });
358 op.controls.sort((a, b) => a.qubit - b.qubit);
359 _ensureQubitCount(circuitEvents, wireIndex);
360 circuitEvents.qubitUseCounts[wireIndex]++;
361 return true;
362 }
363 return false;
364};
365
366/**
367 * Remove a control from the specified operation on the given wire index.
368 *
369 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
370 * @param op The unitary operation from which the control will be removed.
371 * @param wireIndex The index of the wire where the control will be removed.
372 * @returns True if the control was removed, false if it did not exist.
373 */
374const removeControl = (
375 circuitEvents: CircuitEvents,
376 op: Unitary,
377 wireIndex: number,
378): boolean => {
379 if (op.controls) {
380 const controlIndex = op.controls.findIndex(
381 (control) => control.qubit === wireIndex,
382 );
383 if (controlIndex !== -1) {
384 op.controls.splice(controlIndex, 1);
385 circuitEvents.qubitUseCounts[wireIndex]--;
386 if (wireIndex === circuitEvents.qubits.length - 1) {
387 removeTrailingUnusedQubits(circuitEvents);
388 }
389 return true;
390 }
391 }
392 return false;
393};
394
395/**
396 * Resolves overlapping operations in each column of the component grid.
397 * For each column, splits overlapping operations into separate columns so that
398 * no two operations in the same column overlap on their register ranges.
399 * Modifies the component grid in-place.
400 *
401 * @param parentArray The component grid (array of columns) to process.
402 */
403const resolveOverlappingOperations = (parentArray: ComponentGrid): void => {
404 // Helper to resolve a single column into non-overlapping columns
405 const resolveColumn = (col: Column): Column[] => {
406 const newColumn: Column = { components: [] };
407 let [lastMin, lastMax] = [-1, -1];
408 let i = 0;
409 while (i < col.components.length) {
410 const op = col.components[i];
411 const [currMin, currMax] = _getMinMaxRegIdx(op);
412 // Sets up the first operation for comparison or if the current operation doesn't overlap
413 if (i === 0 || !_doesOverlap([lastMin, lastMax], [currMin, currMax])) {
414 [lastMin, lastMax] = [currMin, currMax];
415 i++;
416 } else {
417 // If they overlap, add the current operation to the new column
418 newColumn.components.push(op);
419 col.components.splice(i, 1);
420 }
421 }
422 if (newColumn.components.length > 0) {
423 const newColumns = resolveColumn(newColumn);
424 newColumns.push(col);
425 return newColumns;
426 } else {
427 return [col];
428 }
429 };
430
431 // In-place update of parentArray
432 let i = 0;
433 while (i < parentArray.length) {
434 const col = parentArray[i];
435 const newColumns = resolveColumn(col);
436 if (newColumns.length > 1) {
437 parentArray.splice(i, 1, ...newColumns);
438 i += newColumns.length;
439 }
440 i++;
441 }
442};
443
444/**
445 * Remove trailing unused qubits from the circuit.
446 *
447 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
448 */
449const removeTrailingUnusedQubits = (circuitEvents: CircuitEvents) => {
450 while (
451 circuitEvents.qubitUseCounts.length > 0 &&
452 circuitEvents.qubitUseCounts[circuitEvents.qubitUseCounts.length - 1] === 0
453 ) {
454 circuitEvents.qubits.pop();
455 circuitEvents.qubitUseCounts.pop();
456 }
457};
458
459/**
460 * Determines whether two register index ranges overlap.
461 *
462 * @param op1 The [min, max] register indices of the first operation.
463 * @param op2 The [min, max] register indices of the second operation.
464 * @returns True if the ranges overlap, false otherwise.
465 */
466const _doesOverlap = (
467 op1: [number, number],
468 op2: [number, number],
469): boolean => {
470 const [min1, max1] = op1;
471 const [min2, max2] = op2;
472 return max1 >= min2 && max2 >= min1;
473};
474
475/**
476 * Add an operation to the circuit at the specified location.
477 *
478 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
479 * @param sourceOperation The operation to be added.
480 * @param targetOperationParent The parent grid where the operation will be added.
481 * @param targetLastIndex The index within the parent array where the operation will be added.
482 * @param insertNewColumn Whether to insert a new column when adding the operation.
483 * @param originalOperation The original source operation to be ignored during the check for existing operations.
484 */
485const _addOp = (
486 circuitEvents: CircuitEvents,
487 sourceOperation: Operation,
488 targetOperationParent: ComponentGrid,
489 targetLastIndex: [number, number],
490 insertNewColumn: boolean = false,
491 originalOperation: Operation | null = null,
492) => {
493 const [colIndex, opIndex] = targetLastIndex;
494 if (targetOperationParent[colIndex] == null) {
495 targetOperationParent[colIndex] = { components: [] };
496 }
497
498 insertNewColumn =
499 insertNewColumn || _isClassicallyControlled(sourceOperation);
500
501 // Check if there are any existing operations in the target
502 // column within the wire range of the new operation
503 if (!insertNewColumn) {
504 const [minTarget, maxTarget] = _getMinMaxRegIdx(sourceOperation);
505 for (const op of targetOperationParent[colIndex].components) {
506 if (op === originalOperation) continue;
507
508 const [opMinTarget, opMaxTarget] = _getMinMaxRegIdx(op);
509 if (_doesOverlap([minTarget, maxTarget], [opMinTarget, opMaxTarget])) {
510 insertNewColumn = true;
511 break;
512 }
513 }
514 }
515
516 if (insertNewColumn) {
517 targetOperationParent.splice(colIndex, 0, {
518 components: [sourceOperation],
519 });
520 } else {
521 targetOperationParent[colIndex].components.splice(
522 opIndex,
523 0,
524 sourceOperation,
525 );
526 }
527
528 circuitEvents.incrementQubitUseCountForOp(sourceOperation);
529
530 if (sourceOperation.kind === "measurement") {
531 for (const targetWire of sourceOperation.qubits) {
532 _updateMeasurementLines(circuitEvents, targetWire.qubit);
533 }
534 }
535};
536
537/**
538 * Get the minimum and maximum register indices for a given operation.
539 * Based on getMinMaxRegIdx in process.ts, but without the numQubits.
540 *
541 * @param operation The operation for which to get the register indices.
542 * @returns A tuple containing the minimum and maximum register indices.
543 */
544const _getMinMaxRegIdx = (operation: Operation): [number, number] => {
545 const qRegs: Register[] = getOperationRegisters(operation).filter(
546 ({ result }) => result === undefined,
547 );
548 if (qRegs.length === 0) return [-1, -1];
549 const qRegIdxList: number[] = qRegs.map(({ qubit }) => qubit);
550 // Pad the contiguous range of registers that it covers.
551 const minRegIdx: number = Math.min(...qRegIdxList);
552 const maxRegIdx: number = Math.max(...qRegIdxList);
553
554 return [minRegIdx, maxRegIdx];
555};
556
557/**
558 * Check if an operation is classically controlled.
559 *
560 * @param operation The operation for which to get the register indices.
561 * @returns True if the operation is classically controlled, false otherwise.
562 */
563const _isClassicallyControlled = (operation: Operation): boolean => {
564 if (operation.kind !== "unitary") return false;
565 if (operation.controls === undefined) return false;
566 const clsControl = operation.controls.find(
567 ({ result }) => result !== undefined,
568 );
569 return clsControl !== undefined;
570};
571
572/**
573 * Remove an operation from the circuit.
574 *
575 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
576 * @param sourceOperation The operation to be removed.
577 * @param sourceOperationParent The parent grid from which the operation will be removed.
578 */
579const _removeOp = (
580 circuitEvents: CircuitEvents,
581 sourceOperation: Operation,
582 sourceOperationParent: ComponentGrid,
583) => {
584 if (sourceOperation.dataAttributes === undefined) {
585 sourceOperation.dataAttributes = { removed: "true" };
586 } else {
587 sourceOperation.dataAttributes["removed"] = "true";
588 }
589
590 // Find and remove the operation in sourceOperationParent
591 for (let colIndex = 0; colIndex < sourceOperationParent.length; colIndex++) {
592 const col = sourceOperationParent[colIndex];
593 const indexToRemove = col.components.findIndex(
594 (operation) =>
595 operation.dataAttributes && operation.dataAttributes["removed"],
596 );
597 if (indexToRemove !== -1) {
598 col.components.splice(indexToRemove, 1);
599 if (col.components.length === 0) {
600 sourceOperationParent.splice(colIndex, 1);
601 }
602 break;
603 }
604 }
605
606 circuitEvents.decrementQubitUseCountForOp(sourceOperation);
607
608 if (sourceOperation.kind === "measurement") {
609 for (const result of sourceOperation.results) {
610 _updateMeasurementLines(circuitEvents, result.qubit);
611 }
612 }
613};
614
615/**
616 * Update measurement lines for a specific wire.
617 *
618 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
619 * @param wireIndex The index of the wire to update the measurement lines for.
620 */
621const _updateMeasurementLines = (
622 circuitEvents: CircuitEvents,
623 wireIndex: number,
624) => {
625 _ensureQubitCount(circuitEvents, wireIndex);
626 let resultIndex = 0;
627 for (const col of circuitEvents.componentGrid) {
628 for (const comp of col.components) {
629 if (comp.kind === "measurement") {
630 // Find measurements on the correct wire based on their qubit.
631 const qubit = comp.qubits.find((qubit) => qubit.qubit === wireIndex);
632 if (qubit) {
633 // Remove any existing results and add a new one with the updated index.
634 comp.results = [{ qubit: qubit.qubit, result: resultIndex++ }];
635 }
636 }
637 }
638 }
639 circuitEvents.qubits[wireIndex].numResults =
640 resultIndex > 0 ? resultIndex : undefined;
641};
642
643/**
644 * Ensure that the qubit count in the circuit is sufficient for the given wire index.
645 *
646 * @param circuitEvents The CircuitEvents instance to handle circuit-related events.
647 * @param wireIndex The index of the wire to check.
648 */
649const _ensureQubitCount = (circuitEvents: CircuitEvents, wireIndex: number) => {
650 while (circuitEvents.qubits.length <= wireIndex) {
651 circuitEvents.qubits.push({
652 id: circuitEvents.qubits.length,
653 numResults: undefined,
654 });
655 circuitEvents.qubitUseCounts.push(0);
656 }
657};
658
659export {
660 moveOperation,
661 addOperation,
662 removeOperation,
663 findAndRemoveOperations,
664 addControl,
665 removeControl,
666 resolveOverlappingOperations,
667 removeTrailingUnusedQubits,
668};
669