 # Grover’s algorithm | QuTech Academy

Now we’re going to learn
about another quantum algorithm that, while it doesn’t provide
as large a speedup over its classical counterpart, does still have an interesting structure
that makes it worth discussing. The problem to be solved is as follows. Imagine that there is an array of n switches,
which all have to be set in a correct configuration w, in order to light a bulb. Now, to make the problem difficult, some
of these switches have been installed upside-down, and there’s no manual lying around,
so the all-up configuration isn’t necessarily correct, as it should be. If we tried a certain configuration of switches,
some up some down, it wouldn’t tell us anything about which switch was set incorrectly,
all we would see is that the bulb is either lit or not. For this problem,
if we limit ourselves to classical algorithms, there’s no essentially better strategy
than to guess and check repeatedly until we find w, the correct configuration. This requires a number
of switch flips that scales as 2 to the n, which can get quite large as n grows. To lay out the corresponding quantum algorithm, we’re going to need to make use
of another building block, the oracle. Oracles are used in many different quantum algorithms,
when the complete implementation of a given function is unknown. An oracle is a black box that we can prove is unitary,
though we don’t know the circuit complexity of its implementation. In place of a proper complexity
which is worked out in terms of the space and time cost of running a quantum circuit, we use the number
of queries to the oracle, which is the number of times that it’s used, as a proxy. The oracle for the lightbulb problem will look like this. We input a configuration z,
some eigenstate in the z basis on each qubit, and if the bulb would light up,
an ancilla qubit gets flipped. Already we can see that, if we input
a minus state on the ancilla, we can obtain what I’ll call U_f, which maps w to -w
and acts as the identity on all other states in the z basis. We can see that the operation U_f can be written
as identity minus 2 times w-w. If this is unclear, pause the video, and take
a moment to evaluate the action of this operator on the state w, and on other states
which are orthogonal to w. We can also define another unitary u+
that does almost the same thing, except that it acts as the identity on the all plus state,
and applies a minus one phase to any state orthogonal to the all plus state in the x basis. Now, we’re going to take the product
of these two operators and call it the Grover iterate G. We’re going to show in the following section
that if we apply G k times to the all plus state as an input, we end up with a state
that’s very close to w, the state described in the winning configuration. First, let’s write the all plus state out neatly. We can see that the all plus state is
a uniform superposition over all states in the z basis, and that this necessarily includes w,
regardless of what w actually is. There’s also another term which is proportional
to w perp, which is a uniform superposition of everything in the z basis that’s orthogonal to w. We’re going to write the coefficients of this wavefunction
as angles to simplify our calculation later on. Now we can see that the first part of G, U_f,
just places a minus sign on the w term, easy enough. To see the consequence of then performing U_+,
though, we’ll now have to define another state + perp, which is just a state that’s orthogonal
to the all plus state, written out using w and w perp. Now we can express U_f + in the +,
+perp basis, using a little bit of trigonometry. Eventually, we get to the expression
cos 2 theta + – sin 2 theta + perp. Applying U_+ and changing the basis back,
we can see that the Grover iterate takes our initial angle theta
and replaces it with the angle 3 theta. If we did this k times in a row,
we’d end up with not 3 theta, but 2 k + 1 theta. In order to obtain a state close to w,
then, we have to choose k so that the sine of 2 k + 1 theta is close to one. Now, the sine is close to 1
when the angle is close to pi by 2, so this gives us a k roughly equal to pi divided by 4 theta,
which is roughly pi/4 times root 2 to the n. This scales as the square root of the number
of configurations we’d have to try in the classical case, providing us with an algorithm
that has a polynomial speedup over the classical one.

## One thought to “Grover’s algorithm | QuTech Academy”

1. Aquanjitsu says:

How to create an oracle function U_f without using the |w> state, which is the winning configuration that the algorithm is supposed to find? If we know |w> before running the algorithm, we already know the answer.