Reversible polynomial circuit iff polynomial reversible circuit?

Question

My question is about efficiently computable bijective functions. Informally I'm interested in:

If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective gates?

I have checked the list of relevant questions and didn't spot this one. My precise setting may or may not be orthodox so I include my definitions. I believe the question is research level, but I'm happy to be proven wrong.

Let $B = \{0,1\}$. Let's define a gate as an element of $\mathrm{Alt}(B^n)$ for some finite $n$. For finite $N$ define $G_N = \bigcup_{n \leq N} \mathrm{Alt}(B^n)$, and define $G_\infty = \bigcup_n \mathrm{Alt}(B^n)$. For two gates $\pi_1 \in \mathrm{Alt}(B^m), \pi_2 \in \mathrm{Alt}(B^n)$ write $\pi = \pi_1 | \pi_2$ for the permutation $B^{m+n}$ defined by $\pi(u \cdot v) = \pi_1(u) \cdot \pi_2(v)$ for $u \in B^m, v \in B^n$, where $\cdot$ is concatenation of words. For a set of gates $G$ write $\lceil G \rceil$ for the smallest subset of $\bigcup_n \mathrm{Alt}(B^n)$ containing the identity maps and closed under well-defined function compositions $(\pi_1, \pi_2) \mapsto \pi_1 \circ \pi_2$, and under the operation $|$.

It's known that $\lceil G_N \rceil = G_\infty$ for all $N \geq 4$, let's fix $N = 4$ for concreteness. Concretely this means that any $\pi \in \mathrm{Alt}(B^n)$ for any $n \geq N$ can be written as $\pi = \phi_k \circ \cdots \circ \phi_2 \circ \phi_1$ for some $k$, where for each $\phi_i$ there exists $\ell_i$ and $\pi_i \in \mathrm{Alt}(B^4)$ such that $\phi_i(u \cdot v \cdot w) = u \cdot \pi_i(v) \cdot w$ for all $|u| = \ell_i, |v| = 4$.

For $\pi \in \mathrm{Alt}(B^n)$ an even permutation. If $n \geq 4$, define its reversible gate complexity as the minimal $k$ such that $\pi$ can be written as a composition like the one above. If $n < 4$, define the gate complexity of $\pi$ to be $1$. (One may wish to allow conjugation of gates by the permutations by $uabv \mapsto ubav$. This changes gate complexity only by a linear factor, so for the present purpose it does not matter.)

Suppose that both $\pi \in \mathrm{Alt}(B^n)$ and its inverse are efficiently computable in some sense, e.g. polynomial time, NC$^d$, logspace... Is the reversible gate complexity of $\pi$ then necessarily polynomial in $n$?

I'm interested in an answer or references.

Some observations:

• The proof of Barrington's theorem shows that for a fixed $m \geq 3$, if $\pi$ is of the special form $\pi(u \cdot w) = \psi(u, w) \cdot w$ for some function $\psi : B^m \times B^n \to B^m$, such that the permutations in the $w$-fibers $\{u \cdot w \;|\; u \in B^m\}$ are even for each $w \in B^n$, then the reversible gate complexity of $\pi$ is polynomial in $n$ whenever $\pi$ is in NC$^1$. Namely if there is an NC$^1$ circuit for $\psi$, then there is an NC$^1$ circuit (larger by a constant factor) with $2^m!/2$ special output nodes that record whether a particular permutation was performed in the first $m$ coordinates. We can then show (as in Barrington's theorem's proof) that for each node in this network, every even permutation conditioned on any value of that node, has a polynomial size circuit complexity in $n$. Now combine the ones corresponding to the new special nodes to get a polynomial gate complexity for $\pi$.

• Bennett's trick shows (among other things) that if $\pi \in \mathrm{Alt}(B^n)$ and $\pi^{-1}$ have gate complexity $m$ (computable by an acyclic network of $m$ two-input classical gates), then there is permutation $\pi' \in \mathrm{Alt}s(B^{n+m})$ with reversible gate complexity polynomial in $n + m$ such that $\pi'(u \cdot 0^{n+m}) = (\pi(u) \cdot 0^{n+m})$ for all $u \in B^n$. Namely, let $f$ compute the values of the network in the last $m$ bits, w.r.t. some topological sorting of the network (assuming they are $0$; otherwise we do not care). Let $g$ be the map that sums the $n$ answer bits to the $n$ bits after $u$. Let $h$ exchange the first and second word of length $n$. Then $h \circ f^{-1} \circ g \circ f$ proves the claim.

• One-way bijections in cryptography are permutations of $B^n$, which have the property that they can be computed in polynomial time, but cannot be inverted in polynomial time. (Their defining property is much stronger, but I don't think it's relevant here.) I don't know if this particular definition directly has anything to do with the present problem, as we're dealing with a non-uniform computation model.

Answer 1

Let $f:2^{m}\rightarrow 2^{n}$ be a function. Then define a bijection $L_{f}:2^{m}\times 2^{n}\rightarrow 2^{m}\times 2^{n}$ by letting $L_{f}(x,y)=(x,f(x)\oplus y)$. Then if $L_{f}$ has reversible gate complexity $k$, then $f$ can be computed by a $O(k)$ gate Boolean circuit of width $m+n$. In other words, $L_{f}$ has low reversible gate complexity only when $f$ is computable by a circuit of very low width.