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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.