# Are all operations simply matrix multiplication?

In the most simple example I can think of, we have:

• a linear operator $$A$$, which is also a 2 x 2 matrix.

• a vector $$|v_i⟩$$, which can be considered a 2 x 1 matrix.

If we see an example of an operation such as $$A|v_i⟩$$, which is an operation on the vector. Are we, in all cases, to consider this equivalent to a simple matrix multiplication?

Are there any other considerations to be aware of? This is fascinating stuff, thanks for considering this simple problem.

• A dot product returns a scalar (a single number). An operator $A$ acting on a ket (vector) $|v_i\rangle$ returns another vector $A|v_i\rangle$. – Mark S Sep 5 '19 at 17:05
• thanks and fixed; "dot product" subbed for general "matrix multiplication" – neutrino Sep 5 '19 at 17:07

The question is a bit vague (in other equivalent representations of QM applying operators can have nothing to do with linear algebra) so I will answer with respect to the specific example given of $$\mathbf{A} | v \rangle$$.

If you've chosen to represent your states and operators as vectors in finite-dimensional Hilbert space, then you can describe the corresponding as matrices and vectors in terms of the elements of those matrices, eg:

$$\mathbf{A} := A_{ij}\\ |v\rangle := v_i \\$$

with $$i,j = 1, \dots, 2^n$$ then yes, $$\mathbf{A} | v \rangle$$ will produce a new column vector $$c_j = \sum_i A_{ij} v_i$$ and the previous answer said as much. However, there's a more interesting an efficient way to do this! Suppose we know that $$\mathbf{A}$$ operates on only a size-k subset of the qubits that $$|v\rangle$$ is defined over and that we redefine how we index our operator and state so that they're tensors over two-dimensional axes:

$$\mathbf{A} := A_{i_1,i_2,\cdots, i_{2k}}\\ |v\rangle := v_{i_1,\cdots,i_n} \\$$

with $$i_m \in \{0, 1\}$$ and $$2k \leq n$$. This is certainly allowed because $$\mathbf{A}$$ and $$|v\rangle$$ each have the same number of elements, just arranged in different ways to make computation easier. In certain cases, this allows us to calculate the action of $$\mathbf{A}$$ more efficiently. For example if $$\mathbf{A}$$ is a permutation matrix, then computing $$\mathbf{A} | v \rangle$$ is equivalent to shuffling some of the dimensions of $$|v\rangle$$ and requires no multiplication at all$$^\dagger$$. I give a worked example of this kind of operation at the end of this post.

Finally, I'll note that simulations of Clifford circuits (wherein $$\mathbf{A} \in \{H, CNOT, S\}$$ for example and $$|v\rangle$$ is generated by a similar such circuit) uses what is essentially a lookup table to compute $$\mathbf{A} | v \rangle$$. This method also uses minimal linear algebra which is what allows simulations of those kinds of circuits to be very efficient.

Worked example

Say $$\mathbf{A}$$ is $$X^{(j)}$$, the Pauli-X operator on the j-th qubit. The procedure to compute $$X^{(j)}|v\rangle$$ is as follows:

1. Initialize $$\phi := v_{\cdots i_{j-1} ,0 ,i_{j+1} \cdots}$$
2. $$v_{\cdots i_{j-1} ,0, i_{j+1} \cdots} \rightarrow v_{\cdots i_{j-1} ,1 ,i_{j+1} \cdots}$$ ("swap" the amplitudes of $$v$$ representing $$|0\rangle_j$$ with the amplitudes representing $$|1\rangle_j$$)
3. $$v_{\cdots i_{j-1} ,1, i_{j+1} \cdots} \rightarrow \phi$$ (do another "swap", but this time use the amplitudes that we saved in step (1) that would have been overwritten otherwise)

$$^\dagger$$ In practice, this process has a lot of memory overhead and requires an exponential number of read/write operations. But often that's still better than doing matrix multiplication which can require polynomial-of-exponential resources to do the same thing.

• can you give an example of what you mean by "in other equivalent representations of QM applying operators can have nothing to do with linear algebra"? – glS Sep 9 '19 at 17:55
• The example I had in mind was the Schrodinger equation $\partial_t \psi = H \psi$ in which operators satisfy the canonical commutation relation $[x, p] = 0$. Then the equivalence follows from the Stone-von Neumann theorem. – forky40 Sep 9 '19 at 18:52

I think all unitary operations can be thought of as matrix multiplication, but something like a measurement is non-unitary, and looks like a partial trace over the density matrix, so there is a bit more going on there.