9
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Yes. $\oplus$ is the standard notation for XOR which is addition modulo 2. $\endgroup$
    – Joseph Van Name
    Commented Nov 26, 2017 at 13:15
  • $\begingroup$ please define $CNOT$ gate. $\endgroup$
    – Turbo
    Commented Nov 26, 2017 at 14:07
  • 2
    $\begingroup$ I did define CNOT gate $(x,y)\mapsto(x,x\oplus y)$ in the question. en.wikipedia.org/wiki/Controlled_NOT_gate . $\endgroup$
    – Joseph Van Name
    Commented Nov 26, 2017 at 14:18
  • $\begingroup$ Does Gaussian elimination produce too large an $r$? $\endgroup$
    – Rodrigo de Azevedo
    Commented Nov 26, 2017 at 18:31
  • $\begingroup$ Rodrigo de Azevedo. I am to a large extent interested in the linear transformations where it is known that $r\ll n^{2}$ but where Gaussian elimination will take about $n^{2}$ steps. My uneducated guess is that the $r$ produced Gaussian elimination could be improved a little bit for random matrices though. $\endgroup$
    – Joseph Van Name
    Commented Nov 27, 2017 at 7:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .