A Simple Proof that Toffoli and Hadamard are Quantum Universal
arXiv:quant-ph/0301040
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.
A note. 4 pages
References in corpus (6)
- Elementary gates for quantum computation
- Two-Bit Gates are Universal for Quantum Computation
- Classical simulation of noninteracting-fermion quantum circuits
- Both Toffoli and Controlled-NOT need little help to do universal quantum computation
- On Universal and Fault-Tolerant Quantum Computing
- Encoded Universality in Physical Implementations of a Quantum Computer
Cited by in corpus (48)
- Quantum algorithms for algebraic problems
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
- ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
- Room-Temperature Photonic Logical Qubits via Second-Order Nonlinearities
- Fault-Tolerant Logical Gate Networks for CSS Codes
- Towards a universal set of topologically protected gates for quantum computation with Pfaffian qubits
- Computational Capabilities and Compiler Development for Neutral Atom Quantum Processors: Connecting Tool Developers and Hardware Experts
- Error-detection-based quantum fault tolerance against discrete Pauli noise
- ZX-calculus for the working quantum computer scientist
- Quantum circuits and low-degree polynomials over F_2
- Lectures on Quantum Tensor Networks
- Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
- Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
- Universal fault-tolerant quantum computation with Bacon-Shor codes
- Grover search and the no-signaling principle
- A ZX-Calculus with Triangles for Toffoli-Hadamard, Clifford+T, and Beyond
- QuanFuzz: Fuzz Testing of Quantum Program
- Classical simulation of quantum circuits by half Gauss sums
- State-injection schemes of quantum computation in Spekkens' toy theory
- A Regular Representation of Quantum Circuits
- Universal classical optical computing inspired by quantum information process
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- Ancilla-Error-Transparent Controlled Beam Splitter Gate
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
- Quantum simulation from the bottom up: the case of rebits
- On computation with 'probabilities' modulo k
- Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions
- Universal quantum computation with unlabeled qubits
- Quantum Radio Astronomy: Data Encodings and Quantum Image Processing
- With a Few Square Roots, Quantum Computing is as Easy as Π
- The Hadamard gate cannot be replaced by a resource state in universal quantum computation
- Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
- Generalized Boolean Functions and Quantum Circuits on IBM-Q
- On Interfacing the Brain with Quantum Computers: An Approach to Listen to the Logic of the Mind
- Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit Simulation to a New Level
- Universal quantum computation via quantum controlled classical operations
- HybridQ: A Hybrid Simulator for Quantum Circuits
- Rewriting and Completeness of Sum-Over-Paths in Dyadic Fragments of Quantum Computing
- Towards a quantum-inspired proof for IP = PSPACE
- Using Quantum Computers to Learn Physics
- A Software Package to Construct Polynomial Sets over Z_2 for Determining the Output of Quantum Computations
- Sampling and the complexity of nature
- Some Possibility and Impossibility Results related to Discrete Fourier type transforms in Quantum Information
- Quantum Programming Without the Quantum Physics
- Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
- Shortcuts to adiabaticity and applications to Quantum Computation
- Simulation of Quantum Circuits via Stabilizer Frames