<p>If you allow ancilla bits (which is more natural from the computational perspective, see, e.g. the third paragraph of Section 1.2 of <a href="https://arxiv.org/abs/1504.05155" rel="nofollow noreferrer">Aaronson-Grier-Schaeffer</a>), then the answer is no. In fact, I believe there is an even stronger dichotomy, which is that the growth is either at most linear or is exponential; I'll sketch a proof.</p>
<p>In [AGS] (ibid), they give a full classification of the clones of reversible gate sets, assuming the same operations as in this question plus free ancilla bits (that must be returned to their original value at the end). Following the notation in their main result (Theorem 3), these are the classes, and I've indicated the growth rates and a sketch of proof of the growth rate.</p>
<ol>
<li>The trivial class (only allowing bit swaps). This has linear growth since it embeds <span class="math-container">$S_n$</span> and nothing else.</li>
<li>The class of all invertible transformations of <span class="math-container">$\{0,1\}^n$</span>. This precisely embeds <span class="math-container">$S_{2^n}$</span>, so it has exponential growh <span class="math-container">$2^n$</span></li>
<li>The class of all transformations that preserve Hamming weight. Since this embeds the class of all transformations via the dual-rail encoding, it embeds <span class="math-container">$S_{2^{n/2}}$</span>, so again has exponential growth rate at least <span class="math-container">$2^{n/2}$</span>.</li>
<li>For each <span class="math-container">$k \geq 3$</span>, the class of all transformations that preserve Hamming weight modulo <span class="math-container">$k$</span>. There should be a k-rail encoding so that this embeds <span class="math-container">$S_{2^{n/k}}$</span>, so for each fixed <span class="math-container">$k$</span> this has exponential growth at least <span class="math-container">$2^{n/k}$</span>.</li>
<li>The class of all <span class="math-container">$\mathbb{F}_2$</span>-affine transformations. On <span class="math-container">$n$</span> input bits, these can be realized as the action of <span class="math-container">$(n+1) \times (n+1)$</span> matrices of the form <span class="math-container">$\begin{bmatrix} A &amp; b \\ 0 &amp; 1 \end{bmatrix}$</span> acting on vectors of the form <span class="math-container">$\begin{bmatrix} x \\ 1 \end{bmatrix}$</span>. Because the symmetric group is almost simple, the Abelian part (&quot;b&quot; in the above matrix doesn't help), so it's a question of the largest symmetric group that embeds into <span class="math-container">$GL_n(\mathbb{F}_2)$</span>. For all <span class="math-container">$n &gt; 6$</span>, this is <span class="math-container">$S_{n+1}$</span>, so this has linear growth exactly <span class="math-container">$n+1$</span>.</li>
<li>The class of all affine transformations that preserve Hamming weight modulo 2. Since this is a sub-class of affine transformations, by the preceding case it has at most linear growth. (In fact, by a dual-rail trick, I believe it has growth exactly <span class="math-container">$n/2$</span>.)</li>
<li>The class of all affine transformations that preserve Hamming weight modulo 4. Similar to the previous one, growth is at most linear (and I think is precisely <span class="math-container">$n/4$</span>).</li>
<li>The class of all orthogonal transformations. Since <span class="math-container">$O_n(\mathbb{F}_2) \leq GL_n(\mathbb{F}_2)$</span>, this has growth at most <span class="math-container">$n$</span>. Since all permutation matrices are orthogonal, I believe it has growth exactly <span class="math-container">$n$</span>.</li>
<li>The class of all orthogonal transformations preserving Hamming weight modulo 4. Subclass of (8), so has at most linear growth. (My guess would be growth exactly <span class="math-container">$n/4$</span>, but I'd need to think about it a bit more.)</li>
<li>Any of the classes 1, 3, 7, 8, or 9 augmented by the NOTNOT gate (takes a 2-bit input <span class="math-container">$(x,y)$</span> to its bit-wise negation <span class="math-container">$(\neg x, \neg y)$</span>)</li>
<li>Any of the classes 1, 3, 6, 7, 8, 9 augmented by a NOT gate.</li>
</ol>
<p>For 10 and 11 there's a little work to do. Class 3 already has exponential growth, so if we augment it with anything it will still have exponential growth.</p>
<p>Note that 10 is a subclass of 11, so if we can show that for class 11 (derived from classes 1,6,7,8,9) still has at most linear growth we'll be done.</p>
<p>11.1 (class 11 derived from 1, i.e. 1 plus NOT gates) I believe we get the hyperoctahedral group <span class="math-container">$S_n \wr C_2 = S_n \ltimes \mathbb{F}_2^n$</span>, but no larger symmetric group. (Argument similar to the affine group: the <span class="math-container">$\mathbb{F}_2^n$</span> doesn't help embed any larger symmetric group because it is abelian and <span class="math-container">$S_n$</span> is almost simple nonabelian.)</p>
<p>11.6, 11.7, 11.8, 11.9: 6,7,8,9 are all subclasses of 5 (affine), and NOT is also affine. So these 11.x classes are all subclasses of affine transformations and thus have at most linear growth.</p>
<p>I don't know what happens if you don't allow ancilla bits, as I believe classifying such clones is still open.</p>

CC BY-SA 4.0
2022-05-04T18:50:33.173Z
2024-10-04T19:12:39.383Z
2024-10-04T19:12:39.383Z
Joshua Grochow
<p>Suppose that <span class="math-container">$f_{1},...,f_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$</span> are bijective functions.</p>
<p>For all <span class="math-container">$n\geq r$</span>, let <span class="math-container">$G_{f_{1},...,f_{k};r}=\subseteq S(\{0,1\}^{n})$</span> be the subgroup generated by</p>
<p>i. the functions <span class="math-container">$f_{i}\times Id_{n-r}$</span> where <span class="math-container">$Id_{n-r}:\{0,1\}^{n-r}\rightarrow\{0,1\}^{n-r}$</span> is the identity function, and</p>
<p>ii. the mappings <span class="math-container">$\pi_{\sigma}$</span> for permutations <span class="math-container">$\sigma\in S_{n}$</span> where <span class="math-container">$\pi_{\sigma}(x_{1},...,x_{n})=(x_{\sigma(1)},...,x_{\sigma(n)})$</span>.</p>
<p>Let <span class="math-container">$t_{f_{1},...,f_{k};n}$</span> be the largest natural number <span class="math-container">$m$</span> such that the symmetry group <span class="math-container">$S_{m}$</span> embeds in the group <span class="math-container">$G_{f_{1},...,f_{k};r}$</span>. We say that <span class="math-container">$(f_{1},...,f_{k})$</span> is of exponential growth if there is some <span class="math-container">$\alpha&gt;1$</span> and <span class="math-container">$c&gt;0$</span> where
<span class="math-container">$t_{f_{1},...,f_{k};n}&gt;c\cdot\alpha^{n}$</span> for all <span class="math-container">$n\geq r$</span>. We say that <span class="math-container">$(f_{1},...,f_{k})$</span> is of polynomial growth if there is some polynomial <span class="math-container">$p$</span> where <span class="math-container">$t_{f_{1},...,f_{k};n}&lt;p(n)$</span> for all <span class="math-container">$n\geq r$</span>. We say that <span class="math-container">$(f_{1},...,f_{k})$</span> is of intermediate growth if it is not of polynomial nor exponential growth. Does there exist a collection of bijective functions <span class="math-container">$(f_{1},...,f_{k})$</span> of intermediate growth?</p>

<gr.group-theory><circuits><reversible-computing>
Do there exists reversible gate sets of intermediate growth?
Joseph Van Name
# Do there exists reversible gate sets of intermediate growth?

(Asked by: username_0 on 2018-09-13)

Suppose that $f\_{1},...,f\_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$ are bijective functions.

For all $n\geq r$, let $G\_{f\_{1},...,f\_{k};r}=\subseteq S(\{0,1\}^{n})$ be the subgroup generated by

i. the functions $f\_{i}\times Id\_{n-r}$ where $Id\_{n-r}:\{0,1\}^{n-r}\rightarrow\{0,1\}^{n-r}$ is the identity function, and

ii. the mappings $\pi\_{\sigma}$ for permutations $\sigma\in S\_{n}$ where $\pi\_{\sigma}(x\_{1},...,x\_{n})=(x\_{\sigma(1)},...,x\_{\sigma(n)})$.

Let $t\_{f\_{1},...,f\_{k};n}$ be the largest natural number $m$ such that the symmetry group $S\_{m}$ embeds in the group $G\_{f\_{1},...,f\_{k};r}$. We say that $(f\_{1},...,f\_{k})$ is of exponential growth if there is some $\alpha>1$ and $c>0$ where
$t\_{f\_{1},...,f\_{k};n}>c\cdot\alpha^{n}$ for all $n\geq r$. We say that $(f\_{1},...,f\_{k})$ is of polynomial growth if there is some polynomial $p$ where $t\_{f\_{1},...,f\_{k};n} for all $n\geq r$. We say that $(f\_{1},...,f\_{k})$ is of intermediate growth if it is not of polynomial nor exponential growth. Does there exist a collection of bijective functions $(f\_{1},...,f\_{k})$ of intermediate growth?

**Tags:** gr.group-theory, circuits, reversible-computing


---

## 1 answers

### Answer by username_1 on 2022-05-04. Score: 3

If you allow ancilla bits (which is more natural from the computational perspective, see, e.g. the third paragraph of Section 1.2 of [Aaronson-Grier-Schaeffer](https://arxiv.org/abs/1504.05155)), then the answer is no. In fact, I believe there is an even stronger dichotomy, which is that the growth is either at most linear or is exponential; I'll sketch a proof.

In [AGS] (ibid), they give a full classification of the clones of reversible gate sets, assuming the same operations as in this question plus free ancilla bits (that must be returned to their original value at the end). Following the notation in their main result (Theorem 3), these are the classes, and I've indicated the growth rates and a sketch of proof of the growth rate.

1. The trivial class (only allowing bit swaps). This has linear growth since it embeds $S\_n$ and nothing else.
2. The class of all invertible transformations of $\{0,1\}^n$. This precisely embeds $S\_{2^n}$, so it has exponential growh $2^n$
3. The class of all transformations that preserve Hamming weight. Since this embeds the class of all transformations via the dual-rail encoding, it embeds $S\_{2^{n/2}}$, so again has exponential growth rate at least $2^{n/2}$.
4. For each $k \geq 3$, the class of all transformations that preserve Hamming weight modulo $k$. There should be a k-rail encoding so that this embeds $S\_{2^{n/k}}$, so for each fixed $k$ this has exponential growth at least $2^{n/k}$.
5. The class of all $\mathbb{F}\_2$-affine transformations. On $n$ input bits, these can be realized as the action of $(n+1) \times (n+1)$ matrices of the form $\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}$ acting on vectors of the form $\begin{bmatrix} x \\ 1 \end{bmatrix}$. Because the symmetric group is almost simple, the Abelian part ("b" in the above matrix doesn't help), so it's a question of the largest symmetric group that embeds into $GL\_n(\mathbb{F}\_2)$. For all $n > 6$, this is $S\_{n+1}$, so this has linear growth exactly $n+1$.
6. The class of all affine transformations that preserve Hamming weight modulo 2. Since this is a sub-class of affine transformations, by the preceding case it has at most linear growth. (In fact, by a dual-rail trick, I believe it has growth exactly $n/2$.)
7. The class of all affine transformations that preserve Hamming weight modulo 4. Similar to the previous one, growth is at most linear (and I think is precisely $n/4$).
8. The class of all orthogonal transformations. Since $O\_n(\mathbb{F}\_2) \leq GL\_n(\mathbb{F}\_2)$, this has growth at most $n$. Since all permutation matrices are orthogonal, I believe it has growth exactly $n$.
9. The class of all orthogonal transformations preserving Hamming weight modulo 4. Subclass of (8), so has at most linear growth. (My guess would be growth exactly $n/4$, but I'd need to think about it a bit more.)
10. Any of the classes 1, 3, 7, 8, or 9 augmented by the NOTNOT gate (takes a 2-bit input $(x,y)$ to its bit-wise negation $(\neg x, \neg y)$)
11. Any of the classes 1, 3, 6, 7, 8, 9 augmented by a NOT gate.

For 10 and 11 there's a little work to do. Class 3 already has exponential growth, so if we augment it with anything it will still have exponential growth.

Note that 10 is a subclass of 11, so if we can show that for class 11 (derived from classes 1,6,7,8,9) still has at most linear growth we'll be done.

11.1 (class 11 derived from 1, i.e. 1 plus NOT gates) I believe we get the hyperoctahedral group $S\_n \wr C\_2 = S\_n \ltimes \mathbb{F}\_2^n$, but no larger symmetric group. (Argument similar to the affine group: the $\mathbb{F}\_2^n$ doesn't help embed any larger symmetric group because it is abelian and $S\_n$ is almost simple nonabelian.)

11.6, 11.7, 11.8, 11.9: 6,7,8,9 are all subclasses of 5 (affine), and NOT is also affine. So these 11.x classes are all subclasses of affine transformations and thus have at most linear growth.

I don't know what happens if you don't allow ancilla bits, as I believe classifying such clones is still open.


---

