Talk:Grover's algorithm

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale. Physics Low‑importance This article is within the scope of WikiProject Physics, a collaborative effort to improve the coverage of Physics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.PhysicsWikipedia:WikiProject PhysicsTemplate:WikiProject Physicsphysics Low This article has been rated as Low-importance on the project's importance scale. Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Cryptography: Computer science Mid‑importance This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography Mid This article has been rated as Mid-importance on the importance scale. This article is supported by WikiProject Computer science (assessed as Mid-importance).

Archives

1

This article needs to flesh out the potential uses for Grover's algorithm. There are some real challenges to scalability. Moveovergrover (talk) 00:45, 18 March 2012 (UTC)[reply]

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)[reply]

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)[reply]

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 ${\displaystyle n}$ inputs are zero but shortly after we put them in a superposition of all ${\displaystyle 2^{n}}$ states. We utilize the quantum oracle which maps ${\displaystyle |x\rangle }$ to ${\displaystyle (-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)[reply]

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

Say, input consist of n qubits. How much qubits need measure on output? n qubits or 1 qubit?

We measure all ${\displaystyle 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)[reply]

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)[reply]

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)[reply]

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.

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)[reply]

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)[reply]

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)[reply]

That is odd. I deleted the numerical examples since anyone capable of understanding the rest of the math in the article is presumably capable of plugging in numbers on their own... -- BenRG (talk) 12:39, 4 May 2008 (UTC)[reply]

I could be wrong here so I don't want to make the change without asking others, but I'm a bit confused about something in the section on optimality of Grover's algorithm:

"It is known that Grover's algorithm is optimal. That is, any algorithm that accesses the database only by using the operator U_ω must apply U_ω at least as many times as Grover's algorithm."

Why is the optimality of Grover's algorithm even making reference to U_ω? It is well-known that Grover's algorithm is optimal, but I thought that meant there does not exist any other probabilistic quantum algorithm for solving the search problem in less than O(N^1/2) time? The optimality as stated in the article is much weaker, it seems. JokeySmurf (talk) 19:53, 28 February 2009 (UTC)[reply]

It does seem an odd way to phrase it, but doesn't it amount to the same thing? --Michael C. Price ^talk 23:29, 28 February 2009 (UTC)[reply]

It may, but it seems to me that it's weaker because couldn't there be other probabilistic quantum algorithms that tackle the search problem that don't make use of the operator U_ω? The statement right now just rules out making a new algorithm using that particular operator, but it doesn't seem to rule out creating a new algorithm from scratch that doesn't use that operator at all. JokeySmurf (talk) 00:18, 1 March 2009 (UTC)[reply]

We are given black-box access to a function via U_ω. More appropriately, we are given access to a uniary operator which maps <x><0> to <x><f(x)> where f maps binary strings to a bit (0 is a miss, 1 is a match). We can then implement U_ω by applying Hadamard matrices before and after this implementation of f.

An algorithm which does not make use of the operator U_ω, does not access the database and couldn't possibly solve the problem. Indeed, the statement in the article is stronger than using the big-oh notation, which hides the constant. Skippydo (talk) 00:50, 1 March 2009 (UTC)[reply]

Thanks and apologies. I somehow got it in my head that U_ω was the entire Grover operator.JokeySmurf (talk) 02:59, 1 March 2009 (UTC)[reply]

"The optimality of Grover's algorithm suggests (but does not prove) that NP is not contained in BQP."

This statement is grossly misleading. The failure of Grover's algorithm to solve NP-complete problems efficiently does not "suggest" in any meaningful way that all of BQP also fails. Grover's algorithm is merely performing black box search -- this statement is akin to the oft-repeated "proof" that P does not equal NP, "because you have to check all the (exponentially many) possibilities".

This would be like, if I said that, if I want to find shortest paths in a graph, well if the graph has size n, then there are n! many paths, so if I go down the list crossing them off, I can't do it efficiently. Even using quantum speed up to do the black box search, I still can't do it efficiently. So I guess its impossible to do it efficiently.

Wrong! If you are clever and think about it, it is not hard to come up with efficient algorithms for shortest path. Ruling out one naive approach, which uses none of the mathematical structure of 3SAT at all, and trying to argue from that that BQP probably doesn't contain NP, is like trying a sudoku puzzle, and when you do not get it immediately on your first guess, saying "Gee this suggests its impossible." 64.90.83.200 (talk) 06:27, 25 July 2010 (UTC)[reply]

On a note related to what 64.90.83.200 was saying, I just had to delete a segment saying that Grover's could solve NP complete problems. This isn't at all true. Being able to search a database is differnet from finding a solution. With a database you know exactly what you're looking for, effectively "the solution." However with a problem, you don't know the solution so there's no point in "searching" the solution space. --ScWizard (talk) 21:00, 2 September 2010 (UTC)[reply]

I also found this statement confusing, and had to do a bit of digging. My best guess at the intent of this statement is to represent the chain of reasoning described in this quantum computing stack exchange answer: NP-complete problems are solvable in exponentially many steps, Grover's algorithm provides at most a square-root speedup, the square root of an exponential function is still an exponential function. I proposed an edit to this effect. Tuzki17 (talk) 17:52, 18 August 2022 (UTC)[reply]

