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.

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.