<p>$\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 <a href="http://www.thi.uni-hannover.de/fileadmin/forschung/esslli/07/csp.pdf" rel="nofollow noreferrer">here</a>). 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.</p>

<p>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.</p>

<p>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.)</p>

<p>A <em>set of permutations</em> (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 <em>permutation clone</em> is a set of permutations $\cC$ such that</p>

<blockquote>
  <ol>
  <li><p>Each $\cC\cap\sym(A^n)$ is closed under composition.</p></li>
  <li><p>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$.</p></li>
  <li><p>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$.</p></li>
  </ol>
</blockquote>

<p>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.</p>

<p>A <em>master clone</em> is a permutation clone with allowance of ancillas:</p>

<blockquote>
  <ol start="4">
  <li>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$.</li>
  </ol>
</blockquote>

<p>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\}$:</p>

<ul>
<li><p>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)$.</p></li>
<li><p>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.</p></li>
<li><p>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)$.</p></li>
</ul>

<p>In general, a <em>weight function</em> is a mapping $w\colon A^k\to M$, where $k\in\N$, and $M$ is a commutative monoid. A <em>master weight function</em> 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.</p>

<p>If $f\in\sym(A^n)$, and $w\colon A^k\to M$ is a weight function, we say that $w$ is an <em>invariant of $f$</em>, or (mindlessly borrowing the terminology) that $f$ is a <em>polymorphism of $w$</em>, 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}$:</p>

<blockquote>
  <p>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).$$</p>
</blockquote>

<p>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.</p>

<p>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)&amp;=\{f\in\cP:\forall w\in\cD\,(f\pres w)\},\\
\inv^*(\cC)&amp;=\{w\in\cI:\forall f\in\cC\,(f\pres w)\},\\
\minv^*(\cC)&amp;=\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:</p>

<blockquote>
  <p><strong>Lemma:</strong> If $\cD\subseteq\cI$, then $\pol(\cD)$ is a permutation clone. If $\cD\subseteq\cMI$, then $\pol(\cD)$ is a master clone.</p>
</blockquote>

<p><strong>Proof:</strong> 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}$$</p>

<p>Before we proceed further, we need to fix one problem: monoids can be <em>huge</em>, hence invariants of this form can be rightly suspected of being useless abstract nonsense.</p>

<p>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 <em>finitely generated</em>. 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 <em>finite</em>. 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)&amp;=\mathcal{FW}\cap\inv^*(\cC),\\
\minv(\cC)&amp;=\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 <a href="http://projecteuclid.org/euclid.pjm/1102817095" rel="nofollow noreferrer">Grillet</a> for details.</p>

<p>Now we are ready for the main point of this post:</p>

<blockquote>
  <p><strong>Theorem:</strong> The closed sets of permutations in the Galois connection to finite subdirectly irreducible (master) weight functions are exactly the permutation clones (master clones, resp.).</p>
  
  <p>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))$.</p>
</blockquote>

<p><strong>Proof:</strong> 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.</p>

<p>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'}$.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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</p>

<hr>

<p>EDIT: A generalization of the clone–coclone duality above is now written up in</p>

<p>[1] E. Jeřábek, <em>Galois connection for multiple-output operations</em>, preprint, 2016, <a href="https://arxiv.org/abs/1612.04353" rel="nofollow noreferrer">arXiv:1612.04353 [math.LO]</a>.</p>

