2
$\begingroup$

Suppose I have a list of items: $(a, b, c, d, e, f, g, h)$. I could encode these letters in $3$ qubits such that $a = \vert 000\rangle, b = \vert 001\rangle, \cdots, h = \vert 111\rangle$. If I'm looking for $f$, my oracle is an $8\times 8$ matrix with $1'$s on the diagonal and a $-1$ as the $6^{th}$ element on the diagonal. Then I apply the Grover algorithm and get $f$.

But, what happens if $f$ is encoded as $\vert 111\rangle$ and I don't know that? How do I know how to construct my oracle?

$\endgroup$
3
$\begingroup$

What you're looking for is defined by the search oracle and, in particular, by the space that it acts on. In this case, your oracle acts on the set $\{0,1\}^3$ and it is one of these states that you're searching for. Any mapping to letters is independent of that, and must be provided as additional information. If you don't know that mapping, there's nothing that you can do - an output of 101 (for instance) could mean absolutely anything without the additional information of how to resolve that.

If you are the one building the oracle, then you can define what the mapping between letters and numbers is.

$\endgroup$
2
$\begingroup$

Not very understand about how a computer scientist will say about oracles. This is my understanding. Let's consider some other examples "without" oracles. If there are 8 boxes that have 1-8 numbers inside, no repeated numbers, and there is a box keeper who knows the number inside the box. And what we want to do is try to know which box has the number 6. Every round we will point at a box and ask the box keeper whether this box has number 6. Coming back from this example, we can see that the oracle in Grover's algorithm plays the same role as the box keeper in the example above. Oracle is not created by us, it's created by others, and the important complexity is the query complexity, i.e., how many times we need to use the oracle.

Another understanding from Nielsen and Chuang's book"

This discussion of the oracle without describing how it works in practice is rather abstract, and perhaps even puzzling. It seems as though the oracle already knows the answer to the search problem; what possible use could it be to have a quantum search algorithm based upon such oracle consultations?! The answer is that there is a distinction between knowing the solution to a search problem, and being able to recognize the solution; the crucial point is that it is possible to do the latter without necessarily being able to do the former.

That is, we can ask if the answer is right every time, for example, if we want to factorize number $n$ into two prime numbers, we can ask if number $a$ is a factor of it, this asking will spend us one resource.

$\endgroup$
1
$\begingroup$

My understansing of the Grover algorithm is that oracle can detect the element whcih you search and return it with a negative amplitude. Therefore, it doesn't matter which encoding does the element f have. The oracle can be presented as the following:

if element == "f":
return -|element> // negative amplitude
else:
return |element> // positive amplitude

Via the diffusion operator, the amplitude of the element "f" will be amplified and therefore the oracle can find the element "f".

I hope you can understand what I mean. The tutorial from Qiskit is very helpful: here and its implementation.

$\endgroup$

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.