Geometric Proof of Correctness
Consider the plane spanned by and, where is a ket in the subspace perpendicular to . We will consider the first iteration, acting on the initial ket . Since is one of the basis vectors in the overlap is
In geometric terms, the angle between and is given by:
The operator is a reflection at the hyperplane orthogonal to for vectors in the plane spanned by and ; i.e. it acts as a reflection across . The operator is a reflection through . Therefore, the state vector remains in the plane spanned by and after each application of the operators and, and it is straightforward to check that the operator of each Grover iteration step rotates the state vector by an angle of .
We need to stop when the state vector passes close to ; after this, subsequent iterations rotate the state vector away from, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is:
where r is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore .
Read more about this topic: Grover's Algorithm
Famous quotes containing the words geometric, proof and/or correctness:
“In mathematics he was greater
Than Tycho Brahe, or Erra Pater:
For he, by geometric scale,
Could take the size of pots of ale;
Resolve, by sines and tangents straight,
If bread and butter wanted weight;
And wisely tell what hour o’ th’ day
The clock doth strike, by algebra.”
—Samuel Butler (1612–1680)
“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)
“Rather would I have the love songs of romantic ages, rather Don Juan and Madame Venus, rather an elopement by ladder and rope on a moonlight night, followed by the father’s curse, mother’s moans, and the moral comments of neighbors, than correctness and propriety measured by yardsticks.”
—Emma Goldman (1869–1940)