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.


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).

| improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Jonathcraft May 4 at 19:59
  • $\begingroup$ That's partial application: docs.microsoft.com/en-us/quantum/language/… $\endgroup$ – Mariia Mykhailova May 4 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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