How to convert a basic matrix into a quantum circuit?

Question

Classical gates are not invertible, but larger expressions made from those gates can be invertible. One example of an invertible function is the function $f(A,B,C) = X,Y,Z$:

$X = A \ B \ | \ \neg B \ C$

$Y = B \ C \ | \ \neg B \ (A \oplus C)$

$Z = A \ C \ | \ \neg C \ (A \oplus B)$

This results in a basic invertible matrix.

    [ 1 0 0 0 0 0 0 0 ]
    [ 0 0 0 0 0 0 1 0 ]
    [ 0 0 1 0 0 0 0 0 ]
M = [ 0 1 0 0 0 0 0 0 ]
    [ 0 0 0 1 0 0 0 0 ]
    [ 0 0 0 0 1 0 0 0 ]
    [ 0 0 0 0 0 1 0 0 ]
    [ 0 0 0 0 0 0 0 1 ]

Matrices have dimensions 2^n * 2^n, so a circuit representation is desirable.

But I'm not sure this could be converted to a quantum circuit with ease.

The problem with directly converting the classical circuit to a quantum circuit using ancilla qubits is that it doesn't take advantage of the whole circuit's invertibility, so it requires additional qubits and complexity.

Answer 1

I think circuit such as the following will do the job for you (without any attempt at optimization)

How did I come up with this? Basically, I wrote out the target truth table. Then, I started looking at the quoted formulae in the hope it might give me some insight. So, as an intermediate step, I took calculated $A\oplus B$ and $A\oplus C$ on qubits 2 and 3 (the two controlled-nots in steps 2,3). At that point, I just started noticing things and experimenting. I next added the controlled-not between 2 and 3, realising that that could sort out a couple of discrepancies between my current truth table and the target. Then I realised that two of the ones that weren't working were the two that had (original) inputs 110 and 111, and that the output for 110 was what I wanted for 111. So, I added the Toffoli at the beginning to get that one working. At this point, it was only the inputs 011 and 110 that weren't working (which, by this point in the circuit, had been converted to 001 and 100, and I wanted them to output as 100 and 001. In other words, I needed to swap bits 1 and 3 if the second was 0 (there are two other cases where the second bit is 0, but they are unchanged by swap).