A Simple Proof that Toffoli and Hadamard are Quantum Universal

By Dorit Aharonov. 2003

251 citations recorded by the source corpus.

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.

View Paper: https://www.semanticscholar.org/paper/a7989764c4392f657ea5bb0f4258b6e8fde6a9d6

How researchers see this paper

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

1. Ashley Montanaro
2. Stefan Woerner

Citations in the corpus

• 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.”
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm (2016, unknown): “One such universal gate set consists of H, e π 8 σz and the controlled-phase gate e−i π 4 (I−σ1 z)(I−σ(2) z) [4].”