# 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. – Yuval Filmus Apr 8 at 10:24
• Sorry! Used wrong notation. – mavzolej Apr 8 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. – Yuval Filmus Apr 8 at 10:29
• What do you mean by "matrix multiplication is not linear"? – mavzolej Apr 8 at 10:30
• Instead of answering in the comments, please modify your question to include all relevant details that are necessary to answer it. Don't add an "EDIT:" section, simply add the relevant details to the body of the question. – Yuval Filmus Apr 8 at 10:54

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)$ – mavzolej Apr 8 at 19:02