Minimal Universal Two-Qubit Controlled-NOT-Based Circuits

Published

March 10, 2004

Author(s)

V V. Shende, I L. Markov, Stephen Bullock

Abstract

We show how to implement an arbitrary two-qubit unitary operation in several universal gate libraries using the smallest possible number of gates. To this end, we prove that n-qubit circuits using CNOT and one-qubit gates require at least [1/4 (4n - 3n -1)] CNOT gates in the worst case. For two-qubit operators, this yields a lower bound of three gates, which we match with an upper bound of three gates.Using quantum circuit identities, we improve an earlier lower bound of 17 elementary gates by Bullock and Markov to 18, and their upper bound of 23 elementary gates to 18. We also improve upon the generic circuit with six CNOT gates by Zhang et al. (our circuit uses three), and that by Vidal and Dawson with 11 basic gates (we use 10). Given the available results, it appears that some universal gate libraries are at a disadvantage, at least in the sense that no construction is known to produce smallest possible circuits.

Citation

Physical Review A (Atomic, Molecular and Optical Physics)

Volume

69

Pub Type

Journals

Download Paper

Local Download

Keywords

optimal, quantum circuit, two-qubit

Citation

Shende, V. , Markov, I. and Bullock, S. (2004), Minimal Universal Two-Qubit Controlled-NOT-Based Circuits, Physical Review A (Atomic, Molecular and Optical Physics), [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50706 (Accessed May 3, 2026)

Additional citation formats