Talk:Grover's algorithm

This article needs to flesh out the potential uses for Grover's algorithm.

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)

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 $2^{n}$ states. We utilize the quantum oracle which maps $|x\rangle$ to $(-1)^{f(x)}|x\rangle$. 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

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.

comment on my reverting changes by Cnotgate

Unless you're on of the authors of http://iontrap.physics.lsa.umich.edu/publications/archive/PRA_72_050306_brickman_grover.pdf the image that you included was not your own work. Regardless, the diagram has so much undefined notation it's almost useless without the entire article. Skippydo 09:05, 4 August 2007 (UTC)

If i wrougth who is author of this image and show link to this article, will i can put this image in wikipedia? Cnotgate

If you are the author then yes. Otherwise I'm guessing you'd need the permission of whomever is the copyright holder which I would guess is the publisher of this article. I'm not sure what wikipedias policies are on copyright images. At any rate, the image exists to convey the idea of the note in which it's published. This note is about a specific implementation, it's less general than most of what we deal with in this article. Skippydo 10:27, 4 August 2007 (UTC)

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 πN^1/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)

But then probability to measure each searched state will be 1/k. So at all need ${\frac {k\pi {\sqrt {N/k}}}{4}}$ iterations in best case if you success after first measurment get $k_{1}$, after second measurment measure $k_{2}$, after third measurment measure $k_{3}$ and so on. So if you want to measure say all 4 answers, which you searching, then if you dont success very well, then you say need on average ${\frac {2k\pi {\sqrt {N/k}}}{4}}$ iterations. And how it can be marked all searched states at once? Maybe after first iteration is marked state 1, after second iteration state 2, after third iteration state 3 and so on. After marked last state which we search, grover algorithm again mark repidetly, state 1, then state 2 and so on.

formula after one grover iteration

Here is formula how you can very quickly calculate probabyllity to measure good answer after one grover iteration:

$({\frac {3N-4}{N{\sqrt {N}}}})^{2}$,

Here N is number of states in database.