Title: Both Toffoli and Controlled-NOT need little help to universal quantum computing
Abstract: 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.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 202
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot