Scheduler for quantum gates and instructions

Author: Boxi Li ([email protected])

The finite coherence time of physical qubits is one of the major factors that limits the performance of quantum computation. In principle, the execution time of the circuit has to be much shorter than the coherence time. One way to reduce this execution time is to run several gates in the circuit parallelly. This can spare a lot of time if e.g. the same single-qubit gate is applied to all qubits, as in the Grover algorithm.

A scheduler for a quantum computer, similar to its classical counterpart, schedules a quantum circuit to minimize the execution time. It determines the order in which the gates are executed. As a simple rule, the scheduler allows gates to be executed in parallel if they do not address the same qubits. Further hardware constraints can be included, but here we only focus on this simple criterion by considering gates that do not address the same qubits. The non-trivial part of a scheduler is that it has to consider the possible permutations of commuting quantum gates. Hence, exploring various possibilities for permutation while following physical constraints of the hardware is the main challenging task for the scheduler.

We first show how we can schedule gate execution in quantum circuits using the built-in tools in qutip_qip and then the scheduling of compiled control pulses. In the end, we also show a simple example where the permutation of commuting gates matters in the scheduling and how to handle such situations.

In [1]:
# imports
import qutip

from qutip_qip.circuit import QubitCircuit
from qutip_qip.compiler import Scheduler
from qutip_qip.compiler import Instruction
from qutip_qip.device import LinearSpinChain

Gate schedule

Let's first define a quantum circuit

In [2]:
circuit = QubitCircuit(3)
circuit.add_gate("X", 0)
circuit.add_gate("ISWAP", targets=[1,2])
circuit.add_gate("X", 2)
circuit.add_gate("Y", 0)
circuit.add_gate("X", 0)
circuit
Out[2]:

This is a rather boring circuit, but it is useful as a demonstration for the scheduler. We now define a scheduler and schedule the execution of gates in the circuit

In [3]:
scheduler = Scheduler("ASAP")  # schedule as soon as possible
scheduled_time = scheduler.schedule(circuit)
scheduled_time
Out[3]:
[0, 0, 1, 1, 2]

This result shows the scheduled starting time for each gate. In the first cycle we execute an iSWAP on qubit 0 and 1 and an X gate on qubit 0; In the second cycle we execute one X gate on qubit 2 and one Y gate on qubit 0; In the last cycle, we execute a single X gate on qubit 0. As printed bellow:

In [4]:
cycle_list = [[] for i in range(max(scheduled_time) + 1)]

for i, time in enumerate(scheduled_time):
    gate = circuit.gates[i]
    cycle_list[time].append(gate.name + str(gate.targets))
for cycle in cycle_list:
    print(cycle)
['X[0]', 'ISWAP[1, 2]']
['X[2]', 'Y[0]']
['X[0]']

We can also schedule the gate follows the rule "as late as possible"

In [5]:
scheduler = Scheduler("ALAP")  # schedule as late as possible
scheduled_time = scheduler.schedule(circuit)
cycle_list = [[] for i in range(max(scheduled_time) + 1)]
for i, time in enumerate(scheduled_time):
    gate = circuit.gates[i]
    cycle_list[time].append(gate.name + str(gate.targets))
for cycle in cycle_list:
    print(cycle)
['X[0]']
['ISWAP[1, 2]', 'Y[0]']
['X[2]', 'X[0]']

The only difference is that the "iSWAP" gate and the X gate on qubit 2 are shifted by one cycle.

Instruction/Pulse schedule

Often different quantum gates will have different execution time. To consider this, we define a list of quantum instructions, where X gate has the execution time 1 while the iSWAP gate takes the time 3.5

In [6]:
scheduler = Scheduler("ASAP")
instructions = []

for gate in circuit.gates:
    if gate.name in ("X"):
        duration = 1
    elif gate.name == "ISWAP":
        duration = 3.5
    instruction = Instruction(gate, duration=duration)
    instructions.append(instruction)
scheduler.schedule(instructions)
Out[6]:
[0, 0.0, 3.5, 1, 2]

The scheduled execution time for each gate can no longer be assigned to gate cycles. But we can see this through the noisy circuit simulator of qutip, where the circuit is compiled to control signals: (Notice that the execution time follows the hardware parameter of spin chain and the Y gate is decomposed into a Z-X-Z rotation).

In [7]:
device = LinearSpinChain(3)
device.load_circuit(circuit, "ASAP")  # The circuit are compiled to instructions and scheduled.
device.plot_pulses();

The green and orange pulses represent rotations along the X and Z axis. The green pulse is the iSWAP gate, which is executed simultaneously with a few other single-qubit rotations on qubit 0.

Considering commuting gates

We consider the following circuit:

In [8]:
circuit = QubitCircuit(3)
circuit.add_gate("SNOT", 0)
circuit.add_gate("CNOT", 1, 0)
circuit.add_gate("CNOT", 2, 0)
circuit.add_gate("SNOT", 2)
circuit
Out[8]:

At first sight, it might look like no gates can be run in parallel. However, the two CNOT gates actually commute and if we permute them, we can run one CNOT together with the last Hadamard gate.

In [9]:
scheduler = Scheduler("ALAP")
scheduled_time = scheduler.schedule(circuit)

cycle_list = [[] for i in range(max(scheduled_time) + 1)]
for i, time in enumerate(scheduled_time):
    gate = circuit.gates[i]
    cycle_list[time].append(gate.name + str(gate.targets))
for cycle in cycle_list:
    print(cycle)
['SNOT[0]']
['CNOT[2]']
['CNOT[1]', 'SNOT[2]']

Random shuffle

The scheduling algorithm is heuristic and hence cannot always find the optimal result. Therefore randomness can be added to the scheduling process by the parameters random_shuffle and repeat_num.

In [10]:
from qutip.ipynbtools import version_table
version_table()
Out[10]:
SoftwareVersion
QuTiP4.7.0.dev0+acb6cfe
Numpy1.20.2
SciPy1.6.3
matplotlib3.4.1
Cython0.29.23
Number of CPUs12
BLAS InfoGeneric
IPython7.21.0
Python3.9.4 | packaged by conda-forge | (default, May 10 2021, 22:10:34) [MSC v.1916 64 bit (AMD64)]
OSnt [win32]
Tue Jun 01 18:22:47 2021 W. Europe Daylight Time