Both Toffoli and controlled-NOT need little help to do universal quantum computing

By Yaoyun Shi. Quantum information & computation, 2002

299 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/8de9bdf00be5a63fed58e6624cf693069796749e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Implementation of a Toffoli gate with superconducting circuits (2011, background): “It makes universal reversible classical computation [1] possible and, together with a Hadamard gate [2], forms a uni-”
Quantum algorithms: an overview (2015, unknown): “It is known that any quantum circuit can be approximated using only Toffoli and Hadamard quantum gates [88].”
A Simple Proof that Toffoli and Hadamard are Quantum Universal (2003, methodology): “The question of universality of the set {T,H} was asked by various researchers, and was recently solved by Shi [15] to the affirmative.”
Qudits and High-Dimensional Quantum Computing (2020, background): “In the field of quantum computing, the Toffoli gate plays a central role in quantum error correction [61], fault tolerance [62] and offers a simple universal quantum gate set combined with one qubit Hadamard gates [63].”
Measurement-based quantum computation on cluster states (2003, methodology): “As an example, the set consisting of the Toffoli- and the Hadamard gate is universal [18] as well as the set consisting of the CNOT-, the Hadamard- and the π/4-phase gate”
Improved Simulation of Stabilizer Circuits (2004, background): “Shi [38] has shown that if we generalize stabilizer circuits by adding any 1-or 2-qubit gate not generated by CNOT, Hadamard, and phase, then we immediately obtain a universal set.”
Quantum circuits and low-degree polynomials over F2 (2016, background): “As the set of gates {Hadamard, CCZ} is universal for quantum computation [38, 3], this is sufficient to solve any problem in BQP.”