We study the tradeoffs between the locality and parameters of subsystem codes. We prove lower bounds on both the number and lengths of interactions in any D-dimensional embedding of a subsystem code. Specifically, we show that any embedding of a subsystem code with parameters [[n,k,d]] into R^D must have at least M^* interactions of length at least 𝓁^*, where M^* = Ω(max(k,d)), and 𝓁^* = Ω(max(d/(n^((D-1)/D)), ((kd^(1/(D-1))/n))^((D-1)/D))). We also give tradeoffs between the locality and parameters of commuting projector codes in D-dimensions, generalizing a result of Dai and Li [Dai and Li, 2025]. We provide explicit constructions of embedded codes that show our bounds are optimal in both the interaction count and interaction length.We study the tradeoffs between the locality and parameters of subsystem codes. We prove lower bounds on both the number and lengths of interactions in any D-dimensional embedding of a subsystem code. Specifically, we show that any embedding of a subsystem code with parameters [[n,k,d]] into R^D must have at least M^* interactions of length at least 𝓁^*, where M^* = Ω(max(k,d)), and 𝓁^* = Ω(max(d/(n^((D-1)/D)), ((kd^(1/(D-1))/n))^((D-1)/D))). We also give tradeoffs between the locality and parameters of commuting projector codes in D-dimensions, generalizing a result of Dai and Li [Dai and Li, 2025]. We provide explicit constructions of embedded codes that show our bounds are optimal in both the interaction count and interaction length.

Jan 1, 20250 citations

Locality vs Quantum Codes

Samuel Dai, Ray Li

