How to construct the "Inversion About the Mean" operator?

Question

It seems like it should be simple, based on how Nielsen and Chuang talk about it, but I cannot seem to correctly implement the Inversion About the Mean operator ($2|\psi\rangle \langle\psi| - \mathcal{I}$) that is used in the Grover search algorithm, especially without using any ancilla bits.

I thought about performing a NOT operation on all the working qubits, then performing a controlled-NOT on a separate toggle qubit with the control being all the working qubits, then performing a controlled phase flip with control of the toggle bit, and finally flipping the phase of all the states. I'm not sure how I'd actually implement the controlled phase flipping, though, since, I believe, phase flipping one or all of the bits would not produce the desired effect.

Does anyone know how I can construct this? I am using Q#, by the way, if you'd like to answer in code.

Answer 1

First, let's represent operation $2|\psi\rangle \langle\psi| - \mathcal{I}$ as $H^{\otimes n}(2|0\rangle \langle0| - \mathcal{I})H^{\otimes n}$, as Nielsen and Chuang do.

Doing $H^{\otimes n}$ is easy - it's just ApplyToEach(H, register).

$2|0\rangle \langle0| - \mathcal{I}$ flips the phase of all computational basis states except $|0...0\rangle$. Let's do instead $\mathcal{I} - 2|0\rangle \langle0|$, flipping the phase of only $|0...0\rangle$ (it introduces a global phase of -1 which in this case I think can be ignored).

To flip the phase of only $|0...0\rangle$:

• flip the state of all qubits using ApplyToEach(X, register). Now we need to flip the phase of only $|1...1\rangle$ state.
• do a controlled-Z gate on one of the qubits (for example, the last one), using the rest as control. This can be done using Controlled functor: (Controlled Z)(Most(register), Tail(register)). Tail returns the last element of the array, and Most returns all elements except the last one.
• flip the state of all qubits again to return them to the original state.

Answer 2

Here is another way to flip the phase of only |0...0⟩:

using (ancilla = Qubit()){
    (ControlledOnInt(0, X))(register, ancilla); // Bit flips the ancilla to |1⟩ if register is |0...0⟩   
    Z(ancilla);                                 // Ancilla phase (and therefore whole register phase) becomes -1 if above condition is satisfied
    (ControlledOnInt(0, X))(register, ancilla); // Puts ancilla back in |0⟩  
}