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.

  • $\begingroup$ 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. $\endgroup$ Jan 23, 2019 at 18:05

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.