A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery

Abstract

Given a quantum gate circuit, how does one execute it in a fault-tolerant architecture with as little overhead as possible? In this paper, we discuss strategies for surface-code quantum computing on small, intermediate and large scales. They are strategies for space-time trade-offs, going from slow computations using few qubits to fast computations using many qubits. Our schemes are based on surface-code patches, which not only feature a low space cost compared to other surface-code schemes, but are also conceptually simple, simple enough that they can be described as a tile-based game with a small set of rules. Therefore, no knowledge of quantum error correction is necessary to understand the schemes in this paper, but only the concepts of qubits and measurements. As an example, assuming a physical error rate of $10^{-4}$ and a code cycle time of 1 $\mu$s, a classically intractable 100-qubit quantum computation with a $T$ count of $10^8$ and a $T$ depth of $10^6$ can be executed in 4 hours using 55,000 qubits, in 22 minutes using 120,000 qubits, or in 1 second using 330,000,000 qubits.

Main text: 29 pages, 36 figures; Appendix: 6 pages, 10 figures; v2: simplified rules of the game

References in corpus (50)

• Fault-tolerant quantum computation by anyons
• Surface codes: Towards practical large-scale quantum computation
• Concentrating Partial Entanglement by Local Operations
• Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Error Correction for Quantum Memories
• Reliable Quantum Computers
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Elucidating Reaction Mechanisms on Quantum Computers
• Topological Quantum Distillation
• Roads towards fault-tolerant universal quantum computation
• Surface code quantum computing by lattice surgery
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Topological Order with a Twist: Ising Anyons from an Abelian Model
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Magic state distillation with low overhead
• Halving the cost of quantum addition
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• On-demand quantum state transfer and entanglement between remote microwave cavity memories
• Quantum circuits of T-depth one
• Novel constructions for the fault-tolerant Toffoli gate
• Deterministic remote entanglement of superconducting circuits through microwave two-photon transitions
• Quantum computation with realistic magic state factories
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Multilevel distillation of magic states for quantum computing
• Efficient Discrete Approximations of Quantum Gates
• Poking holes and cutting corners to achieve Clifford gates with the surface code
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Surface code implementation of block code state distillation
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• A magic state's fidelity can be superior to the operations that created it
• Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• Quantum Computing with Majorana Fermion Codes
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• The boundaries and twist defects of the color code and their applications to topological quantum computation
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures
• Braiding by Majorana Tracking and Long-Range CNOT Gates with Color Codes
• Reducing the quantum computing overhead with complex gate distillation
• Fault-tolerant interface between quantum memories and quantum processors
• Chip-to-chip entanglement of transmon qubits using engineered measurement fields
• An efficient magic state approach to small angle rotations
• Optimization of Lattice Surgery is NP-Hard
• Lattice Surgery Translation for Quantum Computation
• Low overhead Clifford gates from joint measurements in surface, color, and hyperbolic codes
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact

Cited by in corpus (201)

