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:quant-ph/9904108 · ACM Symposium on Theory of Computing (STOC)

Self-testing of universal and fault-tolerant sets of quantum gates

Wim van Dam, Frédéric Magniez, Michele Mosca, Miklós Sántha

Published May 1, 2000• 25 citations
arXivHTMLPDF

Abstract

We consider the design of self-testers for quantum gates. A self-tester for the gates F_1,...,F_m is a classical procedure that, given any gates G_1,...,G_m, decides with high probability if each G_i is close to F_i. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that instead of individual gates, we can only design procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: we characterize the gate families by specific properties, we develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a c-NOT gate, and a phase rotation gate of angle pi/4 is self-testable.

DOI
10.1145/335305.335402

Related papers

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates

Wim van Dam, Frédéric Magniez, Michele Mosca +1 more

We consider the design of self-testers for quantum gates. A self-tester for the gates $\boldsymbol{F}_1,\ldots, \boldsymbol{F}_m$ is a procedure that, given any gates $\boldsymbol{G}_1, \ldots, \boldsymbol{G}_m$, decides with high probability if each $\boldsymbol{G}_i$ is close to $\boldsymbol{F}_i$. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that, instead of individual gates, we can design only procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: We characterize the gate families by specific properties, develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a $\mathrm{c\text{-}NOT}$ gate, and a phase rotation gate of angle $\pi/4$ is self-testable.

SIAM Journal on Computing•Jan 1, 2007•15 citations

On Universal and Fault-Tolerant Quantum Computing

P. Oscar Boykin, Tal Mor, Matthew Pulver +2 more

A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and ${σ_z}^{1/4}$), and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of $π$) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by Shor and by Kitaev.

arXiv:quant-ph/9906054•Jun 16, 1999•81 citations

On universal and fault-tolerant quantum computing: a novel basis and a new constructive proof of universality for Shor's basis

P. Oscar Boykin, Tal Mor, Matthew Pulver +2 more

A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and /spl sigma//sub z//sup 1/4 /) and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of /spl pi/) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by P.W. Shor (1996) and A.Y. Kitaev (1997).

Annual Symposium on Foundations of Computer Science•Jan 20, 2003•80 citations

Universal fault-tolerant quantum computing with stabilizer codes

Paul Webster, Michael Vasmer, Thomas R. Scruby +1 more

The quantum logic gates used in the design of a quantum computer should be both universal, meaning arbitrary quantum computations can be performed, and fault-tolerant, meaning the gates keep errors from cascading out of control. A number of no-go theorems constrain the ways in which a set of fault-tolerant logic gates can be universal. These theorems are very restrictive, and conventional wisdom holds that a universal fault-tolerant logic gate set cannot be implemented natively, requiring us to use costly distillation procedures for quantum computation. Here, we present a general framework for universal fault-tolerant logic with stabilizer codes, together with a no-go theorem that reveals the very broad conditions constraining such gate sets. Our theorem applies to a wide range of stabilizer code families, including concatenated codes and conventional topological stabilizer codes such as the surface code. The broad applicability of our no-go theorem provides a new perspective on how the constraints on universal fault-tolerant gate sets can be overcome. In particular, we show how nonunitary implementations of logic gates provide a general approach to circumvent the no-go theorem, and we present a rich landscape of constructions for logic gate sets that are both universal and fault-tolerant. That is, rather than restricting what is possible, our no-go theorem provides a signpost to guide us to new, efficient architectures for fault-tolerant quantum computing.

arXiv:2012.05260•Physical Review Research•Feb 4, 2022•28 citations

Constructing arbitrary single-qubit fault-tolerant gates

Austin G. Fowler

We present a method for constructing optimal fault-tolerant approximations of arbitrary unitary gates using an arbtrary discrete universal gate set. The method presented is numerical and scales exponentially with the number of gates used in the approximation, however, for the specific case of arbitrary single-qubit gates and the fault-tolerant gates permitted by the 7-qubit Steane code, it is shown that the longest practical gates sequences can be found. We also analyse the practicality of the fault-tolerant approximations of the phase rotation gates used in Shor’s algorithm and find that simple non-fault-tolerant phase rotations are more robust for realistic error rates. A general scaling law of how rapidly these fault-tolerant approximations converge to arbitrary single-qubit gates is also determined. In large-scale quantum computation, every qubit of data is encoded across multiple physical qubits to form a logical qubit permitting quantum error correction

arXiv:quant-ph/0411206•Nov 30, 2004•6 citations

State transition diagrams for a universal quantum gate set

Anuradha Mahasinghe, Ayodhya Liyanage

