Proof that $2^n \times 2^n$ operator be decomposed in terms of $2 \times 2$ operators

Question

What is the proof that any $2^n\times 2^n$ quantum operator can be expressed in terms of the tensor product of $n$ number of $2\times 2$ quantum operators acting on a single qubit space each?

Answer 1

I presume you mean a $2^n\times 2^n$ quantum operator, $U$?

Let's assume we can write $$ U=\sum_{x,y\in\{0,1\}^n}U_{xy}|x\rangle\langle y|. $$ All we have to do is show that we can construct any $|x\rangle\langle y|$ using Pauli operators. But this is just the same as $$ \bigotimes_{i=1}^n|x_i\rangle\langle y_i|, $$ so provided I can create any $|x_i\rangle\langle y_i|$ for $x_i,y_i\in\{0,1\}$ using Pauli matrices, I'm done. It's a simple exercise to check $$ |0\rangle\langle 0|=(\mathbb{I}+Z)/2\qquad |1\rangle\langle 1|=(\mathbb{I}-Z)/2 $$ and $$ |0\rangle\langle 1|=(X+iY)/2\qquad |1\rangle\langle 0|=(X-iY)/2. $$