# How does one convert a truth table to a square permutation matrix?

Given a classical circuit of $$m$$ inputs and $$n$$ outputs, composed of various AND gates, OR gates, NOT gates, etc., a truth table is a $$2^{m}\times(m+n)$$-sized matrix, where, in general, the first $$m$$ columns encode the binary inputs while the last $$n$$ columns encode the binary outputs. When the circuit is reversible and consists of CNOT gates, CCNOT gates, CSWAP gates, etc., we have $$m=n$$ as the number of inputs is the same as the number of outputs.

However, certain square matrices can also encode the same information as a truth table. For example, for small enough $$m$$ Karnaugh maps can be used to study simplification of such circuits.

When the circuit is reversible, we can also construct a permutation matrix, which is a square matrix of size $$2^m\times 2^m$$, with a single $$1$$ in each row and each column. Such matrices are also unitary, which is a requirement for use in circuit-based quantum computing. Studying unitary matrices within quantum computing is more useful than studying other matrices such as truth tables, or other square matrices such as Karnaugh maps.

Given a truth table of a reversible circuit with, say, $$5$$ inputs and $$5$$ outputs of size $$2^5\times 10$$, how can we construct the corresponding permutation matrix of size $$2^5\times 2^5$$?

What is the general recipe or procedure for translating a truth table to the permutation/unitary matrix?

Community Wiki

In the standard convention, a state $$|\psi\rangle$$ is a column vector and operator $$M$$ is left multiplied with the state for evolution, i.e $$M|\psi\rangle = |\phi\rangle$$.

In this convention, the (row,col)=$$(i,j)$$ entry of M correspond to (output, input), i.e. if $$\{|b_k\rangle\}$$ is a basis for the Hilbert space, then $$M_{ij} = \langle b_i|M |b_j\rangle$$.

Therefore, to go from truth table to the permutation matrix, you merely have to place 1s in the right location.

Let's consider an example. For the CNOT

input output
$$|00\rangle$$ $$|00\rangle$$
$$|01\rangle$$ $$|01\rangle$$
$$|10\rangle$$ $$|11\rangle$$
$$|11\rangle$$ $$|10\rangle$$

The truth table matrix is $$T = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix}$$

To create the permutation matrix, we just have to run down the rows of T, and for each row read off the input and output, and place the 1 in the corresponding entry of the permutation matrix.

Let's start with a blank matrix, that will turn into a permutation matrix. $$P = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$$

From the first row of $$T$$ we learn that (output,input) = (00,00), which tells that the (row,col) = (0,0) must have a 1 in it. (I am going from binary 00 to decimal 0 here)

$$P = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$$

from the second row of $$T$$ we learn that (output, input) = (01, 01) = (row, col) = (1,1). Then $$P = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$$ Repeating twice more, we learn $$P = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$$