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:
“New York ... is a city of geometric heights, a petrified desert of grids and lattices, an inferno of greenish abstraction under a flat sky, a real Metropolis from which man is absent by his very accumulation.”
—Roland Barthes (1915–1980)
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)
“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)