Optimal and Efficient Decoding of Concatenated Quantum Block Codes

Abstract

We consider the problem of optimally decoding a quantum error correction code -- that is to find the optimal recovery procedure given the outcomes of partial "check" measurements on the system. In general, this problem is NP-hard. However, we demonstrate that for concatenated block codes, the optimal decoding can be efficiently computed using a message passing algorithm. We compare the performance of the message passing algorithm to that of the widespread blockwise hard decoding technique. Our Monte Carlo results using the 5 qubit and Steane's code on a depolarizing channel demonstrate significant advantages of the message passing algorithms in two respects. 1) Optimal decoding increases by as much as 94% the error threshold below which the error correction procedure can be used to reliably send information over a noisy channel. 2) For noise levels below these thresholds, the probability of error after optimal decoding is suppressed at a significantly higher rate, leading to a substantial reduction of the error correction overhead.

Published version

References in corpus (12)

• Fault-tolerant quantum computation by anyons
• Mixed State Entanglement and Quantum Error Correction
• Multiple Particle Interference and Quantum Error Correction
• Quantum Computing with Very Noisy Devices
• Reliable Quantum Computers
• Sparse Graph Codes for Quantum Error-Correction
• Stabilizer Formalism for Operator Quantum Error Correction
• Resilient Quantum Computation: Error Models and Thresholds
• Quantum Channel Capacity of Very Noisy Channels
• Exact Performance of Concatenated Quantum Codes
• Constructions and performance of classes of quantum LDPC codes
• Trellises for stabilizer codes: definition and uses

Cited by in corpus (67)

• Quantum Error Correction for Quantum Memories
• Quantum networks based on color centers in diamond
• Fast Decoders for Topological Quantum Codes
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• High-threshold fault-tolerant quantum computation with analog quantum error correction
• Quantum Graphical Models and Belief Propagation
• Flag fault-tolerant error correction with arbitrary distance codes
• Fault-tolerant thresholds for quantum error correction with the surface code
• Decoding Small Surface Codes with Feedforward Neural Networks
• Analog quantum error correction with encoding a qubit into an oscillator
• Entanglement-assisted quantum turbo codes
• Tensor Networks and Quantum Error Correction
• Deep neural decoders for near term fault-tolerant experiments
• Performance of quantum error correction with coherent errors
• 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
• Coherence in quantum error-correcting codes
• Modeling coherent errors in quantum error correction
• A logical qubit in a linear array of semiconductor quantum dots
• Fault-Tolerant Quantum Computing in the Pauli or Clifford Frame with Slow Error Diagnostics
• Building a large-scale quantum computer with continuous-variable optical technologies
• Comparison of a quantum error correction threshold for exact and approximate errors
• Transversal Clifford gates on folded surface codes
• Hard decoding algorithm for optimizing thresholds under general Markovian noise
• High-threshold topological quantum error correction against biased noise
• Tensor-network codes
• Avoiding coherent errors with rotated concatenated stabilizer codes
• Accuracy threshold for concatenated error detection in one dimension
• Neural ensemble decoding for topological quantum error-correcting codes
• Learning time-dependent noise to reduce logical errors: Real time error rate estimation in quantum error correction
• Tracking Quantum Error Correction
• The XYZ${}^2$ hexagonal stabilizer code
• Tailoring three-dimensional topological codes for biased noise
• Cluster-based architecture for fault-tolerant quantum computation
• Soft Decoding of a Qubit Readout Apparatus
• Many-hypercube codes: High-rate quantum error-correcting codes for high-performance fault-tolerant quantum computing
• Error rates and resource overheads of encoded three-qubit gates
• Belief propagation decoding of quantum channels by passing quantum messages
• Hierarchical memories: Simulating quantum LDPC codes with local gates
• Correctable noise of Quantum Error Correcting Codes under adaptive concatenation
• Measurement-free fault-tolerant logical zero-state encoding of the distance-three nine-qubit surface code in a one-dimensional qubit array
• Optimal correction of concatenated fault-tolerant quantum codes
• Optimal noise estimation from syndrome statistics of quantum codes
• Ising model formulation for highly accurate topological color codes decoding
• Quantum message-passing algorithm for optimal and efficient decoding
• Concatenation Schemes for Topological Fault-tolerant Quantum Error Correction
• Efficient diagnostics for quantum error correction
• Message passing in fault tolerant quantum error correction
• Efficient Concatenated Bosonic Code for Additive Gaussian Noise
• Concatenating quantum error-correcting codes with decoherence-free subspaces and vice versa
• Generality of the concatenated five-qubit code
• Adaptive Syndrome Extraction
• Robustness of the concatenated quantum error-correction protocol against noise for channels affected by fluctuation
• Counting stabiliser codes for arbitrary dimension
• Optimization tools for distance-preserving flag fault-tolerant error correction
• Efficiently computing logical noise in quantum error correcting codes
• Concatenated Steane code with single-flag syndrome checks
• Decoherence and Quantum Error Correction for Quantum Computing and Communications
• Error Correction for Reliable Quantum Computing
• Dynamically generated concatenated codes and their phase diagrams
• Noisy Quantum Trees: Infinite Protection Without Correction
• Optimizing the Frequency of Quantum Error Correction using the [[7,1,3]] Steane Code
• A note on threshold theorem of fault-tolerant quantum computation
• Hierarchical Quantum Error Correction with Hypergraph Product Code and Rotated Surface Code
• Subsystem many-hypercube codes: High-rate concatenated codes with low-weight syndrome measurements
• Simulated-annealing decoder for the XZZX code with greedy-matching initialization
• Universal quantum computation via scalable measurement-free error correction