# Reversible polynomial circuit iff polynomial reversible circuit?

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.

• Have you considered the bijections $L$ where $L(x,y)=(x,x\oplus f(y))$ where $f$ is any desired function? From a reversible circuit computing $L$, you can easily construct a conventional circuit for computing $f$ with very small width. Jan 23 '19 at 18:05

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.