Both Toffoli and Controlled-NOT need little help to do universal quantum computation
arXiv:quant-ph/0205115
Abstract
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.
References in corpus (4)
Cited by in corpus (34)
- Measurement-based quantum computation with cluster states
- Universal Linear Optics
- Qudits and high-dimensional quantum computing
- Improved magic states distillation for quantum universality
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- An introduction to measurement based quantum computation
- Anyons from non-solvable finite groups are sufficient for universal quantum computation
- Scalable photonic quantum computing assisted by quantum-dot spin in double-sided optical microcavity
- Hierarchy of universal entanglement in 2D measurement-based quantum computation
- Hamiltonian Quantum Cellular Automata in 1D
- Room-Temperature Photonic Logical Qubits via Second-Order Nonlinearities
- Fault-Tolerant Logical Gate Networks for CSS Codes
- Generation of Universal Linear Optics by Any Beamsplitter
- Machine learning \& artificial intelligence in the quantum domain
- Level Reduction and the Quantum Threshold Theorem
- Universal MBQC with generalised parity-phase interactions and Pauli measurements
- Matchgate and space-bounded quantum computations are equivalent
- Error-detection-based quantum fault tolerance against discrete Pauli noise
- Guaranteed recovery of quantum processes from few measurements
- ZX-calculus for the working quantum computer scientist
- Supervised learning of time-independent Hamiltonians for gate design
- Graph States, Pivot Minor, and Universality of (X,Z)-measurements
- Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
- Local Hamiltonians in Quantum Computation
- Entanglement of random hypergraph states
- Hybrid quantum computing with ancillas
- Quantum simulation from the bottom up: the case of rebits
- Universal quantum computation with unlabeled qubits
- Quantum computation by teleportation and symmetry
- Phase context decomposition of diagonal unitaries for higher-dimensional systems
- Universal quantum computation via quantum controlled classical operations
- Theoretical realization of a two qubit quantum controlled-not logic gate and a single qubit Hadamard logic gate in the anti-Jaynes-Cummings model
- Sampling and the complexity of nature
- Quantum Theory from Principles, Quantum Software from Diagrams