"Basic" question about Grover's Quantum Computing algorithm

[QComp]

Hi everyone,

I'm a computer scientist (not a physicist), so I will ask a computer scientist's question.

In all the descriptions I found of Grover's algorithm, there is an element that is puzzling the computer scientist in me: it seems that you need to tell the Oracle about the position of the item you are searching for... so that, through "amplitude amplification", measuring the system after it is collapsed indicates the position of the item you are searching for...

But isn't it the same information than the one that was given to the oracle to begin with?

When looking for an answer to this question on the internet, I found that many people already asked this very same question, but I never found a satisfying answer to it...

Hoping that someone in this forum could guide me,

P.

 

[DrClaude]

The Oracle doesn't need to know the position of the item you are searching for. It simply needs to recognise it when it sees it.

 

[QComp]

Dear DrClaude,

I am so happy that you are willing to help.
In a paper where Grover explain his algorithm (The Sciences 1999), he says the following thing (my underlining/boldfacing):

To set up your quantum computer, [...] you arrange things so that each name in the [4 entry] phonebook corresponds to a distinct combination of spins: (0,0), (0,1), (1,0), (1,1). Now, suppose that unbeknownst to you, the name you want to find corresponds to the third state (1,0). That state is the target.
... (many lines)
Now comes the heart of the algorithm.
The first operation changes the sign of the amplitude of the first target state (in my example, the third state); thus, the amplitudes change to (1/2, 1/2, -1/2, 1/2).​

My problem lies there (the very beginning of the algorithm).
Suppose that in the future, we can implement the algorithm for real in a real 50 qubits computer, with n large enough so that you can map all entries of the phonebook to a combination of qubits.
Suppose that you want to do what Google is currently providing everyone with, thanks to their thousands of computers, i.e. find among the 1.5 billion web pages of the Internet the ones that contain the word "Grover". For the sake of simplification, imagine that there exists only one page containing the word Grover.
Because I really don't know which page contains "Grover", how do I complete the first step of the heart of the algorithm, i.e. change the sign of the amplitude of the target state... knowing that... I really don't know which of the 1.5G pages contains the word?

P.

 

[DrClaude]

The oracle is usually taken as a black box, and it may require additional qbits. The important thing is that the oracle can recognise the solution.

Now, suppose that unbeknownst to you, the name you want to find corresponds to the third state (1,0).

What is unbeknownst is which state corresponds to the name, not the name you are looking for. If the phonebook is

1. John
2. Mary
3. Sara
4. Carl

And you are looking for Sara, the oracle must be such that the result is (1/2, 1/2, -1/2, 1/2). If the phone book is

1. Carl
2. John
3. Mary
4. Sara

then the action of the oracle must be to set the result to (1/2, 1/2, 1/2, -1/2).

 

[cosmik debris]

I really don't know which of the 1.5G pages contains the word?

As Dr Claude said the Oracle "knows" the solution, this the same as a conventional database lookup where you must have a function that compares each database entry with the search string.

Cheers

 

[QComp]

Sorry to be thick or slow on the uptake...

To Dr Claude: could you please re-issue your statement on the following setup?

1. John
2. Mary
3. Sara
4. Carl

...

?. Grover

...

1523087387. Claude
You say:

then the action of the oracle must be to set the result to (1/2, 1/2, 1/2, -1/2).

In the above practical setup, what do you set the action of the oracle to?

To cosmik debris (I really like your pseudo, btw :-):
In a conventional database, the comparison function would read something like if(match(name, "Grover")) 1 else 0; where the match function would compare each letter of the name variable to each letter of the "Grover" string.
Is it this that you are setting up the Oracle to? Coaxing it to recognize the sequence of letters G r o v e r in the 1.5 billion text strings that must be searched? If this is what Grover's algorithm is coaxing the Oracle into, then, this is fine with me. But if Grover's algorithm says that you should, before the search begins, set the Oracle to the result (1/2, 1/2, 1/2, -1/2, 1/2, 1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, 1/2, 1/2, 1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, 1/2, 1/2), I don't buy it because, how do I know that it is there that Grover's name can be found (so that I can give the Oracle this setting)?

 

[DrClaude]

In a conventional database, the comparison function would read something like if(match(name, "Grover")) 1 else 0; where the match function would compare each letter of the name variable to each letter of the "Grover" string.
Is it this that you are setting up the Oracle to?

Yes, that's basically it.

 

[cosmik debris]

