A Simple Proof that Toffoli and Hadamard are Quantum Universal

2003/01/09 by Dorit Aharonov, Aharonov, Dorit · 10 citations
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0301040

A note. 4 pages

arxiv created 2003/01/09 · arxiv updated 2009/12/01

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.

Cited by

• Holonomic multi-controlled gates for single-photon states
• Measurement-based quantum computation on weighted graph states with arbitrarily small weight
• Exact Quantum Circuit Optimization is co-NQP-hard
• Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
• On Quantum Computation Using Bias-Preserving Gates
• One rig to control them all
• Two bases suffice for QMA1-completeness
• Anticoherent k-planes and coding techniques for a 3-qubit scheme of universal quantum computing
• Universality of a standard two-qubit gate by catalytic embedding
• Practical Fidelity Limits of Toffoli Gates in Superconducting Quantum Processors

Related

• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• Elementary gates for quantum computation
• Universality of single quantum gates
• On Universal and Fault-Tolerant Quantum Computing
• Universality and programmability of quantum computers