Proof for reversible computing

For simplicity ignore constants and garbage bits, so all $N$ wires can take any of $2^{N}$ values.

The computer program performs a $2^{N} \rightarrow 2^{N}$ mapping. Consider the mapping as a truth table with $2^{N}$ rows.

There are up to $2^{N\times 2^{N}}$ possible tables.

To be reversible, from the output we can infer the input.

Each row in the truth table must be unique. I.e. the truth table contains a permutation of $2^{N}$ numbers.

There are only $2^{N}!$ truth tables (only $2^{N}!$ reversible functions). Only $e^{-2^{N}}$ functions are reversible.

Each reversible function can be represented by a number $1 \ldots 2^{N}!$

$N=6$ example

$N\times 2^{N}=384$ bits $2^{384}=3.9\ 10^{115}$
$2^{N}!= 6.3\ 10^{87}$

• Each gate implements a permutation

  If the set of gates is complete any permutation can be assembled by a suitable sequence of gates.

  For simplicity assume there is at least one way of connecting at least one gate so that it does nothing (identity function).

  
• A program is a sequence of gates.

  As the program executes (pass through each gate) the state of the $N$ lines changes from one permutation to another.

  Each gate transforms the current permutation to another. I.e. maps one number in the range $1 \ldots 2^{N}!$ to another.

  Now each gate is reversible. So each output number is uniquely mapped to one input number.

  We can represent any reversible gate by a $2^{N}! \times 2^{N}!$ square matrix where each row contains exactly one one, and each column contains exactly one one (it is double stochastic).

  $$\begin{eqnarray*} \left( \begin{array}{*{8}{c}l} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \... ...& 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array}\right) \end{eqnarray*}$$
  
  
  
  
  

• If we chose a program at random, it contains a random sequence of gates.

  At each step (gate) the current permutation is randomly changed. The next permutation depends only on the current one and the randomly chosen gate.

  This means the operation of the program is a Markov process whose update matrix is the average of all the gate matrices.

  Since the average matrix is:
  fully connected all permutations can be reached eventually
  acyclic since we have an identity operation the average matrix has at least one non-zero element on the diagonal
  double stochastic

  With long programs, all permutations are equally likely [Feller, 1957].