# Quantum 3D FFT in Tomography
## 2 Quantum Computational Units
### Circuitry for Implementing QFT  
The circuit implementation of QFT makes use of two gates. The one of them is the single-qubit Hadamard gate \(H=\tfrac{1}{\sqrt{2}}\begin{pmatrix}1&1\\ 1&-1\end{pmatrix}\), and the other one is the phase gate \(R_{m}=\begin{pmatrix}1&0\\ 0&e^{2\pi i/2^{m}}\end{pmatrix}\).  
Consider how the QFT operates on a single-qubit state (1-qubit QFT) \(|\psi\rangle=a|0\rangle+b|1\rangle\). Where \(x_{0}=a\), \(x_{1}=b\), and \(N=2\).  
\[y_{0}=\tfrac{1}{\sqrt{2}}\quad\left(a\cdot e^{\tfrac{2\pi i}{2}0\times 0}+b\cdot e ^{\tfrac{2\pi i}{2}1\times 0}\right)=\frac{1}{\sqrt{2}}\;(a+b) \tag{6}\]  
And  
\[y_{1}=\tfrac{1}{\sqrt{2}}\quad\left(a\cdot e^{\tfrac{2\pi i}{2}0\times 1}+b\cdot e ^{\tfrac{2\pi i}{2}1\times 1}\right)=\frac{1}{\sqrt{2}}\;(a-b) \tag{7}\]  
Thus, the final result is the state  
\[U_{QFT}|\psi\rangle=\frac{1}{\sqrt{2}}(a+b)|0\rangle+\frac{1}{\sqrt{2}}(a-b)|1\rangle \tag{8}\]  
This operation is exactly the result of applying the Hadamard gate on the qubit. If we apply the Hadamard gate to the state \(|\psi\rangle=a|0\rangle+b|1\rangle\), we obtain a new state:  
\[\frac{1}{\sqrt{2}}(a+b)|0\rangle+\frac{1}{\sqrt{2}}(a-b)|1\rangle\equiv\overline {a}|0+\overline{b}|1\rangle \tag{9}\]  
The Hadamard gate H for \(n\)-qubit is given  
\[H_{2^{n}}=H_{2}\otimes H_{2^{n-1}},\;\;\;2\leq n\in N \tag{10}\]  
where \(\otimes\) is the Kronecker product, i.e., for \(n=2\), we have the Hadamard gate  
\[H_{2^{2}}=H_{4}=H_{2}\otimes H_{2^{2-1}}=H_{2}\otimes H_{2}=\frac{1}{\sqrt{2} }\begin{pmatrix}1&1\\ 1&-1\end{pmatrix}\otimes\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\ 1&-1\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1&+1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1\end{pmatrix} \tag{11}\]  
Given these two gates, a circuit implementation of \(n\)-qubit QFT is shown in Figure 1[35; 36; 37].  
The basis states that enumerate all the possible states of the \(n\)-qubits is  
\[|x\rangle= |x_{1}\rangle\otimes|x_{2}\rangle\otimes|x_{3}\rangle\otimes\cdots \otimes|x_{n-1}\rangle\otimes|x_{n}\rangle \tag{12}\]  
where \(|x_{k}\rangle\) indicates that qubit \(k\) is the state \(x_{k}\), with \(x_{k}\) being either 1 or 0. The basis state index \(x\) is the binary number encoded by \(x_{k}\) with \(x_{1}\) being the most significant bit. Thus, we can write the QFT as  
\[QFT(|x\rangle)=\frac{1}{\sqrt{N}}\otimes_{k=1}^{n}\left(|0\rangle+e^{\tfrac{2 \pi i}{2}}|1\rangle\right) \tag{13}\]  
Figure 1: The circuit implementation of \(n\)-qubit QFT using the Hadamard gate \(H\) and the phase gate \(R_{n}\).  
After rearranging the sum and the products and expanding \(\sum_{y=0}^{N-1}=\sum_{y_{1}=0}^{1}\sum_{y_{2}=0}^{1}\cdots\)\(\sum_{y_{n}=0}^{1}\), the action of the QFT can be expressed by:  
\[QFT\;(|x_{1}x_{2}x_{3}\cdots x_{n-1}x_{n}))\] \[\qquad\qquad\qquad=\frac{2\pi i\
u_{1}}{2}\left(|0\rangle+e^{\frac {2\pi i\
u_{1}}{2}}|1\rangle\right)\otimes\left(|0\rangle+e^{\frac{2\pi i\
u_{ n-1}}{2}+\frac{2\pi i\
u_{2}}{2}}|1\rangle\right)\otimes\cdots\otimes\qquad(|0\rangle \tag{14}\] \[\qquad\qquad\qquad+e^{\frac{2\pi i\
u_{1}}{2}+\frac{2\pi i\
u_{2}} {2}+\frac{2\pi i\
u_{3}}{2}+\cdots+\frac{2\pi i\
u_{n-1}}{2-1}+\frac{2\pi i\
u _{1}}{2}}|1\rangle)\]  
i.e., for 3-qubit QFT  
\[|y\rangle=\frac{1}{\sqrt{2^{3}}}[(|0\rangle+e^{\frac{2\pi i\
u_{2}}{2}}|1 \rangle)\otimes(|0\rangle+e^{\frac{2\pi i\
u_{2}}{2}+\frac{2\pi i\
u_{3}}{2}}| 1\rangle)\otimes(|0\rangle+e^{\frac{2\pi i\
u_{1}}{2}+\frac{2\pi i\
u_{2}}{2}+ \frac{2\pi i\
u_{3}}{2}}|1\rangle)] \tag{15}\]  
In a similar way, one can extend to \(n\)-qubit QFT.