If quantum gates are reversible how can they possibly perform irreversible classical AND and OR operations?

Question

Quantum gates are said to be unitary and reversible. However, classical gates can be irreversible, like the logical AND and logical OR gates. Then, how is it possible to model irreversible classical AND and OR gates using quantum gates?

Answer 1

Let's say we have a function $f$ which maps $n$ bits to $m$ bits (where $m<n$).

$$f: \{0,1\}^{n} \to \{0,1\}^{m}$$

We could of course design a classical circuit to perform this operation. Let's call it $C_f$. It takes in as input $n$-bits. Let's say it takes as input $X$ and it outputs $f(X)$.

Now, we would like to do the same thing using a quantum circuit. Let's call it $U_f$, which takes as input $|X\rangle$ and outputs $|f(X)\rangle$. Now remember that since quantum mechanics is linear the input qubits could of course be in a superposition of all the $n$-bit strings. So the input could be in some state $\sum_{X\in\{0,1\}^{n}}\alpha_X|X\rangle$. By linearity the output is going to be $\sum_{X\in\{0,1\}^{n}}\alpha_X|f(X)\rangle$.

Evolution in quantum mechanics is unitary. And because it is unitary, it is reversible. This essentially means that if you apply a quantum gate $U$ on an input state $|x\rangle$ and get an ouput state $U|x\rangle$, you can always apply an inverse gate $U^{\dagger}$ to get back to the state $|x\rangle$.

Notice, carefully in the above picture that the number of input lines (i.e. six) is exactly same as the number of output lines at each step. This is because of the unitarity of the operations. Compare this to classical operations like the logical AND where $0\wedge1$ gives a single bit output $0$. You can't reconstruct the initial bits $0$ and $1$ from the output, since even $0\wedge 0$ and $1\wedge0$ would have mapped to the same output $0$. But, consider the classical NOT gate. If the input is $0$ it ouputs $1$, while if the input is $1$ it outputs $0$. Since this mapping is one-one, it can be easily implemented as a reversible unitary gate, namely, the Pauli-X gate. However, for implementing a classical AND or a classical OR gate we need to think a bit more.

Consider the CSWAP gate. Here's a rough diagram showing the scheme:

In the SWAP gate depending on the control bit, we the other two may or may not get swapped. Notice that there are three input lines and three output lines. So, it can be modeled as a unitary quantum gate. Now, if $z=0$: If $x=0$, output is $0$, while if $x=1$, output is $y$.

If you notice, if $x=0$, we are outputting $\bar{x}\wedge y$ while if $x=1$ we are outputting $x\wedge y$. So we could successfully generate the output $x\wedge y$ which we wanted although we ended up with some "junk" outputs $\bar{x}\wedge y$ and $x$. An interesting fact is that the inverse of the CSWAP gate is the CSWAP gate itself (check!).

That's all! Remember that all classical gates can be constructed with the NAND gate, which can of course be constructed an AND and a NOT gate. We effectively modelled the classical NOT and the classical AND gate using reversible quantum gates. Just to be on the safe side we can also add the qauntum CNOT gate to our list, because using CNOT we can copy bits.

Hence, the basic message is that using the quantum CSWAP, CNOT and the NOT gates we can replicate any classical gate. BTW, there's a clever trick to get rid of the "junk" bits which are produced when quantum gates are used, but that's another story.

P.S: It's very important to get rid of the "junk" bits or else they can cause computational errors!

Reference & Image Credits: Quantum Mechanics and Quantum Computation MOOC offered by UC Berkeley on edX.