pith. machine review for the scientific record. sign in

arxiv: quant-ph/9503016 · v1 · submitted 1995-03-23 · 🪐 quant-ph · cond-mat· hep-th

Recognition: unknown

Elementary gates for quantum computation

A. Barenco (Oxford) , C. H. Bennett (IBM) , R. Cleve (Calgary) , D. P. DiVincenzo (IBM) , N. Margolus (MIT) , P. Shor (AT&T) , T. Sleator (NYU) , J. Smolin (UCLA)
show 1 more author
H. Weinfurter (Innsbruck)
Authors on Pith no claims yet
classification 🪐 quant-ph cond-mathep-th
keywords gatesnumberquantumrequiredbitsdeutsch-toffolielementaryinput
0
0 comments X
read the original abstract

We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values $(x,y)$ to $(x,x \oplus y)$) is universal in the sense that all unitary operations on arbitrarily many bits $n$ (U($2^n$)) can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical AND of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two-and three-bit quantum gates, the asymptotic number required for $n$-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary $n$-bit unitary operations.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Quantum measurements and the Abelian Stabilizer Problem

    quant-ph 1995-11 accept novelty 9.0

    Kitaev presents a polynomial quantum algorithm for the Abelian stabilizer problem based on measuring eigenvalues of unitary operators, generalizing Shor's factoring and discrete-log algorithms.

  2. Bridging Krylov Complexity and Universal Analog Quantum Simulator

    quant-ph 2026-05 unverdicted novelty 6.0

    Generalized Krylov complexity predicts the minimum time to realize target operations in analog quantum simulators such as Rydberg atom arrays.

  3. Quantum Simulation of the Real-time Dynamics in the multi-flavor Gross-Neveu Model at the utility scale using Superconducting Quantum Computers

    quant-ph 2026-05 unverdicted novelty 6.0

    A scalable Trotterization and Localized Diagonal Operator Approximation enable real-time quantum simulation of the multi-flavor Gross-Neveu model on utility-scale superconducting hardware.

  4. Quantum simulating multi-particle processes in high energy nuclear physics: dijet production and color (de)coherence

    hep-ph 2026-04 unverdicted novelty 6.0

    A framework is developed that encodes leading-order QCD antenna and dipole processes as quantum circuits, with benchmarks against analytic limits in simplified media.