Quantifying Nonlocality: How Outperforming Local Quantum Codes Is Expensive

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 et al. Phys. Rev. Lett. 104, 050503 (2010) 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 code with distance dn^1/2+ϵ requires (n^1/2+ϵ) interactions of length (n^ϵ). Further, a code satisfying k with distance dn^ requires (n) interactions of length (n^/2). 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.