Composing the CNOT gate as a tensor product of two level matrices

Question

I don't understand, why is the control not gate used so often. As far as I understand it, if you apply two 2 level operations on two qubits then you get a 4 x 4 matrix by the tensor product. So how would you express the CNOT gate as a product of the one matrix acting upon the first qubit and the second acting on the second qubit?

Another thing which I have difficulty understanding is why we use so many single qubits and CNOT gates for implementing the Toffoli gate? Can't we implement it using just an AND between the first two qubits and then applying a controlled NOT for the third one?

Answer 1

The whole point is that CNOT cannot be written in the form $A\otimes B$. This is absolutely essential because if we only ever had operators of the form $A\otimes B$, states of the form $|\psi\rangle\otimes|\phi\rangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer.

As for the Toffoli construction you describe, we require that in a quantum circuit, all gates are reversible. The AND gate is not reversible as you can see from the way the number of outputs is smaller than the number of inputs (so it's impossible to know what the inputs were just by looking at the outputs).

---

The above answers the question actually asked. However, I infer from the follow up comments of the OP, both here and on other questions, that there's something else that they're trying to get at. Here's my attempt to resolve some confusion.

Any $N\times N$ matrix can be composed as a product of "two-level matrices".

This is the normal matrix product, not the tensor product. A "two-level matrix" in this context is a matrix which is the identity everywhere except for two basis elements $s$ and $t$, on which the $2\times 2$ matrix is an arbitrary unitary matrix. The controlled-not is by no means an exception to this rule. In fact, it's a particularly simple example because controlled-not is a two-level matrix where $s=10$ and $t=11$. That makes it a particularly natural building block which allows the further statement

Any $2^n\times 2^n$ two-level matrix can be decomposed in terms of $2\times 2$ two-level matrices and the special case $4\times 4$ two-level matrix that is controlled-not.

remembering that any system on which the gate does not act requires us to take the tensor product of the operator with identity in order to make it act on the correct dimension.

Answer 2

Any two qubit Controlled-U gate is not decomposable as $A\otimes B$ in general. The whole point is that a conditional operator has a non-local nature and it gives rise to non-trivial correlations when operated on a state.

The Physics behind is that; imagine a Controlled operation which can be factored as $A\otimes B$, and the sub-systems (or the two qubits) are separated non-locally in space. then the only way to perform a controlled conditional operation is to measure the state of a first qubit, convey the outcome classically to the second qubit and apply the desired unitary on the second qubit, and finally re-initialize the first qubit. But now note that this is NOT actually a 'true' controlled gate because it cannot work for an arbitrary control qubit.

Hence, the actual nature of a conditional gate is non-local, which essentially implies that it cannot be factored as $A\otimes B$ over the sub-spaces. The intuition can be taken as the operation reads system $A$ and simultaneously changes system $B$ based on the state of system $A$. This is strictly non-local in nature. Physically how it is implemented in experiments is most often by a single exchange of quanta between the states, which is triggered by the state of one sub-system. Hence, this gives rise to entanglement between the sub-systems. It is most often called the 'entanglement generator'.

Also, you can think of $\operatorname{CNOT}$ gate to be the most simplified two-qubit gate which can generate the class of two-qubit non-local gates when combined with few other gates. This is already proved by the Universality of single-qubit gates and the $\operatorname{CNOT}$ gate.

About the Toffoli gate, the most obvious way to implement it (after taking in mind the universality) is to decompose it in parts of $\operatorname{CNOT}$ gates and single qubit gates. This is what is done. And because reversibility is a must requirement for a quantum operation, you cannot use any analogous irreversible gate like the $\operatorname{AND}$ gate in quantum circuits. To perform the $\operatorname{AND}$ analogous operation as you pointed out, this is further broken up in parts of the single qubit and $\operatorname{CNOT}$ gates (to ensure the reversibility and unitarity).

PS: One essential reason why this decomposition is done because in experiments all we can implement are these single qubit and $\operatorname{CNOT}$ gates only. Any such protocol must be decomposed in these gates to cope up with some experimental implementation. And these are intuitive as well, rather than using multi-qubit gates which are nothing but a series of the single qubit gates and $\operatorname{CNOT}$s.

Answer 3

Although $CNOT$ cannot be written as $A\otimes B$, it can be written as a sum of such terms. For example:

$CNOT=\frac12I\otimes I +\frac12Z\otimes I+\frac12 I\otimes X - \frac12 Z\otimes X$.