# How to correctly define $U_\omega$ for Grover's search algorithm

I am working on Grover's algorithm and I am trying to implement the algorithm. I am following the Microsoft quantum katas and I finished and did everything correctly. I am trying to implement the algorithm for a specific case, but I am stuck writing the marking oracle (defined as $$U_\omega$$ on the Wikipedia page). I tried to look into the kata tests but I wasn't very successful.

The goal of the operator is to flip the sign of a state if it is correct. The mathematical representation for this is : $$|x\rangle \, \overset{U_\omega} \longrightarrow \, (-1)^{f(x)}|x\rangle$$This is the problem, I do not know how to implement this sign flipping. Is it done case by case ? Or is the a general "formula" to do so ?

Thanks for reading.

## 1 Answer

There are two types of oracles you can implement (Wikipedia article happily uses them interchangeably, which I don't think helps a lot): a marking oracle and a phase oracle.

Marking oracles are the ones that flip the state of the qubit $$|y\rangle$$ if $$f(x) = 1$$:

$$|x\rangle|y\rangle \, \overset{U_\omega} \longrightarrow \, |x\rangle|y \oplus f(x)\rangle$$

Marking oracles are much easier to build using reversible approach: break down your function into logical steps (such as AND, OR and NOT), implement each step in a reversible manner (using X, CNOT and Toffoli gates) and combine them. SolveSATWithGrover and GraphColoring show how to take a problem and implement it this way.

Phase (or sign flipping) oracles are the ones that flip the sign of the register $$|x\rangle$$ if $$f(x) = 1$$:

$$|x\rangle \, \overset{U_\omega} \longrightarrow \, (-1)^{f(x)}|x\rangle$$

Grover's search algorithm uses phase oracles, so you need to convert a marking oracle into a phase oracle using phase kickback trick (if you follow the katas, that's task 1.4 from GroversAlgorithm kata).

• Thanks a lot for explaining this to me. I didn't really understand the phase kickback trick until now but now everything is clear. I also understand that simply using an X gate is much easier than swapping the phase of the system, although the conversion is quite intelligent and easy to do. I have one more question about the kata, when you use a function to use the phase kickback operation, you leave the register input blank with an underscore. I don't understand what that does to be honest Commented May 4, 2020 at 19:59
• That's partial application: docs.microsoft.com/en-us/quantum/language/… Commented May 4, 2020 at 21:10