Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1901.06319 · Physical Review A

Optimal quantum subsystem codes in two dimensions

Theodore J. Yoder

Published May 22, 2019• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.99.052333

Related papers

A Numerical Study of Bravyi-Bacon-Shor and Subsystem Hypergraph Product Codes

Muyuan Li, Theodore J. Yoder

We provide a numerical investigation of two families of subsystem quantum codes that are related to hypergraph product codes by gauge-fixing. The first family consists of the Bravyi-Bacon-Shor (BBS) codes which have optimal code parameters for subsystem quantum codes local in 2-dimensions. The second family consists of the constant rate “generalized Shor” codes of Bacon and Cassicino [1], which we re-brand as subsystem hypergraph product (SHP) codes. We show that any hypergraph product code can be obtained by entangling the gauge qubits of two SHP codes. To evaluate the performance of these codes, we simulate both small and large examples. For circuit noise, a [21], [4], [3] BBS code and a [49], [16], [3] SHP code have pseudthresholds of 2 × 10-3and 8 × 10-4, respectively. Simulations for phenomenological noise show that large BBS and SHP codes start to outperform surface codes with similar encoding rate at physical error rates 1 × 10-6and 4 × 10-4, respectively.

arXiv:2002.06257•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•17 citations

Subsystem codes with spatially local generators

Sergey B. Bravyi

We study subsystem codes whose gauge group has local generators in two-dimensional (2D) geometry. It is shown that there exists a family of such codes defined on lattices of size $L\ifmmode\times\else\texttimes\fi{}L$ with the number of logical qubits $k$ and the minimum distance $d$ both proportional to $L$. The gauge group of these codes involves only two-qubit generators of type $\mathit{XX}$ and $\mathit{ZZ}$ coupling nearest-neighbor qubits (and some auxiliary one-qubit generators). Our proof is not constructive as it relies on a certain version of the Gilbert-Varshamov bound for classical codes. Along the way, we introduce and study properties of generalized Bacon-Shor codes that might be of independent interest. Secondly, we prove that any 2D subsystem $[n,k,d]$ code with spatially local generators obeys upper bounds $\mathit{kd}=O(n)$ and ${d}^{2}=O(n)$. The analogous upper bound proved recently for 2D stabilizer codes is ${\mathit{kd}}^{2}=O(n)$. Our results thus demonstrate that subsystem codes can be more powerful than stabilizer codes under the spatial locality constraint.

arXiv:1008.1029•Physical Review A•Jan 26, 2011•61 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.

arXiv:2409.15203•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•9 citations

Construction of a Family of Quantum Codes Using Sub-exceding Functions via the Hypergraph Product and the Generalized Shor Construction

Luc Rabefihavanana, Harinaivo Andriatahiny, Randriamiarampanahy Ferdinand

In this paper, we introduce a new family of stabilizer quantum LDPC codes derived from the classical linear codes $L_k$ and $L_k^{+}$, defined via sub-exceding functions. In previous work, these codes demonstrated strong performance in minimum distance, decoding efficiency, and structural simplicity. By combining the hypergraph product framework with a generalized Shor construction, we obtain a scalable class of quantum codes with parameters $[[6k^2,\, k^2,\, d]]$. The resulting quantum codes exhibit a rich combinatorial structure and promising properties, particularly in terms of locality, low-density parity-check (LDPC) structure, and asymptotic behavior. The minimum distance satisfies $d=3$ for $k=3$ and $d=4$ for $k\ge4$, establishing a new framework for structured quantum LDPC code design and optimization.

quant-pharXiv:2603.08213•Mar 10, 2026•0 citations

New decoding algorithms for a class of subsystem codes and generalized shor codes

Pradeep Kiran Sarvepalli, Andreas Klappenecker, Martin Rötteler

In this paper we give new decoding algorithms for the generalized Shor codes and a class of subsystem codes due to Bacon and Casaccino. Our interest in these codes stems from the fact these codes can allow us to construct quantum codes from non-dual containing codes. In this paper we show how to decode these codes efficiently.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•1 citation

Asymmetric and Symmetric Subsystem BCH Codes and Beyond

Salah A. Aly

