This is a very clear explanation of the benefits of quantum computers. But I don't grasp how this would work yet.
I read the Wikipedia page, and maybe I just have to struggle more with it, but it would be great if there was a simpler explanation.
This is a very clear explanation of the benefits of quantum computers. But I don't grasp how this would work yet.
I read the Wikipedia page, and maybe I just have to struggle more with it, but it would be great if there was a simpler explanation.
The real problem you solve with Grover's algorithm is this: you have a black box (usually called an "Oracle operator", but I think the term "Oracle" in this case is misleading) that negates the value of your register along exactly one axis (i.e., if the coordinate on the 00010111 axis is .2 - .1i, it becomes -.2+.1i). You want to figure out which of the 2^n axes in the n-qubit register your black box negates.
Unfortunately, you don't have the luxury of picking the vector that has a coordinate of 1/sqrt(2^n) in each direction, and observing what the black box does to that after a single application, since when you observe your quantum register you always observe a classical state. In contrast, one solution that would work would be to solve the problem the classical-computing way: march through each of the 2^n axes until you find the one you're looking for.
Grover's algorithm gives you a better way. What Grover's algorithm does is repeatedly apply an operation that nudges your register towards the desired state -- basically applying a small rotation. After some number of iterations, the vector representing your register should be pointing in almost the same direction as the vector representing the state you're searching for. Then you can measure the contents of the register and, with high probability, get the answer you were searching for. It turns out you only need O(sqrt(2^n)) queries (rotations), so it's a substantial improvement over the classical case.
I've probably oversimplified a few things, but hopefully this makes things clearer than they were before.