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:1408.1720 · Physical Review A

Fault-tolerant logical gates in quantum error-correcting codes

Fernando Pastawski, Beni Yoshida

Published Jan 8, 2015• 103 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.91.012305

Related papers

Clifford Hierarchy Stabilizer Codes: Transversal Non-Clifford Gates and Magic

Ryohei Kobayashi, Guanyu Zhu, Po-Shen Hsin

A fundamental problem in fault-tolerant quantum computation is the tradeoff between universality and dimensionality, exemplified by the the Bravyi-König bound for $n$-dimensional topological stabilizer codes. In this work, we extend topological Pauli stabilizer codes to a broad class of $n$-dimensional Clifford hierarchy stabilizer codes. These codes correspond to the $(n+1)$D Dijkgraaf-Witten gauge theories with non-Abelian topological order. We construct transversal non-Clifford gates through automorphism symmetries represented by cup products. In 2D, we obtain the first transversal non-Clifford logical gates including T and CS for Clifford stabilizer codes, using the automorphism of the twisted $\mathbb{Z}_2^3$ gauge theory (equivalent to $\mathbb{D}_4$ topological order). We also combine it with the just-in-time decoder to fault-tolerantly prepare the logical T magic state in $O(d)$ rounds via code switching. In 3D, we construct a transversal logical $\sqrt{\text{T}}$ gate in a non-Clifford stabilizer code at the third level of the Clifford hierarchy, located on a tetrahedron corresponding to a twisted $\mathbb{Z}_2^4$ gauge theory. Our constructions surpass the Bravyi-König bound by achieving the logical gates in the $(n+1)$-th level of Clifford hierarchy in $n$ spatial dimension.

quant-pharXiv:2511.02900•Physical Review Letters•Nov 6, 2025•1 citation

Intrinsic locality dimension of quantum codes

Yimin Lu, Esther Xiaozhen Fu, Zi-Wen Liu

Quantum error-correcting codes are a cornerstone of quantum computing, with broad and profound connections to physics and mathematics. In this work, we introduce the notion of intrinsic locality dimension of stabilizer codes, which is independent of the underlying geometry of quantum codes and naturally extends to non-integer values. Drawing on mathematical tools from fractal geometry and geometric measure theory, the intrinsic locality dimension accommodates flexible architectures and provides a quantitative measure of code connectivity, encompassing both topological codes and algebraic constructions such as bivariate-bicycle-type codes. We show how the intrinsic dimension serves as a fundamental organizing parameter that unifies code properties. In particular, we prove general limitations on code parameters and compatible fault-tolerant logical gates induced by the intrinsic dimension, generalizing the Bravyi--Poulin--Terhal and Bravyi--König bounds for regular topological codes, respectively. Furthermore, we consider implications on thermal properties: toward fully characterizing the geometry requirement for self-correcting quantum memories (SCQMs), we present a conditional no-go result for SCQMs in dimension $3-ε$ and take stock of existing results on low-dimensional SCQMs. Our theory provides a unifying mathematical framework for understanding the fundamental capabilities and geometric implementations of quantum error correction and fault tolerance.

quant-pharXiv:2605.31441•Jun 1, 2026•0 citations

No-go theorems for logical gates on product quantum codes

Xiaojun Fu, Han Zheng, Zimu Li +1 more

Quantum error-correcting codes are essential to the implementation of fault-tolerant quantum computation. Homological products of classical codes offer a versatile framework for constructing quantum error-correcting codes with desirable properties, especially quantum low-density parity check (qLDPC) codes. Based on extensions of the Bravyi--König theorem that encompass codes without geometric locality, we establish a series of general no-go theorems for fault-tolerant logical gates supported by hypergraph product codes. Specifically, we show that non-Clifford logical gates cannot be implemented transversally on hypergraph product codes of all product dimensions, and that the dimensions impose various limitations on the accessible level of the Clifford hierarchy gates by constant-depth local circuits. We also discuss examples both with and without geometric locality which attain the Clifford hierarchy bounds. Our results reveal fundamental restrictions on logical gates originating from highly general algebraic structures, extending beyond existing knowledge only in geometrically local, finite logical qubits, transversal, or 2-dimensional product cases, and may guide the vital study of fault-tolerant quantum computation with qLDPC codes.

arXiv:2507.16797•Jul 22, 2025•0 citations

Gauge Color Codes

Héctor Bombín

