Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code

Abstract

We describe two implementations of the optimal error correction algorithm known as the maximum likelihood decoder (MLD) for the 2D surface code with a noiseless syndrome extraction. First, we show how to implement MLD exactly in time $O(n^2)$, where $n$ is the number of code qubits. Our implementation uses a reduction from MLD to simulation of matchgate quantum circuits. This reduction however requires a special noise model with independent bit-flip and phase-flip errors. Secondly, we show how to implement MLD approximately for more general noise models using matrix product states (MPS). Our implementation has running time $O(n{\chi }^3)$ where $\chi$ is a parameter that controls the approximation precision. The key step of our algorithm, borrowed from the DMRG method, is a subroutine for contracting a tensor network on the two-dimensional grid. The subroutine uses MPS with a bond dimension $\chi$ to approximate the sequence of tensors arising in the course of contraction. We benchmark the MPS-based decoder against the standard minimum weight matching decoder observing a significant reduction of the logical error probability for $\chi \ge 4$.

18 pages, 12 figures

References in corpus (27)

• Fault-tolerant quantum computation by anyons
• The density-matrix renormalization group in the age of matrix product states
• Surface codes: Towards practical large-scale quantum computation
• Efficient classical simulation of slightly entangled quantum computations
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Topological quantum memory
• Thermodynamic limit of the density matrix renormalization for the spin-1 Heisenberg chain
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory
• Classical simulation of noninteracting-fermion quantum circuits
• Implementing a strand of a scalable fault-tolerant quantum computing fabric
• Variational study of hard-core bosons in a 2-D optical lattice using Projected Entangled Pair States (PEPS)
• Fast Decoders for Topological Quantum Codes
• Strong Resilience of Topological Codes to Depolarization
• The two-dimensional random-bond Ising model, free fermions and the network model
• Error Threshold for Color Codes and Random 3-Body Ising Models
• Topological Subsystem Codes
• Optimal and Efficient Decoding of Concatenated Quantum Block Codes
• High threshold error correction for the surface code
• Surface code with decoherence: An analysis of three superconducting architectures
• Error Correction and Degeneracy in Surface Codes Suffering Loss
• An efficient Markov chain Monte Carlo algorithm for the surface code
• Fermionic Linear Optics and Matchgates
• Simulation of rare events in quantum error correction
• Optimal complexity correction of correlated errors in the surface code

Cited by in corpus (143)

