Quantifying nonlocality: how outperforming local quantum codes is expensive

Abstract

Quantum low-density parity-check (LDPC) codes are a promising avenue to reduce the cost of constructing scalable quantum circuits. However, it is unclear how to implement these codes in practice. Seminal results of Bravyi & Terhal, and Bravyi, Poulin & Terhal have shown that quantum LDPC codes implemented through local interactions obey restrictions on their dimension $k$ and distance $d$. Here we address the complementary question of how many long-range interactions are required to implement a quantum LDPC code with parameters $k$ and $d$. In particular, in 2D we show that a quantum LDPC with distance $n^{1/2+\epsilon }$ code requires $\Omega (n^{1/2+\epsilon })$ interactions of length $\tilde{\Omega }(n^{\epsilon })$. Further a code satisfying $k\propto n$ with distance $d\propto n^{\alpha }$ requires $\tilde{\Omega }(n)$ interactions of length $\tilde{\Omega }(n^{\alpha /2})$. Our results are derived using bounds on quantum codes from graph metrics. As an application of these results, we consider a model called a stacked architecture, which has previously been considered as a potential way to implement quantum LDPC codes. In this model, although most interactions are local, a few of them are allowed to be very long. We prove that limited long-range connectivity implies quantitative bounds on the distance and code dimension.

References in corpus (13)

• Topological Quantum Distillation
• Experimental Comparison of Two Quantum Computing Architectures
• A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
• Programmable Interactions and Emergent Geometry in an Atomic Array
• Quantum LDPC Codes with Almost Linear Minimum Distance
• A silicon-integrated telecom photon-spin interface
• Universal transversal gates with color codes - a simplified approach
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Constant-overhead quantum error correction with thin planar connectivity
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• Connectivity constrains quantum codes
• Interleaving: Modular architectures for fault-tolerant photonic quantum computing

Cited by in corpus (22)

• High-threshold and low-overhead fault-tolerant quantum memory
• The Future of Quantum Computing with Superconducting Qubits
• Constant-overhead quantum error correction with thin planar connectivity
• Entangling four logical qubits beyond break-even in a nonlocal code
• Toward a 2D Local Implementation of Quantum LDPC Codes
• Quantum LDPC Codes for Modular Architectures
• Single-shot decoding of good quantum LDPC codes
• Constant-Overhead Fault-Tolerant Bell-Pair Distillation using High-Rate Codes
• Hierarchical memories: Simulating quantum LDPC codes with local gates
• Long-range-enhanced surface codes
• Distance-preserving stabilizer measurements in hypergraph product codes
• Analog information decoding of bosonic quantum LDPC codes
• Partial Syndrome Measurement for Hypergraph Product Codes
• Weight Reduced Stabilizer Codes with Lower Overhead
• Adaptive Syndrome Extraction
• Error Correction in Dynamical Codes
• Fault-tolerance in qudit circuit design
• Distributed quantum error correction based on hyperbolic Floquet codes
• Flying-cat parity checks for quantum error correction
• Enhanced Lieb-Robinson bounds for commuting long-range interactions
• Wire Codes
• qSIEVE: Efficient qLDPC Memory via Systolic Movement in Atom Arrays