I Question about Grover's algorithm

[Malamala]

Hello! I am just getting started learning about quantum computing so I apologize if this questions is trivial, but I am a bit confused about the Grover's algorithm. As far as I understand (I read it from here), assuming there is just one solution, you start with N qubits, you put them in an equal superposition (using Hadamard gates), you pass them thorough an oracle that inverts the phase of the right solution, then you have a diffuser operator that reflects this new vector relative to the original one and doing this $\sqrt{N}$ times you get a high probability of measuring the right solution. I think I understand the math behind it and the geometrical interpretation, but I don't understand how it is used in practice. What is that oracle? In both examples given on that page, in order to build the oracle i.e. to make sure that the right solution gets a minus sign, you need to know the right solution beforehand. But if you know it, you don't need an algorithm to find it. Can someone help me understand this? What is the oracle in a real problem and how can I implement it in practice without knowing the answer to my question beforehand? Thank you!

 

[.Scott]

I don't understand how it is used in practice. What is that oracle? In both examples given on that page, in order to build the oracle i.e. to make sure that the right solution gets a minus sign, you need to know the right solution beforehand. But if you know it, you don't need an algorithm to find it. Can someone help me understand this? What is the oracle in a real problem and how can I implement it in practice without knowing the answer to my question beforehand? Thank you!

First, I'm not sure that it is used in practice.

The "oracle" is part of the Quantum Circuitry that determines exactly what problem is to be solved.
So in order to use Grover's algorithm, you need to write another algorithm that is specific to the problem you are attacking.

For example, let's say that you are looking for a large prime number - say greater that 2^1024. So your oracle might take 1024 bits that represent the last 1024 position of a 1025-bit number - the first bit in that number being a "1".

The oracle will now flip all 1024-bit codes that when combined with that initial "1" code for a prime number.

The key here is that the oracle does not flip a bit, it flips the phase of a full code. So with 1024 bits, you may have many billions of correct answers - and about 2^1024 incorrect ones.

When you apply Grovers algorithm, there is a good chance that you will get one of those primes - but, of course, you would check the result.