7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Do you have the circuit $U$ that produces $\mid \psi \rangle$ from $\mid 0 \rangle^{\otimes N}$ or some similar easy reference state $\mid \phi \rangle$? Then you can reduce to $U (2 \mid \phi \rangle \langle \phi \mid - I) U^\dagger$. $\endgroup$
    – AHusain
    Sep 22, 2018 at 22:05

2 Answers 2

7
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ I see the docs use the word functor, but I don't see how it is being used in the sense of mathematical definition of functor. This seems like using the same word for a different concept. $\endgroup$
    – AHusain
    Sep 23, 2018 at 3:31
  • $\begingroup$ "Functor" is a common term in functional programming to denote a mapping of functions to other functions. In Q# it is used in this sense, rather than in mathematical. $\endgroup$ Sep 23, 2018 at 4:24
  • $\begingroup$ Yes, but in cases like Haskell, it is a true functor in both the functional programming and mathematical senses. So this is only one aspect. $\endgroup$
    – AHusain
    Sep 23, 2018 at 4:27
3
$\begingroup$

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⟩  
} 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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