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:0706.1382 · IEEE Transactions on Information Theory

Transversality Versus Universality for Additive Quantum Codes

Bei Zeng, Andrew W. Cross, Isaac L. Chuang

Published Sep 1, 2011• 138 citations
arXivHTMLPDF

Abstract

Logic gates can be performed on data encoded in quantum code blocks such that errors introduced by faulty gates can be corrected. The important class of transversal gates acts bitwise between corresponding qubits of code blocks and thus limits error propagation. If any quantum gate could be implemented using transversal gates, the set would be universal. We study the structure ofGF(4)-additive quantum codes and prove that no universal set of transversal logic gates exists for these codes. This result is in stark contrast with the classical case, where universal transversal gate sets exist, and strongly supports the idea that additional quantum techniques, based, for example, on quantum teleportation or magic state distillation, are necessary to achieve universal fault-tolerant quantum computation on additive codes.

DOI
10.1109/tit.2011.2161917

Related papers

Restrictions on Transversal Encoded Quantum Gate Sets

Bryan Eastin, Emanuel H. Knill

Transversal gates play an important role in the theory of fault-tolerant quantum computation due to their simplicity and robustness to noise. By definition, transversal operators do not couple physical subsystems within the same code block. Consequently, such operators do not spread errors within code blocks and are, therefore, fault tolerant. Nonetheless, other methods of ensuring fault tolerance are required, as it is invariably the case that some encoded gates cannot be implemented transversally. This observation has led to a long-standing conjecture that transversal encoded gate sets cannot be universal. Here we show that the ability of a quantum code to detect an arbitrary error on any single physical subsystem is incompatible with the existence of a universal, transversal encoded gate set for the code.

arXiv:0811.4262•Physical Review Letters•Mar 18, 2009•457 citations

Universal fault-tolerant gates on nondegenerate stabilizer codes

Theodore J. Yoder, Ryuji Takagi, Isaac L. Chuang

It is an oft cited fact that no quantum code can support a set of fault-tolerant logical gates that is both universal and transversal. This no-go theorem is generally responsible for the interest in alternative universality constructions including magic state distillation. Widely overlooked, however, is the possibility of non-transversal, yet still fault-tolerant, gates that work directly on small quantum codes. Here we demonstrate precisely the existence of such gates. In particular, we show how the limits of non-transversality can be overcome by performing rounds of intermediate error-correction to create logical gates on stabilizer codes that use no ancillas other than those required for syndrome measurement. Moreover, the logical gates we construct, the most prominent examples being Toffoli and controlled-controlled-Z, often complete universal gate sets on their codes. We detail such universal constructions for the smallest quantum codes, the 5-qubit and 7-qubit codes, and then proceed to generalize the approach. One remarkable result of this generalization is that any nondegenerate stabilizer code with a complete set of fault-tolerant single-qubit Clifford gates has a universal set of fault-tolerant gates. Another is the interaction of logical qubits across different stabilizer codes, which, for instance, implies a broadly applicable method of code switching.

•Mar 12, 2016•2 citations

Subsystem stabilizer codes cannot have a universal set of transversal gates for even one encoded qudit

Xie Chen, Hyeyoun Chung, Andrew W. Cross +2 more

A long-standing open problem in fault-tolerant quantum computation has been to find a universal set of transversal gates. As shown by Zeng et al. (e-print arXiv:0706.1382), such a set does not exist for binary stabilizer codes. Here we generalize our work to show that for subsystem stabilizer codes in $d$-dimensional Hilbert space, such a universal set of transversal gates cannot exist for even one encoded qudit, for any dimension $d$, prime or nonprime. This result strongly supports the idea that other primitives, such as quantum teleportation, are necessary for universal fault-tolerant quantum computation, and may be an important factor for fault-tolerance noise thresholds.

arXiv:0801.2360•Physical Review A•Jul 28, 2008•46 citations

Complementary 3D color codes for transversal quantum logic

Friederike Butt, Luis Colmenarez, Erik Weilandt +3 more

