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$?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.