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)
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)
“With impressive proof on all sides of magnificent progress, no one can rightly deny the fundamental correctness of our economic system.”
—Herbert Hoover (1874–1964)