The purpose of this post is to discuss historically one of the first decision problems for which quantum computing was shown to provide an exponential advantage over classical computing. One of the initially striking discrepancies between classical logic gates such as \(\text{AND}\) and quantum logic gates \(\Gamma\in U\left(\textbf C^{2^N}\right)\) is that the former need not be invertible or reversible (though they can be like the \(\text{NOT}\) gate) whereas the latter are always invertible being unitary \(\Gamma^{-1}=\Gamma^{\dagger}\). However, this is a bit of an illusion. Actually, given any classical logic gate \(\Gamma:\{0,1\}^n\to\{0,1\}^m\) mapping input \(n\)-bit strings to output \(m\)-bit strings (also called Boolean vector-valued functions), it is possible to construct a reversible classical logic gate \(\tilde{\Gamma}:\{0,1\}^{n+m}\to\{0,1\}^{n+m}\) defined as follows:
\[\tilde{\Gamma}(\xi_1+\xi_2):=\xi_1+\left(\xi_2\oplus\Gamma(\xi_1)\right)\]
for all input bit strings \(\xi_1\in\{0,1\}^n,\xi_2\in\{0,1\}^m\).
👍👍👍