[QUOTE="QComp, post: 6147513, member: 658591" I don't buy it because, how do I know that it is there that Grover's name can be found (so that I can give the Oracle this setting)?[/QUOTE]

I think the assumption made in the Grover example is that there is one and only one match in the database.

Cheers

 

[QComp]

Wow. Thanks for your precise answer, DrClaude. To Cosmik debris, I think there is a version of Grover's algorithm where you can look for multiple matches, but let's keep it simple now.

Would you mind going through the algorithm step by step using the above settings ?
I use exaggerated so that there is no ambiguities left between the number of entries in the database, etc..., so the number are:

• 1.5T entries, in the database (the "web pages" in my previous post), exactly one of which contains the word to search, i.e.
• "Grover" : 6 letters out of an alphabet of 26 letters from a
• 32 characters set, therefore coded on 5 bits (let's drop the notion of caps size for the sake of simplicity so let's use a 32 letters alphabet "abcdef...z + 6-other-characters-I-don't-care-about. Let's suppose that the index of letter "a" is 1, for compatibility with ASCII

Now just a question to begin with: do each entry need to be exactly 6 characters long or could they be of variable length?
In the proposed alphabet, "grover" would use letters 7, 18, 15, 22, 5, 18, so the 6*5 digits binary number corresponding to "grover" would be:
0000 0111, 0001 0010, 0000 1111, 0001 0110, 0000 0101, 0001 0010

So this search would request an (at least) 6x8 = 48 qubits quantum computer with an initial setup to spin +1/2 whenever there is a 0 and -1/2 whenever there is a 1 (or the converse? this is not important, so let's get it right from the beginning).

Could you explain what the next step would be or would you need/want me to go on using my poor understanding of the algorithm?

Thanks,

P.

 

[QComp]

Ok. I think I have been a bit greedy by asking for the next steps... and I think my setup is not very demonstrative as the number of entries in the database is of the same order of magnitude as the number of 6 letter words you can write with a 32 letters alphabet.
Indeed, with 6 letters, you can have as many as 32^6 different words = 1 073 741 824, so having 1.5 billion different entries was unfeasible with 6 letters only.
So let's suppose we have "only" 1 million 6 letters entries, only one of which corresponds exactly to "grover".
Then, I made an error above, because I coded each letter on 8 bits, even though I said the needed alphabet would fit on 5 bits only, so it is not 48 bits that are needed, but "only" 30.

So one step would be to nudge 30 entangled qubits to 00111 10010 01111 10110 00101 10010, i.e. possibly:
+1/2, +1/2, -1/2, -1/2, -1/2, (g)
-1/2, +1/2, +1/2, -1/2, +1/2, (r)
+1/2, -1/2, -1/2, -1/2, -1/2, (o)
-1/2, +1/2, -1/2, -1/2, +1/2, (v)
+1/2, +1/2, -1/2, +1/2, -1/2, (e),
-1/2, +1/2, +1/2, -1/2, +1/2, (r)

Another step would be to get the system to know about the 1 million (6 letters) entries:

1. johnny
2. mariah
3. sarrah
4. carlos
...
?. grover
...
1000000. claude​

In the paper I have from Grover, he says: "Place the information from the phone book into quantum memory, and match each name to a different quantum state."
Do you have any idea how this is done? What would be a "quantum memory"? Does this use other qubits?

Thanks,

P.

​

 

[DrClaude]

I don't get your question.

So one step would be to nudge 30 entangled qubits to 00111 10010 01111 10110 00101 10010, i.e. possibly:
+1/2, +1/2, -1/2, -1/2, -1/2, (g)
-1/2, +1/2, +1/2, -1/2, +1/2, (r)
+1/2, -1/2, -1/2, -1/2, -1/2, (o)
-1/2, +1/2, -1/2, -1/2, +1/2, (v)
+1/2, +1/2, -1/2, +1/2, -1/2, (e),
-1/2, +1/2, +1/2, -1/2, +1/2, (r)

The entangled qubits are not used to encode the data. The data itself can be stored classically. The entangled qubits are used to perform the search.

 

[QComp]

Out of all the possible words that can be coded with 6 letters (from aaaaa, to zzzzz), the target state "grover" would be encoded (in binary) as
00111 10010 01111 10110 00101 10010, one group of bits for each letter. "g" is the 7th letter of the alphabet, so coded 00111 (7 in binary, or "g" in the {@, a, b, c, d, e, f, g, ... z, §, $, + ,= , *, £} alphabet. Note that I added §, $, + ,= , *, £ to complete the 32 possibilities that can be coded with 5 bits, and that I started with "a" in position 1 to comply with ASCII standards. By using qubit entanglement, this would result in:
+1/2, +1/2, -1/2, -1/2, -1/2, -1/2, +1/2, +1/2, -1/2, +1/2, +1/2, -1/2, -1/2, -1/2, -1/2, -1/2, +1/2, -1/2, -1/2, +1/2, +1/2, +1/2, -1/2, +1/2, -1/2, -1/2, +1/2, +1/2, -1/2, +1/2, probability amplitudes (simply the transcription of 00111 10010 01111 10110 00101 10010 into +1/2 for 0, -1/2 for 1).

Let's suppose the data is stored classically, which I will interpret as "in a silicon based computer's Random Access Memory". We could have an array of 6 million letters = 1 million 6-letter words starting with "johhny", "mariah", ..., "grover", ..., "claude" with "claude" being the 1 000 000 th word.
Suppose the array start address is, err... FF 00 00 00 (let's use a 32 bits address space that can support around 4 billion addresses). Supposing that each letter is coded in ASCII using one byte (rather than 5 bits), "johnny" will be stored from addresses FF 00 00 00 to FF 00 00 05, "mariah" will be stored from addresses FF 00 00 06 to FF 00 00 0B, and so on.
We don't know where "grover" is stored in memory, but we know it is there and we know it occurs only once.

Question: How do you "link" the quantum system to this simplistic data storage in order to start the search?

P.

Ps: sorry for being practical, i.e. trying to be specific on one particular case and therefore using realistic addresses, etc... but note also that I am willing to be cooperative :-) if it is difficult for the system to search letters stored on a 8 bit alphabet (ASCII) with an internal qubit representation on 5 bits, we could also use 8 qubits per target letter, but this means the system would need 48 qubits to store the target, not 30..., but because this is currently a "thought experiment", we could adopt 8 bits representation for each letter in the quantum system too if necessary.

Pps: if you think of another way to store the data "classically", could you please describe what you have in mind?

 

[DrClaude]

Have a look at this, which documents an actual implementation of Grover's algorithm: http://kth.diva-portal.org/smash/get/diva2:1214481/FULLTEXT01.pdf

 

[QComp]

This is exactly what I was looking for. It will take me a bit of time to ingest the thing, I suppose. I may come back to ask a question or 2 if there is a point that needs to be clarified.

Thanks a million for this document,

P.