Elementary gates for quantum computation

Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, Harald Weinfurter

    Research output: Contribution to journalArticle

    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,xy)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(2n)] 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.

    Original languageEnglish (US)
    Pages (from-to)3457-3467
    Number of pages11
    JournalPhysical Review A
    Volume52
    Issue number5
    DOIs
    StatePublished - 1995

    ASJC Scopus subject areas

    • Atomic and Molecular Physics, and Optics

    Fingerprint Dive into the research topics of 'Elementary gates for quantum computation'. Together they form a unique fingerprint.

  • Cite this

    Barenco, A., Bennett, C. H., Cleve, R., Divincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995). Elementary gates for quantum computation. Physical Review A, 52(5), 3457-3467. https://doi.org/10.1103/PhysRevA.52.3457