Transversal logical gates provide a direct route to fault-tolerant quantum computation, but the Eastin-Knill theorem forbids a universal transversal gate set within a single quantum error-correcting code. We propose a hybrid architecture based on the tetrahedral three-dimensional color code and its Hadamard-transformed counterpart, which we call the H-tetrahedral code. The two encodings support complementary transversal non-Clifford operations. Combined with bitwise Hadamard transformations that switch between the two encodings and a one-way transversal logical CNOT from the tetrahedral code to the H-tetrahedral code, these operations realize an almost-universal transversal logical gate set that enables both the creation of entanglement and logical states with magic. We complete a universal gate set through a pieceably fault-tolerant round-robin construction of a logical controlled-$Z$ gate between two H-tetrahedral codes. This logical entangling gate is interleaved with reduced-overhead Steane-type syndrome extraction using logical two-dimensional color-code auxiliary qubits. Our construction provides a new route toward implementing classically hard-to-simulate quantum algorithms where magic and most entangling operations are transversal while the resource overhead is concentrated in a small number of non-transversal Clifford entangling operations.

quant-pharXiv:2607.05107•Jul 7, 2026•0 citations

Nonuniform code concatenation for universal fault-tolerant quantum computing

Eesa Nikahd, Mehdi Sedighi, Morteza Saheb Zamani

