Lafont normal form for linear permutation boolean circuits

This program implements the algorithm appears in Lemma 10 and Lemma 11 of the paper Towards an Algebraic Theory of Boolean Circuits. It normalizes any boolean circuit consisting of only Swap and Swap' gate. Such cicuit is called linear permutation circuit. Here

We support upto 11 bits (wires), and show upto 200 reduction steps. Use Sk and Tk to represent Swap gate and Swap' gate on k-th and (k+1)-th bit, counting from 0, top to bottom. Given a circuit represented by a sequence of Sk and Tj, this program normalize it to Lafont normal form. Here is an example (figure 16 and 17 from the paper). The left-handside normalizes to stair-like normal form on the right.

Step 1. Input a sequence of {S0 -- S9, T0 -- T9}. For example,

S1,T2,S0,T1,S0,T1,T2,S0,T1,S0

Step 2. Click Normalize button

See Also

Finding MA normal forms for single qubit operators.

Opened on: 10/10/2022. Last edited on: 10/10/2022