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)
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“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)