# Multiplication mod 2 without extra registers

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.

• You cannot construct such a circuit at all, since matrix multiplication is not linear. Even when $n = 1$ this is impossible. You cannot express AND using only NOT and XOR. Commented Apr 8, 2020 at 10:24
• Sorry! Used wrong notation. Commented Apr 8, 2020 at 10:26
• Can you possible explain your model in full? Assume I don't know anything about quantum computation. What is the input, what is the desired output, and what operations are allowed? Try to be as verbose as possible. Don't assume anything. Commented Apr 8, 2020 at 10:29
• What do you mean by "matrix multiplication is not linear"? Commented Apr 8, 2020 at 10:30
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$$.
• BTW, it's really amazing how the constraint of matrix reversibility allows one to reduce the number of gates from $O(n^2)$ to $O(n^2/\log n)$ Commented Apr 8, 2020 at 19:02