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:2507.16797

No-go theorems for logical gates on product quantum codes

Xiaojun Fu, Han Zheng, Zimu Li, Zi-Wen Liu

Published Jul 22, 2025• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.16797

Related papers

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•110 citations

Theory of (Co)homological Invariants on Quantum LDPC Codes

Zimu Li, Yuguo Shao, Fuchuan Wei +2 more

We establish a systematic mathematical framework for constructing and computing (co)homological invariants that induce logical gates on quantum low-density parity-check (qLDPC) codes. By synthesizing tools from graph theory, algebraic topology, and number theory, we study constructions ranging from hypergraph product (HGP) codes to sheaf codes. Using commutative algebra, we generalize the notion of canonical logical representatives from HGP codes to the sheaf code setting, resolving a longstanding challenge in explicitly characterizing sheaf codewords. Building on this foundation, we present the first comprehensive computation of cup products within the intricate framework of sheaf codes. Given Artin's primitive root conjecture which holds under the generalized Riemann hypothesis, {we establish a nearly linear family of independent cup product cochains on almost-good qLDPC codes. Under a separate nonvanishing pairing condition, they are expected to yield parallel logical multi-controlled-Z gates. Moreover, by interpreting sheaf codes as covering spaces of HGP codes, we construct interlaced families through odd-degree lifts that preserve compatible invariant pairings, allowing nontrivial, constant-depth logical gates throughout an infinite family to be certified on a constant-size HGP seed. Treating local code constructions and expansion bounds as external inputs, our framework identifies the compatibility conditions for combining large dimension and distance, local testability, and constant-depth non-Clifford gates, thereby provides a mathematical foundation for separate constructions that realize these properties simultaneously.

quant-pharXiv:2603.25831•Mar 30, 2026•10 citations

A topological theory for qLDPC: non-Clifford gates and magic state fountain on homological product codes with constant rate and beyond the $N^{1/3}$ distance barrier

Guanyu Zhu

We develop a topological theory for fault-tolerant quantum computation in quantum low-density parity-check (qLDPC) codes. We show that there exist hidden simplicial or CW complex structures encoding the topological data for all qLDPC and CSS codes obtained from product construction by generalizing the Freedman-Hastings code-to-manifold mapping. This is achieved by building manifolds from the Tanner graphs of the skeleton classical or quantum codes, which further form a product manifold and an associated thickened product code defined on its triangulation. One can further deformation retract the manifold back to a CW complex which supports a non-topological code with minimal overhead suitable for near-term implementation. Both types of codes admit cohomology operations including cup product which can induce non-Clifford gates. When applying this mapping to a 3D hypergraph product code obtained from the product of 3 copies of good classical expander codes, we obtain non-Clifford logical CCZ gates via constant depth circuits on a code with constant stabilizer weight $w=O(1)$, constant rate $K=Θ(N)$, and polynomial distance $D=Ω(N^{1/3})$. When applied to logical CCZ on 3D homological product codes consisting of the product of a pair of good quantum and classical LDPC codes, we can further improve the distance to $D=Ω(\sqrt{N})$ exceeding the $N^{1/3}$ distance barrier implied by the Bravyi-König bound for conventional topological codes with the aid of non-Euclidean geometries. Our work suggests that it is feasible to apply native logical non-Clifford gates on qLDPC codes or directly inject high-fidelity magic states as resources ('magic state fountain') without the distillation process. For the homological product construction, the fountain can inject $Θ(\sqrt{N})$ magic states in parallel in a single round.

arXiv:2501.19375•Jan 31, 2025•44 citations

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•27 citations

Non-Abelian qLDPC: TQFT Formalism, Addressable Gauging Measurement and Application to Magic State Fountain on 2D Product Codes

Guanyu Zhu, Ryohei Kobayashi, Po-Shen Hsin

