A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing
arXiv:2404.18369 · doi:10.1109/ISCA59077.2024.00032
Abstract
Quantum error correction is necessary for large-scale quantum computing. A promising quantum error correcting code is the surface code. For this code, fault-tolerant quantum computing (FTQC) can be performed via lattice surgery, i.e., splitting and merging patches of code. Given the frequent use of certain lattice-surgery subroutines (LaS), it becomes crucial to optimize their design in order to minimize the overall spacetime volume of FTQC. In this study, we define the variables to represent LaS and the constraints on these variables. Leveraging this formulation, we develop a synthesizer for LaS, LaSsynth, that encodes a LaS construction problem into a SAT instance, subsequently querying SAT solvers for a solution. Starting from a baseline design, we can gradually invoke the solver with shrinking spacetime volume to derive more compact designs. Due to our foundational formulation and the use of SAT solvers, LaSsynth can exhaustively explore the design space, yielding optimal designs in volume. For example, it achieves 8% and 18% volume reduction respectively over two states-of-the-art human designs for the 15-to-1 T-factory, a bottleneck in FTQC.
arXiv commentPublished in 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)
References in corpus (24)
- Surface codes: Towards practical large-scale quantum computation
- Topological quantum memory
- Improved Simulation of Stabilizer Circuits
- Suppressing quantum errors by scaling a surface code logical qubit
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Topological fault-tolerance in cluster state quantum computation
- Surface code quantum computing by lattice surgery
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- Stim: a fast stabilizer circuit simulator
- A Race Track Trapped-Ion Quantum Processor
- Magic State Distillation: Not as Costly as You Think
- Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
- Universal quantum computing with twist-free and temporally encoded lattice surgery
- The ZX calculus is a language for surface code lattice surgery
- Optimal preparation of graph states
- Synthesis of Arbitrary Quantum Circuits to Topological Assembly
- Lattice Surgery Translation for Quantum Computation
- A High Performance Compiler for Very Large Scale Surface Code Computations
- Inplace Access to the Surface Code Y Basis
- Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
- A Simplified Stabilizer ZX-calculus
- Compilation of algorithm-specific graph states for quantum circuits
- Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories
- A Substrate Scheduler for Compiling Arbitrary Fault-tolerant Graph States