Substrate Scheduler

About The Project

Substrate Scheduler is a tool with core functionalities to efficiently create the input graph state fault-tolerantly using the rules given by Litinski’s "A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery" (GOSC) paper with the goal of minimizing the space-time volume cost. The space-time volume cost is defined to be the space multiplied by the time where space is defined by the area of patches in units of square tiles and time in units of time step as defined in the GoSC paper or one round of syndrome measurement.

Substrate Scheduler is a product of the AQUA, QTS and Zapata for the Bench-Q project.

Features

Substrate Scheduler creates graph states using stabilizer formalism. In the current version, it provides 3 optimzers to reduce the time steps required to create a graph state via stabilizer formalism (note that the time step here is the total number of steps required to create the graph state considering the parallel measurement of the stabilizers) :

• pre_mapping_optimizer

  From the definition of graph state, we know that we can reduce the number of stabilizer generator to be measured by initializing the qubits in a way that they are already stabilized by some stabilizer generators. For example, initialize node a in X-basis (|+> state) while initializing neighbor nodes of a in Z basis (|0> state).
  By converting the problem of finding the optimal reduction to maximum independent set problem, pre_mapping_optimizer reduces the maximum number of stabilizer generators before mapping.

• node_to_patch_mapper

  tbd

• stabilizer measurement scheduler

  Suppose we have already decided where each node in the graph is mapped to which patch, in order to measure a stabilizer generator in this configuration, we need an ancilla patch that covers all the nodes defined in the stabilizer generator. This means that any stabilizer generator which includes a node between the left-most and the right-most nodes of the stabilizer we are trying to measure cannot be measured at the same time.

  By knowing the start and end positions of each stabilizer generator, stabilizer_measurement_scheduler will optimally schedule the stabilizer generators to be measured and reduce the time cost by parallelly measuring as many stabilizers as possible.

| 006 | 005 | 003 | 000 | 002 | 008 | 001 | 009 | 004 | 007 |
|  X  |  Z  |  Z  |  X  |  X  |  X  |  Z  |  Z  |  X  |  Z  |
|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
     ancilla start |---------------------| ancilla end
           One example of the layout after mapping

Installation

To install Substrate Scheduler, you just need to run git clone https://github.com/sfc-aqua/gosc-graph-state-generation.git Substrate Scheduleris written is Python, except for a Python3 compiler, you will also need the networkx, matplotlib and numpy packages.

Usage

For an example of how to use methods from Substrate Scheduler, please run usage_example.py with the following command.

python usage_example.py

The program optimized some graph examples with Substrate Scheduler and returns the following results:

pre-mapping optimization took - 0.00037109400000001624s
node to patch mapping took    - 3.106400000008058e-05s
measurement scheduler took    - 2.7704999999933477e-05s
reduce from 10 to 5
| 006 | 005 | 003 | 000 | 002 | 008 | 001 | 009 | 004 | 007 |
|  X  |  Z  |  Z  |  X  |  X  |  X  |  Z  |  Z  |  X  |  Z  |
|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
                   |---------------------|
                   |---------------------------|
             |---------------------------------------|
 |---------------------------------------------------|
 |---------------------------------------------------------|

It contains:

• Time taken for each optimization process (here is the run time);
• Time step reduced by the optimization;
• An ASCII visualization of the layout (results of the mapping), as well as the starting and ending positions of the stabilizer generator for each step.

Development and Contribution

We use Google-style docstring format. If you'd like to specify types please use PEP 484 type hints instead adding them to docstrings.

There are codestyle-related Github Actions running for PRs.

• If you'd like to report a bug/issue please create a new issue in this repository.
• If you'd like to contribute, please create a pull request to main.

Running tests

Unit tests for this project can be run using make coverage command from the main directory. Alternatively you can also run pytest ..

Style

We are using automatic tools for style and type checking. In order to make sure the code is compliant with them please run: make style from the main directory (this requires dev dependencies).

In-progress work:

• The performance of node_to_patch_mapper needs further testing and improvement.
• Tests are still being polished.

See the open issues for a full list of proposed features (and known issues).

License

Distributed under the MIT License. See LICENSE for more information.