Both Toffoli and controlled-NOT need little help to do universal quantum computing

What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.

• Publication year

  2002

• Venue

  Quantum information & computation

• Publication date

  2002-05-18

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv quant-ph/0205115
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Classical and Quantum Computation

  2002influential reference
• A new universal and fault-tolerant quantum basis

  2000influential reference
• The Heisenberg Representation of Quantum Computers

  1998influential reference
• Reliable quantum computers

  1997cited by this paper
• Quantum computations: algorithms and error correction

  1997influential reference
• A fast quantum mechanical algorithm for database search

  1996cited by this paper
• Elementary gates for quantum computation.

  1995influential reference

• Free quantum computing.

  2026cites this paper
• Tensor Decomposition for Non-Clifford Gate Minimization

  2026cites this paper
• Progress in the development of quantum algorithms and software

  2025cites this paper
• Preparation of cat states in many-body eigenbasis via non-local measurement

  2025cites this paper
• Practical Fidelity Limits of Toffoli Gates in Superconducting Quantum Processors

  2025cites this paper
• One rig to control them all

  2025cites this paper
• Exact distinguishability between real-valued and complex-valued Haar random quantum states

  2025cites this paper
• Anticoherent $k$-planes and coding techniques for a 3-qubit scheme of universal quantum computing

  2025cites this paper
• Universality of a standard two-qubit gate by catalytic embedding

  2025cites this paper
• A small and interesting architecture for early fault-tolerant quantum computers

  2025cites this paper
• Two bases suffice for QMA1-completeness

  2025cites this paper
• Further improvements to stabilizer simulation theory: classical rewriting of CSS-preserving stabilizer circuits, quadratic form expansions of stabilizer operations, and framed hidden variable models

  2025cites this paper
• Hardware-aware Toffoli gate decomposition via echoed cross-resonance gates

  2025cites this paper
• Full Quantum Stack: Ket Platform

  2025cites this paper
• Scalable Improvement of the Generalized Toffoli Gate Realization Using Trapped-Ion-Based Qutrits.

  2024cites this paper
• Qudit-Generalization of the Qubit Echo and Its Application to a Qutrit-Based Toffoli Gate

  2024cites this paper
• Feasibility of All Single-Qubit Gates with Four InGaAs Quantum Dots Coupled to Two Silver Nanowires

  2024cites this paper
• A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits

  2024cites this paper
• How to Bake a Quantum Π

  2023influential citation
• Rewriting and Completeness of Sum-Over-Paths in Dyadic Fragments of Quantum Computing

  2023cites this paper
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming

  2023cites this paper
• Fault Tolerant Quantum Error Mitigation

  2023cites this paper
• Guest Column: The 7 faces of quantum NP

  2023cites this paper
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation

  2023cites this paper
• High-fidelity transmon coupler activated CCZ gate on fluxonium qubits

  2023cites this paper
• Notes on Quantum Computation and Information

  2023cites this paper
• Full-magnetic implementation of a classical Toffoli gate

  2023cites this paper
• The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality

  2023cites this paper
• Visualizing Quantum Circuit Probability - estimating computational action for quantum program synthesis

  2023cites this paper
• Single plasmon routing with the four quantum dots coupled to a cross-type plasmonic waveguide

  2023cites this paper
• Optimized synthesis of circuits for diagonal unitary matrices with reflection symmetry

  2023cites this paper
• A Quantum Algorithm for Functions of Multiple Commuting Hermitian Matrices

  2023cites this paper
• Quantum Merlin-Arthur proof systems for synthesizing quantum states

  2023cites this paper
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation

  2023cites this paper
• Improved Synthesis of Toffoli-Hadamard Circuits

  2023cites this paper
• Scalable quantum processors empowered by the Fermi scattering of Rydberg electrons

  2023cites this paper
• Quantum Control Machine: The Limits of Quantum Programs as Data

  2023cites this paper
• Simple Qudit ZX and ZH Calculi, via Integrals

  2023cites this paper
• Completeness of the ZX-calculus

  2022cites this paper
• Some efficient quantum circuit implementations of Camellia

  2022influential citation
• Completeness of Sum-Over-Paths for Toffoli-Hadamard and the Clifford Hierarchy

  2022cites this paper
• An improvement on the versatility of secure multi-party quantum computation protocol: exploitation of triorthogonal quantum error-correcting codes

  2022cites this paper
• A Multi-Qubit Quantum Gate Using the Zeno Effect

  2022cites this paper
• Quantum Fourier Addition, Simplified to Toffoli Addition

  2022cites this paper
• Graphical calculus for Tensor Network Contractions

  2022cites this paper
