While discussing the relation of the model of reversible computing with quantum computing, my professor made a remark like:
Consider the model of reversible classical circuits on $n$ bits, where the gates are (say) arbitrary permutations of the 8 values of 3 bits. The total group of permutations that you can make in this case is the alternating group $A_{2^n}$ if $n$ is at least 4. (Exercise: Why are odd permutations impossible?)
Now I'm a bit confused here. Shouldn't the group of all possible permutations for $n$ bit be the symmetric group $S_{2^n}$? I'm not sure why it's the alternating group and not the symmetric group. Moreover, why should $n$ be at least 4 and why aren't odd permutations allowed? Even some hints would be helpful.
The proof that only even permutations can be achieved in this way if $n\ge4$ is essentially the proof of Lemma $11$ on page $8$ of this paper. Obviously, if $n=3$, you have the entire $S_3$, so assume $n\ge4$. Then for each permutation that you can apply to $3$ bits, there's a bit that's left unaffected. The overall permutation thus decomposes into a permutation of the values with that bit set and a permutation of the values with that bit cleared, and these permutations have identical cycle structure. It follows that every cycle length occurs an even number of times in the overall permutation, and thus the overall permutation is even.