Using transversal gates is a straightforward and efficient technique for fault-tolerant quantum computing. Since transversal gates alone cannot be computationally universal, they must be combined with other approaches such as magic state distillation, code switching, or code concatenation to achieve universality. In this paper we propose an alternative approach for universal fault-tolerant quantum computing, mainly based on the code concatenation approach proposed in [T. Jochym-O'Connor and R. Laflamme, Phys. Rev. Lett. 112, 010505 (2014)], but in a nonuniform fashion. The proposed approach is described based on nonuniform concatenation of the 7-qubit Steane code with the 15-qubit Reed-Muller code, as well as the 5-qubit code with the 15-qubit Reed-Muller code, which lead to two 49-qubit and 47-qubit codes, respectively. These codes can correct any arbitrary single physical error with the ability to perform a universal set of fault-tolerant gates, without using magic state distillation.

arXiv:1605.07007•Physical Review A•Sep 27, 2017•15 citations

Stabilizer Code-Generic Universal Fault-Tolerant Quantum Computation

Nicholas J. C. Papadopoulos, Ramin Ayanzadeh

Fault-tolerant quantum computation allows quantum computations to be carried out while resisting unwanted noise. Several error-correcting codes have been developed to achieve this task, but none alone are capable of transversal universal quantum computation. This universality is highly desired and often achieved using techniques such as code concatenation, code switching, magic state distillation, or pieceable fault tolerance. Existing constructions can incur substantial overhead or rely on properties specific to particular codes. This work proposes implementing logical Clifford and T gates through novel, ancilla-mediated, pieceable interactions to construct a universal fault-tolerant quantum gate set. Our construction is deterministic, does not modify the underlying data codes or registers, and is generic over all data stabilizer codes. Thus, any single code becomes capable of universal quantum computation by leveraging helper codes in ancilla registers and mid-circuit measurements. Furthermore, since these logical gates are stabilizer code-generic, these implementations enable communication between heterogeneous stabilizer codes.

quant-pharXiv:2601.10964•Jan 19, 2026•0 citations
Logic gates can be performed on data encoded in quantum code blocks such that errors introduced by faulty gates can be corrected. The important class of transversal gates acts bitwise between corresponding qubits of code blocks and thus limits error propagation. If any quantum gate could be implemented using transversal gates, the set would be universal. We study the structure ofGF(4)-additive quantum codes and prove that no universal set of transversal logic gates exists for these codes. This result is in stark contrast with the classical case, where universal transversal gate sets exist, and strongly supports the idea that additional quantum techniques, based, for example, on quantum teleportation or magic state distillation, are necessary to achieve universal fault-tolerant quantum computation on additive codes.
Transversal gates play an important role in the theory of fault-tolerant quantum computation due to their simplicity and robustness to noise. By definition, transversal operators do not couple physical subsystems within the same code block. Consequently, such operators do not spread errors within code blocks and are, therefore, fault tolerant. Nonetheless, other methods of ensuring fault tolerance are required, as it is invariably the case that some encoded gates cannot be implemented transversally. This observation has led to a long-standing conjecture that transversal encoded gate sets cannot be universal. Here we show that the ability of a quantum code to detect an arbitrary error on any single physical subsystem is incompatible with the existence of a universal, transversal encoded gate set for the code.
It is an oft cited fact that no quantum code can support a set of fault-tolerant logical gates that is both universal and transversal. This no-go theorem is generally responsible for the interest in alternative universality constructions including magic state distillation. Widely overlooked, however, is the possibility of non-transversal, yet still fault-tolerant, gates that work directly on small quantum codes. Here we demonstrate precisely the existence of such gates. In particular, we show how the limits of non-transversality can be overcome by performing rounds of intermediate error-correction to create logical gates on stabilizer codes that use no ancillas other than those required for syndrome measurement. Moreover, the logical gates we construct, the most prominent examples being Toffoli and controlled-controlled-Z, often complete universal gate sets on their codes. We detail such universal constructions for the smallest quantum codes, the 5-qubit and 7-qubit codes, and then proceed to generalize the approach. One remarkable result of this generalization is that any nondegenerate stabilizer code with a complete set of fault-tolerant single-qubit Clifford gates has a universal set of fault-tolerant gates. Another is the interaction of logical qubits across different stabilizer codes, which, for instance, implies a broadly applicable method of code switching.
A long-standing open problem in fault-tolerant quantum computation has been to find a universal set of transversal gates. As shown by Zeng et al. (e-print arXiv:0706.1382), such a set does not exist for binary stabilizer codes. Here we generalize our work to show that for subsystem stabilizer codes in ddd-dimensional Hilbert space, such a universal set of transversal gates cannot exist for even one encoded qudit, for any dimension ddd, prime or nonprime. This result strongly supports the idea that other primitives, such as quantum teleportation, are necessary for universal fault-tolerant quantum computation, and may be an important factor for fault-tolerance noise thresholds.
Transversal logical gates provide a direct route to fault-tolerant quantum computation, but the Eastin-Knill theorem forbids a universal transversal gate set within a single quantum error-correcting code. We propose a hybrid architecture based on the tetrahedral three-dimensional color code and its Hadamard-transformed counterpart, which we call the H-tetrahedral code. The two encodings support complementary transversal non-Clifford operations. Combined with bitwise Hadamard transformations that switch between the two encodings and a one-way transversal logical CNOT from the tetrahedral code to the H-tetrahedral code, these operations realize an almost-universal transversal logical gate set that enables both the creation of entanglement and logical states with magic. We complete a universal gate set through a pieceably fault-tolerant round-robin construction of a logical controlled-ZZZ gate between two H-tetrahedral codes. This logical entangling gate is interleaved with reduced-overhead Steane-type syndrome extraction using logical two-dimensional color-code auxiliary qubits. Our construction provides a new route toward implementing classically hard-to-simulate quantum algorithms where magic and most entangling operations are transversal while the resource overhead is concentrated in a small number of non-transversal Clifford entangling operations.
Using transversal gates is a straightforward and efficient technique for fault-tolerant quantum computing. Since transversal gates alone cannot be computationally universal, they must be combined with other approaches such as magic state distillation, code switching, or code concatenation to achieve universality. In this paper we propose an alternative approach for universal fault-tolerant quantum computing, mainly based on the code concatenation approach proposed in [T. Jochym-O'Connor and R. Laflamme, Phys. Rev. Lett. 112, 010505 (2014)], but in a nonuniform fashion. The proposed approach is described based on nonuniform concatenation of the 7-qubit Steane code with the 15-qubit Reed-Muller code, as well as the 5-qubit code with the 15-qubit Reed-Muller code, which lead to two 49-qubit and 47-qubit codes, respectively. These codes can correct any arbitrary single physical error with the ability to perform a universal set of fault-tolerant gates, without using magic state distillation.
Fault-tolerant quantum computation allows quantum computations to be carried out while resisting unwanted noise. Several error-correcting codes have been developed to achieve this task, but none alone are capable of transversal universal quantum computation. This universality is highly desired and often achieved using techniques such as code concatenation, code switching, magic state distillation, or pieceable fault tolerance. Existing constructions can incur substantial overhead or rely on properties specific to particular codes. This work proposes implementing logical Clifford and T gates through novel, ancilla-mediated, pieceable interactions to construct a universal fault-tolerant quantum gate set. Our construction is deterministic, does not modify the underlying data codes or registers, and is generic over all data stabilizer codes. Thus, any single code becomes capable of universal quantum computation by leveraging helper codes in ancilla registers and mid-circuit measurements. Furthermore, since these logical gates are stabilizer code-generic, these implementations enable communication between heterogeneous stabilizer codes.