# QCQI notes: Why single qubit and CNOT gates are universal?

We know that the combination of single-qubit and CNOT gates are universal, they can be used to implement arbitrary operation on n qubits. In this post, we go through this part of QCQI (section 4.5.2).

## References

[1] Nielsen MA, Chuang I. Quantum computation and quantum information.

## Two-level decomposition

In the previous post QCQI: How to decompose unitary matrices and quantum gates? we introduce the procedure to decompose an arbitrary unitary matrix into a product of several two-level matrices. In fact, a two-level matrix can be implemented in a simple way, just with some CNOT gates and single-qubit gates.

## Examples

### Acts only on 000 and 111

If we want to implement such a unitary operation,

$U=\left[\begin{array}{llllllll}{a} & {0} & {0} & {0} & {0} & {0} & {0} & {c} \\ {0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0} \\ {b} & {0} & {0} & {0} & {0} & {0} & {0} & {d}\end{array}\right]$

and $a,b,c,d$ are arbitrary complex number such that $\tilde{U} \equiv\left[\begin{array}{ll}{a} & {c} \\ {b} & {d}\end{array}\right]$ is unitary. Here go through the procedure in a more detailed way.

First of all, we consider the function of $U$, it is obviously,

$|000\rangle \rightarrow a|000\rangle+b|111\rangle$

$|111\rangle \rightarrow c|000\rangle+d|111\rangle$

$U$ only acts on the states $|000\rangle$ and $|111\rangle$, then the gray code connecting $000$ and $111$ is easy to give,

$\begin{array}{ccc}{A} & {B} & {C} \\ {0} & {0} & {0} \\ {0} & {0} & {1} \\ {0} & {1} & {1} \\ {1} & {1} & {1}\end{array}$

hence the circuit of this procedure is also easy to design, here the states of every step are marked,

### Acts only on 010 and 111

First of all, we recall how to recognize the target states of $U$, the method is shown in the following figure,

As we see, the above two-level matrix acts only on $|010\rangle$ and $|111\rangle$. Hence $\tilde{U} \equiv\left[\begin{array}{ll}{a} & {c} \\ {b} & {d}\end{array}\right]$. It actually acts like,

$|010\rangle \rightarrow a|010\rangle+b|111\rangle$

$|111\rangle \rightarrow c|010\rangle+d|111\rangle$

We consider its Gray code,

$\begin{array}{ccc}{A} & {B} & {C} \\ {0} & {1} & {0} \\ {0} & {1} & {1} \\ {1} & {1} & {1}\end{array}$

Hence the circuits can be designed as,

## Discussion

This procedure is simple, however, the effect is magical. The unitary operator $U$ only acts on $|000\rangle, |111\rangle$ and remains the others unchanged. How ever we can not achieve this effect with any single-qubit gate, in the example above, any single-qubit gate will affect FOUR states instead of TWO. In the figure above, the first two quantum gates have done one important thing, manipulated the qubits B and C both to $|1\rangle$ ONLY when the input state is $|000\rangle$,  it is easy to check that, for the other input state, no change occurs. Their function is actually filtering the states $|000\rangle$.

The function of the $CC-\tilde{U}$ is obviously, it performs the $\tilde{U}$ on qubit $A$ controlled by $B, C$ . It is important that in the previous two gates, $A$ always acts as a control qubit, this means the amplitude of eigenstates of the first qubit does not change before the $CC-\tilde{U}$. Hence qubit $A$ is a “platform” for the operation on $|011\rangle$ and $|111\rangle$, as the figure is shown,

The last step is to transform the eigenstates which are modified in the first step to their corresponding original states, however, due to the effects of $latex \tilde{U}$, we cannot restore the modified states exactly to their original state, for example,

However, the point key is that when the original eigenstate of $|011\rangle$ is nontrivial, its amplitude should be added into the amplitude that is coming from the result of $\tilde{U}$, and then, will be transformed into $|000\rangle$ and $|111\rangle$.