• A review on quantum information processing in cavities

  2022cites this paper
• Clique Homology is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{QMA}}}_{1}$$\end{document}QMA1-hard

  2022cites this paper
• Controlled-Controlled-Phase Gates for Superconducting Qubits Mediated by a Shared Tunable Coupler

  2022cites this paper
• Completeness of Sum-Over-Paths for Toffoli-Hadamard and the Dyadic Fragments of Quantum Computation

  2022cites this paper
• Eliminating Intermediate Measurements using Pseudorandom Generators

  2021cites this paper
• Quantum Theory from Principles, Quantum Software from Diagrams

  2021cites this paper
• Entanglement of random hypergraph states

  2021cites this paper
• Room-temperature photonic logical qubits via second-order nonlinearities

  2021cites this paper
• Completeness of the ZH-calculus

  2021cites this paper
• On Lagrangian Formalism of Quantum Computation

  2021cites this paper
• Quantum Meets the Minimum Circuit Size Problem

  2021cites this paper
• Detecting Qubit-coupling Faults in Ion-trap Quantum Computers

  2021cites this paper
• Optimization of CNOT circuits under topological constraints

  2021cites this paper
• The ZH-calculus: completeness and extensions ∗

  2021cites this paper
• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits

  2021influential citation
• Multi-server blind quantum computation protocol with limited classical communication among servers

  2021cites this paper
• Equivalence checking of quantum circuits by nonlocality

  2021cites this paper
• J un 2 02 1 Generators and Relations for the Group O n ( Z [ 1 2 ] )

  2021cites this paper
• Discretization, the Road to Quantum Computing?

  2021cites this paper
• Generators and Relations for the Group On(Z[1/2])

  2021cites this paper
• Universal quantum computation via quantum controlled classical operations

  2021influential citation
• Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

  2020cites this paper
• Constant-round Blind Classical Verification of Quantum Sampling

  2020cites this paper
• A review on reversible quantum adders

  2020cites this paper
• Universality for Doubly Stochastic Matrices

  2020cites this paper
• Towards Quantum-Enhanced Machine Learning for Network Intrusion Detection

  2020cites this paper
• Well-tempered ZX and ZH Calculi

  2020cites this paper
• Qudits and High-Dimensional Quantum Computing

  2020cites this paper
• Quantum Computing and Programming

  2020cites this paper
• ZX-calculus for the working quantum computer scientist

  2020cites this paper
• Quantum feedback for measurement and control

  2020cites this paper
• On the Theory of Modern Quantum Algorithms

  2020influential citation
• Optically controlled quantum gates for three spin qubits in quantum dot–microcavity coupled systems

  2019cites this paper
• Optimization of CNOT circuits on topological superconducting processors

  2019cites this paper
• Optimization of CNOT circuits on limited-connectivity architecture

  2019cites this paper
• Repetition cat-qubits: fault-tolerant quantum computation with highly reduced overhead

  2019cites this paper
• A Survey on quantum computing technology

  2019cites this paper
• Holistic type extension for classical propositional logic in quantum computation

  2019cites this paper
• Quantum Computing: An Applied Approach

  2019cites this paper
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits

  2019cites this paper
• Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup

  2019cites this paper
• Analog and Digital Quantum Simulation of Fermionic Systems: Superconducting Emulator Circuits and Effects of Gate Errors

  2019influential citation
• Universal variational quantum computation

  2019cites this paper
• Holistic Type Extension for Classical Logic via Toffoli Quantum Gate

  2019cites this paper
• Completeness of the ZX-Calculus

  2019cites this paper
• Quantum computing with sine-Gordon qubits

  2019cites this paper
• High‐Fidelity Universal Quantum Controlled Gates on Electron‐Spin Qubits in Quantum Dots Inside Single‐Sided Optical Microcavities

  2019cites this paper
• University of Birmingham ZH

  2019cites this paper
• Machine-learning-based three-qubit gate design for the Toffoli gate and parity check in transmon systems

  2019cites this paper
• Spin-valley system in a gated MoS2-monolayer quantum dot

  2019cites this paper
• J ul 2 01 9 A quantum homomorphic encryption scheme for polynomial-sized circuits

  2019cites this paper
• Feasible Surface Plasmon Routing Based on the Self-Assembled InGaAs/GaAs Semiconductor Quantum Dot Located Between Two Silver Metallic Waveguides

  2019cites this paper
• Fault-tolerant quantum computing with three-dimensional surface codes

  2019cites this paper
• The ZX-Calculus is a powerful graphical language for quantum reasoning and quantum computing introduced

  2019cites this paper
• Towards a quantum-inspired proof for IP = PSPACE

  2019cites this paper