# In amplitude amplification, isn't the speedup hindered by the realization of $S_o$?

In brassard et al. Amplitude Amplification work, they define the Q operator as

$$\mathbf{Q} = -AS_{o}A^{-1}S_{\chi}$$

where $$S_{o}$$ is an operator which flips the sign of the $$|0 \rangle$$ state.

Which is basically a diagonal unitary matrix (in the computational basis) with -1 on the first diagonal element.

I was wondering, isn't Quantum amplification's quantum speedup hindered by the realization of $$S_o$$ when the number of qubits in the circuit is too big? Based on Barenco's et al work (Elementary gates for quantum computation), isn´t the number of gates required for a $$n$$-qubit controlled gate exponential in $$n$$?

No, not at all. Barenco et al.'s work is primarily saying that for certain specific gates (the multi-controlled phase gate, as required for $$S_0$$, being one), you can construct them in a time that is polynomial in $$n$$. Yes, the general case might require exponentially many, but not for every case, and it's the small number of non-exponential cases that we do our best to use.