%0 Journal Article %1 Barenco1995Elementary %A Barenco, A. %A Bennett, C. H. %A Cleve, R. %A DiVincenzo, D. P. %A Margolus, N. %A Shor, P. %A Sleator, T. %A Smolin, J. %A Weinfurter, H. %D 1995 %I American Physical Society %J Physical Review A %K quantumcomputing %N 5 %P 3457--3467 %R 10.1103/physreva.52.3457 %T Elementary gates for quantum computation %U http://dx.doi.org/10.1103/physreva.52.3457 %V 52 %X 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 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.

@article{Barenco1995Elementary, 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.}}, added-at = {2019-02-23T22:09:48.000+0100}, archiveprefix = {arXiv}, author = {Barenco, A. and Bennett, C. H. and Cleve, R. and DiVincenzo, D. P. and Margolus, N. and Shor, P. and Sleator, T. and Smolin, J. and Weinfurter, H.}, biburl = {https://www.bibsonomy.org/bibtex/21180dc6499889d502c169d309add6060/cmcneile}, citeulike-article-id = {7016824}, citeulike-linkout-0 = {http://arxiv.org/abs/quant-ph/9503016}, citeulike-linkout-1 = {http://arxiv.org/pdf/quant-ph/9503016}, citeulike-linkout-2 = {http://dx.doi.org/10.1103/physreva.52.3457}, citeulike-linkout-3 = {http://link.aps.org/abstract/PRA/v52/i5/p3457}, citeulike-linkout-4 = {http://link.aps.org/pdf/PRA/v52/i5/p3457}, day = 23, doi = {10.1103/physreva.52.3457}, eprint = {quant-ph/9503016}, interhash = {7616b120065c576257dd8faf9786e8a6}, intrahash = {1180dc6499889d502c169d309add6060}, issn = {1050-2947}, journal = {Physical Review A}, keywords = {quantumcomputing}, month = mar, number = 5, pages = {3457--3467}, posted-at = {2017-07-16 12:12:52}, priority = {2}, publisher = {American Physical Society}, timestamp = {2019-02-23T22:15:27.000+0100}, title = {{Elementary gates for quantum computation}}, url = {http://dx.doi.org/10.1103/physreva.52.3457}, volume = 52, year = 1995 }