CC BY-SA 3.0
2014-09-18T00:02:07.030Z
Meanwhile, I have progress to report on the concrete question.  I was able to classify all the points in the lattice above the Fredkin gate: the only possibilities are the transformations that preserve the Hamming weight mod k for any k, the transformations that either preserve or flip the Hamming weight mod 2 (generated by Fredkin+NOT), and all transformations.  I can also characterize all points in the lattice above CNOTNOT: they're only the ones I listed in the OP (CNOTNOT+NOT, CNOT, Fredkin+NOTNOT, Fredkin+NOT, everything).
Scott Aaronson
CC BY-SA 3.0
2014-09-18T12:12:51.913Z
Yes, for Fredkin+NOT, we can take $M=C(2)$, $w(x,y)=x\oplus y$. Thanks for the update, this sounds very good.
Emil Jeřábek
CC BY-SA 3.0
2014-09-18T13:23:45.463Z
What Luke and I have been wondering about this morning, is how to use these beautiful "Galois correspondences" to help with concrete classification tasks. (E.g., how does the clone/coclone duality help for Post's original classification problem?) In the reversible case, I notice that the invariants that come from your proof could involve as many as $k=|A|^n$ inputs at a time: if $|A|=2$ and $n$ is 3 or 4 or 5, that could already get a bit unwieldy, no? And of course, nothing in your proof is specific to the $|A|=2$ case, but we know things will get way more complicated when $|A|>2$.
Scott Aaronson
CC BY-SA 3.0
2014-09-18T17:29:34.660Z
OK, more progress on the classification.  I can now show that there are no classes that include a Controlled-U gate, where U is anything other than the identity, besides the ones we've already classified (i.e., the ones that include either Fredkin or CNOTNOT).  More generally, let a Controlled-(U,V) gate be one that applies U to the 2nd through kth bits if the 1st bit is 1, or V to those bits if the 1st bit is 0, while leaving the 1st bit alone.  Then there are no classes that include a Controlled-(U,V) gate for U!=V, besides the ones we've already classified.
Scott Aaronson
CC BY-SA 3.0
2014-09-18T19:23:41.540Z
The hope is of course that the invariants are in practice much smaller than what falls out of the proof. (In the Post case, I believe the worst that can happen is $k\le n+1$.) The Galois connection does not directly help with concrete classification, it is more a methodological tool. First, it may be easier to find previously unidentified classes if one knows what kind of properties to look for. Second, a typical step in the proof of Post’s classification looks as follows. We got to a class $C$ somewhere in the middle of the lattice, and we want to describe the classes above it. ...
Emil Jeřábek
CC BY-SA 3.0
2014-09-18T19:30:34.940Z
... $C$ is determined by its invariant relations $R_1,\dots,R_k$. Then any proper extension of $C$ must contain an $f$ that does not preserve some $R_i$, and usually one can then manipulate $f$ by composition etc. into a particular function in a small number of variables. In this way, one gets a list $f_1,\dots,f_c$ such that every class strictly above $C$ contains the class generated by $C\cup\{f_i\}$ for some $i$, and one can proceed to the part of the lattice above that. This doesn't need the general correspondence, but knowing the invariants of the particular classes one encounters.
Emil Jeřábek
CC BY-SA 3.0
2014-09-17T23:57:57.363Z
Thanks so much for the effort it must've taken to write this up! It will take me time to digest it, as the language of clones and universal algebra is quite abstract for me (indeed, that was a stumbling block when I tried to read this literature in the past). But as we work out the clones concretely, it's useful to know that they'll all be characterized by invariants, as indeed all the examples we knew are. (Incidentally, to see, say, Fredkin+NOT as characterized by an invariant, I guess we look at *pairs* of inputs, and say that every transform preserves the sum of their parities?)
Scott Aaronson
CC BY-SA 3.0
2014-09-17T16:39:02.713Z
2016-12-14T06:50:06.123Z
2016-12-14T06:50:06.123Z
Emil Jeřábek
<p><a href="http://en.wikipedia.org/wiki/Post&#39;s_lattice">Post's lattice</a>, described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the linear functions over GF(2), and all functions.  (Post didn't assume that the constants 0 and 1 were available for free, which made his lattice much more complicated than it would be otherwise.)</p>

<p>My question is whether anything analogous has ever been published for classical <i>reversible</i> gates, like the Toffoli and Fredkin gates.  I.e., which classes of reversible transformations on {0,1}<sup>n</sup> can be generated by some collection of reversible gates?  Here are the rules: you're allowed an unlimited number of ancilla bits, some preset to 0 and others preset to 1, <i>as long as all the ancilla bits are returned to their initial settings once your transformation of {0,1}<sup>n</sup> is finished.</i>  Also, a SWAP of 2 bits (i.e., a relabeling of their indices) is always available for free.  Under these rules, my student Luke Schaeffer and I were able to identify the following ten sets of transformations:</p>