In fault-tolerant quantum computation [1], quantum information is protected from noise by encoding it in somewhat non-local degrees of freedom, thus distributing it among many smaller subsystems, typically qubits. This makes sense under the physically relevant assumption that interactions with the environment have a local nature. The implementation of gates, consequently, must be also as local as possible to preserve the structure of noise. This is naturally achieved with transversal gates, i.e. unitary operators that transform encoded states by acting separately on suitable subsystems, in the simplest case independently on each qubit. Unfortunately, no code admits a universal transversal set of gates [2]. Topological quantum error correcting codes [3] introduce a richer notion of locality by considering the spatial location of the physical qubits, which are assumed to be arranged on a lattice. They come in families parametrized with a lattice size, for a fixed spatial dimension. Their defining features are (i) that the measurements needed to recover information about errors only involve a few neighbouring qubits and (ii) that no encoded information can be recovered without access to a number of physical qubits comparable to the system size. Rather than sticking to the above definition of transversality, for topological codes it is natural to consider instead quantum circuits of fixed depth with geometrically local gates [4, 5]. Remarkably, it has been recently shown that spatial dimension imposes constraints on the transversal gates that are allowed [5]. In particular, this is true in the case of topological stabilizer codes, where it has been found that transversal gates on D-dimensional codes have to belong to certain sets PD. A first main result of this work [6] is that codes that saturate these bounds can be constructed for every D, in the sense that they admit at least a transversal gate in PD (not belonging to PD−1). In particular, the result applies to color codes [7, 8, 9, 10], where the single-qubit gate RD := ( 1 0 0 e2πi/2 D ) is transversal (in the more strict non-topological sense).

•Nov 4, 2013•2 citations

No-Go Theorem on Fault Tolerant Gadgets for Multiple Logical Qubits

Aranya Chakraborty, Daniel Gottesman

Identifying stabilizer codes that admit fault-tolerant implementations of the full logical Clifford group would significantly advance fault-tolerant quantum computation. Motivated by this goal, we study several classes of fault-tolerant gadget constructions consisting of Clifford gates acting on the physical qubits, including transversal gadgets, code automorphisms, and fold-transversal gadgets. While stabilizer codes encoding a single logical qubit, most notably the [[7,1,3]] Steane code, are known to admit transversal implementations of the full logical Clifford group, no analogous examples are known for codes encoding multiple logical qubits. In this work, we prove a no-go theorem establishing that no stabilizer code admits a fully transversal implementation of the Clifford group on more than one logical qubit. We further strengthen this result by showing that fold-transversal implementations of the full logical Clifford group are impossible for stabilizer codes encoding more than two logical qubits. More generally, we introduce the notion of k-fold transversal gadgets and prove that implementing the full Clifford group on k logical qubits requires at least k-fold transversal gadgets at the physical level. In addition, we analyze code-automorphism based constructions and demonstrate that they also fail to realize the full Clifford group on multiple logical qubits for any stabilizer code. Together, these results place fundamental constraints on fault-tolerant Clifford gadget design and show that stabilizer codes supporting the full logical Clifford group on multiple logical qubits via these architectures do not exist. Since the Clifford group is a core component of universal gate sets, our findings imply that quantum computing with codes encoding multiple logical qubits within a single code block necessarily entails more complex constructions for fault tolerance.

quant-pharXiv:2602.13395•PRX Quantum•Feb 17, 2026•0 citations

Quantum Logic Codes: Complete Transversal Logical Clifford Instruction Sets for High-Rate Stabilizer Quantum Error Correcting Codes

Adam Holmes

We study the structure and transversal logical capabilities of stabilizer quantum error correcting codes. Among our results, we identify universal lower bounds on circuit depth to generate a full logical Clifford algebra, and develop novel constructions of logical transversal gates including a new depth-one transversal phase $\mathrm{\overline{S}}$ gate in the rotated surface code and a depth-one intra-block $\mathrm{\overline{CZ}}$ gate in the 2D-toric code that generalizes to all odd distances and all lengths $L\ge3$, respectively. Finally, we construct a high-rate non-LDPC CSS code family with parameters $[[n,\sqrt{n},Θ({n^β})]]$ where $β\approx 0.2823$ in one demonstrated case, that provably possesses a constant-depth complete 2-local transversal logical Clifford basis instruction set architecture (ISA) composed of all individually targeted $\mathrm{\overline{S}}$, $\mathrm{\overline{SHS}} = \sqrt{X}$, and $\mathrm{\overline{CZ}}$ gates. This ISA is depth-one for certain subfamilies that we design and generally constant-depth under certain conditions. The code family is built from a small code with parameters $[[n_0, 2, d_0]]$, and is tunable in the standard way: it tiles out to form utility-scale logical qubit counts, and it scales up through concatenation to achieve higher distances and error suppression. We show that this construction preserves the depth-one complete transversal logical Clifford basis ISA when composed with these commuting construction actions, inheriting structure from the core codes so that at scale the complete logical Clifford basis ISA remains depth-one up to depth-two addressable operations between tiled cores. We call these Quantum Logic Codes.

