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$.

Leave a Reply

Your email address will not be published. Required fields are marked *