# A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with [PERSON]'s Algorithm
## 3 Proposed Method
### Parallel Quantum Circuit for LSH
```
1:\(T[i]\), \(T[i+8]\), \(SC[i]\), (\(0\leq i\leq 7\))
2:\(T[i+8]\leftarrow\textbf{Parallel\_adder}(T[i],\,T[i+8])\)
3:a_rotation(\(T[i]\))
4:Applying X gate to \(T[i]\) according to \(SC[i]\)
5:\(T[i+8]\leftarrow\textbf{Parallel\_adder}(T[i],\,T[i+8])\)
6:b_rotation(\(T[i+8]\))
7:\(T[i]\leftarrow\textbf{Parallel\_adder}(T[i+8],\,T[i])\)
8:c_rotation(\(T[i+8]\))
```

**Algorithm 2** Quantum circuit of the Mix function. ## 4 Evaluation

The proposed LSH quantum circuit was evaluated using a quantum emulator (i.e., IBM ProjectQ). Among various compilers provided by IBM, the ProjectQ quantum compiler can estimate the resources of implemented quantum circuits. It measures the number of Toffoli gates, CNOT gates, X gates, and qubits used in a quantum circuit. One of the important elements of a quantum circuit is making it work with minimal resources and depth. Currently, the number of qubits available in quantum computer technology is limited, and it is efficient to reduce the quantum resource cost. The depth of a quantum circuit is related to the time complexity required for quantum operations performed on quantum hardware [20; 21; 22; 23; 24; 25]. Therefore, many studies are being conducted to reduce the depth associated with errors on a noisy quantum computer. With this research motivation, we have worked to reduce the number of quantum gates and qubits for the implementation of quantum circuits. Further, we devised a reduction of the depth of the quantum circuit with an efficient trade-off between quantum resources. We designed a parallel LSH structure using an optimal quantum adder for the LSH quantum circuit. As a result, the parallel quantum circuit significantly reduces depth with an efficient trade-off in terms of quantum resources. The adder in the previous work [19] performed addition sequentially to reduce the ancilla qubits used. However, since LSH can be operated in parallel, such sequential operation is inefficient because it greatly increases the depth of the LSH quantum circuit. Table 5 shows the quantum resources of our previous work [19], and Table 6 shows the quantum resources of the parallel LSH proposed in this paper. Compared with the previous work, the proposed circuit uses an additional 15-qubit and uses more CNOT gates and X gates, but uses fewer Toffoli gates. However, the Toffoli gate is a more expensive resource than the X gate and CNOT gate. Due to this trade-off of quantum resources, the circuit depth is greatly reduced. As a result, we argue for an efficient quantum circuit implementation with a slight quantum resource trade-off. The depth of the proposed LSH quantum circuit was reduced by about 96% compared to previous work. Table 7 shows the resources required to perform a Grover attack on LSH using the proposed quantum circuit. To get the correct result for the attack, the [PERSON]'s algorithm \(\lfloor\frac{\pi}{4}\sqrt{2^{n}}\rfloor\) times. LSH-256/512-\(n\) with \(n\)-bit hash length repeats the [PERSON]'s algorithm \(\lfloor\frac{\pi}{4}\sqrt{2^{n}}\rfloor\) times. Therefore, the quantum resource required for [PERSON]'s algorithm attack is calculated as (2 \(\times\) Table 6 \(\times\lfloor\frac{\pi}{4}\sqrt{2^{n}}\rfloor\)). The operation of the current small-scale quantum computer is unclear for the proposed LSH quantum circuit. According to the quantum computer development roadmap announced by IBM, it aims to develop more than 1000 qubits by 2023 and 1K-1M qubits after 2024. We predict that an attack on the LSH hash function will be possible after 2024 when the available resources of a large-scale quantum computer reach the resources required for [PERSON]'s algorithm.