Recently, the theory of quantum error control codes has been extended to subsystem codes over symmetric and asymmetric quantum channels -- qubit-flip and phase-shift errors may have equal or different probabilities. Previous work in constructing quantum error control codes has focused on code constructions for symmetric quantum channels. In this paper, we develop a theory and establish the connection between asymmetric quantum codes and subsystem codes. We present families of subsystem and asymmetric quantum codes derived, once again, from classical BCH and RS codes over finite fields. Particularly, we derive an interesting asymmetric and symmetric subsystem codes based on classical BCH codes with parameters $[[n,k,r,d]]_q$, $[[n,k,r,d_z/d_x]]_q$ and $[[n,k',0,d_z/d_x]]_q$ for arbitrary values of code lengths and dimensions. We establish asymmetric Singleton and Hamming bounds on asymmetric quantum and subsystem code parameters; and derive optimal asymmetric MDS subsystem codes. Finally, our constructions are well explained by an illustrative example. This paper is written on the occasion of the 50th anniversary of the discovery of classical BCH codes and their quantum counterparts were derived nearly 10 years ago.

arXiv:0803.0764•Mar 6, 2008•11 citations
Given any two classical codes with parameters [n1,k,d1][{n}_{1},k,{d}_{1}][n1​,k,d1​] and [n2,k,d2][{n}_{2},k,{d}_{2}][n2​,k,d2​], we show how to construct a quantum subsystem code in two dimensions with parameters [[N,K,D]][[N,K,D]][[N,K,D]] satisfying N\ensuremath≤2n1n2,K=kN\ensuremath{\le}2{n}_{1}{n}_{2}, K=kN\ensuremath≤2n1​n2​,K=k, and D=min(d1,d2)D=min({d}_{1},{d}_{2})D=min(d1​,d2​). 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)KD=O(N)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.
We provide a numerical investigation of two families of subsystem quantum codes that are related to hypergraph product codes by gauge-fixing. The first family consists of the Bravyi-Bacon-Shor (BBS) codes which have optimal code parameters for subsystem quantum codes local in 2-dimensions. The second family consists of the constant rate “generalized Shor” codes of Bacon and Cassicino [1], which we re-brand as subsystem hypergraph product (SHP) codes. We show that any hypergraph product code can be obtained by entangling the gauge qubits of two SHP codes. To evaluate the performance of these codes, we simulate both small and large examples. For circuit noise, a [21], [4], [3] BBS code and a [49], [16], [3] SHP code have pseudthresholds of 2 × 10-3and 8 × 10-4, respectively. Simulations for phenomenological noise show that large BBS and SHP codes start to outperform surface codes with similar encoding rate at physical error rates 1 × 10-6and 4 × 10-4, respectively.
We study subsystem codes whose gauge group has local generators in two-dimensional (2D) geometry. It is shown that there exists a family of such codes defined on lattices of size $L\ifmmode\times\else\texttimes\fi{}L$ with the number of logical qubits kkk and the minimum distance ddd both proportional to LLL. The gauge group of these codes involves only two-qubit generators of type XX\mathit{XX}XX and ZZ\mathit{ZZ}ZZ coupling nearest-neighbor qubits (and some auxiliary one-qubit generators). Our proof is not constructive as it relies on a certain version of the Gilbert-Varshamov bound for classical codes. Along the way, we introduce and study properties of generalized Bacon-Shor codes that might be of independent interest. Secondly, we prove that any 2D subsystem [n,k,d][n,k,d][n,k,d] code with spatially local generators obeys upper bounds kd=O(n)\mathit{kd}=O(n)kd=O(n) and d2=O(n){d}^{2}=O(n)d2=O(n). The analogous upper bound proved recently for 2D stabilizer codes is kd2=O(n){\mathit{kd}}^{2}=O(n)kd2=O(n). Our results thus demonstrate that subsystem codes can be more powerful than stabilizer codes under the spatial locality constraint.
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]][[n,k,d]][[n,k,d]] quantum stabilizer code with 2D-locality must satisfy kd2≤O(n)kd^2\le O(n)kd2≤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,dn,k,dn,k,d: above the BPT bound, any 2D-embedding must have at least Ω(#∗)Ω(\#^*)Ω(#∗) interactions of length Ω(ℓ∗)Ω(\ell^*)Ω(ℓ∗), where #∗=max⁡(k,d)\#^*= \max(k,d)#∗=max(k,d) and ℓ∗=max⁡(dn,(kd2n)1/4)\ell^*=\max\big(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)ℓ∗=max(n​d​,(nkd2​)1/4). 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,dn,k,dn,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 ddd and dimension kkk, the number of long-range interactions is asymptotically minimized by a good qLDPC code of length Θ(max⁡(k,d))Θ(\max(k,d))Θ(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.
In this paper, we introduce a new family of stabilizer quantum LDPC codes derived from the classical linear codes LkL_kLk​ and Lk+L_k^{+}Lk+​, defined via sub-exceding functions. In previous work, these codes demonstrated strong performance in minimum distance, decoding efficiency, and structural simplicity. By combining the hypergraph product framework with a generalized Shor construction, we obtain a scalable class of quantum codes with parameters [[6k2, k2, d]][[6k^2,\, k^2,\, d]][[6k2,k2,d]]. The resulting quantum codes exhibit a rich combinatorial structure and promising properties, particularly in terms of locality, low-density parity-check (LDPC) structure, and asymptotic behavior. The minimum distance satisfies d=3d=3d=3 for k=3k=3k=3 and d=4d=4d=4 for k≥4k\ge4k≥4, establishing a new framework for structured quantum LDPC code design and optimization.
Recently, the theory of quantum error control codes has been extended to subsystem codes over symmetric and asymmetric quantum channels -- qubit-flip and phase-shift errors may have equal or different probabilities. Previous work in constructing quantum error control codes has focused on code constructions for symmetric quantum channels. In this paper, we develop a theory and establish the connection between asymmetric quantum codes and subsystem codes. We present families of subsystem and asymmetric quantum codes derived, once again, from classical BCH and RS codes over finite fields. Particularly, we derive an interesting asymmetric and symmetric subsystem codes based on classical BCH codes with parameters [[n,k,r,d]]q[[n,k,r,d]]_q[[n,k,r,d]]q​, [[n,k,r,dz/dx]]q[[n,k,r,d_z/d_x]]_q[[n,k,r,dz​/dx​]]q​ and [[n,k′,0,dz/dx]]q[[n,k',0,d_z/d_x]]_q[[n,k′,0,dz​/dx​]]q​ for arbitrary values of code lengths and dimensions. We establish asymmetric Singleton and Hamming bounds on asymmetric quantum and subsystem code parameters; and derive optimal asymmetric MDS subsystem codes. Finally, our constructions are well explained by an illustrative example. This paper is written on the occasion of the 50th anniversary of the discovery of classical BCH codes and their quantum counterparts were derived nearly 10 years ago.