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

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?

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.

• As to the first part, so you are saying CNOT is for entanglement? I thought it's just an operator that we need for reversability. But either way, isn't it a theorem which states that every 4 level matrix can be expressed as a multiple of 2 level matrices? As for second part, Toffoli gate Feb 7, 2019 at 17:15
• As for second part on Toffoli gate . I understand your point. But can't we just perform another output which would specify the input . I mean , perform some operation/s that would reveal the input. My point is , that it can be in the end much easier. No? Feb 7, 2019 at 17:31
• Also, I am reading a book. And it looks strange but it says there, that for a generalization of Toffoli gate, we can perform AND operations on all n controll-qubits and then apply a U operation on the k qubits you have for action conditioned on the control ones. So why here do they allow for an and operation if I have general n qubits for control and k for operation. Feb 7, 2019 at 18:35
• "can't we just perform another output which would specify the input". Actually, that's exactly what the Toffoli gate is. So you'd be going around in circles. Feb 7, 2019 at 20:46
• @bilanush please check out my edit, which I hope resolves any confusion you had on this question, and the other. Feb 20, 2019 at 12:08

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.

• Thanks. So CNOT is basically an entanglement operator? Are all entanglement operators are two qubits operations ? Or even a regular 4x4 matrix is considered a two qubits operation? Feb 7, 2019 at 20:12
• And please, in my book it proves that all NxN matrices can be decomposed to multiple of two level matrices so... So is a CNOT gate? Or is a CNOT gate an exception? Feb 7, 2019 at 20:14
• By that, I meant it is a fundamental operation to give rise to an entangled state. If you talk about the entanglement between two qubits only, then yes. But any highly entangled state with any $n$ qubits can be decomposed with CNOTs in a complicated manner. A $4\times 4$ is a valid two-qubit operation but it does not necessarily mean it will be non-local. Feb 7, 2019 at 20:16
• Beware the swap gate! It cannot be written in the form $A\otimes B$, but it is also not entangling. Feb 8, 2019 at 16:22
• It’s still the same issue. Nobody claims every gate can be written in the form $A\otimes B$ because that’s the tensor product not the matrix product. The vast majority of gates cannot be written in the tensor product form. Feb 20, 2019 at 20:14

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

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