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:0810.1983 · New Journal of Physics

A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes

Sergey B. Bravyi, Barbara M. Terhal

Published Apr 24, 2009• 257 citations
arXivHTMLPDF

Abstract

We study properties of stabilizer codes that permit a local description on a regular D -dimensional lattice. Specifically, we assume that the stabilizer group of a code (the gauge group for subsystem codes) can be generated by local Pauli operators such that the support of any generator is bounded by a hypercube of size O (1). Our first result concerns the optimal scaling of the distance d with the linear size of the lattice L . We prove an upper bound d = O ( L D -1 ) which is tight for D =1, 2. This bound applies to both subspace and subsystem stabilizer codes. Secondly, we analyze the suitability of stabilizer codes for building a self-correcting quantum memory. Any stabilizer code with geometrically local generators can be naturally transformed to a local Hamiltonian penalizing states that violate the stabilizer condition. A degenerate ground state of this Hamiltonian corresponds to the logical subspace of the code. We prove that for D =1, 2, different logical states can be mapped into each other by a sequence of single-qubit Pauli errors such that the energy of all intermediate states is upper bounded by a constant independent of the lattice size L . The same result holds if there are unused logical qubits that are treated as 'gauge qubits'. It demonstrates that a self-correcting quantum memory cannot be built using stabilizer codes in dimensions D =1, 2. This result is in sharp contrast with the existence of a classical self-correcting memory in the form of a two-dimensional (2D) ferromagnet. Our results leave open the possibility for a self-correcting quantum memory based on 2D subsystem codes or on 3D subspace or subsystem codes.

DOI
10.1088/1367-2630/11/4/043029

Related papers

Stabilizer subsystem codes with spatially local generators

Sergey B. Bravyi

We derive new tradeoffs for reliable quantum information storage in a 2D local architecture based on subsystem quantum codes. Our results apply to stabilizer subsystem codes, that is, stabilizer codes in which part of the logical qubits does not encode any information. A stabilizer subsystem code can be specified by its gauge group - a subgroup of the Pauli group that includes the stabilizers and the logical operators on the unused logical qubits. We assume that the physical qubits are arranged on a two-dimensional grid and the gauge group has spatially local generators such that each generator acts only on a few qubits located close to each other. Our main result is an upper bound kd = O(n), where k is the number of encoded qubits, d is the minimal distance, and n is the number of physical qubits. In the special case when both gauge group and the stabilizer group have spatially local generators, we derive a stronger bound kd2= O(n) which is tight up to a constant factor.

IEEE Information Theory Workshop (ITW)•Aug 1, 2010•4 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•54 citations

Topological subsystem codes

Héctor Bombín

We introduce a family of two-dimensional (2D) topological subsystem quantum error-correcting codes. The gauge group is generated by two-local Pauli operators, so that two-local measurements are enough to recover the error syndrome. We study the computational power of code deformation in these codes and show that boundaries cannot be introduced in the usual way. In addition, we give a general mapping connecting suitable classical statistical mechanical models to optimal error correction in subsystem stabilizer codes that suffer from depolarizing noise.

arXiv:0908.4246•Physical Review A•Mar 3, 2010•122 citations

Topological approach toward quantum codes with realistic physical constraints

Beni Yoshida

The following open problems, which concern a fundamental limit on coding properties of quantum codes with realistic physical constraints, are analyzed and partially answered here: (a) the upper bound on code distances of quantum error-correcting codes with geometrically local generators, (b) the feasibility of a self-correcting quantum memory. To investigate these problems, we study stabilizer codes supported by local interaction terms with translation and scale symmetries on a $D$-dimensional lattice. Our analysis uses the notion of topology emerging in geometric shapes of logical operators, which sheds a surprising new light on theory of quantum codes with physical constraints.

arXiv:1010.3282•Oct 15, 2010•0 citations

Fault-tolerant logical gates in quantum error-correcting codes

Fernando Pastawski, Beni Yoshida

