003 - Transforming Quantum Circuits using Qiskit's Transpiler with Matthew Treinish: Qiskit Summer School

0:00 Introduction

0:17 Terminology

0:51 Why Quantum Circuit Compilation

3:22 Constraints on Quantum Hardware

6:06 Connectivity Limitations

10:49 Transpiler Graph Representation

17:17 Init Stage

22:49 Layout Passes

36:16 Single Cubit UPO

38:26 Two Cubit UPO

41:38 Commutative Cancellation Pass

43:03 Scheduling

1. Connectivity is not always sufficient to fully map the abstract circuit directly onto the physical qubits.

2. To address this, the compiler uses techniques like SWAP gates to move quantum states between qubits.

3. This process of moving states can be expensive in terms of computational resources and errors, so the compiler's job is to minimize these operations as much as possible.

• The image on the right likely shows a quantum circuit that uses SWAP gates (indicated by the X-shaped symbols) to move states between qubits. The "+" symbols still indicate interactions like controlled gates (such as CNOT gates).

• SWAP Gates: In this case, the compiler has inserted SWAP gates in places where qubits need to exchange states due to connectivity limitations. This allows non-adjacent qubits to interact indirectly by routing their states through intermediate qubits.

• Global Phase (3π/2) 是整体的相位因子，虽然不影响测量结果，但它需要放在最左边（即最后乘上去）

• √X 表示 X 门的平方根（又称为 √NOT 或 V 门）

• CZ 表示受控-Z 门

• ⊗ 表示张量积

• 表示门的组合（按从右到左的顺序应用）

1. 最右边的 (√X ⊗ √X) 首先作用

2. 然后是 CZ

3. 接着是另一个 (√X ⊗ √X)

4. 再一个 CZ

5. 最后一个 (√X ⊗ √X)

6. 最后乘上整体相位因子 Global Phase (3π/2)

1. Gate Errors
• Single qubit Errors
• Multiqubit Errors

2. Decoherence
• T1: Energy Relaxation, defined as the time for a qubit at |1⟩ to decay to ground state |0⟩
• T2: Dephasing of a qubit in superposition state

3. Readout Error

• Washington (Eagle R1, 127Q)

• Ithaca (Hummingbird R3, 65Q)

• Peekskill (Falcon R8, 27Q)

1. CNOT (Controlled NOT gate) errors (in blue)

2. Measurement errors (in orange)

1. In Qiskit, the constraints of a given compilation target are modeled by the 'Target' class.

2. The target contains a list of every instruction (operation/gate on qubits) and their associated properties, typically including error rate, duration, and pulse calibration.

3. Additional properties about qubits and other device characteristics used for compilation are also contained within the target.

4. The right side of the image shows an example output of printing a backend target, which displays various instructions with their corresponding properties like duration, error rate, and pulse schedule calibration.

5. The number of qubits for this particular target appears to be 5, based on the instruction indices shown (e.g., (0,1), (1,2), etc., up to (4,3)).

6. The image seems to be from a presentation or educational material, possibly from the "Qiskit Global Summer School 2024" as indicated at the bottom.

7. A URL is provided at the bottom left, pointing to IBM's Qiskit documentation for more information on the Target class.

1. Qiskit uses DAG to represent quantum circuits internally.

2. The graph shows data flow from input nodes (green) through operations (blue) to output nodes (red).

3. Edges in the graph track both quantum and classical bits, as well as other classical variables.

4. This representation facilitates circuit analysis and understanding dependencies between operations.

5. It also simplifies in-place mutation and substitution of operations.

1. A circuit diagram showing quantum bits (q0-q3), gates (Ry), and measurements.

2. A DAG representation of a quantum circuit, illustrating the flow from input nodes (green) through various operations (blue) to output nodes (red).

1. Pass Manager: This is the central component that orchestrates the execution of various passes and maintains a global context about the circuit as it progresses through the pipeline.

2. Passes: There are four passes shown:
• Pass 1: Unroll to basis
• Pass 2: Cancel redundant gates
• Pass 3: Map to device by swapping
• Pass 4: Cancel redundant gates (again)

3. Global Property Set: This includes properties like Depth, Commuting Sets, Layout, and Fixed Point Condition.

• The complexity of scheduling is solely in the pass manager, to keep passes simple.

