Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Minimal Universal Two-Qubit Controlled-NOT-Based Circuits



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


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.
Physical Review A (Atomic, Molecular and Optical Physics)


optimal, quantum circuit, two-qubit


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], (Accessed April 14, 2024)
Created March 9, 2004, Updated October 12, 2021