REVIEW 17 cited by
A Simple Proof that Toffoli and Hadamard are Quantum Universal
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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.
Forward citations
Cited by 17 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.
-
On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
Short-time dynamics of geometrically local classical systems are dequantized and shown BPP-complete, while long-time dynamics are shown as powerful as exponential-time quantum computation.
-
Highly-entangled, highly-doped states that are efficiently cross-device verifiable
Two remote parties can efficiently estimate the overlap of any pair of real Clifford-transformed W-states using Bell sampling and Pauli measurements, even though these states resist classical MPS and low-magic learning.
-
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.
-
Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
Unitaries over the rings Z[1/2], Z[1/√2], Z[1/i√2], and Z[1/2,i] are exactly the circuits over four Clifford+T-derived gate sets.
-
Realified tensor networks: quantum circuit simulation on real-valued matrix accelerators
Any complex tensor network can be converted into a real-valued tensor network with arithmetic overhead 1+2m+r (never above 3x) and at most doubled intermediate sizes, with measured speedups on real-only NPUs.
-
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.
-
No-Go Theorem on Fault Tolerant Gadgets for Multiple Logical Qubits
No stabilizer code can implement the full logical Clifford group on multiple logical qubits using transversal gates, fold-transversal gates beyond two qubits, or code automorphisms.
-
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.
-
The Hardness of Learning Quantum Circuits and its Cryptographic Applications
Secure quantum cryptography (one-way state generators, signatures, commitments, encryption) is constructed from new conjectures about the hardness of learning and cloning random quantum circuit outputs.
-
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.
-
A small and interesting architecture for early fault-tolerant quantum computers
An early fault-tolerant quantum computer architecture that uses teleportation between the [[4,2,2]] and [[8,3,2]] color codes for a universal transversal gate set, plus a mirror-circuit benchmarking protocol.
-
Eigenstate Preparation on Quantum Computers
A dissertation presenting adiabatic evolution with optimal control, the Rodeo Algorithm, and a new Variational Rodeo Algorithm that uses Rodeo success probability as a variational cost function.
-
Practical Fidelity Limits of Toffoli Gates in Superconducting Quantum Processors
Benchmarking a decomposed Toffoli gate on IBM quantum hardware yields 56-64% state fidelities, but the claimed state-dependent error pattern is confounded by using different devices.
-
Progress in the development of quantum algorithms and software
A review of the Russian Quantum Center's 2020-2024 quantum software roadmap, summarizing algorithms, emulators, error correction, and cloud execution, with no new results.
-
A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
A nine-ECR-gate decomposition of the Toffoli gate is asserted without verification or comparison to known CNOT-based decompositions.
Discussion (0). Continue with ORCID to comment.