Recently, S. Bravyi and R. K\"onig [Phys. Rev. Lett. 110, 170503 (2013)] have shown that there is a trade-off between fault-tolerantly implementable logical gates and geometric locality of stabilizer codes. They consider locality-preserving operations which are implemented by a constant-depth geometrically local circuit and are thus fault tolerant by construction. In particular, they show that, for local stabilizer codes in $D$ spatial dimensions, locality-preserving gates are restricted to a set of unitary gates known as the $D\mathrm{th}$ level of the Clifford hierarchy. In this paper, we explore this idea further by providing several extensions and applications of their characterization to qubit stabilizer and subsystem codes. First, we present a no-go theorem for self-correcting quantum memory. Namely, we prove that a three-dimensional stabilizer Hamiltonian with a locality-preserving implementation of a non-Clifford gate cannot have a macroscopic energy barrier. This result implies that non-Clifford gates do not admit such implementations in Haah's cubic code and Michnicki's welded code. Second, we prove that the code distance of a $D$-dimensional local stabilizer code with a nontrivial locality-preserving $m\mathrm{th}$-level Clifford logical gate is upper bounded by $O({L}^{D+1\ensuremath{-}m})$. For codes with non-Clifford gates ($m>2$), this improves the previous best bound by S. Bravyi and B. Terhal [New. J. Phys. 11, 043029 (2009)]. Topological color codes, introduced by H. Bombin and M. A. Martin-Delgado [Phys. Rev. Lett. 97, 180501 (2006); Phys. Rev. Lett. 98, 160502 (2007); Phys. Rev. B 75, 075103 (2007)], saturate the bound for $m=D$. Third, we prove that the qubit erasure threshold for codes with a nontrivial transversal $m\mathrm{th}$-level Clifford logical gate is upper bounded by $1/m$. This implies that no family of fault-tolerant codes with transversal gates in increasing level of the Clifford hierarchy may exist. This result applies to arbitrary stabilizer and subsystem codes and is not restricted to geometrically local codes. Fourth, we extend the result of Bravyi and K\"onig to subsystem codes. Unlike stabilizer codes, the so-called union lemma does not apply to subsystem codes. This problem is avoided by assuming the presence of an error threshold in a subsystem code, and a conclusion analogous to that of Bravyi and K\"onig is recovered.

arXiv:1408.1720•Physical Review A•Jan 8, 2015•103 citations

Stabilizer codes over general phase spaces

Sayan Chakraborty, Victor V. Albert

We develop a theory of stabilizer codes whose stabilizer groups consist of commuting qudit Paulis, oscillator displacements, and/or planar-rotor displacements. We consider codes whose stabilizer groups form generalized lattices in quantum phase space, a condition that guarantees a finite logical dimension. We construct oscillator-rotor, rotor-qudit, and oscillator-rotor-qubit codes that cannot be decomposed into separate subsystems by generalized Clifford transformations. We also introduce an oscillator-qubit code arising from a partially lifted Golay code, where Construction A is applied to half of the Golay code coordinates. We derive analytical forms of logical operators from the symplectic dual lattice, determine Clifford-Gaussian gates from lattice symmetries, show that the code dimension equals the covolume of the stabilizer lattice, and organize the syndrome subspaces into a vector bundle. Our technique builds on earlier non-commutative geometric results by Rieffel, but it can often be interpreted simply as concatenating a given stabilizer code with a Gottesman-Kitaev-Preskill (GKP) code, applying conventional lattice-theoretic results, and unconcatenating. We formulate distances, optimal decoding, and quantum weight enumerators, recovering the Pauli, qudit, and GKP versions together with known MacWilliams identities. We construct finite-energy codewords whose encoding is an isometry up to an error exponentially small in the inverse damping parameter.

