Finite-rate sparse quantum codes aplenty

Abstract

We introduce a methodology for generating random multi-qubit stabilizer codes based on solving a constraint satisfaction problem (CSP) on random bipartite graphs. This framework allows us to enforce stabilizer commutation, $X/Z$ balancing, finite rate, sparsity, and maximum-degree constraints simultaneously in a CSP that we can then solve numerically. Using a state-of-the-art CSP solver, we obtain convincing evidence for the existence of a satisfiability threshold. Furthermore, the extent of the satisfiable phase increases with the number of qubits. In that phase, finding sparse codes becomes an easy problem. Moreover, we observe that the sparse codes found in the satisfiable phase practically achieve the channel capacity for erasure noise. Our results show that intermediate-size finite-rate sparse quantum codes are easy to find, while also demonstrating a flexible methodology for generating good codes with custom properties. We therefore establish a complete and customizable pipeline for random quantum code discovery.

References in corpus (19)

• Surface codes: Towards practical large-scale quantum computation
• Good Quantum Error-Correcting Codes Exist
• Stabilizer Codes and Quantum Error Correction
• Simple Quantum Error Correcting Codes
• Quantum codes on a lattice with boundary
• Capacities of Quantum Erasure Channels
• Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
• Tradeoffs for reliable quantum information storage in 2D systems
• Fault-tolerant thresholds for quantum error correction with the surface code
• Asymptotically Good Quantum Codes
• Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel
• Constant-overhead quantum error correction with thin planar connectivity
• Fault-tolerant quantum computing with color codes
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• Quantum coding with low-depth random circuits
• Three-dimensional color code thresholds via statistical-mechanical mapping
• Combining hard and soft decoders for hypergraph product codes
• Tradeoffs for reliable quantum information storage in surface codes and color codes
• Short random circuits define good quantum error correcting codes

Cited by in corpus (2)

• Quantum Error Correction via Noise Guessing Decoding
• Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder