# A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with [PERSON]'s Algorithm
## 3 Proposed Method
### Parallel Quantum Circuit for LSH
This adder uses 16 ancilla qubits \(c\) to store carry values per message pair. Since the adder uses ancilla qubits \(c_{j}\) individually, it can perform parallel additions on pairs of input messages. As a result, the Algorithm 1 is run concurrently for the number of message pairs. ```
0:\(M_{k}\) and \(M_{k-1}\) pair, ancilla \(c_{k}\) (\(1\leq k\leq 16\))
1:for\(i=0\) to \(29\)do
2:\(M_{k-1}[i+1]\leftarrow\text{CNOT}(M_{k}[i+1],\,M_{k-1}[i+1])\)
3:endfor
4:\(c_{k}\leftarrow\text{CNOT}(M_{k}[1],\,c_{k})\)
5:\(c_{k}\leftarrow\text{Toffoli}(M_{k}[0],\,M_{k-1}[0],\,c_{k})\)
6:\(M_{k}[1]\leftarrow\text{CNOT}(M_{k}[2],\,M_{k}[1])\)
7:\(M_{k}[1]\leftarrow\text{[PERSON]}(c_{k},\,M_{k-1}[1],\,M_{k}[1])\)
8:\(M_{k}[2]\leftarrow\text{CNOT}(M_{k}[3],\,M_{k}[2])\)
9:for\(i=0\) to \(26\)do
10:\(M_{k}[i+2]\leftarrow\text{[PERSON]}(M_{k}[i+1],\,M_{k-1}[i+2],\,M_{k}[i+2])\)
11:\(M_{k}[i+3]\leftarrow\text{CNOT}(M_{k}[i+4],\,M_{k}[i+3])\)
12:endfor
13:\(M_{k}[29]\leftarrow\text{Toffoli}(M_{k}[28],\,M_{k-1}[29],\,M_{k}[29])\)
14:\(M_{k-1}[31]\leftarrow\text{CNOT}(M_{k}[30],\,M_{k-1}[31])\)
15:\(M_{k-1}[31]\leftarrow\text{CNOT}(M_{k}[31],\,M_{k-1}[31])\)
16:\(M_{k-1}[31]\leftarrow\text{Toffoli}(M_{k}[29],\,M_{k-1}[30],\,M_{k-1}[31])\)
17:for\(i=0\) to \(28\)do
18:\(\text{X}(M_{k-1}[i+1])\)
19:endfor
20:\(M_{k-1}[1]\leftarrow\text{CNOT}(c_{k},\,M_{k-1}[1])\)
21:for\(i=0\) to \(28\)do
22:\(M_{k-1}[i+2]\leftarrow\text{CNOT}(M_{k}[i+1],\,M_{k-1}[i+2])\)
23:endfor
24:\(M_{k}[29]\leftarrow\text{Toffoli}(M_{k}[28],\,M_{k-1}[29],\,M_{k}[29])\) \begin{table}
\begin{tabular}{c c c c c c c c} \hline \(l\) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \(\tau(l)\) & 3 & 2 & 0 & 1 & 7 & 4 & 5 & 6 \\ \hline \(l\) & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline \(\tau(l)\) & 11 & 10 & 8 & 9 & 15 & 12 & 13 & 14 \\ \hline \end{tabular}
\end{table} 
Table 4: Permutation table for the LSH expansion function. ```
1:for\(i\)=0 to 26 do
2:\(M_{k}[28\text{-}i]\leftarrow\text{Toffoli}(M_{k}[27\text{-}i],\,M_{k-1}[28\text{-}i],\,M_{k}[28 \text{-}i])\)
3:\(M_{k}[29\text{-}i]\leftarrow\text{CNOT}(M_{k}[30\text{-}i],\,M_{k}[29\text{-}i])\)
4:\(X(M_{k-1}[29\text{-}i])\)
5:endfor
6:\(M_{k}[1]\leftarrow\text{[PERSON]}(c_{k},\,M_{k-1}[1],\,M_{k}[1])\)
7:\(M_{k}[2]\leftarrow\text{CNOT}(M_{k}[3],\,M_{k}[2])\)
8:X(\(M_{k-1}[2]\))
9:\(c_{k}\leftarrow\text{Toffoli}(M_{k}[0],\,M_{k-1}[0],\,c_{k})\)
10:\(M_{k}[1]\leftarrow\text{CNOT}(M_{k}[2],\,M_{k}[1])\)
11:X(\(M_{k-1}[1]\))
12:\(c_{k}\leftarrow\text{CNOT}(M_{k}[1],\,c_{k})\)
13:for\(i\)=0 to 30 do
14:\(M_{k-1}[i]\leftarrow\text{CNOT}(M_{k}[i],\,M_{k-1}[i])\)
15:endfor
```
**Algorithm 1**_Cont._

In Mix, adders operate in parallel for \(T[i]\) and \(T[i+8]\)\((0\leq i\leq 7)\) pairs, respectively. The result of the addition operation is stored in \(T[i]\). Since addition operations of \(T[i]\) and \(T[i+8]\) do not affect each other, the parallel operation is possible. The adder used in Mix is the same as Algorithm 1, and message block pairs (i.e., \(M_{j-1},\,M_{j-2},\,\,2\leq j\leq N_{s}\)) are changed to \(T[i]\), \(T[i+8]\)\((0\leq i\leq 7)\) pairs at the input. Algorithm 2 shows the quantum circuit implementation of the Mix function. One Mix function is performed with two word pairs \(T[i]\), \(T[i+8]\), \((0\leq i\leq 7)\) and a total of eight Mix functions are operated per round. In the Mix function quantum circuit, the a_rotation, b_rotation, and c_rotation functions of lines 2, line 5, and line 7 perform index rotation. The rotation value is determined according to the number of words (32-bit or 64-bit) and the \(j\) value of the step function \(Step_{j}\). Since only the swap gate is used in the rotation operation, additional quantum resources are not used.