2
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$ Commented Apr 8, 2020 at 10:24
  • $\begingroup$ Sorry! Used wrong notation. $\endgroup$
    – mavzolej
    Commented Apr 8, 2020 at 10:26
  • $\begingroup$ 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. $\endgroup$ Commented Apr 8, 2020 at 10:29
  • $\begingroup$ What do you mean by "matrix multiplication is not linear"? $\endgroup$
    – mavzolej
    Commented Apr 8, 2020 at 10:30
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 8, 2020 at 10:54

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you so much!! $\endgroup$
    – mavzolej
    Commented Apr 8, 2020 at 11:05
  • $\begingroup$ 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)$ $\endgroup$
    – mavzolej
    Commented Apr 8, 2020 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.