Elementary gates for quantum computation
Adriano Barenco, Charles H. Bennett, Richard Cleve et al. · Physical Review A · 1995
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\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(${2}^{\mathit{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.
Cited by 4,295 works. doi:10.1103/physreva.52.3457 Open-access PDF
Authors
- Adriano Barenco
- Charles H. Bennett
- Richard Cleve
- David Peter Divincenzo
- Norman Margolus
- Peter W. Shor
- Tycho Sleator
- John A. Smolin
- Harald Weinfurter
References
- The Principles of Quantum Mechanics
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Logical Reversibility of Computation
- Quantum computational networks
- Quantum Computations with Cold Trapped Ions
- Irreversibility and Heat Generation in the Computing Process
- Rapid solution of problems by quantum computation
- Irreversibility and heat generation in the computing process
- Two-bit gates are universal for quantum computation
- Quantum coding