As for gate complexity, we need to decompose the many-qubit control gates \( \sum _{k=0}^{M-1}|k\rangle \langle k|\otimes H_{k}^{g}\)  into basic qubit gates. If we restrict to only one-body and two-body interactions, a \(m\) -qubit controlled Pauli gate \(C^{m}(U)\)  can be decomposed of \(M_{c}=32(m-1)+4\)  basic gates [1]}. For each iteration, the complexity is \( O(\mathcal {N}^{4}\log _{2}\mathcal {N})\) .
By contrast, diagonalizing a \(2^{\mathcal {N}}\) -dimension symmetric matrix on a classic computer using the symmetric Gaussian elimination takes \(O(2^{3\mathcal {N}})\)  steps. Therefore, in the circumstances where iteration steps \(k \in O(\text{poly} N)\) , QCSH achieves expoential speedup compared with classical Shell model.
