Question: I have somehow lost sight of the big picture in my study of quantum computing. I understand that we still don't know if quantum computers are more powerful than classical ones, in the sense of computational complexity. But I'm wondering: 

Since every quantum gate can be seen as a (unitary) matrix multiplication, and matrix multiplication can be done classically in polynomial time, where is the supposed advantage coming from? What prevents me from taking a polynomial size quantum circuit and implementing it as a polynomial number of matrix multiplications (that require polynomial time)? what is the operation that is classically unavailable?

Answer: 
Matrix multiplication is polynomial in the number of matrix elements. In quantum computing the number of matrix elements is basically the number of elements in the quantum state vector, which is *exponential* in the size of the input (the number of qubits).
The false point in the premise is that a composition of single-qubit and two-qubit gates will be represented by some sort of composition of 2×2 and 4×4 matrices. In fact, if a single-qubit gate (for two-qubit this is similar) acts on the $i$-th qubit out of $n$, the matrix must be cast to
$$(Id\_2)^{\otimes (i-1)} \otimes A \otimes (Id\_2)^{\otimes (n-i)},$$
where $A$ is the original $2×2$ matrix, in order to describe its action on the $n$-qubit state. This is a matrix of dimensions $2^n × 2^n$ regardless of the type of the gate.

While the tensor product with identities looks trivial, let's just recall what it means for an application on a state vector using the most straightforward algorithm:

```
for each index u, 0 ≤ u < 2^n:
  define u_i = bit value of i-th bit of u
  define v = u XOR 2^i
  if u_i = 0:
    new (psi[u], psi[v]) = a*psi[u] + b*psi[v]
  else:
    new (psi[u], psi[v]) = d*psi[u] + c*psi[v]

```

Yes, in the core of this pseudo-algorithm there's just a 2-dimensional multiplication. But it is done $2^n$ times.

Even before one gets to *perform* the actual classical simulation, one can run out of available memory in even *storing* the state at any particular instant. Take $n = 100$ qubits, that's $2^{100}$ complex double-precision amplitudes (128 bits each). I'm getting an estimate exceeding the data storage capacity of all computers on Earth by some 14 orders of magnitude so we're not going to see that anytime soon. *Meanwhile, a quantum computer with 100 bits would just about start to be interesting for applications,* in theory it's not uncommon to see many more than that envisaged.