$\def\N{\mathbb N}\DeclareMathOperator\sym{Sym}\def\cC{\mathcal C}\def\cD{\mathcal D}\def\cP{\mathcal P}\def\cI{\mathcal W}\def\cMI{\mathcal{MW}}\DeclareMathOperator\pol{Pol}\DeclareMathOperator\inv{Inv}\DeclareMathOperator\minv{MInv}\let\pres\parallel$This is a presentation of one half of a duality for reversible transformations, analogous to the standard clone–coclone duality (such as here). It doesn’t answer the question, but it shows that all closed classes of such functions are determined by preservation of properties of a particular form.
In contrast to the standard case, the main complication is that permutations can count (they preserve cardinality), hence their invariants need to involve a bit of arithmetic to account for this.
Let me start with some tentative terminology. Fix a finite base set $A$. (In the classical case Scott asks about, $A=\{0,1\}$. Parts of the discussion also work for infinite $A$, but not the main characterization.)
A set of permutations (or: reversible transformations) is a subset $\cC\subseteq\cP:=\bigcup_{n\in\N}\sym(A^n)$, where $\sym(X)$ denotes the group of permutations of $X$. A permutation clone is a set of permutations $\cC$ such that
Each $\cC\cap\sym(A^n)$ is closed under composition.
For any $\pi\in\sym(\{1,\dots,n\})$, the permutation $\tilde\pi\in\sym(A^n)$ defined by $\tilde\pi(x_1,\dots,x_n)=(x_{\pi(1)},\dots,x_{\pi(n)})$ is in $\cC$.
If $f\in\cC\cap\sym(A^n)$ and $g\in\cC\cap\sym(A^m)$, the permutation $f\times g\in\sym(A^{n+m})$ defined by $(f\times g)(x,y)=(f(x),g(y))$ is in $\mathcal C$.
Since $A$ is finite, 1 means that $\cC\cap\sym(A^n)$ is a subgroup of $\sym(A^n)$. The OP only demands 2 for transpositions $\pi$, but the version here is clearly equivalent. Condition 3 is equivalent to what I called introduction of dummy variables in the comments above.
A master clone is a permutation clone with allowance of ancillas:
- Let $f\in\sym(A^{n+m})$, $g\in\sym(A^n)$, and $a\in A^m$ be such that $f(x,a)=(g(x),a)$ for all $x\in A^n$. Then $f\in\cC$ implies $g\in\cC$.
We aim to characterize permutation clones and master clones by certain invariants. Let me first motivate the latter by a few examples on $A=\{0,1\}$:
The master clone of permutations preserving Hamming weight (generated by the Fredkin gate). If $w$ denotes the inclusion of $\{0,1\}$ in $\N$, these permutations are characterized by the property
$$y=f(x)\implies\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i),$$
where $f\in\sym(A^n)$, and I write $x=(x_1,\dots,x_n)$.
The master clone of permutations preserving Hamming weight modulo fixed $m$, mentioned in the comments. This is characterized by the same formula as above, if we interpret $w$ as a function from $\{0,1\}$ to the cyclic group $C(m)$, and compute the sum there.
The master clone of affine permutations $f(x)=Mx\oplus b$, $M\in\mathrm{GL}(n,\mathbb F_2)$, $b\in\mathbb F_2^n$ (generated by CNOT). One checks easily (or knows from the Post case) that a single-output function $\mathbb F_2^n\to\mathbb F_2$ is affine iff it preserves the relation $x^1\oplus x^2\oplus x^3\oplus x^4=0$. Thus, if we define $w\colon\{0,1\}\to\{0,1\}$ by
$$w(x^1,x^2,x^3,x^4)=x^1\oplus x^2\oplus x^3\oplus x^4,$$
an $f\in\sym(A^n)$ is in the clone iff
$$y^1=f(x^1)\land\dots\land y^4=f(x^4)\implies\max_{i=1}^nw(x^1_i,\dots,x^4_i)=\max_{i=1}^nw(y^1_i,\dots,y^4_i),$$
so we are dealing with sums in the monoid $(\{0,1\},0,\max)$.
In general, a weight function is a mapping $w\colon A^k\to M$, where $k\in\N$, and $M$ is a commutative monoid. A master weight function is one that maps all the diagonal $k$-tuples $(a,\dots,a)$, $a\in A$, to invertible elements of $M$. Let $\cI$ denote the class of all weight functions, and $\cMI$ the master weight functions.
If $f\in\sym(A^n)$, and $w\colon A^k\to M$ is a weight function, we say that $w$ is an invariant of $f$, or (mindlessly borrowing the terminology) that $f$ is a polymorphism of $w$, and write $f\pres w$, if the following condition holds for all $(x_i^j)_{i=1..n}^{j=1..k},(y_i^j)_{i=1..n}^{j=1..k}\in A^{n\times k}$:
If $y^1=f(x^1),\dots,y^k=f(x^k)$, then
$$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).$$
Here, $x^j=(x^j_1,\dots,x^j_n)$, $x_i=(x_i^1,\dots,x_i^k)$, and similarly for $y$. In other words, $f\pres w$ if $f$ (or rather its parallel extension to $(A^k)^n$) preserves the sum of $w$-weights of its arguments.
The relation $\pres$ between $\cP$ and $\cI$ (or $\cMI$) induces a Galois connection between sets of permutations $\cC\subseteq\cP$, and classes of weight functions $\cD\subseteq\cI$, in the usual way:
\begin{align*}
\pol(\cD)&=\{f\in\cP:\forall w\in\cD\,(f\pres w)\},\\
\inv^*(\cC)&=\{w\in\cI:\forall f\in\cC\,(f\pres w)\},\\
\minv^*(\cC)&=\cMI\cap\inv^*(\cC),
\end{align*}
and thus a dual isomorphism between the complete lattices of closed sets of permutations, and closed classes of (master) weight functions, respectively. To see that we are on the right track, we observe that closed sets of permutations are indeed clones:
Lemma: If $\cD\subseteq\cI$, then $\pol(\cD)$ is a permutation clone. If $\cD\subseteq\cMI$, then $\pol(\cD)$ is a master clone.
Proof: The first assertion is more or less obvious. For the second, let $w\in\cD$, $f,g,a$ be as in condition 4 so that $f\pres w$, and let $(x_i^j),(y_i^j)$ be as in the definition of $g\pres w$. Put $\bar x^j=(x^j,a)$, $\bar y^j=(y^j,a)=f(\bar x^j)$, and $u_i=w(a_i,\dots,a_i)$. Then $f\pres w$ implies
$$\sum_{i=1}^nw(x_i)+\sum_{i=1}^mu_i=\sum_{i=1}^{n+m}w(\bar x_i)=\sum_{i=1}^{n+m}w(\bar y_i)=\sum_{i=1}^nw(y_i)+\sum_{i=1}^mu_i.$$
However, $u_i$ are invertible in $M$ as $w$ is a master weight function, hence
$$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).\tag*{QED}$$
Before we proceed further, we need to fix one problem: monoids can be huge, hence invariants of this form can be rightly suspected of being useless abstract nonsense.
First, given a weight function $w\colon A^k\to M$, we can assume that $M$ is generated by $w(A^k)$ (and by additive inverses of images of diagonal elements in the master case), as other elements of $M$ do not enter the picture. In particular, $M$ is finitely generated. Second, by general results from universal algebra, we can write $M$ as a subdirect product
$$M\subseteq\prod_{i\in I}M_i,$$
where each $M_i$ is subdirectly irreducible, and $M_i$ is a quotient of $M$ via the $i$th product projection $\pi_i$; in particular, it is still a finitely generated commutative monoid. By a result of Mal'cev, f.g. subdirectly irreducible commutative monoids (or semigroups) are in fact finite. The mapping $w_i=\pi_i\circ w\colon A^k\to M_i$ is again a weight function, master if $w$ was, and it is easy to see that
$$\pol(w)=\bigcap_{i\in I}\pol(w_i).$$
Thus, we can without loss of generality restrict attention to weight functions $w\colon A^k\to M$, where $M$ is finite and subdirectly irreducible. Let $\mathcal{FW}$ be the class of such weight functions, and put
\begin{align*}
\inv(\cC)&=\mathcal{FW}\cap\inv^*(\cC),\\
\minv(\cC)&=\mathcal{FW}\cap\minv^*(\cC).
\end{align*}
Examples of finite subdirectly irreducible commutative monoids are the cyclic groups $C(p^d)$, and the truncated addition monoids $(\{0,\dots,d\},0,\min\{d,x+y\})$. The general case is more complicated, nevertheless one can say a lot about their structure: one can write each in a certain way as a disjoint union of a $C(p^d)$, and a finite nilsemigroup with some properties. See Grillet for details.
Now we are ready for the main point of this post:
Theorem: The closed sets of permutations in the Galois connection to finite subdirectly irreducible (master) weight functions are exactly the permutation clones (master clones, resp.).
That is, if $\cC\subseteq\cP$, then the permutation clone generated by $\cC$ is $\pol(\inv(\cC))$, and the master clone generated by $\cC$ is $\pol(\minv(\cC))$.
Proof: In view of the preceding discussion, it suffices to show that if $\cC$ is a permutation clone, and $f\in\sym(A^n)\smallsetminus\cC$, there is an invariant $w\colon A^k\to M$ of $\cC$ such that $f\nparallel w$, and one can take $w$ to be a master weight function if $\cC$ is a master clone.
Put $k=|A|^n$, and let $F$ be the free monoid generated by $A^k$ (i.e., finite words over alphabet $A^k$). We define a relation $\sim$ on $F$ by
$$x_1\cdots x_m\sim y_1\cdots y_m\iff\hbox{$\exists g\in\cC\cap\sym(A^m)\,\forall j=1,\dots,k\,g(x^j_1,\dots,x^j_m)=(y^j_1,\dots,y^j_m).$}$$
(Words of unequal length are never related by $\sim$.) Since each $\cC\cap\sym(A^m)$ is a group, $\sim$ is an equivalence relation (in fact, its restriction to words of length $m$ is just the orbit equivalence relation of $\cC\cap\sym(A^m)$ acting in the obvious way on $A^{mk}$). Moreover, $\sim$ is a monoid congruence: if $g\in\cC\cap\sym(A^m)$ and $g'\in\sym(A^{m'})$ witness that $x_1\cdots x_m\sim y_1\cdots y_m$ and $x'_1\cdots x'_{m'}\sim y'_1\cdots y'_{m'}$, respectively, then $g\times g'\in\cC\cap\sym(A^{m+m'})$ witnesses $x_1\cdots x_mx'_1\cdots x'_{m'}\sim y_1\cdots y_my'_1\cdots y'_{m'}$.
Thus, we can form the quotient monoid $M=F/{\sim}$. The swap permutation witnesses that $xy\sim yx$ for each $x,y\in A^k$; that is, the generators of $M$ commute, hence $M$ is commutative. Define a weight function $w\colon A^k\to M$ as the natural inclusion of $A^k$ in $F$ composed with the quotient map.
It is easy to see that $\cC\subseteq\pol(w)$: indeed, if $g\in\cC\cap\sym(A^m)$, and $y^1=f(x^1),\dots,y^k=f(x^k)$, then
$$\sum_{i=1}^mw(x_i)=x_1\cdots x_m/{\sim}=y_1\cdots y_m/{\sim}=\sum_{i=1}^mw(y_i)$$
by the definition of $\sim$ (using the notation as in the definition of $\pres$). On the other hand, assume $f\pres w$. Let $\{a^j:j=1,\dots,k\}$ be an enumeration of $A^n$, $b^j=f(a^j)$, and let $a_i,b_i\in A^k$ for $i=1,\dots,n$ be again as in the definition of $\pres$. Then
$$a_1\cdots a_n/{\sim}=\sum_{i=1}^nw(a_i)=\sum_{i=1}^nw(b_i)=b_1\cdots b_n/{\sim},$$
hence by the definition of $\sim$, there exists $g\in\cC\cap\sym(A^n)$ such that $g(a^j)=b^j=f(a^j)$ for each $j$. However, since the $a^j$ exhaust $A^n$, this means $g=f$, i.e., $f\in\cC$, a contradiction. This completes the proof for permutation clones.
Even if $\cC$ is a master clone, $w$ needn’t be a master weight function, in fact, the diagonal elements are not even necessarily cancellative in $M$, hence we need to fix it. For each $c\in A$, let $c^*=(c,\dots,c)\in A^k$, and define a new equivalence relation $\approx$ on $F$ by
$$x_1\cdots x_m\approx y_1\cdots y_m\iff\exists c_1,\dots,c_r\in A\,x_1\cdots x_mc_1^*\cdots c_r^*\sim y_1\cdots y_mc_1^*\cdots c_r^*.$$
Using the fact that elements of $A^k$ commute modulo $\sim$, it is easy to show that $\approx$ is again a congruence, hence we can form the monoid $M'=F/{\approx}$, and a weight function $w'\colon A^k\to M'$. Since $\approx$ extends $\sim$, $M'$ is commutative, and a quotient of $M$; in particular, $\cC\subseteq\pol(w')$. On the other hand, if $f\pres w'$, then the same argument as above together with the definition of $\approx$ would give a $g\in\cC\cap\sym(A^{n+r})$, and $c_1,\dots,c_r\in A$ such that
$$g(x,c_1,\dots,c_r)=(f(x),c_1,\dots,c_r)$$
for all $x\in A^n$, thus $f\in\cC$ as $\cC$ is a master clone, a contradiction.
The definition of $\approx$ ensures that
$$xc^*\approx yc^*\implies x\approx y$$
for all $x,y\in F$, and $c\in A$. It follows that the elements $c^*/{\approx}=w'(c^*)$ are cancellative in $M'$. It is an easy well-known fact that any commutative monoid can be embedded in another one where all cancellative elements become invertible. The composition of such an embedding with $w'$ is then a master weight function $w''$, and $\pol(w')=\pol(w'')$, hence $w''\in\minv^*(\cC)\setminus\minv^*(f)$. QED
EDIT: A generalization of the clone–coclone duality above is now written up in
[1] E. Jeřábek, Galois connection for multiple-output operations, preprint, 2016, arXiv:1612.04353 [math.LO].
