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

Question

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}

Answer 1

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} $$