quant-pharXiv:2606.13521•Jun 12, 2026•0 citations
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(LD+1\ensuremath−m)O({L}^{D+1\ensuremath{-}m})O(LD+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.
A fundamental problem in fault-tolerant quantum computation is the tradeoff between universality and dimensionality, exemplified by the the Bravyi-König bound for nnn-dimensional topological stabilizer codes. In this work, we extend topological Pauli stabilizer codes to a broad class of nnn-dimensional Clifford hierarchy stabilizer codes. These codes correspond to the (n+1)(n+1)(n+1)D Dijkgraaf-Witten gauge theories with non-Abelian topological order. We construct transversal non-Clifford gates through automorphism symmetries represented by cup products. In 2D, we obtain the first transversal non-Clifford logical gates including T and CS for Clifford stabilizer codes, using the automorphism of the twisted Z23\mathbb{Z}_2^3Z23​ gauge theory (equivalent to D4\mathbb{D}_4D4​ topological order). We also combine it with the just-in-time decoder to fault-tolerantly prepare the logical T magic state in O(d)O(d)O(d) rounds via code switching. In 3D, we construct a transversal logical T\sqrt{\text{T}}T​ gate in a non-Clifford stabilizer code at the third level of the Clifford hierarchy, located on a tetrahedron corresponding to a twisted Z24\mathbb{Z}_2^4Z24​ gauge theory. Our constructions surpass the Bravyi-König bound by achieving the logical gates in the (n+1)(n+1)(n+1)-th level of Clifford hierarchy in nnn spatial dimension.
Quantum error-correcting codes are a cornerstone of quantum computing, with broad and profound connections to physics and mathematics. In this work, we introduce the notion of intrinsic locality dimension of stabilizer codes, which is independent of the underlying geometry of quantum codes and naturally extends to non-integer values. Drawing on mathematical tools from fractal geometry and geometric measure theory, the intrinsic locality dimension accommodates flexible architectures and provides a quantitative measure of code connectivity, encompassing both topological codes and algebraic constructions such as bivariate-bicycle-type codes. We show how the intrinsic dimension serves as a fundamental organizing parameter that unifies code properties. In particular, we prove general limitations on code parameters and compatible fault-tolerant logical gates induced by the intrinsic dimension, generalizing the Bravyi--Poulin--Terhal and Bravyi--König bounds for regular topological codes, respectively. Furthermore, we consider implications on thermal properties: toward fully characterizing the geometry requirement for self-correcting quantum memories (SCQMs), we present a conditional no-go result for SCQMs in dimension 3−ε3-ε3−ε and take stock of existing results on low-dimensional SCQMs. Our theory provides a unifying mathematical framework for understanding the fundamental capabilities and geometric implementations of quantum error correction and fault tolerance.
Quantum error-correcting codes are essential to the implementation of fault-tolerant quantum computation. Homological products of classical codes offer a versatile framework for constructing quantum error-correcting codes with desirable properties, especially quantum low-density parity check (qLDPC) codes. Based on extensions of the Bravyi--König theorem that encompass codes without geometric locality, we establish a series of general no-go theorems for fault-tolerant logical gates supported by hypergraph product codes. Specifically, we show that non-Clifford logical gates cannot be implemented transversally on hypergraph product codes of all product dimensions, and that the dimensions impose various limitations on the accessible level of the Clifford hierarchy gates by constant-depth local circuits. We also discuss examples both with and without geometric locality which attain the Clifford hierarchy bounds. Our results reveal fundamental restrictions on logical gates originating from highly general algebraic structures, extending beyond existing knowledge only in geometrically local, finite logical qubits, transversal, or 2-dimensional product cases, and may guide the vital study of fault-tolerant quantum computation with qLDPC codes.
In fault-tolerant quantum computation [1], quantum information is protected from noise by encoding it in somewhat non-local degrees of freedom, thus distributing it among many smaller subsystems, typically qubits. This makes sense under the physically relevant assumption that interactions with the environment have a local nature. The implementation of gates, consequently, must be also as local as possible to preserve the structure of noise. This is naturally achieved with transversal gates, i.e. unitary operators that transform encoded states by acting separately on suitable subsystems, in the simplest case independently on each qubit. Unfortunately, no code admits a universal transversal set of gates [2]. Topological quantum error correcting codes [3] introduce a richer notion of locality by considering the spatial location of the physical qubits, which are assumed to be arranged on a lattice. They come in families parametrized with a lattice size, for a fixed spatial dimension. Their defining features are (i) that the measurements needed to recover information about errors only involve a few neighbouring qubits and (ii) that no encoded information can be recovered without access to a number of physical qubits comparable to the system size. Rather than sticking to the above definition of transversality, for topological codes it is natural to consider instead quantum circuits of fixed depth with geometrically local gates [4, 5]. Remarkably, it has been recently shown that spatial dimension imposes constraints on the transversal gates that are allowed [5]. In particular, this is true in the case of topological stabilizer codes, where it has been found that transversal gates on D-dimensional codes have to belong to certain sets PD. A first main result of this work [6] is that codes that saturate these bounds can be constructed for every D, in the sense that they admit at least a transversal gate in PD (not belonging to PD−1). In particular, the result applies to color codes [7, 8, 9, 10], where the single-qubit gate RD := ( 1 0 0 e2πi/2 D ) is transversal (in the more strict non-topological sense).
Identifying stabilizer codes that admit fault-tolerant implementations of the full logical Clifford group would significantly advance fault-tolerant quantum computation. Motivated by this goal, we study several classes of fault-tolerant gadget constructions consisting of Clifford gates acting on the physical qubits, including transversal gadgets, code automorphisms, and fold-transversal gadgets. While stabilizer codes encoding a single logical qubit, most notably the [[7,1,3]] Steane code, are known to admit transversal implementations of the full logical Clifford group, no analogous examples are known for codes encoding multiple logical qubits. In this work, we prove a no-go theorem establishing that no stabilizer code admits a fully transversal implementation of the Clifford group on more than one logical qubit. We further strengthen this result by showing that fold-transversal implementations of the full logical Clifford group are impossible for stabilizer codes encoding more than two logical qubits. More generally, we introduce the notion of k-fold transversal gadgets and prove that implementing the full Clifford group on k logical qubits requires at least k-fold transversal gadgets at the physical level. In addition, we analyze code-automorphism based constructions and demonstrate that they also fail to realize the full Clifford group on multiple logical qubits for any stabilizer code. Together, these results place fundamental constraints on fault-tolerant Clifford gadget design and show that stabilizer codes supporting the full logical Clifford group on multiple logical qubits via these architectures do not exist. Since the Clifford group is a core component of universal gate sets, our findings imply that quantum computing with codes encoding multiple logical qubits within a single code block necessarily entails more complex constructions for fault tolerance.
We study the structure and transversal logical capabilities of stabilizer quantum error correcting codes. Among our results, we identify universal lower bounds on circuit depth to generate a full logical Clifford algebra, and develop novel constructions of logical transversal gates including a new depth-one transversal phase S‾\mathrm{\overline{S}}S gate in the rotated surface code and a depth-one intra-block CZ‾\mathrm{\overline{CZ}}CZ gate in the 2D-toric code that generalizes to all odd distances and all lengths L≥3L\ge3L≥3, respectively. Finally, we construct a high-rate non-LDPC CSS code family with parameters [[n,n,Θ(nβ)]][[n,\sqrt{n},Θ({n^β})]][[n,n​,Θ(nβ)]] where β≈0.2823β\approx 0.2823β≈0.2823 in one demonstrated case, that provably possesses a constant-depth complete 2-local transversal logical Clifford basis instruction set architecture (ISA) composed of all individually targeted S‾\mathrm{\overline{S}}S, SHS‾=X\mathrm{\overline{SHS}} = \sqrt{X}SHS=X​, and CZ‾\mathrm{\overline{CZ}}CZ gates. This ISA is depth-one for certain subfamilies that we design and generally constant-depth under certain conditions. The code family is built from a small code with parameters [[n0,2,d0]][[n_0, 2, d_0]][[n0​,2,d0​]], and is tunable in the standard way: it tiles out to form utility-scale logical qubit counts, and it scales up through concatenation to achieve higher distances and error suppression. We show that this construction preserves the depth-one complete transversal logical Clifford basis ISA when composed with these commuting construction actions, inheriting structure from the core codes so that at scale the complete logical Clifford basis ISA remains depth-one up to depth-two addressable operations between tiled cores. We call these Quantum Logic Codes.