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

CC BY-SA 4.0
2019-01-23T22:05:02.287Z
2019-01-23T22:05:02.287Z
Joseph Van Name
<p>My question is about efficiently computable bijective functions. Informally I'm interested in:</p>

<blockquote>
  <p>If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective gates?</p>
</blockquote>

<p>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.</p>

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

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

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

<blockquote>
  <p>Suppose that both <span class="math-container">$\pi \in \mathrm{Alt}(B^n)$</span> and its inverse are efficiently computable in some sense, e.g. polynomial time, NC<span class="math-container">$^d$</span>, logspace... Is the reversible gate complexity of <span class="math-container">$\pi$</span> then necessarily polynomial in <span class="math-container">$n$</span>?</p>
</blockquote>

<p>I'm interested in an answer or references.</p>

<p>Some observations:</p>

<ul>
<li><p>The proof of Barrington's theorem shows that for a fixed <span class="math-container">$m \geq 3$</span>, if <span class="math-container">$\pi$</span> is of the special form <span class="math-container">$\pi(u \cdot w) = \psi(u, w) \cdot w$</span> for some function <span class="math-container">$\psi : B^m \times B^n \to B^m$</span>, such that the permutations in the <span class="math-container">$w$</span>-fibers <span class="math-container">$\{u \cdot w \;|\; u \in B^m\}$</span> are even for each <span class="math-container">$w \in B^n$</span>, then the reversible gate complexity of <span class="math-container">$\pi$</span> is polynomial in <span class="math-container">$n$</span> whenever <span class="math-container">$\pi$</span> is in NC<span class="math-container">$^1$</span>. Namely if there is an NC<span class="math-container">$^1$</span> circuit for <span class="math-container">$\psi$</span>, then there is an NC<span class="math-container">$^1$</span> circuit (larger by a constant factor) with <span class="math-container">$2^m!/2$</span> special output nodes that record whether a particular permutation was performed in the first <span class="math-container">$m$</span> 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 <span class="math-container">$n$</span>. Now combine the ones corresponding to the new special nodes to get a polynomial gate complexity for <span class="math-container">$\pi$</span>.</p></li>
<li><p>Bennett's trick shows (among other things) that if <span class="math-container">$\pi \in \mathrm{Alt}(B^n)$</span> and <span class="math-container">$\pi^{-1}$</span> have gate complexity <span class="math-container">$m$</span> (computable by an acyclic network of <span class="math-container">$m$</span> two-input classical gates), then there is permutation <span class="math-container">$\pi' \in \mathrm{Alt}s(B^{n+m})$</span> with reversible gate complexity polynomial in <span class="math-container">$n + m$</span> such that <span class="math-container">$\pi'(u \cdot 0^{n+m}) = (\pi(u) \cdot 0^{n+m})$</span> for all <span class="math-container">$u \in B^n$</span>. Namely, let <span class="math-container">$f$</span> compute the values of the network in the last <span class="math-container">$m$</span> bits, w.r.t. some topological sorting of the network (assuming they are <span class="math-container">$0$</span>; otherwise we do not care). Let <span class="math-container">$g$</span> be the map that sums the <span class="math-container">$n$</span> answer bits to the <span class="math-container">$n$</span> bits after <span class="math-container">$u$</span>. Let <span class="math-container">$h$</span> exchange the first and second word of length <span class="math-container">$n$</span>. Then <span class="math-container">$h \circ f^{-1} \circ g \circ f$</span> proves the claim.</p></li>
<li><p>One-way bijections in cryptography are permutations of <span class="math-container">$B^n$</span>, 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.</p></li>
</ul>

CC BY-SA 4.0
2019-01-23T18:05:14.720Z
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.
Joseph Van Name
<circuit-complexity><permutations><reversible-computing>
Reversible polynomial circuit iff polynomial reversible circuit?
Ville Salo
# Reversible polynomial circuit iff polynomial reversible circuit?

(Asked by: username_0 on 2019-01-14)

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.

**Tags:** circuit-complexity, permutations, reversible-computing
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2019-01-23. Score: 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.


---