A quantum Turing machine (QTM) is an abstract model of computing that serves as the quantum counterpart of a classical Turing machine. Closely related to the probabilistic Turing machine, a QTM utilises quantum effects such as superposition, entanglement and unitary evolution. Despite its historical role as a framework for devising quantum algorithms and the significance of its classical counterpart in theoretical computing, very little attention has been paid in literature to the state transition of QTM’s for basic quantum gates. In this paper, we construct the state transition diagrams for a set of elementary quantum gates that consists of the Hadamard, CNOT, and T gates, providing a universal basis for fault tolerant quantum computation. We verify the necessary conditions to ensure that the designed state transition diagrams comply with the postulates of quantum mechanics, verifying their well formedness.

JUCS - Journal of Universal Computer Science•Mar 23, 2026•0 citations
We consider the design of self-testers for quantum gates. A self-tester for the gates F_1,...,F_m is a classical procedure that, given any gates G_1,...,G_m, decides with high probability if each G_i is close to F_i. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that instead of individual gates, we can only design procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: we characterize the gate families by specific properties, we develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a c-NOT gate, and a phase rotation gate of angle pi/4 is self-testable.
We consider the design of self-testers for quantum gates. A self-tester for the gates F1,…,Fm\boldsymbol{F}_1,\ldots, \boldsymbol{F}_mF1​,…,Fm​ is a procedure that, given any gates G1,…,Gm\boldsymbol{G}_1, \ldots, \boldsymbol{G}_mG1​,…,Gm​, decides with high probability if each Gi\boldsymbol{G}_iGi​ is close to Fi\boldsymbol{F}_iFi​. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that, instead of individual gates, we can design only procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: We characterize the gate families by specific properties, develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a c-NOT\mathrm{c\text{-}NOT}c-NOT gate, and a phase rotation gate of angle π/4\pi/4π/4 is self-testable.
A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and σz1/4{σ_z}^{1/4}σz​1/4), and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of πππ) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by Shor and by Kitaev.
A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and /spl sigma//sub z//sup 1/4 /) and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of /spl pi/) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by P.W. Shor (1996) and A.Y. Kitaev (1997).
The quantum logic gates used in the design of a quantum computer should be both universal, meaning arbitrary quantum computations can be performed, and fault-tolerant, meaning the gates keep errors from cascading out of control. A number of no-go theorems constrain the ways in which a set of fault-tolerant logic gates can be universal. These theorems are very restrictive, and conventional wisdom holds that a universal fault-tolerant logic gate set cannot be implemented natively, requiring us to use costly distillation procedures for quantum computation. Here, we present a general framework for universal fault-tolerant logic with stabilizer codes, together with a no-go theorem that reveals the very broad conditions constraining such gate sets. Our theorem applies to a wide range of stabilizer code families, including concatenated codes and conventional topological stabilizer codes such as the surface code. The broad applicability of our no-go theorem provides a new perspective on how the constraints on universal fault-tolerant gate sets can be overcome. In particular, we show how nonunitary implementations of logic gates provide a general approach to circumvent the no-go theorem, and we present a rich landscape of constructions for logic gate sets that are both universal and fault-tolerant. That is, rather than restricting what is possible, our no-go theorem provides a signpost to guide us to new, efficient architectures for fault-tolerant quantum computing.
We present a method for constructing optimal fault-tolerant approximations of arbitrary unitary gates using an arbtrary discrete universal gate set. The method presented is numerical and scales exponentially with the number of gates used in the approximation, however, for the specific case of arbitrary single-qubit gates and the fault-tolerant gates permitted by the 7-qubit Steane code, it is shown that the longest practical gates sequences can be found. We also analyse the practicality of the fault-tolerant approximations of the phase rotation gates used in Shor’s algorithm and find that simple non-fault-tolerant phase rotations are more robust for realistic error rates. A general scaling law of how rapidly these fault-tolerant approximations converge to arbitrary single-qubit gates is also determined. In large-scale quantum computation, every qubit of data is encoded across multiple physical qubits to form a logical qubit permitting quantum error correction
A quantum Turing machine (QTM) is an abstract model of computing that serves as the quantum counterpart of a classical Turing machine. Closely related to the probabilistic Turing machine, a QTM utilises quantum effects such as superposition, entanglement and unitary evolution. Despite its historical role as a framework for devising quantum algorithms and the significance of its classical counterpart in theoretical computing, very little attention has been paid in literature to the state transition of QTM’s for basic quantum gates. In this paper, we construct the state transition diagrams for a set of elementary quantum gates that consists of the Hadamard, CNOT, and T gates, providing a universal basis for fault tolerant quantum computation. We verify the necessary conditions to ensure that the designed state transition diagrams comply with the postulates of quantum mechanics, verifying their well formedness.