Talk:Grovers algorithm

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 U_s 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