<ol>
<li>The empty set</li>
<li>The set generated by the NOT gate</li>
<li>The set generated by NOTNOT (i.e., NOT gates applied to any 2 of the bits)</li>
<li>The set generated by CNOT (i.e., the Controlled-NOT gate)</li>
<li>The set generated by CNOTNOT (i.e., flip the 2nd and 3rd bits iff the 1st bit is 1)</li>
<li>The set generated by CNOTNOT and NOT</li>
<li>The set generated by the Fredkin (i.e., Controlled-SWAP) gate</li>
<li>The set generated by Fredkin and CNOTNOT</li>
<li>The set generated by Fredkin, CNOTNOT, and NOT</li>
<li>The set of all transformations</li>
</ol>

<p>We'd like to identify any remaining families, and then prove that the classification is complete---but before we spend much time on it, we'd like to know whether anyone has done it before.</p>

CC BY-SA 3.0
2015-04-21T14:53:32.117Z
See the paper http://eccc.hpi-web.de/report/2015/066/ in which these ideas have been polished, and which also references Emil's answer below.
András Salamon
CC BY-SA 3.0
2014-09-10T22:30:44.150Z
Are you missing NOTCSWAP and (CSWAP,NOTCSWAP) where NOTCSWAP is like a controlled-swap but swaps its x,y arguments when its c argument is 0 (instead of swapping when c is 1 as in a CSWAP)? You need both of these to get all Hamming weight preserving permutations: CSWAP permutes only vectors of Hamming weight ≥2 while NOTCSWAP permutes only vectors of Hamming weight ≤n-2.
David Eppstein
CC BY-SA 3.0
2014-09-10T22:34:39.543Z
Also (ran out of room in previous comment) by requiring a larger number of control bits to be zero or nonzero you can get even more limited subsets of the Hamming weight preserving permutations, only permuting vectors with Hamming weight at least or at most an arbitrary bound. So this gives countably many classes of transformations.
David Eppstein
CC BY-SA 3.0
2014-09-10T23:49:16.003Z
Thanks, David -- but I assumed 0 and 1 ancillas were available for free, precisely in order to rule out such "perversities."  Does it not do so?
Scott Aaronson
CC BY-SA 3.0
2014-09-11T07:45:12.703Z
Ok, I guess. That's a bit of a weird assumption, though, in the reversible case, unless you require that these auxiliary values only are used as inputs to gates that have an output always equal to that input.
David Eppstein
CC BY-SA 3.0
2014-09-11T12:35:30.037Z
As I said in the OP, we demand that the ancilla bits *eventually* get returned to their initial states, by the end of the computation.  That's perfectly sufficient for (e.g.) quantum interference, or other applications of reversibility.
Scott Aaronson
CC BY-SA 3.0
2014-09-13T17:03:33.873Z
I wonder whether there is a variant of the clone–coclone duality for these transformations.
Emil Jeřábek
CC BY-SA 3.0
2014-09-13T17:26:02.967Z
By the way, you didn’t state it explicitly, but I take it that apart from variable permutations and ancilla bit removal, you want the classes to contain the identity and be closed under composition and introduction of dummy variables?
Emil Jeřábek
CC BY-SA 3.0
2014-09-13T20:06:30.377Z
Let $C_n$ be the class of all permutations preserving Hamming weight modulo $n$. Then $C_n$ satisfies your requirements, and $C_n\subseteq C_m$ iff $m|n$: the noninclusions of $C_n$ elsewhere are witnessed by the $n$-ary function $f_n$ s.t. $f_n(0^n)=1^n$, $f_n(1^n)=0^n$, and $f(x)=x$ for $x\ne0^n,1^n$. In particular, all these infinitely many classes are distinct.
Emil Jeřábek
CC BY-SA 3.0
2014-09-14T19:25:18.197Z
One can get more classes by intersection. In particular, the class of affine functions (= generated by CNOT) has a nontrivial intersection with $C_4$, containing e.g. the function $f(x_1,\dots,x_6)$ that negates all variables iff $x_1\oplus\dots\oplus x_6=1$. I suspect one can do a similar thing for every $C_{2^k}$.
Emil Jeřábek
CC BY-SA 3.0
2014-09-14T21:01:56.010Z
Kenichi Morita has a lot of results on reversible automata. [Recent work](http://eptcs.web.cse.unsw.edu.au/paper.cgi?MCU2013.3) of his examines reversible gates having one bit of memory, finding a surprisingly small number of closed classes, with some tantalizing open questions.
Matt
CC BY-SA 3.0
2014-09-14T21:12:27.793Z
Do your ancillary bits mean that you have fan-out available?  Post assumes it is free, as does Pippenger in chapter 1 of his Theories of Computability.  If it is not free, then you have to consider functions with multiple outputs (which is not customary in the non-reversible world), and the lattice gets much more complicated (but the gate implementability question does remain decidable, barely). I do not know of work on closed sets of _reversible_ gates, except for Morita's work.
Matt
CC BY-SA 3.0
2014-09-14T21:22:48.323Z
@Emil: The clone-coclone duality depends heavily on the availability of fan-out.  I spent quite a bit of effort trying to develop a modified form of duality to cover those parts of the lattice which are not above fan-out (and thus not part of Post's lattice), but to no avail.
Matt
CC BY-SA 3.0
2014-09-14T21:49:41.830Z
@Matt: Yes. I’m not asking for the dual notion here to resemble coclones as such. Rather, the clone–coclone duality shows that clones are completely determined by relations they preserve, and I believe it is reasonable to expect that closed classes of reversible transformations are also determined by preservation of *something*. (Certainly all classes given above can be recast that way.) Figuring out what kind of *something* should we be looking for here might help a lot with identification of closed classes and description of the lattice.
Emil Jeřábek
CC BY-SA 3.0
2014-09-14T23:07:50.030Z
Emil: Yes, the classes contain the identity (which follows from the fact that you can always apply no gates).  I'm not sure what it means to be closed under introduction of dummy variables -- how is that different from allowing ancillas?
Scott Aaronson
CC BY-SA 3.0
2014-09-14T23:12:05.463Z
Also, Emil: I should have clarified this, but we're really interested in the "limit" of the set of transformations that you can generate, as the number of bits n gets large.  This rules out any constructions (like yours) that work only for some particular value of n.  (Maybe this even follows from our allowing an unlimited number of ancillas, without needing to say anything additional?)
Scott Aaronson
CC BY-SA 3.0
2014-09-14T23:43:18.730Z
Incidentally, for anyone who wants to think about this, I should say that Luke and I made some progress this weekend.  We can now show that, once you have a CNOTNOT gate (i.e., you're above the "CNOTNOT" point in the lattice), there are no classes of transformations other than the 6 that I listed in the OP.  And I believe we can also prove that any nonempty class of conservative transformations generates the Fredkin gate.
Scott Aaronson
CC BY-SA 3.0
2014-09-15T05:40:10.427Z
@Emil: I agree. It feels like the preservation of relations in this case is in the _space_ of the circuit, rather than in _time_ (e.g. monotonic functions preserve non-decreasingness (a relation applied independently to each wire in the circuit) over time). So things will be rather different.
Matt
CC BY-SA 3.0
2014-09-15T10:18:11.303Z
@Scott: Introduction of dummy variables means that from a function $f\colon\{0,1\}^n\to\{0,1\}^n$, you can produce a function $g\colon\{0,1\}^m\to\{0,1\}^m$ such that $g(x,y)=(f(x),y)$. It *increases* the number of variables. The ancilla bit operation produces $g$ from $f$ if there is $a$ such that for all $x$, $f(x,a)=(g(x),a)$. It *decreases* the number of variables. The two are kind of inverse to each other, and you need both.
Emil Jeřábek
CC BY-SA 3.0
2014-09-15T10:21:53.343Z
@Scott: I have no idea what you mean by “limit”, and how could it preclude my examples. If two classes of functions differ for functions on $n$ variables, they also differ for functions on $n'$ variables for every $n'\ge n$ (by introduction of dummy variables).
Emil Jeřábek
CC BY-SA 3.0
2014-09-15T11:32:45.943Z
I sense there is some confusion going on. The $m$ in $C_m$ is a constant that parametrizes the class, it has nothing to do with the number of variables. If it helps you understand it, three of the $C_m$ classes already appear on your list: $C_1$ is 10, $C_2$ (= parity-preserving transformations) is 8, and $C_0$ (= Hamming weight-preserving; is this what you call “conservative”?) is 7. If it also helps, $C_m$ (for $m\ne1$) is generated by Controlled-SWAP and the $f_m$ function I defined in the original comment.
Emil Jeřábek
CC BY-SA 3.0
2014-09-15T13:57:12.240Z
@Emil: OK, you're absolutely right, and I'm sorry for being dense.  I had indeed thought you were restricting the number of variables, but no, even with no such restriction, you can get infinitely many inequivalent classes using the $C_m$'s you proposed.  And thanks for explaining what you meant by "dummy variables" -- one indeed has that.
Scott Aaronson
<circuit-families>
Classifying reversible gates
Scott Aaronson
# Classifying reversible gates

(Asked by: username_0 on 2014-09-10)

[Post's lattice](http://en.wikipedia.org/wiki/Post's_lattice), described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the linear functions over GF(2), and all functions. (Post didn't assume that the constants 0 and 1 were available for free, which made his lattice much more complicated than it would be otherwise.)

My question is whether anything analogous has ever been published for classical *reversible* gates, like the Toffoli and Fredkin gates. I.e., which classes of reversible transformations on {0,1}n can be generated by some collection of reversible gates? Here are the rules: you're allowed an unlimited number of ancilla bits, some preset to 0 and others preset to 1, *as long as all the ancilla bits are returned to their initial settings once your transformation of {0,1}n is finished.* Also, a SWAP of 2 bits (i.e., a relabeling of their indices) is always available for free. Under these rules, my student Luke Schaeffer and I were able to identify the following ten sets of transformations:

1. The empty set
2. The set generated by the NOT gate
3. The set generated by NOTNOT (i.e., NOT gates applied to any 2 of the bits)
4. The set generated by CNOT (i.e., the Controlled-NOT gate)
5. The set generated by CNOTNOT (i.e., flip the 2nd and 3rd bits iff the 1st bit is 1)
6. The set generated by CNOTNOT and NOT
7. The set generated by the Fredkin (i.e., Controlled-SWAP) gate
8. The set generated by Fredkin and CNOTNOT
9. The set generated by Fredkin, CNOTNOT, and NOT
10. The set of all transformations

We'd like to identify any remaining families, and then prove that the classification is complete---but before we spend much time on it, we'd like to know whether anyone has done it before.

**Tags:** circuit-families
> **Comments:**
> **username_2**: Are you missing NOTCSWAP and (CSWAP,NOTCSWAP) where NOTCSWAP is like a controlled-swap but swaps its x,y arguments when its c argument is 0 (instead of swapping when c is 1 as in a CSWAP)? You need both of these to get all Hamming weight preserving permutations: CSWAP permutes only vectors of Hamming weight ≥2 while NOTCSWAP permutes only vectors of Hamming weight ≤n-2.  
> **username_2**: Also (ran out of room in previous comment) by requiring a larger number of control bits to be zero or nonzero you can get even more limited subsets of the Hamming weight preserving permutations, only permuting vectors with Hamming weight at least or at most an arbitrary bound. So this gives countably many classes of transformations.  
> **username_0**: Thanks, David -- but I assumed 0 and 1 ancillas were available for free, precisely in order to rule out such "perversities."  Does it not do so?  
> **username_2**: Ok, I guess. That's a bit of a weird assumption, though, in the reversible case, unless you require that these auxiliary values only are used as inputs to gates that have an output always equal to that input.  
> **username_0**: As I said in the OP, we demand that the ancilla bits *eventually* get returned to their initial states, by the end of the computation.  That's perfectly sufficient for (e.g.) quantum interference, or other applications of reversibility.  
> **username_3**: I wonder whether there is a variant of the clone–coclone duality for these transformations.  
> **username_3**: By the way, you didn’t state it explicitly, but I take it that apart from variable permutations and ancilla bit removal, you want the classes to contain the identity and be closed under composition and introduction of dummy variables?  
> **username_3**: Let $C_n$ be the class of all permutations preserving Hamming weight modulo $n$. Then $C_n$ satisfies your requirements, and $C_n\subseteq C_m$ iff $m|n$: the noninclusions of $C_n$ elsewhere are witnessed by the $n$-ary function $f_n$ s.t. $f_n(0^n)=1^n$, $f_n(1^n)=0^n$, and $f(x)=x$ for $x\ne0^n,1^n$. In particular, all these infinitely many classes are distinct.  
> **username_3**: One can get more classes by intersection. In particular, the class of affine functions (= generated by CNOT) has a nontrivial intersection with $C_4$, containing e.g. the function $f(x_1,\dots,x_6)$ that negates all variables iff $x_1\oplus\dots\oplus x_6=1$. I suspect one can do a similar thing for every $C_{2^k}$.  
> **username_4**: Kenichi Morita has a lot of results on reversible automata. [Recent work](http://eptcs.web.cse.unsw.edu.au/paper.cgi?MCU2013.3) of his examines reversible gates having one bit of memory, finding a surprisingly small number of closed classes, with some tantalizing open questions.  
> **username_4**: Do your ancillary bits mean that you have fan-out available?  Post assumes it is free, as does Pippenger in chapter 1 of his Theories of Computability.  If it is not free, then you have to consider functions with multiple outputs (which is not customary in the non-reversible world), and the lattice gets much more complicated (but the gate implementability question does remain decidable, barely). I do not know of work on closed sets of _reversible_ gates, except for Morita's work.  
> **username_4**: @Emil: The clone-coclone duality depends heavily on the availability of fan-out.  I spent quite a bit of effort trying to develop a modified form of duality to cover those parts of the lattice which are not above fan-out (and thus not part of Post's lattice), but to no avail.  
> **username_3**: @Matt: Yes. I’m not asking for the dual notion here to resemble coclones as such. Rather, the clone–coclone duality shows that clones are completely determined by relations they preserve, and I believe it is reasonable to expect that closed classes of reversible transformations are also determined by preservation of *something*. (Certainly all classes given above can be recast that way.) Figuring out what kind of *something* should we be looking for here might help a lot with identification of closed classes and description of the lattice.  
> **username_0**: Emil: Yes, the classes contain the identity (which follows from the fact that you can always apply no gates).  I'm not sure what it means to be closed under introduction of dummy variables -- how is that different from allowing ancillas?  
> **username_0**: Also, Emil: I should have clarified this, but we're really interested in the "limit" of the set of transformations that you can generate, as the number of bits n gets large.  This rules out any constructions (like yours) that work only for some particular value of n.  (Maybe this even follows from our allowing an unlimited number of ancillas, without needing to say anything additional?)  
> **username_0**: Incidentally, for anyone who wants to think about this, I should say that Luke and I made some progress this weekend.  We can now show that, once you have a CNOTNOT gate (i.e., you're above the "CNOTNOT" point in the lattice), there are no classes of transformations other than the 6 that I listed in the OP.  And I believe we can also prove that any nonempty class of conservative transformations generates the Fredkin gate.  
> **username_4**: @Emil: I agree. It feels like the preservation of relations in this case is in the _space_ of the circuit, rather than in _time_ (e.g. monotonic functions preserve non-decreasingness (a relation applied independently to each wire in the circuit) over time). So things will be rather different.  
> **username_3**: @Scott: Introduction of dummy variables means that from a function $f\colon\{0,1\}^n\to\{0,1\}^n$, you can produce a function $g\colon\{0,1\}^m\to\{0,1\}^m$ such that $g(x,y)=(f(x),y)$. It *increases* the number of variables. The ancilla bit operation produces $g$ from $f$ if there is $a$ such that for all $x$, $f(x,a)=(g(x),a)$. It *decreases* the number of variables. The two are kind of inverse to each other, and you need both.  
> **username_3**: @Scott: I have no idea what you mean by “limit”, and how could it preclude my examples. If two classes of functions differ for functions on $n$ variables, they also differ for functions on $n'$ variables for every $n'\ge n$ (by introduction of dummy variables).  
> **username_3**: I sense there is some confusion going on. The $m$ in $C_m$ is a constant that parametrizes the class, it has nothing to do with the number of variables. If it helps you understand it, three of the $C_m$ classes already appear on your list: $C_1$ is 10, $C_2$ (= parity-preserving transformations) is 8, and $C_0$ (= Hamming weight-preserving; is this what you call “conservative”?) is 7. If it also helps, $C_m$ (for $m\ne1$) is generated by Controlled-SWAP and the $f_m$ function I defined in the original comment.  
> **username_0**: @Emil: OK, you're absolutely right, and I'm sorry for being dense.  I had indeed thought you were restricting the number of variables, but no, even with no such restriction, you can get infinitely many inequivalent classes using the $C_m$'s you proposed.  And thanks for explaining what you meant by "dummy variables" -- one indeed has that.  
> **username_1**: See the paper http://eccc.hpi-web.de/report/2015/066/ in which these ideas have been polished, and which also references Emil's answer below.  

---

## 1 answers

### Answer by username_3 on 2014-09-17. Score: 13 | Accepted answer

$\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](http://www.thi.uni-hannover.de/fileadmin/forschung/esslli/07/csp.pdf)). 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

> 1. Each $\cC\cap\sym(A^n)$ is closed under composition.
> 2. 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$.
> 3. 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:

> 4. 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](http://projecteuclid.org/euclid.pjm/1102817095) 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]](https://arxiv.org/abs/1612.04353).

> **Comments:**
> **username_0**: Thanks so much for the effort it must've taken to write this up! It will take me time to digest it, as the language of clones and universal algebra is quite abstract for me (indeed, that was a stumbling block when I tried to read this literature in the past). But as we work out the clones concretely, it's useful to know that they'll all be characterized by invariants, as indeed all the examples we knew are. (Incidentally, to see, say, Fredkin+NOT as characterized by an invariant, I guess we look at *pairs* of inputs, and say that every transform preserves the sum of their parities?)  
> **username_0**: Meanwhile, I have progress to report on the concrete question.  I was able to classify all the points in the lattice above the Fredkin gate: the only possibilities are the transformations that preserve the Hamming weight mod k for any k, the transformations that either preserve or flip the Hamming weight mod 2 (generated by Fredkin+NOT), and all transformations.  I can also characterize all points in the lattice above CNOTNOT: they're only the ones I listed in the OP (CNOTNOT+NOT, CNOT, Fredkin+NOTNOT, Fredkin+NOT, everything).  
> **username_3**: Yes, for Fredkin+NOT, we can take $M=C(2)$, $w(x,y)=x\oplus y$. Thanks for the update, this sounds very good.  
> **username_0**: What Luke and I have been wondering about this morning, is how to use these beautiful "Galois correspondences" to help with concrete classification tasks. (E.g., how does the clone/coclone duality help for Post's original classification problem?) In the reversible case, I notice that the invariants that come from your proof could involve as many as $k=|A|^n$ inputs at a time: if $|A|=2$ and $n$ is 3 or 4 or 5, that could already get a bit unwieldy, no? And of course, nothing in your proof is specific to the $|A|=2$ case, but we know things will get way more complicated when $|A|>2$.  
> **username_0**: OK, more progress on the classification.  I can now show that there are no classes that include a Controlled-U gate, where U is anything other than the identity, besides the ones we've already classified (i.e., the ones that include either Fredkin or CNOTNOT).  More generally, let a Controlled-(U,V) gate be one that applies U to the 2nd through kth bits if the 1st bit is 1, or V to those bits if the 1st bit is 0, while leaving the 1st bit alone.  Then there are no classes that include a Controlled-(U,V) gate for U!=V, besides the ones we've already classified.  
> **username_3**: The hope is of course that the invariants are in practice much smaller than what falls out of the proof. (In the Post case, I believe the worst that can happen is $k\le n+1$.) The Galois connection does not directly help with concrete classification, it is more a methodological tool. First, it may be easier to find previously unidentified classes if one knows what kind of properties to look for. Second, a typical step in the proof of Post’s classification looks as follows. We got to a class $C$ somewhere in the middle of the lattice, and we want to describe the classes above it. ...  
> **username_3**: ... $C$ is determined by its invariant relations $R_1,\dots,R_k$. Then any proper extension of $C$ must contain an $f$ that does not preserve some $R_i$, and usually one can then manipulate $f$ by composition etc. into a particular function in a small number of variables. In this way, one gets a list $f_1,\dots,f_c$ such that every class strictly above $C$ contains the class generated by $C\cup\{f_i\}$ for some $i$, and one can proceed to the part of the lattice above that. This doesn't need the general correspondence, but knowing the invariants of the particular classes one encounters.  

---