A fundamental problem of fault-tolerant quantum computation with quantum low-density parity-check (qLDPC) codes is the tradeoff between connectivity and universality. It is widely believed that in order to perform native logical non-Clifford gates, one needs to resort to 3D product-code constructions. In this work, we extend Kitaev's framework of non-Abelian topological codes on manifolds to non-Abelian qLDPC codes (realized as Clifford-stabilizer codes) and the corresponding combinatorial topological quantum field theories (TQFT) defined on Poincaré CW complexes and certain types of general chain complexes. We also construct the spacetime path integrals as topological invariants on these complexes. Remarkably, we show that native non-Clifford logical gates can be realized using constant-rate 2D hypergraph-product codes and their Clifford-stabilizer variants. This is achieved by a spacetime path integral effectively implementing the addressable gauging measurement of a new type of 0-form subcomplex symmetries, which correspond to addressable transversal Clifford gates and become higher-form symmetries when lifted to higher-dimensional CW complexes or manifolds. Building on this structure, we apply the gauging protocol to the magic state fountain scheme for parallel preparation of $O(\sqrt{n})$ disjoint CZ magic states with code distance of $O(\sqrt{n})$, using a total number of $n$ qubits.

quant-pharXiv:2601.06736•Jan 13, 2026•24 citations

Fast and Parallelizable Logical Computation with Homological Product Codes

Qian Xu, Hengyun Zhou, Guo Zheng +4 more

Quantum error correction is necessary to perform large-scale quantum computation but requires extremely large overheads in both space and time. High-rate quantum low-density-parity-check (qLDPC) codes promise a route to reduce qubit numbers, but performing computation while maintaining low space cost has required serialization of operations and extra time costs. In this work, we design fast and parallelizable logical gates for qLDPC codes and demonstrate their utility for key algorithmic subroutines such as the quantum adder. Our gate gadgets utilize transversal logical s between a data qLDPC code and a suitably constructed ancilla code to perform parallel Pauli product measurements (PPMs) on the data logical qubits. For hypergraph product codes, we show that the ancilla can be constructed by simply modifying the base classical codes of the data code, achieving parallel PPMs on a subgrid of the logical qubits with a lower space-time cost than existing schemes for an important class of circuits. Generalizations to 3D and 4D homological product codes further feature fast PPMs in constant depth. While prior work on qLDPC codes has focused on individual logical gates, we initiate the study of fault-tolerant compilation with our expanded set of native qLDPC code operations, constructing algorithmic primitives for preparing k -qubit Greenberger-Horne-Zeilinger states and distilling or teleporting k magic states with O ( 1 ) space overhead in O ( 1 ) and O ( k log k ) logical cycles, respectively. We further generalize this to key algorithmic subroutines, demonstrating the efficient implementation of quantum adders using parallel operations. Our constructions are naturally compatible with reconfigurable architectures such as neutral atom arrays, paving the way to large-scale quantum computation with low space and time overheads.

