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

A Simple Proof that Toffoli and Hadamard are Quantum Universal

Dorit Aharonov

Published Jan 9, 2003• 122 citations
arXivHTMLPDF

Abstract

Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It shows that one only needs to add the Hadamard gate to make a 'classical' set of gates quantum universal. In this note we give a few lines proof of this fact relying on Kitaev's universal set of gates, and discuss the meaning of the result.

DOI
10.48550/arxiv.quant-ph/0301040

Related papers

Strutture Algebriche nella Computazione Quantistica

Maria L. Dalla Chiara, Giuseppe Sergioli

Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the basic algebraic properties of this system by introducing the notion of Shi-Abaronov quantum computational structure. Finally, we investigate the possibility of an algebraic abstraction from Hilbert-space structures, by proposing the notion of Toffoli-Hadamard algebra. From an intuitive point of view, such abstract algebras represent a natural quantum generalization of both classical and fuzzy-like structures.

•Jan 1, 2011•0 citations

Toffoli or Control-NOT needs little help to do universal quantum computation

Yaoyun Shi

What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Control-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Control-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.

•May 18, 2002•0 citations

The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality

Patrick Roy, John van de Wetering, Lia Yeh

We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits.We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e 2πi/d ].For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits.We generalise this connection to qudits, by finding that the two-qudit |0 -controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate.We prove that our construction is asymptotically optimal up to a logarithmic term.Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0 -controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.

arXiv:2307.10095•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•8 citations

QMA has perfect completeness

Sabee Grewal, Dorian Rudolph

We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

quant-pharXiv:2609.13032•Sep 14, 2026•0 citations

Both Toffoli and Controlled-NOT need little help to do universal quantum computation

Yaoyun Shi

What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.

arXiv:quant-ph/0205115•May 18, 2002•91 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
Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It shows that one only needs to add the Hadamard gate to make a 'classical' set of gates quantum universal. In this note we give a few lines proof of this fact relying on Kitaev's universal set of gates, and discuss the meaning of the result.
Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the basic algebraic properties of this system by introducing the notion of Shi-Abaronov quantum computational structure. Finally, we investigate the possibility of an algebraic abstraction from Hilbert-space structures, by proposing the notion of Toffoli-Hadamard algebra. From an intuitive point of view, such abstract algebras represent a natural quantum generalization of both classical and fuzzy-like structures.
What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Control-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Control-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.
We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits.We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e 2πi/d ].For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits.We generalise this connection to qudits, by finding that the two-qudit |0 -controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate.We prove that our construction is asymptotically optimal up to a logarithmic term.Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0 -controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.
We prove QMA=QMA1\mathsf{QMA} = \mathsf{QMA_1}QMA=QMA1​, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and XXX gates, yielding a universal gate set for QMA1\mathsf{QMA_1}QMA1​. As a consequence, quantum 333-SAT is QMA\mathsf{QMA}QMA-complete. The construction relativizes to classical oracles, so known classical-oracle separations of QMA\mathsf{QMA}QMA from QCMA\mathsf{QCMA}QCMA extend to QMA1\mathsf{QMA_1}QMA1​.
What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.
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.