This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes. Quantum codes give a promising avenue towards quantum fault tolerance, but the practical constraint of locality limits their quality. The seminal Bravyi-Poulin-Terhal (BPT) bound says that a $[[n,k,d]]$ quantum stabilizer code with 2D-locality must satisfy $kd^2\le O(n)$ . We answer the natural question: for better code parameters, how much "non-locality" is needed? In particular, (i) how long must the long-range interactions be, and (ii) how many long-range interactions must there be? We give a complete answer to both questions for all $n,k,d$ : above the BPT bound, any 2D-embedding must have at least $Ω(\#^*)$ interactions of length $Ω(\ell^*)$ , where $\#^*= \max(k,d)$ and $\ell^*=\max\big(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)$ . Conversely, we exhibit quantum codes that show, in strong ways, that our interaction length $\ell^*$ and interaction count $\#^*$ are asymptotically optimal for all $n,k,d$ . Our results generalize or improve all prior works on this question, including the BPT bound and the results of Baspin and Krishna. One takeaway of our work is that, for any desired distance $d$ and dimension $k$ , the number of long-range interactions is asymptotically minimized by a good qLDPC code of length $Θ(\max(k,d))$ . Following Baspin and Krishna, we also apply our results to the codes implemented in the stacked architecture and obtain better bounds. In particular, we rule out any implementation of hypergraph product codes in the stacked architecture.This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes. Quantum codes give a promising avenue towards quantum fault tolerance, but the practical constraint of locality limits their quality. The seminal Bravyi-Poulin-Terhal (BPT) bound says that a $[[n,k,d]]$ quantum stabilizer code with 2D-locality must satisfy $kd^2\le O(n)$. We answer the natural question: for better code parameters, how much "non-locality" is needed? In particular, (i) how long must the long-range interactions be, and (ii) how many long-range interactions must there be? We give a complete answer to both questions for all $n,k,d$: above the BPT bound, any 2D-embedding must have at least $Ω(\#^*)$ interactions of length $Ω(\ell^*)$, where $\#^*= \max(k,d)$ and $\ell^*=\max\big(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)$. Conversely, we exhibit quantum codes that show, in strong ways, that our interaction length $\ell^*$ and interaction count $\#^*$ are asymptotically optimal for all $n,k,d$. Our results generalize or improve all prior works on this question, including the BPT bound and the results of Baspin and Krishna. One takeaway of our work is that, for any desired distance $d$ and dimension $k$, the number of long-range interactions is asymptotically minimized by a good qLDPC code of length $Θ(\max(k,d))$. Following Baspin and Krishna, we also apply our results to the codes implemented in the stacked architecture and obtain better bounds. In particular, we rule out any implementation of hypergraph product codes in the stacked architecture.

arXiv:2409.15203ACM Symposium on Theory of Computing (STOC)Jun 15, 20251 citation

Optimal quantum subsystem codes in two dimensions

Theodore J. Yoder

Given any two classical codes with parameters $[{n}_{1},k,{d}_{1}]$ and $[{n}_{2},k,{d}_{2}]$ , we show how to construct a quantum subsystem code in two dimensions with parameters $[[N,K,D]]$ satisfying $N\ensuremath{\le}2{n}_{1}{n}_{2}, K=k$, and $D=min({d}_{1},{d}_{2})$ . These quantum codes are in the class of generalized Bacon-Shor codes introduced by Bravyi [Phys. Rev. A 83, 012320 (2011)]. We note that constructions of good classical codes can be used to construct quantum codes that saturate Bravyi's bound $KD=O(N)$ on the code parameters of two-dimensional subsystem codes. One of these good constructions uses classical expander codes. This construction has the additional advantage of a linear time quantum decoder based on the classical Sipser-Spielman flip decoder. Finally, while the subsystem codes we create do not have asymptotic thresholds, we show how they can be gauge fixed to certain hypergraph product codes that do.Given any two classical codes with parameters $[{n}_{1},k,{d}_{1}]$ and $[{n}_{2},k,{d}_{2}]$, we show how to construct a quantum subsystem code in two dimensions with parameters $[[N,K,D]]$ satisfying $N\ensuremath{\le}2{n}_{1}{n}_{2}, K=k$, and $D=min({d}_{1},{d}_{2})$. These quantum codes are in the class of generalized Bacon-Shor codes introduced by Bravyi [Phys. Rev. A 83, 012320 (2011)]. We note that constructions of good classical codes can be used to construct quantum codes that saturate Bravyi's bound $KD=O(N)$ on the code parameters of two-dimensional subsystem codes. One of these good constructions uses classical expander codes. This construction has the additional advantage of a linear time quantum decoder based on the classical Sipser-Spielman flip decoder. Finally, while the subsystem codes we create do not have asymptotic thresholds, we show how they can be gauge fixed to certain hypergraph product codes that do.

arXiv:1901.06319Physical Review AMay 22, 201911 citations

Wire Codes

Nouédyn Baspin, Dominic J. Williamson

Quantum information is fragile and must be protected by a quantum error-correcting code for large-scale practical applications. Recently, highly efficient quantum codes have been discovered which require a high degree of spatial connectivity. This raises the question of how to realize these codes with minimal overhead under physical hardware connectivity constraints. Here, we introduce a general recipe to transform any quantum stabilizer code into a subsystem code that has local interactions, with weight and degree three, on a given graph. We call the subsystem codes produced by our recipe wire codes, and their code parameters depend on the input code and the given graph. Wire codes can be adapted to have a local implementation on any graph that supports a low-density embedding of the input Tanner graph, with an overhead that depends on the embedding. In particular, applying our results to a stabilizer code and a subdivision of its own Tanner graph, yields a quantum weight reduction procedure with a multiplicative qubit overhead and distance reduction that are linear in the input check degree and weight, respectively. Applying our results to hypercubic lattices leads to a construction of local subsystem codes with optimal scaling code parameters in any fixed spatial dimension. Similarly, applying our results to families of expanding graphs leads to local codes on these graphs with code parameters that depend on the degree of expansion. Our results constitute a general method to construct low-overhead subsystem codes on general graphs, which can be applied to adapt highly efficient quantum error correction procedures to hardware with restricted connectivity.Quantum information is fragile and must be protected by a quantum error-correcting code for large-scale practical applications. Recently, highly efficient quantum codes have been discovered which require a high degree of spatial connectivity. This raises the question of how to realize these codes with minimal overhead under physical hardware connectivity constraints. Here, we introduce a general recipe to transform any quantum stabilizer code into a subsystem code that has local interactions, with weight and degree three, on a given graph. We call the subsystem codes produced by our recipe wire codes, and their code parameters depend on the input code and the given graph. Wire codes can be adapted to have a local implementation on any graph that supports a low-density embedding of the input Tanner graph, with an overhead that depends on the embedding. In particular, applying our results to a stabilizer code and a subdivision of its own Tanner graph, yields a quantum weight reduction procedure with a multiplicative qubit overhead and distance reduction that are linear in the input check degree and weight, respectively. Applying our results to hypercubic lattices leads to a construction of local subsystem codes with optimal scaling code parameters in any fixed spatial dimension. Similarly, applying our results to families of expanding graphs leads to local codes on these graphs with code parameters that depend on the degree of expansion. Our results constitute a general method to construct low-overhead subsystem codes on general graphs, which can be applied to adapt highly efficient quantum error correction procedures to hardware with restricted connectivity.

arXiv:2410.10194QuantumApr 24, 20261 citation

Quantifying Nonlocality: How Outperforming Local Quantum Codes Is Expensive

Nouédyn Baspin, Anirudh Krishna

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

arXiv:2109.10982Physical Review LettersJul 28, 202237 citations

Permutation-invariant codes: a numerical study and qudit constructions

Liam J. Bond, Jiří Minář, Māris Ozols +2 more

We investigate Permutation-Invariant (PI) quantum error-correcting codes encoding a logical qudit of dimension $\mathrm{d}_\mathrm{L}$ in PI states using physical qudits of dimension $\mathrm{d}_\mathrm{P}$ . We extend the Knill--Laflamme (KL) conditions for $d-1$ deletion errors from qubits to qudits and investigate numerically both qubit ( $\mathrm{d}_\mathrm{L} = \mathrm{d}_\mathrm{P} = 2$ ) and qudit ( $\mathrm{d}_\mathrm{L} > 2$ or $\mathrm{d}_\mathrm{P} > 2$ ) PI codes. We analyze the scaling of the block length $n$ in terms of the code distance $d$ , and compare to existing families of PI codes due to Ouyang, Aydin--Alekseyev--Barg (AAB) and Pollatsek--Ruskai (PR). Our three main findings are: (i) We conjecture that qubit PI codes correcting up to $d-1$ deletion errors have block length $n(d) \geq (3d^2 + 1) / 4$ , which implies an upper bound $d \leq \sqrt{12n-3}/3$ on their code distance, and that PR codes can saturate this bound. (ii) For qudit PI codes encoding a single qudit we numerically observe that increasing $\mathrm{d}_\mathrm{P}$ results in $n$ monotonically decreasing and approaching the quantum Singleton bound $n(d) \geq 2d-1$ . (iii) We propose a semi-analytic extension of the qubit AAB construction to qudits that finds explicit solutions by solving a linear program. Our results therefore provide key insights into lower bounds on the block length scaling of both qubit and qudit PI codes, and demonstrate the benefit of increased physical local dimension in the context of PI codes.We investigate Permutation-Invariant (PI) quantum error-correcting codes encoding a logical qudit of dimension $\mathrm{d}_\mathrm{L}$ in PI states using physical qudits of dimension $\mathrm{d}_\mathrm{P}$. We extend the Knill--Laflamme (KL) conditions for $d-1$ deletion errors from qubits to qudits and investigate numerically both qubit ($\mathrm{d}_\mathrm{L} = \mathrm{d}_\mathrm{P} = 2$) and qudit ($\mathrm{d}_\mathrm{L} > 2$ or $\mathrm{d}_\mathrm{P} > 2$) PI codes. We analyze the scaling of the block length $n$ in terms of the code distance $d$, and compare to existing families of PI codes due to Ouyang, Aydin--Alekseyev--Barg (AAB) and Pollatsek--Ruskai (PR). Our three main findings are: (i) We conjecture that qubit PI codes correcting up to $d-1$ deletion errors have block length $n(d) \geq (3d^2 + 1) / 4$, which implies an upper bound $d \leq \sqrt{12n-3}/3$ on their code distance, and that PR codes can saturate this bound. (ii) For qudit PI codes encoding a single qudit we numerically observe that increasing $\mathrm{d}_\mathrm{P}$ results in $n$ monotonically decreasing and approaching the quantum Singleton bound $n(d) \geq 2d-1$. (iii) We propose a semi-analytic extension of the qubit AAB construction to qudits that finds explicit solutions by solving a linear program. Our results therefore provide key insights into lower bounds on the block length scaling of both qubit and qudit PI codes, and demonstrate the benefit of increased physical local dimension in the context of PI codes.

quant-pharXiv:2603.10981Mar 12, 20260 citations

[[n,k,d]]

quantum stabilizer code with 2D-locality must satisfy

kd^2\le O(n)

. We answer the natural question: for better code parameters, how much "non-locality" is needed? In particular, (i) how long must the long-range interactions be, and (ii) how many long-range interactions must there be? We give a complete answer to both questions for all

n,k,d

: above the BPT bound, any 2D-embedding must have at least

Ω(\#^*)

interactions of length

Ω(\ell^*)

, where

\#^*= \max(k,d)

and

\ell^*=\max\big(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)

. Conversely, we exhibit quantum codes that show, in strong ways, that our interaction length

\ell^*

and interaction count

\#^*

are asymptotically optimal for all

n,k,d

. Our results generalize or improve all prior works on this question, including the BPT bound and the results of Baspin and Krishna. One takeaway of our work is that, for any desired distance

d

and dimension

k

, the number of long-range interactions is asymptotically minimized by a good qLDPC code of length

Θ(\max(k,d))

. Following Baspin and Krishna, we also apply our results to the codes implemented in the stacked architecture and obtain better bounds. In particular, we rule out any implementation of hypergraph product codes in the stacked architecture.

Given any two classical codes with parameters

[{n}_{1},k,{d}_{1}]

and

[{n}_{2},k,{d}_{2}]

, we show how to construct a quantum subsystem code in two dimensions with parameters

[[N,K,D]]

satisfying $N\ensuremath{\le}2{n}_{1}{n}_{2}, K=k$, and

D=min({d}_{1},{d}_{2})

. These quantum codes are in the class of generalized Bacon-Shor codes introduced by Bravyi [Phys. Rev. A 83, 012320 (2011)]. We note that constructions of good classical codes can be used to construct quantum codes that saturate Bravyi's bound

KD=O(N)

on the code parameters of two-dimensional subsystem codes. One of these good constructions uses classical expander codes. This construction has the additional advantage of a linear time quantum decoder based on the classical Sipser-Spielman flip decoder. Finally, while the subsystem codes we create do not have asymptotic thresholds, we show how they can be gauge fixed to certain hypergraph product codes that do.

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

We investigate Permutation-Invariant (PI) quantum error-correcting codes encoding a logical qudit of dimension

\mathrm{d}_\mathrm{L}

in PI states using physical qudits of dimension

\mathrm{d}_\mathrm{P}

. We extend the Knill--Laflamme (KL) conditions for

d-1

deletion errors from qubits to qudits and investigate numerically both qubit (

\mathrm{d}_\mathrm{L} = \mathrm{d}_\mathrm{P} = 2

) and qudit (

\mathrm{d}_\mathrm{L} > 2

\mathrm{d}_\mathrm{P} > 2

) PI codes. We analyze the scaling of the block length

n

in terms of the code distance

d

, and compare to existing families of PI codes due to Ouyang, Aydin--Alekseyev--Barg (AAB) and Pollatsek--Ruskai (PR). Our three main findings are: (i) We conjecture that qubit PI codes correcting up to

d-1

deletion errors have block length

n(d) \geq (3d^2 + 1) / 4

, which implies an upper bound

d \leq \sqrt{12n-3}/3

on their code distance, and that PR codes can saturate this bound. (ii) For qudit PI codes encoding a single qudit we numerically observe that increasing

\mathrm{d}_\mathrm{P}

results in

n

monotonically decreasing and approaching the quantum Singleton bound

n(d) \geq 2d-1

. (iii) We propose a semi-analytic extension of the qubit AAB construction to qudits that finds explicit solutions by solving a linear program. Our results therefore provide key insights into lower bounds on the block length scaling of both qubit and qudit PI codes, and demonstrate the benefit of increased physical local dimension in the context of PI codes.