A quantum algorithm for a FULL adder operation based on registers of the CPU in a quantum-gated computer (Q2239688)

The paper is devoted to the problem of describing operations like AND, OR, XOR in quantum computing by using quantum gates through both the superposition and the phase factor connected by the phase kick-back formation. The main result is exposed in Section 2. Start from the input state \(|\psi_0\rangle=|0\rangle^{\otimes 4}|1\rangle \), and use the componentwise Hadamard transform to arrive at the state \(|\psi_1\rangle= \sum_{x\in\{0,1\}} \frac{|x\rangle}{2^4}\left[ \frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]\). The main idea is next to use the kick-back formation operator \(U_f |x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle\) to obtain the state \(|\psi_2\rangle=\sum_{x\in\{0,1\}} \frac{(-1)^{f(x)}|x\rangle}{2^4}\left[ \frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]\). The last phase is to apply again the componentwise Hadamard transform to arrive at the state \(\psi_3=\pm|f(0,0)f(0,1)f(1,0)f(1,1)\rangle\left[ \frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]\). The authors apply this to the Boolean function \(f_1(x,y) = x \wedge y\) and obtain the recognition of AND on quantum-gated computers. This technique can be applied to other Boolean functions like \(f_6(x,y) = \mathrm{XOR}(x,y)\), \(f_7(x,y) = \mathrm{OR}(x,y)\).