Jump to content

Talk:Grover's algorithm/Archive 1

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
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