Phase shift and multi-controlled Z-type gates

One of the most famous algorithms in quantum computations is the Grover search algorithm. Under certain assumptions, this algorithm provides quantum speedup for the search problem. We always assume that we can build it efficiently, but assume for a moment that you are limited in the gates you are allowed to use for the implementation of the Grover diffusion operator. For example, if you need to use at most two-channel gates, what would be the complexity of the decomposition circuit for the diffusion operator itself? Here, we show that it is sufficient to use just only the Z-base operators (such \(\root 2^n \of {Z}\) and controlled CZ) and Hadamard operators, but also we show that in this case, the number of used gates can grow exponentially. At least, the number of the multi-controlled Z gates needed to build diffusion operator decomposition circuit only of the following gates: Z, controlled Z, multi-controlled Z gates, or is summed into \(2^n-1\) for the n-dimensional phase shift and cannot be decreased if we will not allow other gates.