Multiplication mod 2 without extra registers

Question

For an arbitrary bitstring $(x_1, x_2,\ldots, x_n)$ and an $n\times n$ invertible binary matrix $M$ (fixed ahead of time), I would like to construct a circuit $C$ acting on these $n$ bits whose output will be such a bitstring $(y_1, y_2,\ldots, y_n)$ that: $$ \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ \ldots \\ y_n \end{pmatrix} = M \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \ldots \\ x_n \end{pmatrix} \bmod 2 \ , $$ The extra registers are not allowed. The circuit $C$ should only contain $NOT$ and $CNOT$ gates (where $CNOT(x, y) = (x, x+y \bmod 2) $). The matrix $M$ is such that it permits for a reversible calculation.

The lower bound is trivially given by $O(n^2)$ operations. (That's how you would usually multiply matrices, if you had access to the original values of registers all the time. The question, however, is inspired by quantum computation, where one cannot store the initial values, and extra qubits are expensive.)

A known fact from quantum information is that such circuit can be constructed with at most $O(\exp(n))$ gates. The goal is to design it using a sub-exponential number of gates.

Answer 1

Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.