1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Does this answer your question? How to convert a simple matrix into circuit? $\endgroup$ May 26, 2023 at 6:13
  • $\begingroup$ Hi @MarkSpinelli! I did ask the other question yesterday. Unfortunately, I did it from an unregistered account, and I lost access to it when StackExchange tried to merge it with my this account. This is a new account, so I can't message anyone or comment anywhere apart from my own questions. So I had to make a new post to be able to add details and respond to answers. Thank you for your input yesterday, it helped me explore some options and clarify the question. $\endgroup$
    – G S
    May 26, 2023 at 8:47
  • $\begingroup$ Thank you @MartinVesely for bringing attention to it. If you read the comment above, you'll see that that post is an unfortunate duplicate. I saw that you edited the two questions, so thank you for that. I can't delete the other post or flag it in any way, or else I'd do that. $\endgroup$
    – G S
    May 26, 2023 at 8:49
  • $\begingroup$ @GS based on your comments I closed the other post as duplicate of this one $\endgroup$
    – glS
    May 26, 2023 at 11:36
  • $\begingroup$ Thank you @glS! $\endgroup$
    – G S
    May 26, 2023 at 14:44

1 Answer 1

1
$\begingroup$

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

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

$\endgroup$
2
  • 1
    $\begingroup$ Wow, just wow! I was so close to giving up. This is exactly what I was looking for. It's hard to understand, but I'm sure there's some simplicity here that makes these reversible gates so powerful. I'll definitely look into it. $\endgroup$
    – G S
    May 26, 2023 at 9:16
  • $\begingroup$ I would have never gotten there from symbolic manipulation. I translated your circuit into Boolean algebra and I got this: CCNOT: C → (A & B)^C; 1st CNOT: B → A^B; 2nd CNOT: (A & B)^C → (A & B)^C^A = (A & ~B)^C; 3rd CNOT: A^B → A^B^(A & ~B)^C = BC | (~B & (A^C)); CSWAP: generates the two missing terms, AB | ~BC at the top and AC | (~C & (A^B)) at the bottom. By here the algebra is just too complex. $\endgroup$
    – G S
    May 26, 2023 at 9:18

Your Answer

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