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 $d\propto n^{1/2+ϵ}$ requires $\mathrm{\Omega }(n^{1/2+ϵ})$ interactions of length $\tilde{\mathrm{\Omega }}(n^{ϵ})$. Further, a code satisfying $k\propto n$ with distance $d\propto n^{\alpha }$ requires $\tilde{\mathrm{\Omega }}(n)$ interactions of length $\tilde{\mathrm{\Omega }}(n^{\alpha /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.

Figure 1

(a) A schematic for a concatenated code [28]. The qubits of the code are themselves encoded in an error correcting code and this gives rise to a hierarchical structure. (b) A two-dimensional stacked architecture. Qubits are the bottommost layer. Stabilizers, identified with their support, are assigned to different layers above and are depicted using blue circles. Stabilizers in a given layer have a radius of support depending on the layer. This interaction range increases as we move up the stack or, equivalently, the radius of the circles increases. On the other hand, the number of stabilizers in each layer decreases exponentially.