• Quantum computational chemistry
• Suppressing quantum errors by scaling a surface code logical qubit
• The Future of Quantum Computing with Superconducting Qubits
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Building a fault-tolerant quantum computer using concatenated cat codes
• The XZZX Surface Code
• Virtual Distillation for Quantum Error Mitigation
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Magic State Distillation: Not as Costly as You Think
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Quantum advantage with noisy shallow circuits in 3D
• Quantum Error Correction with the Gottesman-Kitaev-Preskill Code
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Entangling logical qubits with lattice surgery
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Holographic tensor network models and quantum error correction: A topical review
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Phase Gadget Synthesis for Shallow Circuits
• Fault tolerant resource estimation of quantum random-access memories
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• The ZX calculus is a language for surface code lattice surgery
• Fault-tolerant magic state preparation with flag qubits
• Nonadiabatic geometric quantum computation with cat qubits via invariant-based reverse engineering
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes
• Three-dimensional surface codes: Transversal gates and fault-tolerant architectures
• Parallel window decoding enables scalable fault tolerant quantum computation
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• High threshold codes for neutral atom qubits with biased erasure errors
• Surface code compilation via edge-disjoint paths
• Applying quantum algorithms to constraint satisfaction problems
• Anyon condensation and the color code
• Real-Time Decoding for Fault-Tolerant Quantum Computing: Progress, Challenges and Outlook
• Logical blocks for fault-tolerant topological quantum computation
• Fault-Tolerant Weighted Union-Find Decoding on the Toric Code
• Optimized compiler for Distributed Quantum Computing
• Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Grid-based methods for chemistry simulations on a quantum computer
• Universal fault-tolerant measurement-based quantum computation
• A scalable and fast artificial neural network syndrome decoder for surface codes
• Transitions in Entanglement Complexity in Random Circuits
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• The Impact of Hardware Specifications on Reaching Quantum Advantage in the Fault Tolerant Regime
• Partially Fault-tolerant Quantum Computing Architecture with Error-corrected Clifford Gates and Space-time Efficient Analog Rotations
• Artificial Intelligence for Quantum Computing
• Fault-tolerant multiqubit geometric entangling gates using photonic cat-state qubits
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Tailored XZZX codes for biased noise
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Constructing quantum circuits with global gates
• Quantum Computation for Periodic Solids in Second Quantization
• A real-time, scalable, fast and highly resource efficient decoder for a quantum computer
• Morphing quantum codes
• Shorter quantum circuits via single-qubit gate approximation
• A circuit-level protocol and analysis for twist-based lattice surgery
• Fault-Tolerant One-Bit Addition with the Smallest Interesting Colour Code
• Techniques for combining fast local decoders with global decoders under circuit-level noise
• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
• Toward a 2D Local Implementation of Quantum LDPC Codes
• Pseudo-2D superconducting quantum computing circuit for the surface code: the proposal and preliminary tests
• Floquetifying the Colour Code
• Data centers with quantum random access memory and quantum networks
• A High Performance Compiler for Very Large Scale Surface Code Computations
• Inplace Access to the Surface Code Y Basis
• Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device
• A Spin-Optical Quantum Computing Architecture
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• A four-dimensional toric code with non-Clifford transversal gates
• Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus
• Logical Clifford Synthesis for Stabilizer Codes
• Quantum simulation of battery materials using ionic pseudopotentials
• Pipelined correlated minimum weight perfect matching of the surface code
• Towards early fault tolerance on a 2$\times$N array of qubits equipped with shuttling
• Handbook for Quantifying Robustness of Magic
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Fault-tolerant Post-Selection for Low Overhead Magic State Preparation
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Constant-Overhead Fault-Tolerant Bell-Pair Distillation using High-Rate Codes
• Compilation of algorithm-specific graph states for quantum circuits
• Error-corrected Hadamard gate simulated at the circuit level
• Convolutional neural network based decoders for surface codes
• Hierarchical memories: Simulating quantum LDPC codes with local gates
• Quantum error correction with fractal topological codes
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Color code decoder with improved scaling for correcting circuit-level noise
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Transversal Diagonal Logical Operators for Stabiliser Codes
• Error correction of transversal CNOT gates for scalable surface code computation
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Clifford recompilation for faster classical simulation of quantum circuits
• Realistic Cost to Execute Practical Quantum Circuits using Direct Clifford+T Lattice Surgery Compilation
• Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
• Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Tangling schedules eases hardware connectivity requirements for quantum error correction
• Actis: A Strictly Local Union-Find Decoder
• Compilation of a simple chemistry application to quantum error correction primitives
• Fault-tolerant logical measurements via homological measurement
• Designing fault-tolerant circuits using detector error models
• A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing
• Low-overhead quantum computing with the color code
• TISCC: A Surface Code Compiler and Resource Estimator for Trapped-Ion Processors
• Robust sparse IQP sampling in constant depth
• Pauli-based model of quantum computation with higher-dimensional systems
• Linear and non-linear relational analyses for Quantum Program Optimization
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Accelerating Quantum Algorithms with Precomputation
• Local Clustering Decoder as a fast and adaptive hardware decoder for the surface code
• Low-overhead magic state distillation with color codes
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Surface Code Design for Asymmetric Error Channels
• Quantum computer error structure probed by quantum error correction syndrome measurements
• Bulk-to-boundary anyon fusion from microscopic models
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Preparation of high fidelity entangled cat states with composite pulses
• Time-Efficient Logical Operations on Quantum Low-Density Parity Check Codes
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Symmetric Clifford twirling for cost-optimal quantum error mitigation in early FTQC regime
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Spatially parallel decoding for multi-qubit lattice surgery
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Spatially-Coupled QLDPC Codes
• Low-overhead fault-tolerant quantum computation by gauging logical operators
• Classically Replaceable Operations
• Leveraging Zero-Level Distillation to Generate High-Fidelity Magic States
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• Locality-aware Pauli-based computation for local magic state preparation
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• Fault-tolerant quantum computing with the parity code and noise-biased qubits
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Certifying nonstabilizerness in quantum processors
• Characterization of errors in a CNOT between surface code patches
• Faster computation of nonstabilizerness
• Resource Estimation of Quantum Multiplication Algorithms
• Synchronization for Fault-Tolerant Quantum Computers
• Lower T-count with faster algorithms
• Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation
• Single-shot and measurement-based quantum error correction via fault complexes
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• A Substrate Scheduler for Compiling Arbitrary Fault-tolerant Graph States
• Role of quantum state texture in probing resource theories and quantum phase transition
• Perturbative gadgets for gate-based quantum computing: Non-recursive constructions without subspace restrictions
• Distributed quantum error correction based on hyperbolic Floquet codes
• Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
• Lattice surgery-based logical state teleportation via noisy links
• Almost fault-tolerant quantum machine learning with drastic overhead reduction
• End-to-end switchless architecture for fault-tolerant photonic quantum computing
• Feasibility of Logical Bell State Generation in Memory Assisted Quantum Networks
• Magic State Injection on IBM Quantum Processors Above the Distillation Threshold
• Low-density parity-check representation of fault-tolerant quantum circuits
• Superconducting qubits in the millions: the potential and limitations of modularity
• Fault-tolerant quantum simulation of generalized Hubbard models
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Achieving computational gains with quantum error-correction primitives: Generation of long-range entanglement enhanced by error detection
• Averting multi-qubit burst errors in surface code magic state factories
• Single-shot quantum error correction with the three-dimensional subsystem toric code
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• Parallel Logical Measurements via Quantum Code Surgery
• Optimal Scheduling of Graph States via Path Decompositions
• Scalable Spider Nests (...Or How to Graphically Grok Transversal Non-Clifford Gates)
• Unified Architecture for Quantum Lookup Tables
• Optimal number of stabilizer measurement rounds in an idling surface code patch
• Type-Based Verification of Connectivity Constraints in Lattice Surgery
• Geometrical Approach to Logical Qubit Fidelities of Neutral Atom CSS Codes
• Measurement Schemes for Quantum Linear Equation Solvers
• Topological stabilizer models on continuous variables
• Lattice Surgery Compilation Beyond the Surface Code
• Noise-Agnostic Unbiased Quantum Error Mitigation for Logical Qubits
• Catalytic $z$-rotations in constant $T$-depth
• Unfolded distillation: very low-cost magic state preparation for biased-noise qubits
• Towards self-correcting quantum codes for neutral atom arrays
• Generating Compilers for Qubit Mapping and Routing
• Building globally controlled quantum processors with ZZ interactions
• Entanglement boosting: Low-volume logical Bell pair preparation for distributed fault-tolerant quantum computation
• Error-mitigated initialization of surface codes with non-Pauli stabilizers
• Color code with a logical control-$S$ gate using transversal $T$ rotations
• Managing Classical Processing Requirements for Quantum Error Correction
• Snowflake: A Distributed Streaming Decoder
• RESCQ: Realtime Scheduling for Continuous Angle Quantum Error Correction Architectures
• qSIEVE: Efficient qLDPC Memory via Systolic Movement in Atom Arrays
• Lattice Surgery for Dummies
• Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms
• Accelerating Fault-Tolerant Quantum Computation with Good qLDPC Codes
• Orthogonal frequency-division multiplexing for simultaneous gate operations on multiple qubits via a shared control line
• Dense packing of the surface code: code deformation procedures and hook-error-avoiding gate scheduling
• Simple Diagonal State Designs with Reconfigurable Real-Time Circuits
• Pinball: A Cryogenic Predecoder for Surface Code Decoding Under Circuit-Level Noise
• Planar fault-tolerant circuits for non-Clifford gates on the 2D color code
• Hierarchical Quantum Error Correction with Hypergraph Product Code and Rotated Surface Code
• Network Requirements for Distributed Quantum Computation
• CQM: Cyclic Qubit Mappings
• Universal fault tolerant quantum computation in 2D without getting tied in knots
• Preparing Code States via Seed-Entangler-Enriched Sequential Quantum Circuits: Application to Tetra-Digit Topological Error-Correcting Codes
• Benchmarking fault-tolerant quantum computing hardware via QLOPS