 | This is an archive of past discussions about Grover's algorithm. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 |
My understanding is that Grover's algorithm still takes exponential time to solve NP-complete problems. The solution will be much faster than a naive brute force solution on a conventional computer, but not necessarily faster than a smart algorithm on a conventional computer. Is this correct?
- Yes, AFAIK -- CYD
I added a sentence to that effect.
I have another question: the article claims that Us is a reflection about s, which I take to mean a reflection about the line through s, and this is correct. But Uω is not a reflection about ωx in the same sense. For the operator V to be a reflection about the vector w, we need to have Vw = w and Vx = -x whenever w and x are orthogonal. Uω doesn't have that property; it is a reflection at the plane spanned by all x≠ω. --AxelBoldt
- Yup. For vectors in the plane, it acts as a reflection about ωx, which is what we want. That was a rather misleading statement. I've fixed it up; check if you agree now. Thanks :-) -- CYD