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)
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)
“The surest guide to the correctness of the path that women take is joy in the struggle. Revolution is the festival of the oppressed.”
—Germaine Greer (b. 1939)