# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 2 Background  
### Quantum Computing  
Quantum computers leverage two fundamental quantum mechanical properties: superposition and entanglement. Superposition allows a qubit to exist simultaneously in multiple states, rather than being confined to a binary state as with classical bits. Entanglement, a uniquely quantum phenomenon, links qubits in such a manner that the state of one instantly influences the state of another, irrespective of distance. When \(n\) qubits are in a superposition state, these can represent \(2^{n}\) values. Operations in all states can be performed at once. A qubit in a quantum superposition can be represented as follows:  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Symbols** & **Meaning** \\ \hline \(FFM\) & This means multiplication in a finite field. \\ \hline \(Inv\)\(FFM\) & This represents the inverse operation for FFM. \\ \hline \(Mont\) & This refers to the Montgomery reduction function. It is used in NTT and InvNTT. \\ \hline \(NTT_{sub1,sub2}\) & These are sub-functions used in NTT. These perform addition or subtraction on two qubits. \\ \hline \(Barret\) & This refers to the Barrett reduction function. It is used in InvNTT. \\ \hline \(\oplus\) & Perform XOR operation. \\ \hline \(\circ\) & Connect the algorithms from left to right. \\ \hline \hline \end{tabular}
\end{table}
Table 1: Meanings for symbols used in this paper.  
\[|\psi\rangle=\alpha|1\rangle+\beta|0\rangle\]  
Any measurement on these qubits will always yield one of two eigenvalues, although we cannot predict which one will be observed [26]. \(\alpha\) and \(\beta\) are the probability amplitudes, where the probability of a result \(|1\rangle\) with a value 1 is \(|\alpha|^{2}\) and the probability of a result \(|0\rangle\) with a value 0 is \(|\beta|^{2}\). Normalizing that state guarantees this equation:  
\[|\alpha|^{2}+|\beta|^{2}=1\]  
In quantum computing, all operations are reversible, barring measurements. This reversibility means that one can recover the original state from the resultant state without extra information, requiring the quantum gates to possess equal numbers of input and output bits. Below are the X, CNOT, Toffoli, and SWAP matrices, which are representative quantum gates utilized for the manipulation of qubits within quantum computing:  
\[X=\frac{1}{\sqrt{2}}\bigg{[}\begin{array}{cc}0&1\\ 1&0\end{array}\bigg{]}\hskip 56.905512 ptCNOT=\left[\begin{array}{ccccc}1&0&0&0 \\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\end{array}\right]\]  
\[Toffoli=\left[\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0\\ 0&0&1&0&0&0&0\\ 0&0&0&1&0&0&0\\ 0&0&0&0&1&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1\\ 0&0&0&0&0&1&0\end{array}\right]\hskip 56.905512 ptSWAP=\left[\begin{array}{cccccccc}1&0&0&0 \\ 0&0&1&0\\ 0&1&0&0\\ 0&0&0&1\end{array}\right]\]  
Figure 1 visually presents the quantum gate operations corresponding to each aforementioned gate. The (a) X(NOT) gate works on a single qubit, flipping its state. The (b) CNOT gate uses two qubits: a control and a target qubit. The target's state is inverted only if the control is set to one. The (c) Toffoli gate employs three qubits: two as controls and one as a target. Only when both control qubits are set to one does the target's state reverse. The (d) SWAP gate interchanges the physical positions of two qubits.  
Figure 1: Quantum logic gates ([[https://en.wikipedia.org/wiki/Quantum_logic_gate](https://en.wikipedia.org/wiki/Quantum_logic_gate)]([https://en.wikipedia.org/wiki/Quantum_logic_gate](https://en.wikipedia.org/wiki/Quantum_logic_gate)), accessed on 30 August 2023).