Minimal universal two-qubit controlled-NOT-based circuits

We give quantum circuits that simulate an arbitrary two-qubit unitary operator up to a global phase. For several quantum gate libraries we prove that gate counts are optimal in the worst and average cases. Our lower and upper bounds compare favorably to previously published results. Temporary storage is not used because it tends to be expensive in physical implementations. For each gate library, the best gate counts can be achieved by a single universal circuit. To compute the gate parameters in universal circuits, we use only closed-form algebraic expressions, and in particular do not rely on matrix exponentials. Our algorithm has been coded in $\mathrm{C}++$.

Figure 1

Circuit identities to move ${\sigma }_x,{\sigma }_z$ past CNOT. The ${\sigma }_x$ identity is standard in the theory of classical reversible circuits, where ${\sigma }_x$ is just the NOT gate, and amounts to the statement that $\left(1\oplus a\right)\oplus \left(1\oplus b\right)=\left(a\oplus b\right)$. The ${\sigma }_z$ identity can be obtained from it by conjugating by $H\otimes H$.

Figure 2

A universal two-qubit circuit with three CNOT gates. It requires 10 basic gates [3] or 18 gates from {CNOT, $R_y$,$R_z$}.

Figure 3

Another universal two-qubit circuit with three CNOT gates. It requires 10 basic gates [3] or 18 gates from {CNOT, $R_x,R_z$}.

Figure 4

The result of our algorithm applied to the two-qubit quantum Fourier transform. The circuit contains three one-qubit gates and three CNOTs, but the one-qubit gates are broken up into elementary gates for specificity. Here, $T_z=R_z\left(\pi ∕4\right)$ is the $T$ gate defined in [1] up to a global phase.