arXiv:2407.18490•Physical Review X•May 22, 2025•64 citations
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.
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 establish a systematic mathematical framework for constructing and computing (co)homological invariants that induce logical gates on quantum low-density parity-check (qLDPC) codes. By synthesizing tools from graph theory, algebraic topology, and number theory, we study constructions ranging from hypergraph product (HGP) codes to sheaf codes. Using commutative algebra, we generalize the notion of canonical logical representatives from HGP codes to the sheaf code setting, resolving a longstanding challenge in explicitly characterizing sheaf codewords. Building on this foundation, we present the first comprehensive computation of cup products within the intricate framework of sheaf codes. Given Artin's primitive root conjecture which holds under the generalized Riemann hypothesis, {we establish a nearly linear family of independent cup product cochains on almost-good qLDPC codes. Under a separate nonvanishing pairing condition, they are expected to yield parallel logical multi-controlled-Z gates. Moreover, by interpreting sheaf codes as covering spaces of HGP codes, we construct interlaced families through odd-degree lifts that preserve compatible invariant pairings, allowing nontrivial, constant-depth logical gates throughout an infinite family to be certified on a constant-size HGP seed. Treating local code constructions and expansion bounds as external inputs, our framework identifies the compatibility conditions for combining large dimension and distance, local testability, and constant-depth non-Clifford gates, thereby provides a mathematical foundation for separate constructions that realize these properties simultaneously.
A topological theory for qLDPC: non-Clifford gates and magic state fountain on homological product codes with constant rate and beyond the N1/3N^{1/3}N1/3 distance barrier
We develop a topological theory for fault-tolerant quantum computation in quantum low-density parity-check (qLDPC) codes. We show that there exist hidden simplicial or CW complex structures encoding the topological data for all qLDPC and CSS codes obtained from product construction by generalizing the Freedman-Hastings code-to-manifold mapping. This is achieved by building manifolds from the Tanner graphs of the skeleton classical or quantum codes, which further form a product manifold and an associated thickened product code defined on its triangulation. One can further deformation retract the manifold back to a CW complex which supports a non-topological code with minimal overhead suitable for near-term implementation. Both types of codes admit cohomology operations including cup product which can induce non-Clifford gates. When applying this mapping to a 3D hypergraph product code obtained from the product of 3 copies of good classical expander codes, we obtain non-Clifford logical CCZ gates via constant depth circuits on a code with constant stabilizer weight w=O(1)w=O(1)w=O(1), constant rate K=Θ(N)K=Θ(N)K=Θ(N), and polynomial distance D=Ω(N1/3)D=Ω(N^{1/3})D=Ω(N1/3). When applied to logical CCZ on 3D homological product codes consisting of the product of a pair of good quantum and classical LDPC codes, we can further improve the distance to D=Ω(N)D=Ω(\sqrt{N})D=Ω(N​) exceeding the N1/3N^{1/3}N1/3 distance barrier implied by the Bravyi-König bound for conventional topological codes with the aid of non-Euclidean geometries. Our work suggests that it is feasible to apply native logical non-Clifford gates on qLDPC codes or directly inject high-fidelity magic states as resources ('magic state fountain') without the distillation process. For the homological product construction, the fountain can inject Θ(N)Θ(\sqrt{N})Θ(N​) magic states in parallel in a single round.
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.
A fundamental problem of fault-tolerant quantum computation with quantum low-density parity-check (qLDPC) codes is the tradeoff between connectivity and universality. It is widely believed that in order to perform native logical non-Clifford gates, one needs to resort to 3D product-code constructions. In this work, we extend Kitaev's framework of non-Abelian topological codes on manifolds to non-Abelian qLDPC codes (realized as Clifford-stabilizer codes) and the corresponding combinatorial topological quantum field theories (TQFT) defined on Poincaré CW complexes and certain types of general chain complexes. We also construct the spacetime path integrals as topological invariants on these complexes. Remarkably, we show that native non-Clifford logical gates can be realized using constant-rate 2D hypergraph-product codes and their Clifford-stabilizer variants. This is achieved by a spacetime path integral effectively implementing the addressable gauging measurement of a new type of 0-form subcomplex symmetries, which correspond to addressable transversal Clifford gates and become higher-form symmetries when lifted to higher-dimensional CW complexes or manifolds. Building on this structure, we apply the gauging protocol to the magic state fountain scheme for parallel preparation of O(n)O(\sqrt{n})O(n​) disjoint CZ magic states with code distance of O(n)O(\sqrt{n})O(n​), using a total number of nnn qubits.
Quantum error correction is necessary to perform large-scale quantum computation but requires extremely large overheads in both space and time. High-rate quantum low-density-parity-check (qLDPC) codes promise a route to reduce qubit numbers, but performing computation while maintaining low space cost has required serialization of operations and extra time costs. In this work, we design fast and parallelizable logical gates for qLDPC codes and demonstrate their utility for key algorithmic subroutines such as the quantum adder. Our gate gadgets utilize transversal logical s between a data qLDPC code and a suitably constructed ancilla code to perform parallel Pauli product measurements (PPMs) on the data logical qubits. For hypergraph product codes, we show that the ancilla can be constructed by simply modifying the base classical codes of the data code, achieving parallel PPMs on a subgrid of the logical qubits with a lower space-time cost than existing schemes for an important class of circuits. Generalizations to 3D and 4D homological product codes further feature fast PPMs in constant depth. While prior work on qLDPC codes has focused on individual logical gates, we initiate the study of fault-tolerant compilation with our expanded set of native qLDPC code operations, constructing algorithmic primitives for preparing k -qubit Greenberger-Horne-Zeilinger states and distilling or teleporting k magic states with O ( 1 ) space overhead in O ( 1 ) and O ( k log k ) logical cycles, respectively. We further generalize this to key algorithmic subroutines, demonstrating the efficient implementation of quantum adders using parallel operations. Our constructions are naturally compatible with reconfigurable architectures such as neutral atom arrays, paving the way to large-scale quantum computation with low space and time overheads.