• Each pass does one small, well-defined task.

• The pass manager maintains a global context about the circuit as it runs through the pipeline.

Overview:

• The Pass Manager in Qiskit organizes the quantum circuit compilation into discrete stages, each performing specific transformations to prepare the circuit for execution on a quantum device.

• By default, Qiskit uses six stages for its preset pass managers, but users can manually create their own stages if needed.

The Six Stages:

1. Init Stage:
• This stage operates on the abstract circuit, handling any logical optimizations and decomposing larger gates into smaller gates (like 1-qubit and 2-qubit gates).
• Prepares the circuit for further processing by enabling the subsequent stages.

2. Layout Stage:
• Responsible for mapping the logical qubits in the circuit to the physical qubits in the target quantum device.

3. Routing Stage:
• This stage deals with the connectivity limitations of the quantum device.
• It introduces Swap gates or similar operations to move quantum states between qubits and ensure the circuit can be implemented on the device.

4. Translation Stage:
• Transforms all operations in the circuit into gates supported by the target device.
• This ensures the circuit is fully compatible with the quantum hardware’s gate set.

5. Optimization Stage:
• Performs circuit optimizations, especially after stages like routing, where extra operations (e.g., Swap gates) may have been introduced.
• This stage helps reduce the circuit's complexity and execution cost.

6. Scheduling Stage (Optional):
• This final stage handles the timing of operations in the circuit, accounting for when each operation should be executed based on the circuit’s structure and the device’s timing requirements.

Key Point:

• The Pass Manager is designed to handle the complexity of orchestrating these stages, ensuring that each stage performs its specific task to optimize the circuit incrementally.

Init Stage:

• Two Phases:
1. Decompose Larger Gates: This phase focuses on breaking down gates involving 3 or more qubits into 1-qubit and 2-qubit gates. This decomposition is crucial because many quantum devices can only implement 1-qubit and 2-qubit gates natively.
2. Logical Optimizations: This phase performs logical-level optimizations on the circuit to reduce unnecessary operations and make the overall execution more efficient.

• End of the Init Stage:
• Once these two phases are completed, the circuit is ready for the next stage, which is the Layout Stage. At this point, the circuit is modeled as a graph, allowing for easier manipulation in subsequent stages.

• Diagram: The diagram included in the image visually represents the decomposition and optimization processes in the init stage, showing how a complex circuit is broken down into more manageable operations.

VF2Layout

• The VF2Layout pass is designed to find an optimal layout for a quantum circuit by treating the problem as a subgraph isomorphism challenge. It utilizes the VF2++ algorithm to identify a "perfect layout" where the circuit's qubits are directly mapped to the physical qubits of the quantum device without needing additional SWAP gates.

• Perfect Layout Identification: If a perfect mapping is found, the layout is set in the property set, eliminating the need for further routing.

• Error Rate Consideration: VF2Layout can incorporate error rates from backend properties to score potential layouts, enhancing the quality of the mapping based on operational reliability.

• Stopping Conditions: The pass can terminate under specific conditions, such as finding a solution or determining that no suitable layout exists[2][3][5].

Sabre

• The Sabre layout pass is more dynamic and iterative compared to VF2Layout. It uses a heuristic approach to optimize qubit allocation by inserting SWAP gates as needed based on the circuit's structure and connectivity constraints.

• Iterative Routing: Sabre starts with an initial layout of virtual qubits mapped to physical qubits and iteratively processes through the circuit's directed acyclic graph (DAG), inserting SWAP gates where necessary to maintain connectivity for 2-qubit gates.

• Heuristic Optimization: It scores potential SWAP candidates based on various heuristics, aiming to minimize both the number of SWAPs and the overall depth of the circuit. This allows it to adaptively respond to the specific requirements of the circuit being executed.

• Multiple Trials: Sabre can run multiple trials with different random seeds, selecting the best outcome based on minimizing SWAPs inserted during routing. This feature enhances its robustness in practical applications[6][8].

Comparison

1. Purpose: VF2Layout creates a graph from 2-qubit interactions in the circuit and attempts to find an isomorphic subgraph of the target quantum device's connectivity graph.

2. Goal: If a subgraph is found, it indicates a layout that doesn't require swap operations, which is desirable for efficiency.

3. Optimization: If multiple layouts are found, the pass selects the one with the lowest predicted error rate.

