Scheduler

The scheduler is a tool within TopQAD that determines when quantum operations should be executed and which resources should be consumed. It takes a circuit composed of Pauli product rotations, generates a logical map for the place where these quantum operations will be performed, then creates a schedule for discrete time steps. At each time step, a set of quantum operations is expected to be performed by generating entanglement using lattice surgery to connect the qubits requested by the operations considering the physical constraints of the layout and the logical constraints of the circuit. The scheduler outputs data about the generated logical map, the operations performed in each logical time step, and the logical qubits used to generate the entanglements.

Theory

Logical qubit map and lattice surgery

The scheduler considers a 2D topological quantum error correcting code, such as surface codes. In these codes, fault-tolerant quantum computation is performed in a central zone consisting of a lattice containing square tiles that resemble a chess board. Each tile in the lattice may be occupied by a patch associated with logical qubits. Due to the square tiling, patches are polyominoes, but usually only square or rectangular shapes are considered. Each patch is usually associated with one or two qubits, and each of its edges is associated with a Pauli X or Z operator.

Quantum operations in a circuit are represented as Pauli product rotations $P_{\theta} := exp(i \theta P)$, where $P$ is a Pauli operator and $\theta$ is a rotation angle. Circuits are required to have operations with the rotation angle $\theta = \pi/8$ (PI8 rotations) and, optionally, the rotation angle $\theta = \pi/4$ (PI4 rotations). Qubit measurements are also supported.

These quantum operations are performed using lattice surgery, which facilitates long-range entanglement of logical qubits via auxiliary patches, called ancilla patches. Ancilla patches use tiles in the lattice dedicated for these entanglement operations. The set of these dedicated tiles for lattice surgery form the quantum bus. Ancilla patches can be created in the quantum bus in parallel to perform multiple operations simultaneously as long as they do not share a tile and are not connected to the same qubit.

The scheduling of the three operation types in the circuit considered are as follows:

• Qubit measurements require the generation of an ancilla patch using the quantum bus that connects all qubits requested by its Pauli operator $P$, that is all qubits associated with X, Y or Z operators;
• PI8 rotations correspond to a $P \otimes Z$ operation where $Z$ is a Pauli operator involving a qubit in a special state called magic state;
• PI4 rotations correspond to a $P \otimes Y$ operation where $Y$ is a Pauli operator involving a qubit in a special state called zero state.

The scheduler module generates by default a central zone as shown below. Each square (or rectangle) is associated with a patch and colors represent different qubit types, as explained next. The line edges are associated with Pauli X operators and the dashed edges are associated with Pauli Z operations.

The central zone comprises patches of the following types:

• bus qubits (green) are one-tile patches that occupy each tile in the quantum bus;
• data qubits (purple) are patches associated with the qubits requested by the Pauli operators of the quantum operations in the circuit to be scheduled. By default, data qubits are associated with two-qubit two-tile patches. Although data qubits can be one-tile patches, two-tile patches facilitate the scheduling of quantum operations that request Pauli Y operators, since Y operators can only be performed by entangling the X and Z operators of a qubit simultaneously along one of the edges in the patch associated with this qubit. ;
• magic state storage qubits (red) are one-tile patches that store a qubit in the magic state to be consumed when performing PI8 rotations. Magic states are prepared using magic state distillation, which is performed in an external zone to the central zone, therefore the magic state storage qubits are located at the boundary of the central zone;
• ancillary qubits (pink) are patches associated with a qubit that can be instantly initialized in the zero state to be consumed when performing PI4 rotations. Ancillary qubits are two-tile patches since only Y operators are performed using it.

An example of two parallel operations scheduled for the same time step using lattice surgery is shown below. The gray ancilla patch represents a PI4 rotation with a Pauli operator $P = X \otimes I \otimes I \otimes Z$--note that its ancilla patch is connect to both X and Z operators in the ancillary qubit, representing a Y operator-- and the black ancilla patch represents a PI8 rotation with a Pauli operator $P = I \otimes Y \otimes Y \otimes I$.

Solving the scheduling problem

The scheduling problem is solved using a decomposition approach. First, the logical relations between operations in the circuit is mapped into a dependency graph, using a trivial commutation rule, and the logical qubit map is mapped into an adjacency graph (see more in [1]). The decomposition approach uses an earliest-available-first policy, where operations are tentatively scheduled as they become available. Given a dependency and adjacency graph, the EAF algorithm implemented is:

1. While dependency graph is not empty do:
2.     Advance one time step;
3.     Get root nodes of the dependency graph (*candidates* in this time step);
4.     Schedule all candidates that an ancilla patch could be generated in the adjacency graph observing the physical constraints;
5.     Remove scheduled operations from the dependency graph;
6. Return operations schedule and ancilla patches generated.

The ancilla patches in Step 4 are generated in a random order for the candidates by solving a terminal Steiner tree problem usng a modified version of the classical Melhorn's algorithm (see more in [1]).

Parameters

Input

Output

Scheduler report:

Relevant Papers

[1] A. Silva, X. Zhang, Z. Webb, M. Kramer, C.-W. Yang, X. Liu, J. Lemieux, K.-W. Chen, A. Scherer, and P. Ronagh, Multi-qubit Lattice Surgery Scheduling, in 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 1:1–1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024), https://doi.org/10.4230/LIPIcs.TQC.2024.1