Connectivity constrains quantum codes

Abstract

Quantum low-density parity-check (LDPC) codes are an important class of quantum error correcting codes. In such codes, each qubit only affects a constant number of syndrome bits, and each syndrome bit only relies on some constant number of qubits. Constructing quantum LDPC codes is challenging. It is an open problem to understand if there exist good quantum LDPC codes, i.e. with constant rate and relative distance. Furthermore, techniques to perform fault-tolerant gates are poorly understood. We present a unified way to address these problems. Our main results are a) a bound on the distance, b) a bound on the code dimension and c) limitations on certain fault-tolerant gates that can be applied to quantum LDPC codes. All three of these bounds are cast as a function of the graph separator of the connectivity graph representation of the quantum code. We find that unless the connectivity graph contains an expander, the code is severely limited. This implies a necessary, but not sufficient, condition to construct good codes. This is the first bound that studies the limitations of quantum LDPC codes that does not rely on locality. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space.

References in corpus (13)

• Local stabilizer codes in three dimensions without string logical operators
• Topological Quantum Distillation
• Topological Order with a Twist: Ising Anyons from an Abelian Model
• Quantum Low-Density Parity-Check Codes
• A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
• Quantum LDPC Codes with Almost Linear Minimum Distance
• Balanced Product Quantum Codes
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Fault-tolerant logical gates in quantum error-correcting codes
• Quantum accuracy threshold for concatenated distance-3 codes
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• Quantum XYZ Product Codes
• Limitations on transversal gates for hypergraph product codes

Cited by in corpus (20)

• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Relaxing Hardware Requirements for Surface Code Circuits using Time-dynamics
• Bias-tailored quantum LDPC codes
• Quantifying nonlocality: how outperforming local quantum codes is expensive
• Toward a 2D Local Implementation of Quantum LDPC Codes
• Quantum LDPC Codes for Modular Architectures
• LDPC-cat codes for low-overhead quantum computing in 2D
• Constant-Overhead Fault-Tolerant Bell-Pair Distillation using High-Rate Codes
• Hierarchical memories: Simulating quantum LDPC codes with local gates
• Local tensor-network codes
• Entanglement Purification with Quantum LDPC Codes and Iterative Decoding
• Analog information decoding of bosonic quantum LDPC codes
• Partial Syndrome Measurement for Hypergraph Product Codes
• Weight Reduced Stabilizer Codes with Lower Overhead
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes
• On the Cleaning Lemma of Quantum Coding Theory
• Quantum State Transfer via a Multimode Resonator
• Single-shot preparation of hypergraph product codes via dimension jump
• Enhanced Lieb-Robinson bounds for commuting long-range interactions
• Wire Codes