# In Grover's algorithm how do we flip all Fourier transformed states *except* the 0th?

According to this source, Grover's algorithm works as follows:

1. Begin with uniform superposed state (i.e. Hadamard gate applied to |00000>)
2. Apply the Oracle (flip amplitude of state that matches search criterion)
3. Quantum Fourier Transform
4. Reverse the sign of all states except |0> which represents the mean (DC component of the QFT)
5. Inverse QFT
6. 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.

First, you surround the operation you want to do with NOT gates so that you want to negate the $|1111...1\rangle$ state. Then, inside the NOTs, you surround one of the qubits with Hadamard gates. This turns the operation you want from a many-controlled-Z into a many-controlled-NOT with that qubit as the target.

Now we have a classical problem: given fixed sized gates (e.g. CCNOTs / Toffolis), how do we implement NOTs with arbitrarily many controls? One way is to combine controls two at a time, storing the combined value on a clean ancilla, until we get down to two controls. Then we can use those two controls to toggle the intended target.

On a quantum computer it's important that we not generate any entangled garbage, so after doing that we must uncompute each of the merged controls.

That's pretty much all there is to it.

• Your circuit appears to flip a single bit rather than a single state. My understanding was that QFT works over states not bits? or am I wrong there? – Sideshow Bob Aug 29 '17 at 11:18
• @SideshowBob The Hadamard operation converts between bit flips and phase flips. You can test the circuits in my drag-and-drop quantum circuit simulator Quirk if you want to get a better feel for it. – Craig Gidney Aug 29 '17 at 15:17
• Wow, so many questions here. Firstly, I don't understand your diagrams. According to the key on your (amazing!) simulator the thing in between the Hadamard gates is a probe, and so are the black dots. So nothing is being changed by the probes - where is the gate they control? – Sideshow Bob Aug 31 '17 at 10:37
• Secondly, I get that H converts between bit (|0> vs |1>) and phase (|0>+|1> vs |0>-|1>, renormalized) for a single bit. But the states of the circuit consist of entangled bits. So to invert a multi bit state such as |0010> we first have to identify it, then invert the phase, is that right? Is it correct that states are ordered by binary encoding, i.e. |0000> represents the mean amplitude (after QFT)? – Sideshow Bob Aug 31 '17 at 10:42
• @SideshowBob Actually that thing between the Hadamards is a NOT gate (an X gate). In the case where all the qubits with a black dot are ON, the qubit with the NOT gets toggled. The reason I use the same symbol (but smaller) for an X-axis control (the 'probe') is that in quantum computing controls are kind of like operations. – Craig Gidney Aug 31 '17 at 21:56