# A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with [PERSON]'s Algorithm
## 3 Proposed Method  
### LSH Quantum Circuit  
This section describes the parallel quantum circuit for LSH. In this paper, the parallel operation is designed for the independently operable part of the LSH hash function. This is designed to reduce the quantum circuit depth of LSH through an efficient quantum resource trade-off. We implemented the message expansion(MsgExp) function and the message mix(Mix) function in parallel. As a result, the parallel quantum circuit shows about a 96% reduction in the depth of the quantum circuit compared to the previous work [19]. In message expansion(MsgExp) and message mix(Mix), which are internal functions of the LSH hash function, each message is independently calculated in units of words. Therefore, since they do not affect each other's results, it shows that the depth of the circuit can be greatly reduced by processing the operation of each message word in parallel. That is, both functions can significantly reduce the depth of the quantum circuit by processing the operation of each message word in parallel. We design the parallel operation in the LSH using the parallel adder proposed by [27]. In a previous work, [PERSON] et al. [19] used a sequential adder [27] in the LSH quantum circuit. The quantum adder is performed by reusing 1-ancilla qubits. However, since the ancilla qubits used in the quantum adder are reused, sequential operations must be performed even if parallel operations are possible. The sequential adder uses \((2n-2)\) Toffoli gates, \(4n\) CNOT gates, and \((6n-2)\) depth; (\(n\): bit length). Figure 5 shows the sequential addition operation in MsgExp. In this adder, the message block pairs \(M_{j}\), \(M_{j-1}\) are calculated sequentially. Since 16 additions are performed one by one, the quantum circuit has a depth of \(16\times(6n-2)\). The sequential adder of the LSH quantum circuit is inefficient in terms of quantum circuit depth because it greatly increases the depth. As a result, the sequential quantum circuit of the previous work was implemented at a depth of hundreds of thousands (#LSH-256-\(n\) : about 210,050; #LSH-512-\(m\) : about 421,850).  
We propose a method to utilize the adder in [27] as an efficient parallel quantum adder in LSH. We design a parallel addition structure that uses an optimal quantum adder for the LSH quantum circuit and has an efficient trade-off between quantum resources. The parallel quantum adder uses \((2n-3)\) Toffoli gates, \((5n-7)\) CNOT gates, and \((2n-6)\) X gates, and has a depth of \((2n+3)\). Figure 6 shows the parallel addition operation in MsgExp. In this adder, the message block pairs \(M_{j}\), \(M_{j-1}\) are calculated in parallel. Since 16 additions are performed at once, the depth of the quantum circuit is only (\(2n+3\)). The parallel adder increases the number of CNOT and X gates. However, it reduces the number of Toffoli gates, which is a more expensive resource than CNOT, X gates, and significantly reduces the depth of the quantum circuit. Consequently, we saw this as a very efficient trade-off. We describe quantum circuits based on LSH-256-\(n\). In fact, we show the result of reducing the total depth by about 96% compared to the previous work by implementing the parallel structure. The trade-off results for quantum resources are described in detail in Section 4.  
Figure 5: Sequential addition in MsgExp function. (Depth: \(16\times(6n-2)\)).  
Figure 6: Parallel addition in MsgExp function. (Depth: only \(2n+3\)).