###### tags: `Quantum Calculation`

# Additions in Quantum Fourier Transformations

This page is aimed for operating addtions by quatum fourier transformations (QFT).

## Quantum Fourier Transformations
QFT is [discrete Fourier transform (DFT)](https://hackmd.io/DiOVWD-2RSOzt_-8FoOcAQ?view) done by quantum circuits.
\begin{eqnarray}
QFT \left|x\right> = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{i\frac{2\pi}{N}xk} \left|k\right>
\end{eqnarray}

The inverse QFT corresponds to inverse DFT.

Inplemantion of QFT by Pennylane (using default function):

import sys
from pennylane import numpy as np
import pennylane as qml


nqubit=2
wires=range(nqubit)
dev = qml.device("default.qubit", wires=wires, shots=1)
@qml.qnode(dev)
def circuit(n):
    binlist=bin(n)[2:].zfill(nqubit)
    print(binlist)
    for i in range(len(binlist)):
        if int(binlist[i])==1:
            qml.PauliX(wires=i)
    qml.QFT(wires=wires)
    return qml.state()

Inverse QFT can be done by `qml.QFT(wires=wires).inv()`.

### Examples
#### $N=2$ (nqubit=1).
\begin{eqnarray}
QFT \left|x\right> = \frac{1}{\sqrt{2}}\sum_{k=0}^{1} e^{i\pi xk} \left|k\right>
\end{eqnarray}

If $x=0$
\begin{eqnarray}
\frac{1}{\sqrt{2}}\sum_{k=0}^{1} e^{i\pi xk} \left|k\right> = \frac{1}{\sqrt{2}} (\left|0\right> + \left|1\right>),
\end{eqnarray}
if $x=1$
\begin{eqnarray}
\frac{1}{\sqrt{2}}\sum_{k=0}^{1} e^{i\pi xk} \left|k\right> = \frac{1}{\sqrt{2}} (\left|0\right> - \left|1\right>).
\end{eqnarray}

#### $N=4$ (nqubit=2).
\begin{eqnarray}
QFT \left|x\right> = \frac{1}{2}\sum_{k=0}^{3} e^{i \frac{\pi}{2} xk} \left|k\right>
\end{eqnarray}

If $x=0$
\begin{eqnarray}
\frac{1}{2}\sum_{k=0}^{3} e^{i\pi xk} \left|k\right> = \frac{1}{2} (\left|00\right> + \left|01\right> + \left|10\right> + \left|11\right>),
\end{eqnarray}
if $x=1$
\begin{eqnarray}
\frac{1}{2}\sum_{k=0}^{3} e^{i\pi xk} \left|k\right> = \frac{1}{2} (\left|00\right> + i\left|01\right> - \left|10\right> -i\left|11\right>),
\end{eqnarray}
if $x=2$
\begin{eqnarray}
\frac{1}{2}\sum_{k=0}^{3} e^{i\pi xk} \left|k\right> = \frac{1}{2} (\left|00\right> - \left|01\right> + \left|10\right> -\left|11\right>),
\end{eqnarray}
if $x=3$
\begin{eqnarray}
\frac{1}{2}\sum_{k=0}^{3} e^{i\pi xk} \left|k\right> = \frac{1}{2} (\left|00\right> - i\left|01\right> - \left|10\right> +i\left|11\right>).
\end{eqnarray}

## Additions
The fillwing is the procedure how to calculate $m+n$ by QFT.

1. First calculate QFT of $m$, namley $QFT\left|m\right>$.

2. Second, do some operators to phase of $QFT\left|m\right>$ and get the QFT state of $\left|m+n\right>$, namely $QFT\left|m+n\right>$.
$QFT\left|m+n\right>$ can be calculated by multiplying $e^{i \frac{2\pi}{n}k L}$ to the phase of $\left|k\right>$ in $QFT \left|m\right>$.

\begin{eqnarray}
QFT \left|m\right> = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{i\frac{2\pi}{N}mk} \left|k\right>
\end{eqnarray}

\begin{eqnarray}
QFT \left|m+n\right> = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{i\frac{2\pi}{N}(m+n)k} \left|k\right>
\end{eqnarray}
This can be done by applying phase-shift gate ~~with respect to binary of $n$~~ to all qubits.

Pennylane code:

for i in range(n_qubit)
	qml.PhaseShift(2*np.pi*n/2**i)

3. Finally calculate the inverse QFT of $QFT\left|m+n\right>$ and get $\left|m+n\right>$.