Do there exists reversible gate sets of intermediate growth?

Question

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}<p(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?

Answer 1

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), 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.