Elementary gates for quantum computation

作者：Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter W. Shor, Tycho Sleator, John A. Smolin, Harald Weinfurter · 发表于：Physical Review A · 年份：1995 · DOI：10.1103/physreva.52.3457 · 被引用次数：4415 · 研究领域：Quantum Computing Algorithms and Architecture、Quantum Information and Cryptography、Quantum-Dot Cellular Automata

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.