Timeline for What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 24 at 3:44 | history | protected | Mark Spinelli | ||
| Aug 19, 2024 at 10:16 | answer | added | tangyao | timeline score: 0 | |
| May 3, 2021 at 11:57 | answer | added | Michele Amoretti | timeline score: 1 | |
| May 3, 2021 at 11:28 | history | edited | glS♦ | CC BY-SA 4.0 | edited title |
| S Nov 9, 2019 at 17:20 | history | suggested | lcdx | CC BY-SA 4.0 | improved grammar and spelling |
| Nov 8, 2019 at 23:39 | review | Suggested edits | |||
| S Nov 9, 2019 at 17:20 | |||||
| Apr 24, 2019 at 1:29 | answer | added | Woody1193 | timeline score: 3 | |
| Apr 3, 2019 at 11:38 | answer | added | Brendan M | timeline score: 4 | |
| Oct 20, 2018 at 0:57 | comment | added | R. Chopin | If you understand that, then you should study the operator that is able to increase the amplitude of the desired term in the superposition while at the same time decreasing the amplitude of the undesired terms of the superposition. To me the easiest way to approach Grover's is to look at the inverse-about-mean operator. (Some people take the geometric view, but I don't find it as clear.) | |
| Oct 20, 2018 at 0:55 | comment | added | R. Chopin | @SanparithMarukatat It's not correct. The items of your list are the terms of the superposition of the state involved in the search. When the Oracle operates on this state, it counts as a single operation. The ability of the Oracle to mark the searched-for term of your superposition is a fundamental part of Grover's insight. To understand Grover's algorithm, I recommend you first understand how this marking off of the desired state happens. Afterwards, make sure to understand the role of the state $|- \rangle$ in the Oracle. | |
| Aug 1, 2018 at 15:39 | comment | added | Sanparith Marukatat | I also have difficulty understanding the advantage of Grover’s algorithm. Suppose that I have N items in the list. At each call to the Oracle, did it evaluate all N possibilities? Even if the evaluation is very fast but if we still need to iterate over all configurations, then the complexity of Oracle evaluation is O(N). So the Grover’s algorithm doesn’t seem to be faster than dumb search. Is this correct? | |
| May 22, 2018 at 5:34 | vote | accept | incud | ||
| May 21, 2018 at 7:09 | answer | added | DaftWullie | timeline score: 7 | |
| May 20, 2018 at 16:10 | history | edited | incud | CC BY-SA 4.0 | deleted 33 characters in body |
| May 20, 2018 at 15:37 | history | edited | incud | CC BY-SA 4.0 | deleted 12 characters in body; deleted 1 character in body |
| May 20, 2018 at 15:35 | answer | added | kludg | timeline score: 16 | |
| May 20, 2018 at 13:58 | history | edited | incud | CC BY-SA 4.0 | lighter example |
| May 20, 2018 at 13:53 | history | edited | incud | CC BY-SA 4.0 | lighter example |
| May 20, 2018 at 13:20 | history | edited | incud | CC BY-SA 4.0 | added some other infos |
| May 20, 2018 at 11:41 | history | asked | incud | CC BY-SA 4.0 |