# Improved Low-Depth SHA3 Quantum Circuit for Fault-Tolerant Quantum Computers
## 3 SHA3 Quantum Circuit
### Theta \((\theta)\)  
Theta \((\theta)\) is one of the five phases of the SHA3 (i.e., Keccak-k) hash function. In the \(\theta\) phase, the data are processed in the three-dimensional state array structure shown in Figure 4. The result of \(\Sigma((x-1),z)\oplus\Sigma((x+1),(z-1))\) saves to \((x,y,z)\) bits. The final result value is stored in \((x,y,z)\).  
\[\begin{split}& C[x,z]=A[x,0,z]\oplus A[x,1,z]\oplus A[x,2,z] \oplus A[x,3,z]\oplus A[x,4,z],\ \ \forall x,y\\ & D[x,z]=C[(x-1)\%4,z]\oplus C[(x+1)\%4,(z-1)\%w],\ \forall x\ and\ 0\leq z\leq w\\ & R[x,y,z]=A[x,y,z]\oplus D[x,z]\end{split} \tag{1}\]  
Equation (1) is the theta \((\theta)\) operation in a classic computer. In classic computer operation, temporary registers (hereafter referred to as \(temp\)) of \(C\), \(D\), and \(R\) are allocated to store intermediate calculation values. Therefore, four 1600-bit \(temp\) are used. Quantum circuits reduce the use of 4800 qubits by allocating one 1600-bit \(temp\) of one state size. The proposed quantum circuit avoids an increase in depth by not initializing \(temp\) qubits through reverse operation in each round. This scheme allocates one temp qubit to replace the inverse operation per round.  
Figure 5 shows (a) the exclusion of the inverse operation and (b) the inclusion of the inverse operation in theta (\(\theta\)). \(T\) represents the _temp_ qubit. The scheme excluding the inverse operation includes only one \(\theta\) function in the quantum circuit per round. The scheme including the inverse operation involves the \(\theta\) function and the \(\theta^{\dagger}\) function to return the temporary qubit \(T\) to its original state in the quantum circuit each round. Including the inverse operation can reduce \(T\) qubits but increases the number of quantum gates and the depth. In an attempt to reduce the depth, the scheme excluding inverse operations was selected in this paper. Compared to [8], the operation process proposed in this paper increased the CNOT gate by about 36.36% and reduced the depth by about 71.27% in \(\theta\) (trade-off between quantum gates and depth). In the implementation of [8], \(\theta^{\dagger}\) used the most CNOT gates and increased the depth. Considering this, the proposed quantum circuit replaced \(\theta^{\dagger}\) with the use of \(T\) qubits. As a result, a trade-off occurred between 1,360,000 CNOT gates \(+\) 25 depth and 1600 qubits at \(\theta^{\dagger}\) per round (increase: qubit, decrease: CNOT gate \(+\) depth).  
Algorithm 1 shows the operation of our quantum circuit for theta (\(\theta\)). In the input, \(X\) and \(T\) denote the input qubit and the _temp_ qubit. All operations performed by the CNOT gate updated \(T\), and \(T\) was returned at the end. Compared to previous research results [8], the proposed algorithm increased the CNOT gate but reduced the full depth in theta (\(\theta\)).  
Figure 4: Each part of the three-dimensional bit array matrix state in Keccak-f[1600].  
Figure 5: Quantum circuit for \(\theta\). (\(T\): temporary qubits).  
```
1:for(i = 0 to 5) : for(j = 0 to 5) : for(k = 0 to 64) :
2:for\(s\) = 0 to 5 do
3:\(T[i][j][k]\leftarrow\textbf{CNOT}(X[(i-1)\%5][s][k],T[i][j][k])\)
4:\(T[i][j][k]\leftarrow\textbf{CNOT}(X[(i+1)\%5][s][(k-1)\%64],T[i][j][k])\)
5:\(T[i][j][k]\leftarrow\textbf{CNOT}(X[i][j][k],T[i][j][k])\)
6:endfor Return\(T\)
```  
**Algorithm 1** Quantum algorithm for theta (\(\theta\))