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

作者：Y-Y Shi · 发表于：Quantum Information and Computation · 年份：2003 · DOI：10.26421/qic3.1-7 · 被引用次数：199 · 研究领域：Quantum Computing Algorithms and Architecture、Quantum Information and Cryptography、Computability, Logic, AI Algorithms

What additional gates are needed for a set of classical universal gates to do universal quantum computation? We prove that any single-qubit real gate suffices, except those that preserve the computational basis. The Gottesman-Knill Theorem 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 like) 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.