Talk:Grover's algorithm
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Physics, which collaborates on articles related to physics. |
| ??? | This article has not yet received a rating on the assessment scale. [FAQ] |
| ??? | This article has not yet received an importance rating within physics. |
|
Help with this template Please rate this article, and then leave comments to explain the ratings and/or to identify its strengths and weaknesses. |
|
This article needs to flesh out the potential uses for Grover's algorithm.
Contents |
[edit] Incorrect use of O-notation?
from the article: Furthermore, the probability of obtaining the wrong answer becomes O(1/N), which goes to zero for large N.
I could be way off the mark, especially because I don't understand the content of the article, but I understand O-notation is used in expressing the performance of an algorithm, not for the probability of a particular output. However, I really know nothing about quantum physics, barely more about the study of algorithms, and I haven't even read the entire article. Moskvax 14:34, 16 November 2005 (UTC)
It's also used for describing errors and the like ("infinitesimal asymptotics"), exactly in this case. See Big_O_notation. Captain Segfault 19:05, 23 November 2005 (UTC)
[edit] but HOW?
How grover's algorithm can find some state if on input is all |0> - all the same states? If we by phase chose some state, then we fake up and we do just same operations, like as if the just check all qubits... How we knew, what are we seaching? 212.59.24.195
- The n inputs are zero but shortly after we put them in a superposition of all 2n states. We utilize the quantum oracle which maps
to 
. That is, when we get a database hit (ie f(x)=1) we get add phase difference of -1. The next task is to turn the phase difference into a amplitude difference. Skippydo 05:49, 3 August 2007 (UTC)
- But if you want to mark state, you will do classical operation. SO, ON OUTPUT WILL BE THAT STATE, WHICH WAS MARKED? 212.59.24.195
[edit] How much qubits need measuring on output?
Say, input consist of n qubits. How much qubits need measure on output? n qubits or 1 qubit?
- We measure all n qubits, as the s we are looking for is n-bits. You may want to start with a simpler algorithm such as the Deutsch-Jozsa algorithm if you're just getting started in this field. Skippydo 05:49, 3 August 2007 (UTC)
- In my opinion Deutsch-Jozsa algorithm is much harder than grover algorithm... Here is almost full scheme for grover algorithm with 2 qubits: http://iontrap.physics.lsa.umich.edu/publications/archive/PRA_72_050306_brickman_grover.pdf . I will be very happy if i see such scheme for more qubits. Becouse in this scheme i don't see any superior quantum search algorithm compare with random number generator, say (maybe need more qubits?). So in general, like shown in that scheme, rotating or not rotating each of two qubits, we can mark |00> or |01> or |10> or |11>. And on output we will measure state, which we mark(?). Did i correctly understood? But then it is just classical computation(!). Becouse we can marked one of 4 possible states, and will measure one of his state (measure state, which is markerd). Or maybe on ouput will be say entanglet |00> or |11> if we find correct state? 212.59.24.195
- In general there is no way to mark a specific state within a superposition and ensure that this is the state that is measured. The implications of this are, for instance, faster than light communication. The N=4 case is special in that only one iteration of the algorithm is required. So it looks as though we may mark our state we want and force it to be measured but the techniques used cannot be extended. I suggested that the Deutsch-Jozsa algorithm is easier because it is deterministic, requires one iteration, and there's no requirement of turning a phase difference into an amplitude difference. Skippydo 05:10, 4 August 2007 (UTC)
- I think, you don't understand what i want to say. Iterations, amplification is not general principe how algorithm work! But i has though, that if you want to mark some state (say this state is |010101>), you need with classical computer mark whis state, and this is classical operation! So if this is classsical operation, then all algorithm is classical! Becouse we classicaly mark this state, and on ouptu with 1/N probability get this state (|010101>). So what goal is to search this state (|010101>)? It is just waist of time!212.59.24.195
- What do you mean by mark a state? I assumed you meant adding a phase difference of -1 (which is not a classical operation) but I guess I'm wrong. Skippydo 08:55, 4 August 2007 (UTC)
- Look, to chang phase, need rotate qubits. To rotate each qubit need it do with classical computer. Qubits is n. Then you need rotate n qubits. If you want, for example, to mark state |010101>. You need rotate second, fourth and sixth qubit. So you do classical operations by rotating each qubit (see in my last link).
- Also there is though, what to grover algorithm need quadratic more gates, than to probabilistic.
- What do you mean by mark a state? I assumed you meant adding a phase difference of -1 (which is not a classical operation) but I guess I'm wrong. Skippydo 08:55, 4 August 2007 (UTC)
- I think, you don't understand what i want to say. Iterations, amplification is not general principe how algorithm work! But i has though, that if you want to mark some state (say this state is |010101>), you need with classical computer mark whis state, and this is classical operation! So if this is classsical operation, then all algorithm is classical! Becouse we classicaly mark this state, and on ouptu with 1/N probability get this state (|010101>). So what goal is to search this state (|010101>)? It is just waist of time!212.59.24.195
- In general there is no way to mark a specific state within a superposition and ensure that this is the state that is measured. The implications of this are, for instance, faster than light communication. The N=4 case is special in that only one iteration of the algorithm is required. So it looks as though we may mark our state we want and force it to be measured but the techniques used cannot be extended. I suggested that the Deutsch-Jozsa algorithm is easier because it is deterministic, requires one iteration, and there's no requirement of turning a phase difference into an amplitude difference. Skippydo 05:10, 4 August 2007 (UTC)
- In my opinion Deutsch-Jozsa algorithm is much harder than grover algorithm... Here is almost full scheme for grover algorithm with 2 qubits: http://iontrap.physics.lsa.umich.edu/publications/archive/PRA_72_050306_brickman_grover.pdf . I will be very happy if i see such scheme for more qubits. Becouse in this scheme i don't see any superior quantum search algorithm compare with random number generator, say (maybe need more qubits?). So in general, like shown in that scheme, rotating or not rotating each of two qubits, we can mark |00> or |01> or |10> or |11>. And on output we will measure state, which we mark(?). Did i correctly understood? But then it is just classical computation(!). Becouse we can marked one of 4 possible states, and will measure one of his state (measure state, which is markerd). Or maybe on ouput will be say entanglet |00> or |11> if we find correct state? 212.59.24.195
[edit] How grover algorithm work if we searching more than one componenet?
So if we search one state, then we mark this state changing this state sign. But how grovers algorithm can change sign if we are searching more than one state at once? What will be on output? Two state at once? 212.59.24.195
- If, instead of 1 matching entry, there are k matching entries, the same algorithm works but the number of iterations must be π(N/k)1/2/4 instead of πN1/2/4
- is a quote from the article. This is the probability of getting one of the entries. If you want them all you have to run the algorithm at least k times. Don't forget to sign your posts with four tildas ~~~~ . Skippydo 01:05, 6 August 2007 (UTC)
[edit] Better explanation
What do these oracle operators look like? Am I required to store for every f(x) a different oracle operator to find x? How do I have to imagine that? Can't I just find y (a number) corresponding to x (another number) by just querying f(x)? —Preceding unsigned comment added by 84.75.137.125 (talk) 00:26, 14 January 2008 (UTC)
[edit] Why N=16?
The article often seems to use the example of N=16. I say seems since there is no explanatory text that says for example for N = 16. Is this intentional? --Michael C. Price talk 12:00, 4 May 2008 (UTC)