4. Implementation: It uses the rustworkx library's VF2 algorithm implementation to efficiently search for an isomorphism.

5. Visual representation: The image shows two graphs - an "Interaction Graph" representing qubit interactions in the circuit, and a "Connectivity Graph" representing the physical connections between qubits on the target device.

6. Documentation: A link to the Qiskit documentation for VF2Layout is provided for further information.

7. Limitations: The caption at the bottom notes that "this pass is not guaranteed to work," indicating that it may not always find an optimal or even viable layout.

1. Purpose: SabreLayout pass is employed if VF2Layout doesn't find a layout.

2. Origin: It's based on the SABRE algorithm, originally detailed in a paper (link provided in the image).
https://arxiv.org/pdf/1809.02573

3. Process:
• Runs a routing algorithm to insert swap gates
• Starts with an initial random guess
• Instead of inserting swaps, it swaps qubits in the layout
• Fully "routes" the circuit
• Reverses the edge direction in the DAG (Directed Acyclic Graph) and repeats
• This process is performed multiple times

4. Goal: To minimize the number of swaps needed in the quantum circuit.

5. Implementation: Qiskit's implementation has significantly improved upon the original algorithm from the paper.
27:07 Building off the original algorithm is that we we wrote this uh algorithm in Rust and we can take advantage of parallelism in multi-threading and we're able to execute this algorithm uh in parallel so what we do is we run this with uh 20 different random starting points and that's what this looks like here so this visualization is running the same algorithm with 20 different random starting points.

6. Further Information: A link to Qiskit's documentation for SabreLayout is provided for more details.
https://docs.quantum.ibm.com/api/qiskit/qiskit.transpiler.passes.SabreLayout

Routing Stage:

• Purpose:
• This stage takes the quantum circuit with a defined layout and inserts Swap gates where necessary to handle qubit connectivity constraints.

• Default Pass:
• The default pass for this stage is SabreSwap, which efficiently inserts the required Swap gates into the circuit.

• Optimized Workflow:
• If you're running Qiskit with default settings, this pass (SabreSwap) is often skipped for efficiency, as it's included as part of the SabreLayout pass during the Layout Stage.

• Post-Swap Layout Optimization:
• After the swap insertion is complete, the transpiler re-runs the layout using VF2PostLayout to search for an improved layout that may further optimize the circuit.

VF2PostLayout:

• Purpose:
• This pass functions similarly to VF2Layout by creating a graph from the 2-qubit interactions in the circuit. It then tries to find an isomorphic subgraph of the device's connectivity graph to optimize the layout after the routing stage has been completed.

• Difference from VF2Layout:
• The key difference with VF2PostLayout is that after routing, it is guaranteed that there is at least one isomorphic subgraph, so this pass focuses on finding additional layouts.
• It then selects the layout with the lowest predicted error rate for the circuit’s execution.

Graphs:

• Interaction Graph: Represents the interactions between qubits in the circuit.

• Connectivity Graph: Represents the physical qubit connections on the quantum device. VF2PostLayout attempts to map the interaction graph onto this connectivity graph.

Importance:

• Post-Optimization: This pass allows for additional layout optimization after the swap gates have been inserted, providing a chance to further minimize error rates and improve the overall efficiency of the quantum circuit.

Translation Stage:

• Purpose:
• This stage takes the routed circuit (which now satisfies the connectivity constraints of the quantum device) and ensures that all the operations in the circuit are supported by the target hardware.

• Process:
• It runs the same passes as those used in the first phase of the Init Stage, but now it processes all operations, not just those involving three or more qubits. This means all circuit operations, regardless of their complexity, are checked and converted into operations that can be executed on the target hardware.

• Key Role:
• Ensures that the final circuit is fully compatible with the device by converting all unsupported gates into those supported by the quantum hardware’s gate set.

Basis Translator:

• Function:
• The Basis Translator uses an equivalence library that builds a graph of equivalent circuits for each gate in the quantum circuit. This helps convert unsupported gates into equivalent gate sequences that the target hardware can execute.

• Algorithm:
• Dijkstra's Algorithm is used to find the shortest path from a given gate to an equivalent set of gates supported by the target device. This ensures that the gate transformation is efficient and minimizes the number of operations.

