# Optimized Implementation and Analysis of CHAM in Quantum Computing
## 2 Background
### Quantum Gates  
This section briefly mentions what is related to quantum computing and explains the quantum gates required to implement the cryptographic operation of ciphers. In a quantum computer environment, a quantum bit (qubit) is the unit of quantum information, and has the property of being able to have both \(0\) and \(1\) at the same time. This property is called quantum superposition, and it exponentially increases the computational space of quantum computers. Gates must be used for computation, but in a quantum computer environment, logic gates such as AND, OR, and XOR used in classical computers cannot be used, so quantum gates are used as a means to replace logic gates.  
There are many quantum gates, but a single-qubit gate and controlled gate are generally considered basic. Single-qubit gates that cause the spin to revolve around some axis [29] include X (NOT), H, S gates, etc. Controlled gates including CNOT, Toffoli gate, etc., affect a target qubit through one or more control qubits. Among the quantum gates, the following four quantum gates are often used to implement quantum circuits in cryptography. The four quantum gates are shown in Figure 1.  
The X gate shown in Figure 1a is the simplest reversible flip gate among the basic gates. The X gate performs an operation that inverts a single qubit that comes as an input. It has the same operation as a classical bit flip and can be matched with a NOT gate among logic gates.  
The CNOT gate shown in Figure 1b stands for a Controlled-NOT gate. It inverts the target qubit only when the state of the control qubit is \(|1\rangle\). CNOT gates are often used when performing an in-place XOR operation between two inputs.  
The Toffoli gate shown in Figure 1c stands for a Controlled-Controlled-NOT gate and is also called CNOT. It can be seen as a CNOT gate with two control qubits, and the target qubit can be inverted only when both control qubits are \(|1\rangle\). The Toffoli gate is not a universal quantum gate, and it can be implemented by a combination of Clifford +\(T\) gates. Here, Clifford +\(T\) gates are a set of universal quantum gates consisting of Clifford, which includes H gate, S gate, and CNOT gate, and a single T gate, which is non-Clifford. By fixing this set of gates, we can estimate the number of quantum gates, circuit depth, cost, etc. We adopt the method of decomposing Toffoli gates into \(8\) Clifford + \(7T\) gates from [30]. In this case, the full depth is \(8\) and theT-depth is \(4\). The Toffoli gate has the highest quantum cost among the four basic quantum gates of Figure 1.  
The Swap Gate shown in Figure 1d exchanges the states of two qubits that come in as inputs. Unlike the previous gates, the SWAP gate does not use quantum resources. Except for the SWAP gate, the quantum resource cost of other gates increases in the mentioned order.  
While NAND or NOR gates are universal gates in classical computing, universal quantum gate sets include Clifford gates (X, CNOT, H, S) +\(T\) gate, rotation gates, and others. By using these universal quantum gate sets, it is possible to perform any quantum operation. In this paper, we estimate the complexity of total quantum gates at the Clifford + \(T\) level.