Quantum Algorithm
Reversible computation
A set of (classical) gates is said to be functionally complete (or “universal”)if every possible truth table (ie. Boolean function) can be expressed using members of the set. e.g. {AND, OR, NOT} is functionally complete. (NAND gate is sufficient actually) But, AND, OR gates are not reversible -> not unitary, hence we cannot implement them in a quantum computer.
To be reversible, we can determine the inputs from the outputs.
Reversible Logics in the Quantum context:
One Qubit Adder
A one bit adder using only reversible gates:
How to implement a irreversible function: simply propagate the inputs.
Deutsch-Josza Algorithm
Given a boolean function, $f$, determine if: $f$ is constant (always gives the same result), or $f$ is balanced (gives equal numbers of 0s and 1s)
implementation of a constant function:
On the first line, which is the input register, it is kept to make this function a reversible function. On the second line, which is the output register, the evaluated result is always flipped. that is to say, if we define a constant function that always output 1, then our second line input should be \(\vert 0\rangle\); On the other hand, if we require a constant function that always output 0, then our second line register should be \(\vert 1\rangle\).
This function gate has a flip design. i.e. the function will have some constant output register, say $\vert 1\rangle$ here, if the input register is \(\vert 0\rangle\). But if the input register is $\vert 1\rangle$, the output register will get flipped. This is a balanced function, in other words, the output register can flip, and it depends on the input register.
The measure result will always return a 0, here the measurement result is 0 with 100% probability and that shows the function is constant.
\[\vert\psi_1\rangle = H\vert 0\rangle\otimes H\vert 1\rangle = \frac{\vert 0\rangle+\vert 1\rangle}{\sqrt 2}\otimes\frac{\vert 0 \rangle-\vert 1\rangle}{\sqrt 2} = \vert+\rangle \otimes\vert-\rangle\]
\[\vert\psi_2\rangle = \text{CNOT}\vert+\rangle \otimes\vert-\rangle\] \[\vert\psi_2\rangle = \text{CNOT}\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt 2}\otimes\frac{\vert 0 \rangle-\vert 1\rangle}{\sqrt 2} =\text{CNOT} \frac{\vert 0\rangle}{\sqrt 2}\frac{\vert 0 \rangle-\vert 1\rangle}{\sqrt 2} + \frac{\vert 1\rangle}{\sqrt 2}\frac{\vert 0 \rangle-\vert 1\rangle}{\sqrt 2}\] \[\vert\psi_2\rangle = \frac{\vert 0\rangle}{\sqrt 2}\frac{\vert 0 \rangle-\vert 1\rangle}{\sqrt 2} + \frac{\vert 1\rangle}{\sqrt 2}\frac{\vert 1 \rangle-\vert 0\rangle}{\sqrt 2} = \frac{\vert 0\rangle - \vert 1\rangle}{\sqrt 2}\frac{\vert 0\rangle - \vert 1\rangle}{\sqrt 2} = \vert -\rangle\vert -\rangle\]
Notice there is a Control-X gate Phase kickback during the last steps.
\[\vert\psi_3\rangle = H \vert -\rangle\otimes\vert -\rangle = \vert 1\rangle\otimes\vert-\rangle\]
This shows us that the measurement result will always be 1, which tells us that the function sits in the middle is a balanced function. In contrary, recall that the constant function will give us a result of 0.
During this process, we’ve seen the phase kickback on a Control-X gate. For example on a X gate applied to the output register, we can have the following gates:
Phase kickback on a control-X gate:
We have demonstrated that:
\[\text{CNOT}\vert+\rangle\vert-\rangle=\vert-\rangle\vert-\rangle\]If there are multiple Qubit inputs, then the constant function and the balanced function will look like the following:
Multi-qubit representations:
Hence after the first H gates, the system state will become:
\[\vert\psi\rangle=\frac{1}{\sqrt N}\sum_x\vert x\rangle\otimes\frac{\vert0\rangle-\vert1\rangle}{\sqrt2}\]Using the phase kickback property, after the function is applied, we have:
\[\vert\psi\rangle=\frac{1}{\sqrt N}\sum_x(-1)^{f(x)}\vert x\rangle\otimes\frac{\vert0\rangle-\vert1\rangle}{\sqrt2}\]If the function evaluates to “1” then the target qubit flipped, and we pick up a phase. Otherwise, there is no phase applied. This is a simple way to write that.