• Recursive Substitution:
• The gates in the circuit are recursively substituted along the path found by Dijkstra’s algorithm to construct an equivalent circuit that conforms to the target’s gate set.

• DAG Replacement:
• Once an equivalent circuit is found, each gate is replaced in the DAG (Directed Acyclic Graph) representation of the circuit by the equivalent circuit. This ensures that the final circuit can be executed on the specific quantum hardware.

• Identify Source Basis: The translator first determines the set of gates present in the input circuit.

• Dijkstra Search: It performs a search over the equivalence library using Dijkstra's algorithm to find paths from the source gates to the target basis gates. This search generates new gates based on the rules defined in the provided equivalence library.

• Compose Replacement Rules: Once paths are found, these are composed into a set of gate replacement rules.

• Apply Substitutions: The replacement rules are then applied to each operation node in the circuit that is not already part of the target basis, effectively transforming the circuit into one that can be executed on the specified hardware[1][6].

Key Features

• Equivalence Library: The Basis Translator relies on an EquivalenceLibrary, which contains mappings of various gates to their equivalent representations in different bases. This library can be customized or extended, allowing users to define new equivalences as needed[2][6].

• Error Handling: If there are gates in the input circuit that cannot be translated into the target basis (for example, if they are not included in the equivalence library), a TranspilerError is raised. This typically indicates that either the target basis is not universal or additional equivalence rules are required[6][7].

• Integration with Transpiler Pipeline: The Basis Translator is part of a larger transpilation pipeline that includes stages such as layout mapping, routing, and optimization. It is often invoked multiple times during this process to ensure that all components of the circuit are compatible with the target hardware[1][5].

Usage Example

Optimization Stage:

• Purpose:
• This stage takes the mapped quantum circuit and performs various optimizations to reduce unnecessary operations and improve efficiency.

• Process:
• The optimization stage runs in a loop, repeatedly applying optimization passes to the circuit.
• This process continues until a minimum point is reached in terms of the circuit’s depth and size.

• Optimization Goal:
• The goal is to reduce both the number of gates and the depth (the longest path of operations) in the circuit, minimizing the overall complexity and the chance of errors.

Diagram:

• The diagram at the bottom represents the optimization process, showing how various passes are applied (like UnitarySynthesis, Optimize1qGateDecomposition, and CancelRedundantOperations) to refine the circuit. This loop continues until further optimizations no longer reduce the circuit's size or depth.

Scheduling Stage:

• Purpose:
• This stage takes the mapped and optimized circuit and analyzes the runtime of all operations, identifying idle periods for each qubit.

• Inserting Operations:
• Once the idle periods are identified, the scheduling stage inserts explicit operations (such as delays) to account for all the time in the circuit, ensuring that the timing is managed correctly.

Scheduling Approaches:

• ALAP (As Late As Possible):
• The left diagram shows the ALAPScheduleAnalysis, which schedules operations to be executed as late as possible without affecting the overall circuit performance. This method minimizes idle time at the beginning of the circuit.

• ASAP (As Soon As Possible):
• The right diagram shows the ASAPScheduleAnalysis, which schedules operations as soon as possible, leaving idle time towards the end of the circuit. This method reduces overall execution time by prioritizing early execution of operations.

Overview of the Scheduling Stage

Key Components of Scheduling

1. Analysis and Constraint Mapping: The scheduling process begins with an analysis phase where scheduling algorithms, such as ALAP (As Late As Possible) or ASAP (As Soon As Possible), are applied. These algorithms determine the earliest or latest possible start times for each gate operation based on the circuit's structure and timing constraints of the backend.

2. Padding Pass: After establishing an initial schedule, additional passes may be run to account for timing constraints specific to the target backend. This often involves a padding pass, such as PadDelay or PadDynamicalDecoupling, which inserts delay instructions into the circuit to ensure that qubits have sufficient time to return to their ground state before executing subsequent operations.

3. Idle Time Management: The scheduling stage explicitly manages idle times, which are periods when qubits are not actively involved in computations. By inserting delays, the scheduler helps mitigate potential decoherence effects that can arise during these idle periods.

Example Implementation

Scheduling Methods

• As Soon As Possible (ASAP): Schedules pulses at the earliest possible time on available qubits.

• As Late As Possible (ALAP): Schedules pulses as late as possible to keep qubits in their ground state when they are not being used.

Conclusion