Return to Question

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},\dots,x_{i},\dots,x_{j},\dots,x_{n})=(x_{1},\dots,x_{i},\dots,x_{i}\oplus x_{j},\dots,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.

If $i \neq j$, then let $C_{i,j} : F_{2}^{n} \to F_{2}^{n}$ be the elementary linear transformation defined by

$$C_{i,j}(x_{1},\dots,x_{i},\dots,x_{j},\dots,x_{n}) :=(x_{1},\dots,x_{i},\dots,x_{i}\oplus x_{j},\dots,x_{n})$$

which 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 that takes a non-singular linear transformation $L:F_{2}^{n} \to F_{2}^{n}$ and outputs a decomposition

$$L = C_{i_{r},j_{r}} \circ \cdots \circ C_{i_{1},j_{1}}$$

such that $r$ is minimized or nearly minimized?

I would like to find 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.

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.

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},\dots,x_{i},\dots,x_{j},\dots,x_{n})=(x_{1},\dots,x_{i},\dots,x_{i}\oplus x_{j},\dots,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.

If $i\neq j$, then let $C_{i,j}:\Bbb F_{2}^{n}\rightarrow \Bbb 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 (or equivalently an XOR) 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:\Bbb F_{2}^{n}\rightarrow \Bbb 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.

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.