How to represent an $n$-qubit circuit in matrix form?

Question

If a given quantum circuit has $n$ qubit inputs and a certain number of gates, how can we represent the whole circuit in matrix form? Here's an example:

I am sorry, I am confused on how to express the circuit above in matrix form. Especially on how I'll be a able to take into consideration the circuit lines affected by a Toffoli gate? How does the matrix representation of the first Toffoli gate (read from left to right) differ to the matrix representation of the second Toffoli gate since they have different control and target lines. Also what's the difference of the matrix representation of the NOT gate applied to the first circuit line to a NOT gate applied to the second line?

Thank you.

Answer 1

The overall matrix can be built from the knowledge of the matrices representing each element of the circuit (in your example, the Toffoli and single-qubit gates) by simple matrix multiplication.

To obtain the matrix representation of a Toffoli gate acting between three qubits, a good way to start is by first writing down its bra-ket representation. This amounts to writing down how the gate operates on the various elements of the computational basis. In this case, this would amount to

1. List all the elements of the computational basis of five qubits, that is, all bit-strings of length $5$: $|00000\rangle,|00001\rangle,|00010\rangle$ etc.
2. Determine how the gate under consideration acts on each one of these states. For example, the first Toffoli in the circuit sends $|00000\rangle$ to $|00000\rangle$, but $|11000\rangle$ to $|11100\rangle$.
3. Write down the operation as a sum of operators of the form $|q_p\rangle\!\langle p|$, where $|p\rangle$ ranges over all computational basis elements, and $q_p$ is the element obtained by acting with the gate over $|p\rangle$.

To obtain the matrix representation, you now build the matrix whose $p$-th column has a single $1$ at the position $q_p$ (note that the bra-ket representation of the gate is not actually necessary here, it's just a way to write down the action of the gate in a systematic way, but can be skipped once you are familiar with the process).

For example, the action of the first Toffoli gate in your circuit can be written as $$ |11100\rangle\!\langle 11000| + |11000\rangle\!\langle 11100| + (\text{identity over all other elements}). $$ The matrix representation is then the matrix which only differs from the diagonal by its acting off-diagonally in the positions corresponding to $|11000\rangle$ and $|11100\rangle$. Note that which positions correspond to these states partly depends on the notation you are using. A standard notation is to list computational basis states as if you were counting in binary, so $|00000\rangle\to 0$, $|00001\rangle\to 1,...,|11000\rangle\to 2^4 + 2^3=24$, etc.

This trick will work to find the matrix representation of any gate which acts as a permutation over computational basis elements.

Answer 2

As mentioned in answer by qIS, you should decompose the circuit to steps. In case no gate is applied in the circuit, you have to replace this empty place with identity operator $I$ acting on one qubit.

Note, that symbol $CCNOT$ is used for Toffoli gate.

Here are matrices describing each step:

1. $S_1 = I \otimes X \otimes I \otimes I \otimes I$
2. $S_2 = CCNOT \otimes I \otimes I$
3. $S_3 = X \otimes X \otimes I \otimes I \otimes I$
4. $S_4 = CCNOT_{1,2 \rightarrow 4} \otimes I $. Matrix $CCNOT_{1,2 \rightarrow 4}$ is a Toffoli gate controlled by first and second qubit but acting on fourth qubit. If you follow construction proposed by qIS you will get matrix shown below.
5. $S_5 = I \otimes I \otimes X \otimes X \otimes I$
6. $S_6 = I \otimes I \otimes CCNOT$

The last step to obtain matrix desribing whole circuit is to do matrix multiplication $S_{6}S_{5}S_{4}S_{3}S_{2}S_{1}$.

Matrix $CCNOT_{1,2 \rightarrow 4}$: