Analysis
Now we'll analyze Grover's algorithm to understand how it works. We'll start with what could be described as a symbolic analysis, where we calculate how the Grover operation acts on certain states, and then we'll tie this symbolic analysis to a geometric picture that's helpful for visualizing how the algorithm works.
Solutions and non-solutions
Let's start by defining two sets of strings.
The set contains all of the solutions to our search problem while contains the strings that aren't solutions (which we can refer to as non-solutions when it's convenient). These two sets satisfy and which is to say that this is a bipartition of
Next we'll define two unit vectors representing uniform superpositions over the sets of solutions and non-solutions.
Formally speaking, each of these vectors is only defined when its corresponding set is nonempty, but hereafter we're going to focus on the case that neither nor is empty. The cases that and are easily handled separately, and we'll do that later.
As an aside, the notation being used here is common: any time we have a finite and nonempty set we can write to denote the quantum state vector that's uniform over the elements of
Let's also define to be a uniform quantum state over all -bit strings:
Notice that
We also have that so represents the state of the register after the initialization in step 1 of Grover's algorithm.
This implies that just before the iterations of happen in step 2, the state of is contained in the two-dimensional vector space spanned by and and moreover the coefficients of these vectors are real numbers. As we will see, the state of will always have these properties — meaning that the state is a real linear combination of and — after any number of iterations of the operation in step 2.
An observation about the Grover operation
We'll now turn our attention to the Grover operation
beginning with an interesting observation about it.
Imagine for a moment that we replaced the function by the composition of with the NOT function — or, in other words, the function we get by flipping the output bit of We'll call this new function and we can express it using symbols in a few alternative ways.
Notice that
for every string and therefore
This means that if we were to substitute the function with the function Grover's algorithm wouldn't function any differently — because the states we obtain from the algorithm in the two cases are necessarily equivalent up to a global phase.
This isn't a problem! Intuitively speaking, the algorithm doesn't care which strings are solutions and which are non-solutions — it only needs to be able to distinguish solutions and non-solutions to operate correctly.
Action of the Grover operation
Now let's consider the action of on the quantum state vectors and
First, let's observe that the operation has a very simple action on and
Second, we have the operation The operation is defined as
again for every string and a convenient alternative way to express this operation is like this:
A simple way to verify that this expression agrees with the definition of is to evaluate its action on standard basis states.
The operation can therefore be written like this:
using the same notation, that we used above for the uniform superposition over all -bit strings.
And now we have what we need to compute the action of on and First let's compute the action of on
And second, let's compute the action of on
In both cases we're using the equation
along with the expressions
that follow.
In summary, we have
As we already noted, the state of just prior to step 2 is contained in the two-dimensional space spanned by and and we have just established that maps any vector in this space to another vector in the same space. This means that, for the sake of the analysis, we can focus our attention exclusively on this subspace.
To better understand what's happening within this two-dimensional space, let's express the action of on this space as a matrix,
whose first and second rows/columns correspond to and respectively. So far in this series, we've always connected the rows and columns of matrices with the classical states of a system, but matrices can also be used to describe the actions of linear mappings on different bases like we have here.
While it isn't at all obvious at first glance, the matrix is what we obtain by squaring a simpler-looking matrix.
The matrix
is a rotation matrix, which we can alternatively express as
for
This angle is going to play a very important role in the analysis that follows, so it's worth stressing its importance here as we see it for the first time.
In light of this expression of this matrix, we observe that
This is because rotating by the angle two times is equivalent to rotating by the angle Another way to see this is to make use of the alternative expression
together with the double angle formulas from trigonometry:
In summary, the state of the register at the start of step 2 is
and the effect of applying to this state is to rotate it by an angle within the space spanned by and So, for example, we have
and in general
Geometric picture
Now let's connect the analysis we just went through to a geometric picture. The idea is that the operation is the product of two reflections, and And the net effect of performing two reflections is to perform a rotation.
Let's start with As we already observed previously, we have
Within the two-dimensional vector space spanned by and this is a reflection about the line parallel to which we'll call Here's a figure illustrating the action of this reflection on a hypothetical unit vector which we're assuming is a real linear combination of and
Second we have the operation which we've already seen can be written as
This is also a reflection, this time about the line parallel to the vector Here's a figure depicting the action of this reflection on a unit vector
When we compose these two reflections, we obtain a rotation — by twice the angle between the lines of reflection — as this figure illustrates.
This explains, in geometric terms, why the effect of the Grover operation is to rotate linear combinations of and by an angle of