<p>I have some great news. If you know how to compute a function and its inverse, then you may compute the function reversibly without producing any garbage information (though the computation needs to temporarily use <a href="https://en.wikipedia.org/wiki/Ancilla_bit" rel="noreferrer">ancilla</a> bits for scratchwork). Let me informally state and prove a couple of results.</p>

<p>$\textbf{Theorem 1:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ is a function which is easy to compute.
Then there exists a known and easy to compute reversible circuit $H:\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x}))$ on each input $\mathbf{x}$</p>

<p>$\mathbf{Proof:}$ It is a standard process to turn a conventional irreversible circuit into a reversible circuit at the expense where one produces a lot of garbage information along with the desired output (I will leave the process of simulating irreversible gates such as the AND gate and the OR gate by saving the inputs and using reversible gates such as Toffoli gates or Fredkin gates). Therefore, there exists a circuit $C$ along with a function $L$ such that $$C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{z})=
(0,f(\mathbf{x}),L(\mathbf{x}),\mathbf{z})$$ for each $\mathbf{x},\mathbf{z}$. Let $N$ be the circuit where $N(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{z})=
(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{x}\oplus\mathbf{z})$. Then
let $H=C^{-1}\circ N\circ C$. Then</p>

<p>$$H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$</p>

<p>$$=C^{-1}\circ N\circ C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$</p>

<p>$$=C^{-1}\circ N(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),\mathbf{0})$$</p>

<p>$$=C^{-1}(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),f(\mathbf{x}))$$</p>

<p>$$=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x})).$$</p>

<p>Q.E.D.</p>

<p>The technique used in Theorem 1 is known as the compute ($C$)-copy ($N$)-<a href="https://en.wikipedia.org/wiki/Uncomputation" rel="noreferrer">uncompute</a> ($C^{-1}$) technique. This technique is essential for reversible algorithms and quantum algorithms. Since reversible circuits cannot delete any information, for a non-bijective function $f$, one must save the input $\mathbf{x}$. However, the following theorem shows that it is possible to reversibly compute a bijective function without needing to save the input $\mathbf{x}$.</p>

<p>$\textbf{Theorem 2:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijective function with inverse $f^{-1}$. Suppose furthermore that an irreversible circuit that computes $f$ and an irreversible circuit that computes $f^{-1}$ are known. Then there exists a reversible circuit
$K:\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}$ such that
$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{0},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit string $\mathbf{x}.$</p>

<p>$\mathbf{Proof:}$ By Theorem 1, there exists a reversible circuit $H$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{x},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit input $\mathbf{x}$.</p>

<p>Now, there exists a reversible circuit $D:\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}$ along with a function
$L:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ such that
$D(\mathbf{y},\mathbf{0})=(f^{-1}(\mathbf{y}),L(\mathbf{y}))$ for each $\mathbf{y}\in\{0,1\}^{n}$. Let $M:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}$ be the function defined by $M(\mathbf{x},\mathbf{y})=(\mathbf{x}\oplus\mathbf{y},\mathbf{y})$.</p>

<p>Let
$$K=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)\circ H.$$ </p>

<p>Then $K$ is easily computable by a reversible circuit. However, for each $\mathbf{x}\in\{0,1\}^{n}$, we have
$$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)\circ H(\mathbf{x},\mathbf{0},\mathbf{0})$$</p>

<p>$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)(\mathbf{x},f(\mathbf{x}),\mathbf{0})$$</p>

