According to this source, Grover's algorithm works as follows:
- Begin with uniform superposed state (i.e. Hadamard gate applied to |00000>)
- Apply the Oracle (flip amplitude of state that matches search criterion)
- Quantum Fourier Transform
- Reverse the sign of all states except |0> which represents the mean (DC component of the QFT)
- Inverse QFT
- Goto step 2
I am curious as to how step 4 can be implemented, as it seems to alter a single state without affecting the others (or all states except for one - same thing). To do this, don't we need to know from within an individual state whether this state is the one to flip (as we did in step 2 by testing the search criterion)?
This may relate to my confusion over the QFT. To take a Fourier transform would imply the states are ordered in some fashion - what determines this order? And to apply step 4 implies knowing which state is the 0th state, which also appears to be a question of ordering.