• Suppressing quantum errors by scaling a surface code logical qubit
• Interfacing spin qubits in quantum dots and donors - hot, dense and coherent
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• The XZZX Surface Code
• Degenerate Quantum LDPC Codes With Good Finite Length Performance
• Differentiable Programming Tensor Networks
• Almost-linear time decoding algorithm for topological codes
• Ultrahigh Error Threshold for Surface Codes with Biased Noise
• A Neural Decoder for Topological Codes
• Hyper-optimized tensor network contraction
• Quantum LDPC Codes with Almost Linear Minimum Distance
• Machine-learning-assisted correction of correlated qubit errors in a topological code
• Tailoring surface codes for highly biased noise
• Fault-tolerant thresholds for the surface code in excess of 5% under biased noise
• Sparse Blossom: correcting a million errors per core second with minimum-weight matching
• Matching and maximum likelihood decoding of a multi-round subsystem quantum error correction experiment
• Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes
• The surface code with a twist
• Quantum error correction for the toric code using deep reinforcement learning
• Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel
• Classical Simulation of Quantum Supremacy Circuits
• Low overhead fault-tolerant quantum error correction with the surface-GKP code
• Calibrated decoders for experimental quantum error correction
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Learning to Decode the Surface Code with a Recurrent, Transformer-Based Neural Network
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes
• Neural-Network Decoders for Quantum Error Correction using Surface Codes:A Space Exploration of the Hardware Cost-Performance Trade-Offs
• Advantages of versatile neural-network decoding for topological codes
• Simulating the performance of a distance-3 surface code in a linear ion trap
• Comparing neural network based decoders for the surface code
• Coherence in logical quantum channels
• A repetition code of 15 qubits
• Quantum Error Correction with the Semion Code
• Hamiltonian Learning for Quantum Error Correction
• Real-Time Decoding for Fault-Tolerant Quantum Computing: Progress, Challenges and Outlook
• A fast fault-tolerant decoder for qubit and qudit surface codes
• Analysing correlated noise on the surface code using adaptive decoding algorithms
• Fault-Tolerant Weighted Union-Find Decoding on the Toric Code
• Logical blocks for fault-tolerant topological quantum computation
• Decoding algorithms for surface codes
• A blueprint for fault-tolerant quantum computation with Rydberg atoms
• Transversal Clifford gates on folded surface codes
• Multi-path Summation for Decoding 2D Topological Codes
• Enhanced noise resilience of the surface-GKP code via designed bias
• Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes
• Exploiting Degeneracy in Belief Propagation Decoding of Quantum Codes
• Accurate simulation for finite projected entangled pair states in two dimensions
• Coherent error threshold for surface codes from Majorana delocalization
• Linear-time general decoding algorithm for the surface code
• Density Matrix Renormalization Group with Tensor Processing Units
• Tailored XZZX codes for biased noise
• Reducing Spontaneous Emission in Circuit Quantum Electrodynamics by a Combined Readout/Filter Technique
• Fault-Tolerant Quantum Error Correction for non-Abelian Anyons
• A local pre-decoder to reduce the bandwidth and latency of quantum error correction
• Stability of mixed-state quantum phases via finite Markov length
• Comparing Zeeman qubits to hyperfine qubits in the context of the surface code: ${}^{174}$Yb${}^{+}$ and ${}^{171}$Yb${}^{+}$
• Gauge color codes in two dimensions
• Leakage mitigation for quantum error correction using a mixed qubit scheme
• Deep Q-learning decoder for depolarizing noise on the toric code
• Morphing quantum codes
• A decoder for the triangular color code by matching on a Möbius strip
• Clifford-deformed Surface Codes
• Tensor-network codes
• Practical Topological Cluster State Quantum Computing Requires Loss Below 1%
• Learning correlated noise in a 39-qubit quantum processor
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• General tensor network decoding of 2D Pauli codes
• Learning time-dependent noise to reduce logical errors: Real time error rate estimation in quantum error correction
• A simple decoder for topological codes
• Surface codes, quantum circuits, and entanglement phases
• Coherent errors and readout errors in the surface code
• Correcting non-independent and non-identically distributed errors with surface codes
• Machine Learning for Continuous Quantum Error Correction on Superconducting Qubits
• Fidelity Threshold of the Surface Code Beyond Single-Qubit Error Models
• Classical Simulation of Quantum Error Correction in a Fibonacci Anyon Code
• Conservation laws and quantum error correction: towards a generalised matching decoder
• The XYZ${}^2$ hexagonal stabilizer code
• Robust teleportation of a surface code and cascade of topological quantum phase transitions
• Quantum Error Correction with the GKP Code and Concatenation with Stabilizer Codes
• The role of entropy in topological quantum error correction
• Efficient simulation of quantum error correction under coherent error based on non-unitary free-fermionic formalism
• Tensor networks for quantum computing
• Symmetries for a High Level Neural Decoder on the Toric Code
• Performance enhancement of surface codes via recursive MWPM decoding
• A Silicon Surface Code Architecture Resilient Against Leakage Errors
• Topological quantum error correction in the Kitaev honeycomb model
• Concatenation of the Gottesman-Kitaev-Preskill code with the XZZX surface code
• Tensor Network Decoding Beyond 2D
• Many-hypercube codes: High-rate quantum error-correcting codes for high-performance fault-tolerant quantum computing
• Active error correction for Abelian and non-Abelian anyons
• Achieving fault tolerance on capped color codes with few ancillas
• Quantum error correction with the color-Gottesman-Kitaev-Preskill code
• Hierarchical memories: Simulating quantum LDPC codes with local gates
• Convolutional neural network based decoders for surface codes
• Fault-Tolerant Computing with Single Qudit Encoding
• A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing
• Data-driven decoding of quantum error correcting codes using graph neural networks
• Error-correction and noise-decoherence thresholds for coherent errors in planar-graph surface codes
• Closest lattice point decoding for multimode Gottesman-Kitaev-Preskill codes
• Neural network decoder for near-term surface-code experiments
• Local tensor-network codes
• A high threshold code for modular hardware with asymmetric noise
• Optimization of decoder priors for accurate quantum error correction
• On maximum-likelihood decoding with circuit-level errors
• Decoding the Projective Transverse Field Ising Model
• Quantifying fermionic nonlinearity of quantum circuits
• Error-rate-agnostic decoding of topological stabilizer codes
• Improved Belief Propagation Decoding Algorithms for Surface Codes
• Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
• Discovery of Optimal Quantum Error Correcting Codes via Reinforcement Learning
• Méthodes de calcul avec réseaux de tenseurs en physique (Basic tensor network computations in physics)
• On Belief Propagation Decoding of Quantum Codes with Quaternary Reliability Statistics
• Statistical mechanical mapping and maximum-likelihood thresholds for the surface code under generic single-qubit coherent errors
• Extending C++ for Heterogeneous Quantum-Classical Computing
• The domain wall color code
• Progressive-Proximity Bit-Flipping for Decoding Surface Codes
• Exact results on finite size corrections for surface codes tailored to biased noise
• Decoherence and Quantum Error Correction for Quantum Computing and Communications
• A NEAT Quantum Error Decoder
• Magic Mirror on the Wall, How to Benchmark Quantum Error Correction Codes, Overall ?
• On the Efficacy of Surface Codes in Compensating for Radiation Events in Superconducting Devices
• Enhancing Quantum Memory Lifetime with Measurement-Free Local Error Correction and Reinforcement Learning
• Thresholds for post-selected quantum error correction from statistical mechanics
• Fundamental thresholds for computational and erasure errors via the coherent information
• Generalizing the matching decoder for the Chamon code
• Positive bias makes tensor-network contraction tractable
• The surface code beyond Pauli channels: Logical noise coherence, information-theoretic measures, and errorfield-double phenomenology
• Revisiting Nishimori multicriticality through the lens of information measures
• Quantum Lego and XP Stabilizer Codes
• Distributed Realization of Color Codes for Quantum Error Correction
• GAN decoder on a quantum toric code for noise-robust quantum teleportation
• Self-attention U-Net decoder for toric codes
• Improved Logical Error Rate via List Decoding of Quantum Polar Codes
• Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs
• Boundary Criticality at the Nishimori Multicritical Point
• Hardness results for decoding the surface code with Pauli noise
• Simulated-annealing decoder for the XZZX code with greedy-matching initialization
• Neural Decoders for Universal Quantum Algorithms
• On the interpretability of neural network decoders
• Exploring the quantum capacity of a Gaussian random displacement channel using Gottesman-Kitaev-Preskill codes and maximum likelihood decoding
• Convolutional Polar Codes on Channels with Memory using Tensor Networks
• Biased-Noise Thresholds of Zero-Rate Holographic Codes with Tensor-Network Decoding
• Gottesman-Kitaev-Preskill codes: A lattice perspective