<p>$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})(\mathbf{x},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$</p>

<p>$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})(\mathbf{x},\mathbf{x},L(f(\mathbf{x}))$$</p>

<p>$$=(\mathrm{Id}_{n}\times D^{-1})(\mathbf{0},\mathbf{x},L(f(\mathbf{x}))$$</p>

<p>$$=(\mathrm{Id}_{n}\times D^{-1})(\mathbf{0},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$</p>

<p>$$=(\mathbf{0},f(\mathbf{x}),\mathbf{0}).$$ Q.E.D.</p>

CC BY-SA 3.0
2018-03-01T04:29:23.960Z
2018-03-01T04:29:23.960Z
Joseph Van Name
<p>Consider an invertible function that maps an $N$ bit string $x$ to an $N$ bit string $f(x)$. Let us use $F(x)$ to denote the inverse of the function $f(x)$, such that $F(f(x)) = x$.</p>

<p>Suppose that I know a circuit with ${\rm poly} \, N$ reversible Boolean logic gates that can compute this function. However, it also produces an additional output string $g(x)$ (with may be a copy of the input, for example).</p>

<p>Given this scenario, I have two questions that I believe to be equivalent.</p>

<ul>
<li><p>Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit that only outputs $f(x)$?</p></li>
<li><p>Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit to output $F(x)$ (and may or may not also output some $G(x)$)?</p></li>
</ul>

<cc.complexity-theory>
Complexity of computing invertible functions with reversible circuits
Matthew Matic
# Complexity of computing invertible functions with reversible circuits

(Asked by: username_0 on 2013-11-14)

Consider an invertible function that maps an $N$ bit string $x$ to an $N$ bit string $f(x)$. Let us use $F(x)$ to denote the inverse of the function $f(x)$, such that $F(f(x)) = x$.

Suppose that I know a circuit with ${\rm poly} \, N$ reversible Boolean logic gates that can compute this function. However, it also produces an additional output string $g(x)$ (with may be a copy of the input, for example).

Given this scenario, I have two questions that I believe to be equivalent.

* Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit that only outputs $f(x)$?
* Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit to output $F(x)$ (and may or may not also output some $G(x)$)?

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2018-03-01. Score: 5 | Accepted answer

I have some great news. If you know how to compute a function and its inverse, then you may compute the function reversibly without producing any garbage information (though the computation needs to temporarily use [ancilla](https://en.wikipedia.org/wiki/Ancilla_bit) bits for scratchwork). Let me informally state and prove a couple of results.

$\textbf{Theorem 1:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ is a function which is easy to compute.
Then there exists a known and easy to compute reversible circuit $H:\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x}))$ on each input $\mathbf{x}$

$\mathbf{Proof:}$ It is a standard process to turn a conventional irreversible circuit into a reversible circuit at the expense where one produces a lot of garbage information along with the desired output (I will leave the process of simulating irreversible gates such as the AND gate and the OR gate by saving the inputs and using reversible gates such as Toffoli gates or Fredkin gates). Therefore, there exists a circuit $C$ along with a function $L$ such that $$C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{z})=
(0,f(\mathbf{x}),L(\mathbf{x}),\mathbf{z})$$ for each $\mathbf{x},\mathbf{z}$. Let $N$ be the circuit where $N(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{z})=
(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{x}\oplus\mathbf{z})$. Then
let $H=C^{-1}\circ N\circ C$. Then

$$H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$

$$=C^{-1}\circ N\circ C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$

$$=C^{-1}\circ N(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),\mathbf{0})$$

$$=C^{-1}(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),f(\mathbf{x}))$$

$$=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x})).$$

Q.E.D.

The technique used in Theorem 1 is known as the compute ($C$)-copy ($N$)-[uncompute](https://en.wikipedia.org/wiki/Uncomputation) ($C^{-1}$) technique. This technique is essential for reversible algorithms and quantum algorithms. Since reversible circuits cannot delete any information, for a non-bijective function $f$, one must save the input $\mathbf{x}$. However, the following theorem shows that it is possible to reversibly compute a bijective function without needing to save the input $\mathbf{x}$.

$\textbf{Theorem 2:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijective function with inverse $f^{-1}$. Suppose furthermore that an irreversible circuit that computes $f$ and an irreversible circuit that computes $f^{-1}$ are known. Then there exists a reversible circuit
$K:\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}$ such that
$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{0},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit string $\mathbf{x}.$

$\mathbf{Proof:}$ By Theorem 1, there exists a reversible circuit $H$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{x},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit input $\mathbf{x}$.

Now, there exists a reversible circuit $D:\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}$ along with a function
$L:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ such that
$D(\mathbf{y},\mathbf{0})=(f^{-1}(\mathbf{y}),L(\mathbf{y}))$ for each $\mathbf{y}\in\{0,1\}^{n}$. Let $M:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}$ be the function defined by $M(\mathbf{x},\mathbf{y})=(\mathbf{x}\oplus\mathbf{y},\mathbf{y})$.

Let
$$K=(\mathrm{Id}\_{n}\times D^{-1})\circ(M\times\mathrm{Id}\_{m})\circ(\mathrm{Id}\_{n}\times D)\circ H.$$

Then $K$ is easily computable by a reversible circuit. However, for each $\mathbf{x}\in\{0,1\}^{n}$, we have
$$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathrm{Id}\_{n}\times D^{-1})\circ(M\times\mathrm{Id}\_{m})\circ(\mathrm{Id}\_{n}\times D)\circ H(\mathbf{x},\mathbf{0},\mathbf{0})$$

$$=(\mathrm{Id}\_{n}\times D^{-1})\circ(M\times\mathrm{Id}\_{m})\circ(\mathrm{Id}\_{n}\times D)(\mathbf{x},f(\mathbf{x}),\mathbf{0})$$

$$=(\mathrm{Id}\_{n}\times D^{-1})\circ(M\times\mathrm{Id}\_{m})(\mathbf{x},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$

$$=(\mathrm{Id}\_{n}\times D^{-1})\circ(M\times\mathrm{Id}\_{m})(\mathbf{x},\mathbf{x},L(f(\mathbf{x}))$$

$$=(\mathrm{Id}\_{n}\times D^{-1})(\mathbf{0},\mathbf{x},L(f(\mathbf{x}))$$

$$=(\mathrm{Id}\_{n}\times D^{-1})(\mathbf{0},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$

$$=(\mathbf{0},f(\mathbf{x}),\mathbf{0}).$$ Q.E.D.


---

