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/9906054

On Universal and Fault-Tolerant Quantum Computing

P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, Farrokh Vatan

Published Jun 16, 1999• 81 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/9906054

Related papers

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

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

New Limits on Fault-Tolerant Quantum Computation

Harry Buhrman, Richard Cleve, Monique Laurent +3 more

We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows

arXiv:quant-ph/0604141•Annual Symposium on Foundations of Computer Science•Jan 1, 2006•59 citations

Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem

H. F. Chau

Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of $ε> 0$ requires $\text{O}(\log^c[1/ε])$ quantum gates with $c > 1.44042$. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using $Ω(\log[1/ε])$ gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using $\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)$ FT gates chosen from a finite set depending on the value of $ε$. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy $ε> 0$. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.

arXiv:2406.04846•Jun 7, 2024•0 citations

Fault-Tolerant Quantum Computation With Constant Error Rate

Dorit Aharonov, Michael Ben-Or

This paper proves the threshold result, which asserts that quantum computation can be made robust against errors and inaccuracies, when the error rate, $η$, is smaller than a constant threshold, $η_c$. The result holds for a very general, not necessarily probabilistic noise model, for quantum particles with any number of states, and is also generalized to one dimensional quantum computers with only nearest neighbor interactions. No measurements, or classical operations, are required during the quantum computation. The proceeding version was very succinct, and here we fill all the missing details, and elaborate on many parts of the proof. In particular, we devote a section for a discussion of universality issues and proofs that the sets of gates that we use are universal. Another section is devoted to a rigorous proof that fault tolerance can be achieved in the presence of general non probabilistic noise. The systematic structure of the fault tolerant procedures for polynomial codes is explained in length. The proof that the concatenation scheme works is written in a clearer way. The paper also contains new and significantly simpler proofs for most of the known results which we use. For example, we give a simple proof that it suffices to correct bit and phase flips, we significantly simplify Calderbank and Shor's original proof of the correctness of CSS codes. We also give a simple proof of the fact that two-qubit gates are universal. The paper thus provides a self contained and complete proof for universal fault tolerant quantum computation.

arXiv:quant-ph/9906129•Jun 30, 1999•18 citations

Practical Scheme for Quantum Computation with Any Two-Qubit Entangling Gate

Michael J. Bremner, Christopher M. Dawson, Jennifer L. Dodd +5 more

Which gates are universal for quantum computation? Although it is well known that certain gates on two-level quantum systems (qubits), such as the controlled-not, are universal when assisted by arbitrary one-qubit gates, it has only recently become clear precisely what class of two-qubit gates is universal in this sense. We present an elementary proof that any entangling two-qubit gate is universal for quantum computation, when assisted by one-qubit gates. A proof of this result for systems of arbitrary finite dimension has been provided by Brylinski and Brylinski; however, their proof relies on a long argument using advanced mathematics. In contrast, our proof provides a simple constructive procedure which is close to optimal and experimentally practical.

arXiv:quant-ph/0207072•Physical Review Letters•Nov 25, 2002•292 citations
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).
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
We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows
Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of ε>0ε> 0ε>0 requires O(log⁡c[1/ε])\text{O}(\log^c[1/ε])O(logc[1/ε]) quantum gates with c>1.44042c > 1.44042c>1.44042. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using Ω(log⁡[1/ε])Ω(\log[1/ε])Ω(log[1/ε]) gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using O(log⁡[1/ε]log⁡log⁡[1/ε]log⁡log⁡log⁡[1/ε]⋯ )\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)O(log[1/ε]loglog[1/ε]logloglog[1/ε]⋯) FT gates chosen from a finite set depending on the value of εεε. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy ε>0ε> 0ε>0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.
This paper proves the threshold result, which asserts that quantum computation can be made robust against errors and inaccuracies, when the error rate, ηηη, is smaller than a constant threshold, ηcη_cηc​. The result holds for a very general, not necessarily probabilistic noise model, for quantum particles with any number of states, and is also generalized to one dimensional quantum computers with only nearest neighbor interactions. No measurements, or classical operations, are required during the quantum computation. The proceeding version was very succinct, and here we fill all the missing details, and elaborate on many parts of the proof. In particular, we devote a section for a discussion of universality issues and proofs that the sets of gates that we use are universal. Another section is devoted to a rigorous proof that fault tolerance can be achieved in the presence of general non probabilistic noise. The systematic structure of the fault tolerant procedures for polynomial codes is explained in length. The proof that the concatenation scheme works is written in a clearer way. The paper also contains new and significantly simpler proofs for most of the known results which we use. For example, we give a simple proof that it suffices to correct bit and phase flips, we significantly simplify Calderbank and Shor's original proof of the correctness of CSS codes. We also give a simple proof of the fact that two-qubit gates are universal. The paper thus provides a self contained and complete proof for universal fault tolerant quantum computation.
Which gates are universal for quantum computation? Although it is well known that certain gates on two-level quantum systems (qubits), such as the controlled-not, are universal when assisted by arbitrary one-qubit gates, it has only recently become clear precisely what class of two-qubit gates is universal in this sense. We present an elementary proof that any entangling two-qubit gate is universal for quantum computation, when assisted by one-qubit gates. A proof of this result for systems of arbitrary finite dimension has been provided by Brylinski and Brylinski; however, their proof relies on a long argument using advanced mathematics. In contrast, our proof provides a simple constructive procedure which is close to optimal and experimentally practical.