Skip to main content
3 of 7
added 108 characters in body

Does there exist an algorithm that decomposes a matrix into a minimal number of elementary matrices for $F_{2}$?

If $i\neq j$, then let $C_{i,j}:F_{2}^{n}\rightarrow F_{2}^{n}$ be the linear transformation defined by $$C_{i,j}(x_{1},...,x_{n})=(x_{1},...,x_{i},...,x_{i}\oplus x_{j},...,x_{n}).$$ i.e. $C_{i,j}$ is an elementary linear transformation and the operation $C_{i,j}$ applies the CNOT gate $(x,y)\mapsto(x,x\oplus y)$ to the $i$-th and $j$-th bits.

Does there exist an efficient algorithm such that given a non-singular linear transformation $L:F_{2}^{n}\rightarrow F_{2}^{n}$ the algorithm outputs a decomposition $$L=C_{i_{r},j_{r}}\circ\ldots\circ C_{i_{1},j_{1}}$$ such that $r$ is minimized or nearly minimized?

I would like such an algorithm in order to optimize circuits composed almost exclusively of CNOT gates. A more general version of this question has been asked here.