A Substrate Scheduler for Compiling Arbitrary Fault-tolerant Graph States

Abstract

Graph states are useful computational resources in quantum computing, particularly in measurement-based quantum computing models. However, compiling arbitrary graph states into executable form for fault-tolerant surface code execution and accurately estimating the compilation cost and the run-time resource cost remains an open problem. We introduce the Substrate Scheduler, a compiler module designed for fault-tolerant graph state compilation. The Substrate Scheduler aims to minimize the space-time volume cost of generating graph states. We show that Substrate Scheduler can efficiently compile graph states with thousands of vertices for "A Game of Surface Codes"-style patch-based surface code systems. Our results show that our module generates graph states with the lowest execution time complexity to date, achieving graph state generation time complexity that is at or below linear in the number of vertices and demonstrating specific types of graphs to have constant generation time complexity. Moreover, it provides a solid foundation for developing compilers that can handle a larger number of vertices, up to the millions or billions needed to accommodate a wide range of post-classical quantum computing applications.

arXiv comment11 pages, 11 figures

References in corpus (23)

• Quantum Computing in the NISQ era and beyond
• Fault-tolerant quantum computation by anyons
• Quantum Computing
• Surface codes: Towards practical large-scale quantum computation
• Topological quantum memory
• Quantum Error Correction for Quantum Memories
• Multi-party entanglement in graph states
• Fault-tolerant quantum computation with high threshold in two dimensions
• Quantum Error Correction for Beginners
• Stabilizer Codes and Quantum Error Correction
• Validating quantum computers using randomized model circuits
• Surface code quantum computing by lattice surgery
• Cluster-state quantum computation
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Topological Order with a Twist: Ising Anyons from an Abelian Model
• Overhead and noise threshold of fault-tolerant quantum error correction
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Graphical description of the action of local Clifford transformations on graph states
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
• Optimal preparation of graph states
• Mapping graph state orbits under local complementation
• Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms

Cited by in corpus (3)

• A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing
• Superconducting qubits in the millions: the potential and limitations of modularity
• Hybrid Reward-Driven Reinforcement Learning for Efficient Quantum Circuit Synthesis