Htydjtk

I don't understand, why they all the time use the control not gate. 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 $Aotimes B$. This is absolutely essential because if we only ever had operators of the form $Aotimes B$, states of the form $|psirangleotimes|phirangle$ 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).

Any two qubit Controlled-U gate is not decomposable as $Aotimes 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 $Aotimes 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 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 $Aotimes 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.