A Simple Proof that Toffoli and Hadamard are Quantum Universal
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 12 Pith papers
-
On the Complexity of the Circuit Width Problem
Deciding circuit width w(f) ≤ k for degree-3 polynomials with no constant term is NP-complete, with 49/48-ε inapproximability, ETH lower bounds, and FPT algorithms.
-
A sharp interaction-degree threshold for simulating QAOA
There is a sharp threshold at interaction degree 3 where classical sampling from depth-1 QAOA becomes hard enough to collapse the polynomial hierarchy, contrasting with efficient simulation at degree 2 for logarithmic depth.
-
Toward fault-tolerant quantum computation exploiting quantum spatial distribution and gauge symmetry
Gauge symmetry applied to quantum spatial distributions of particles corrects decoherence and dephasing in a stabilizer code and enables vertically and horizontally stackable architectures with only nearest-neighbor i...
-
Exponential quantum advantage in processing massive classical data
A polylog-sized quantum computer achieves exponential advantage over classical machines in classification and dimension reduction of massive classical data using quantum oracle sketching combined with classical shadows.
-
Ancilla-Error-Transparent Controlled Beam Splitter Gate
Proposal for an ancilla-error-transparent controlled beam splitter gate implemented via Kerr-cat qubits in circuit QED.
-
From Pauli Strings to Quantum Dynamics: A Unified Characterization
Develops an invariant-based framework connecting Pauli Lie algebras to transvection-generated Clifford subgroups for quantum reachability and dynamics analysis.
-
A sharp interaction-degree threshold for simulating QAOA
QAOA sampling hardness has a sharp threshold at interaction degree 3, where depth-1 approximate sampling implies PH collapse to the third level, but degree-2 instances remain efficiently simulable at logarithmic depth.
-
Engineering long-range and multi-body interactions via global kinetic constraints
A driven Bose-Hubbard model with global density-density interactions induces tunable global kinetic constraints for efficient implementation of multi-body gates and entangled states.
-
AutoQ 2.0: From Verification of Quantum Circuits to Verification of Quantum Programs (Technical Report)
AutoQ 2.0 verifies quantum programs with classical control flow and successfully checks RUS algorithms instantly plus weak-measurement Grover search on 100 qubits in about 20 minutes.
-
Toward fault-tolerant quantum computation exploiting quantum spatial distribution and gauge symmetry
Gauge symmetry in a 3+2-particle nested-square system corrects a unified noise model on spin/position states and permits stacked implementations of stabilizer measurements, logical Hadamard, Toffoli, and adder gates u...
-
Toward fault-tolerant quantum computation exploiting quantum spatial distribution and gauge symmetry
A 3+2 particle system on nested squares encodes Shor's nine-qubit code with gauge symmetry providing resilience to unified spin-position noise and enabling stacked architectures for logical gates and adders.
-
Toward fault-tolerant quantum computation exploiting quantum spatial distribution and gauge symmetry
Gauge symmetry combined with quantum spatial distribution in a 3+2 particle stabilizer code corrects unified decoherence and dephasing noise while enabling local implementations of error detection, Hadamard, Toffoli, ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.