The states are defined as vectors named 1,2...N. The definition of Uω is such that ω appears to be one of the identifiers of the eigenvectors, i.e. ω=1,2....N. In the algorithm description, however:

"Our goal is to identify this eigenstate, or equivalently the eigenvalue ω, that Uω acts specially upon"

The naming of eigenstates here is inconsistent and confusing. Up to this point one has to assume that ω is one of 1,2....N, i.e. one of the integers and not one of the eigenvalues. In this sentence, however, it is said explicitly that ω refers to one of the eigenvalues and not to one of the integers. The reason this is unfortunate is because the reader has to keep reading whilst keeping multiple possible interpretations of Uω in mind at the same time. (The text further on becomes ambiguosu too). In a typical Physics text this is rarely a problem, the state could be referred to by any synonym, ω_i, i, lambda_i (i=1,2...N), whatever. The present context, however, is an abstract algorithm so it becomes difficult to follow if the Uω differentiates between "i's" or "lambda's" and since the i's are in a binary representation (and the Uω makes phase changes and what not...) the text becomes unnecessarily tough. I would like to change the text but since it's been hanging around for so long I'm hesitant to mess with it. (Sure, a quantum mind would have no problem keeping both interpretations in the head at the same time until the collaps at the end but it's sort of unnecessary obfuscation). — Preceding unsigned comment added by 79.161.24.236 (talk) 11:42, 22 October 2011 (UTC)[reply]

I removed the mention of the eigenvalue. Does that address your concern?

Along similar lines, I think the mention of the lambdas can go as well. The eigenvalues are 1 and -1, I'm not sure if anything more needs to be said about them. Skippydo (talk) 18:05, 22 October 2011 (UTC)[reply]

I think the lambdas can stay but I'm also not happy about the Uω. The text is ambiguous because it reads as if the value of ω is given a preori. In Grovers original text he uses a "C" without an index and terminology like "Let there be a unique state, say Sν, that satisfies the condition C(Sν).." and "there is a unique state Sν such that the final state is Sv". To me that is better, i.e. something like "given a U such that there is a ω, to be determined, such that...." would be more "safe" on the intent. Note, this is not more elborate text, just less ambiguous. The way the text reads it can be erroneously interpreted as "given ω, U is designed so that for this given ω Uω has the desired properties". ( "Us" with "s" for "search" would be OK but since s already is in use then perhaps Uc (c for compare) would do just as well). — Preceding unsigned comment added by 79.161.24.236 (talk) 22:59, 23 October 2011 (UTC)[reply]

The definition reads "Each of the eigenstates of Ω encode one of the entries in the database, in a manner that we will describe." The encoding of the entries is nowhere described (and of course is not needed). Was text removed ? The sentence needs to be changed. The way it reads now the only interpretation possible is that the lambdas encode the entries(which of course could be, but isn't described). Suggestion: retain mention of the "entries" but change this sentence so that the encoded entries are given as { C1, C2, C3...CN }. This avoids confusion. — Preceding unsigned comment added by 79.161.24.236 (talk) 21:08, 25 October 2011 (UTC)[reply]

I rewrote the setup section but I don't think it addresses your latest concern, other than removing the offending sentence. A function f is usually defined as a quantum map via the transformation |x>|y> to |x>|f(x)+y>. Given such a map corresponding to the database search criterion, this can be turned into the map described in the article by using an auxillary qubit intitialized to |1> and two Hadammard maps. That is, |x>|1> to |x> (|0>-|1>) to |x> (|f(x)>-|1+f(x)>) to (-1)^f(x) |x>|1>. This is what happens in the Deutsch–Jozsa algorithm as well. I'm not sure if it can/should be worked into the article. Skippydo (talk) 00:34, 28 October 2011 (UTC)[reply]

In the Algorithm description the measurement Ω and the measurement result λω are not properly defined. — Preceding unsigned comment added by 79.161.24.236 (talk) 21:47, 16 June 2013 (UTC)[reply]

There should be U_f on the image, not U_w.

--Dandan~ukwiki (talk) 07:47, 5 May 2021 (UTC)[reply]

I see what happened: U_w used to denote both U_f and U_w, so the image worked because of the ambiguous notation. I edited this to separate the definitions, causing this issue. The best solution might be just to make a new image, which I'll do if I get the time. Fawly (talk) 22:31, 5 May 2021 (UTC)[reply]

Done, please let me know if I made any errors.

Fawly (talk) 17:40, 7 June 2021 (UTC)[reply]

In the Limitations section it may be useful to point out that the algorithm does not work if half the possible binary strings are solutions. MClerc (talk) 11:46, 1 July 2023 (UTC)[reply]

Clarification for both this and issues with greater than half solutions in the multiple entry case has now been provided in the multiple matching entries section. Deep Gabriel (talk) 06:22, 1 September 2023 (UTC)[reply]

https://www.youtube.com/watch?v=ElYwWPsPRUY Doug youvan (talk) 20:02, 13 February 2024 (UTC)[reply]