Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage bits consisting solely of CNOT gates $(x,y)\mapsto(x,x\oplus y)$ and SWAP gates $(x,y)\mapsto(y,x)$ and that computes the linear transformation $L$. Said differently, let $w(L)$ be the least number of elementary row operations on $F_{2}^{n}$ needed to produce the linear transformation $L$.

Let $w^{\sharp}(L)$ be the gate count of the smallest reversible circuit with an arbitrary amount of ancilla/garbage bits that computes the linear transformation $L$. Let $\iota_{+m}:F_{2}^{n}\rightarrow F_{2}^{n}\oplus F_{2}^{m}$ be the function where $\iota_{+m}(x)=(x,0)$ and let $\pi_{-m}:F_{2}^{n}\oplus F_{2}^{m}\rightarrow F_{2}^{n}$ be the projection mapping where $\pi_{-m}(x,y)=x$ whenever $x\in F_{2}^{n},y\in F_{2}^{m}$. Define $w^{\sharp}(L)=\min\{w(M)\mid M:F_{2}^{n}\oplus F_{2}^{m}\rightarrow F_{2}^{n}\oplus F_{2}^{m},L=\pi_{-m}M\iota_{+m}\}.$ We say that $L$ is strongly reversible if $w(L)=w^{\sharp}(L)$.

For each $n$, let $t_{n}$ be $\max(w(L):L:F_{2}^{n}\rightarrow F_{2}^{n},w(L)=w^{\sharp}(L)\}$.

  1. What are some lower and upper bounds on the constants $t_{n}$?

  2. Does there exist an efficient (probabilistic) algorithm such that on an input $n$ the algorithm returns a linear transformation $L:F_{2}^{n}\rightarrow F_{2}^{n}$ such that either

a. $L$ is strongly reversible and $w(L)=t_{n}$,

b. $L$ is strongly reversible and $W(L)$ is near $t_{n}$, or

c. (with probability at least $1-o(2^{-n})$) $w^{\sharp}(L)$ is near $w(L)$ (by near, I will accept $w(L)-w^{\sharp}(L)\leq n$) and $w(L)$ is large (here we shall informally call $L$, nearly reversible).

  1. Can a linear transformation obtained by iterating a linear cellular automata over $F_{2}$ of dimension $1$ or $2$ be reversible or nearly reversible (I do not care if you have special boundary conditions or if the cellular automata is on a torus)?

The motivation for this question is that I want to know if and when reversible computation produces a significant computational overhead when computing invertible linear transformations over a vector space over $F_{2}$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.