quant-pharXiv:2610.04694•Oct 6, 2026•0 citations
We study properties of stabilizer codes that permit a local description on a regular D -dimensional lattice. Specifically, we assume that the stabilizer group of a code (the gauge group for subsystem codes) can be generated by local Pauli operators such that the support of any generator is bounded by a hypercube of size O (1). Our first result concerns the optimal scaling of the distance d with the linear size of the lattice L . We prove an upper bound d = O ( L D -1 ) which is tight for D =1, 2. This bound applies to both subspace and subsystem stabilizer codes. Secondly, we analyze the suitability of stabilizer codes for building a self-correcting quantum memory. Any stabilizer code with geometrically local generators can be naturally transformed to a local Hamiltonian penalizing states that violate the stabilizer condition. A degenerate ground state of this Hamiltonian corresponds to the logical subspace of the code. We prove that for D =1, 2, different logical states can be mapped into each other by a sequence of single-qubit Pauli errors such that the energy of all intermediate states is upper bounded by a constant independent of the lattice size L . The same result holds if there are unused logical qubits that are treated as 'gauge qubits'. It demonstrates that a self-correcting quantum memory cannot be built using stabilizer codes in dimensions D =1, 2. This result is in sharp contrast with the existence of a classical self-correcting memory in the form of a two-dimensional (2D) ferromagnet. Our results leave open the possibility for a self-correcting quantum memory based on 2D subsystem codes or on 3D subspace or subsystem codes.
We derive new tradeoffs for reliable quantum information storage in a 2D local architecture based on subsystem quantum codes. Our results apply to stabilizer subsystem codes, that is, stabilizer codes in which part of the logical qubits does not encode any information. A stabilizer subsystem code can be specified by its gauge group - a subgroup of the Pauli group that includes the stabilizers and the logical operators on the unused logical qubits. We assume that the physical qubits are arranged on a two-dimensional grid and the gauge group has spatially local generators such that each generator acts only on a few qubits located close to each other. Our main result is an upper bound kd = O(n), where k is the number of encoded qubits, d is the minimal distance, and n is the number of physical qubits. In the special case when both gauge group and the stabilizer group have spatially local generators, we derive a stronger bound kd2= O(n) which is tight up to a constant factor.
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.
We introduce a family of two-dimensional (2D) topological subsystem quantum error-correcting codes. The gauge group is generated by two-local Pauli operators, so that two-local measurements are enough to recover the error syndrome. We study the computational power of code deformation in these codes and show that boundaries cannot be introduced in the usual way. In addition, we give a general mapping connecting suitable classical statistical mechanical models to optimal error correction in subsystem stabilizer codes that suffer from depolarizing noise.
The following open problems, which concern a fundamental limit on coding properties of quantum codes with realistic physical constraints, are analyzed and partially answered here: (a) the upper bound on code distances of quantum error-correcting codes with geometrically local generators, (b) the feasibility of a self-correcting quantum memory. To investigate these problems, we study stabilizer codes supported by local interaction terms with translation and scale symmetries on a DDD-dimensional lattice. Our analysis uses the notion of topology emerging in geometric shapes of logical operators, which sheds a surprising new light on theory of quantum codes with physical constraints.
Recently, S. Bravyi and R. K\"onig [Phys. Rev. Lett. 110, 170503 (2013)] have shown that there is a trade-off between fault-tolerantly implementable logical gates and geometric locality of stabilizer codes. They consider locality-preserving operations which are implemented by a constant-depth geometrically local circuit and are thus fault tolerant by construction. In particular, they show that, for local stabilizer codes in DDD spatial dimensions, locality-preserving gates are restricted to a set of unitary gates known as the DthD\mathrm{th}Dth level of the Clifford hierarchy. In this paper, we explore this idea further by providing several extensions and applications of their characterization to qubit stabilizer and subsystem codes. First, we present a no-go theorem for self-correcting quantum memory. Namely, we prove that a three-dimensional stabilizer Hamiltonian with a locality-preserving implementation of a non-Clifford gate cannot have a macroscopic energy barrier. This result implies that non-Clifford gates do not admit such implementations in Haah's cubic code and Michnicki's welded code. Second, we prove that the code distance of a DDD-dimensional local stabilizer code with a nontrivial locality-preserving mthm\mathrm{th}mth-level Clifford logical gate is upper bounded by $O({L}^{D+1\ensuremath{-}m})$. For codes with non-Clifford gates (m>2m>2m>2), this improves the previous best bound by S. Bravyi and B. Terhal [New. J. Phys. 11, 043029 (2009)]. Topological color codes, introduced by H. Bombin and M. A. Martin-Delgado [Phys. Rev. Lett. 97, 180501 (2006); Phys. Rev. Lett. 98, 160502 (2007); Phys. Rev. B 75, 075103 (2007)], saturate the bound for m=Dm=Dm=D. Third, we prove that the qubit erasure threshold for codes with a nontrivial transversal mthm\mathrm{th}mth-level Clifford logical gate is upper bounded by 1/m1/m1/m. This implies that no family of fault-tolerant codes with transversal gates in increasing level of the Clifford hierarchy may exist. This result applies to arbitrary stabilizer and subsystem codes and is not restricted to geometrically local codes. Fourth, we extend the result of Bravyi and K\"onig to subsystem codes. Unlike stabilizer codes, the so-called union lemma does not apply to subsystem codes. This problem is avoided by assuming the presence of an error threshold in a subsystem code, and a conclusion analogous to that of Bravyi and K\"onig is recovered.
We develop a theory of stabilizer codes whose stabilizer groups consist of commuting qudit Paulis, oscillator displacements, and/or planar-rotor displacements. We consider codes whose stabilizer groups form generalized lattices in quantum phase space, a condition that guarantees a finite logical dimension. We construct oscillator-rotor, rotor-qudit, and oscillator-rotor-qubit codes that cannot be decomposed into separate subsystems by generalized Clifford transformations. We also introduce an oscillator-qubit code arising from a partially lifted Golay code, where Construction A is applied to half of the Golay code coordinates. We derive analytical forms of logical operators from the symplectic dual lattice, determine Clifford-Gaussian gates from lattice symmetries, show that the code dimension equals the covolume of the stabilizer lattice, and organize the syndrome subspaces into a vector bundle. Our technique builds on earlier non-commutative geometric results by Rieffel, but it can often be interpreted simply as concatenating a given stabilizer code with a Gottesman-Kitaev-Preskill (GKP) code, applying conventional lattice-theoretic results, and unconcatenating. We formulate distances, optimal decoding, and quantum weight enumerators, recovering the Pauli, qudit, and GKP versions together with known MacWilliams identities. We construct finite-energy codewords whose encoding is an isometry up to an error exponentially small in the inverse damping parameter.