An efficient Markov chain Monte Carlo algorithm for the surface code

Abstract

Minimum-weight perfect matching (MWPM) has been been the primary classical algorithm for error correction in the surface code, since it is of low runtime complexity and achieves relatively low logical error rates [Phys. Rev. Lett. 108, 180501 (2012)]. A Markov chain Monte Carlo (MCMC) algorithm [Phys. Rev. Lett. 109, 160503 (2012)] is able to achieve lower logical error rates and higher thresholds than MWPM, but requires a classical runtime complexity which is super-polynomial in L, the linear size of the code. In this work we present an MCMC algorithm that achieves significantly lower logical error rates than MWPM at the cost of a polynomially increased classical runtime complexity. For error rates p close to the threshold, our algorithm needs a runtime complexity which is increased by O(L^2) relative to MWPM in order to achieve a lower logical error rate. If p is below an L-dependent critical value, no increase in the runtime complexity is necessary any longer. For p->0, the logical error rate achieved by our algorithm is exponentially smaller (in L) than that of MWPM, without requiring an increased runtime complexity. Our algorithm allows for trade-offs between runtime and achieved logical error rates as well as for parallelization, and can be also used to correct in the case of imperfect stabilizer measurements.

10 pages, 10 figures; v2: includes community feedback

References in corpus (7)

• Surface codes: Towards practical large-scale quantum computation
• Fault-tolerant quantum computation with high threshold in two dimensions
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Symmetrised Characterisation of Noisy Quantum Processes
• Kitaev's Z_d-Codes Threshold Estimates
• Stabilizer quantum error correction toolbox for superconducting qubits
• Quantum memories and error correction

Cited by in corpus (53)

• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Quantum memories at finite temperature
• Almost-linear time decoding algorithm for topological codes
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Ultrahigh Error Threshold for Surface Codes with Biased Noise
• A Neural Decoder for Topological Codes
• Machine-learning-assisted correction of correlated qubit errors in a topological code
• Fault-tolerant error correction with the gauge color code
• The surface code with a twist
• Tensor-Network Simulations of the Surface Code under Realistic Noise
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes
• Combining Topological Hardware and Topological Software: Color Code Quantum Computing with Topological Superconductor Networks
• Quantum coding with low-depth random circuits
• Cellular-automaton decoders for topological quantum memories
• Quantum Error Correction with the Semion Code
• A repetition code of 15 qubits
• 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
• Decoding non-Abelian topological quantum memories
• Multi-path Summation for Decoding 2D Topological Codes
• Linear-time general decoding algorithm for the surface code
• Improved HDRG decoders for qudit and non-Abelian quantum error correction
• Cellular automaton decoders of topological quantum memories in the fault tolerant setting
• Fault-Tolerant Quantum Error Correction for non-Abelian Anyons
• Deep Q-learning decoder for depolarizing noise on the toric code
• A decoder for the triangular color code by matching on a Möbius strip
• Practical Topological Cluster State Quantum Computing Requires Loss Below 1%
• Creating entangled logical qubits in the heavy-hex lattice with topological codes
• Logical Error Rate Scaling of the Toric Code
• General tensor network decoding of 2D Pauli codes
• A simple decoder for topological codes
• Breakdown of Surface Code Error Correction Due to Coupling to a Bosonic Bath
• Classical Simulation of Quantum Error Correction in a Fibonacci Anyon Code
• The XYZ${}^2$ hexagonal stabilizer code
• Conservation laws and quantum error correction: towards a generalised matching decoder
• Pipelined correlated minimum weight perfect matching of the surface code
• Topological quantum error correction in the Kitaev honeycomb model
• Symmetries for a High Level Neural Decoder on the Toric Code
• A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing
• Convolutional neural network based decoders for surface codes
• A proposal for a minimal surface code experiment
• 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
• Mitigating errors in logical qubits
• Error-rate-agnostic decoding of topological stabilizer codes
• Error correcting power of small topological codes
• Exact results on finite size corrections for surface codes tailored to biased noise
• Magic Mirror on the Wall, How to Benchmark Quantum Error Correction Codes, Overall ?
• Revisiting Nishimori multicriticality through the lens of information measures
• Minimising surface-code failures using a color-code decoder
• Hierarchical Quantum Error Correction with Hypergraph Product Code and Rotated Surface Code
• Simulated-annealing decoder for the XZZX code with greedy-matching initialization