Okay. So, to see how powerful this, this Hadamard Transform can be, let's look at
the following simple problem, which is a parity problem. So, we're given some
function f from n bits to one bit, and it's given to us as a black box. So, we're
given a program that will compute this function for us but we cannot look inside
the program to see how it's doing so. All we can do is run this program on any given
input. So, program or a black box containing a circuit for computing this
function f. Now, we're also told that this, this, this function f has some, has
a very special property. It's, all it is, is a parity of some subset of the, of the
bits. So it's of the form U.x for some hidden U which is an n bit string. So, for
example, n might be equal to three, U equal to one, zero, one, in which case,
what this function does is on input x1, x2, x3. So, x is a three, three bit
string, f(x) is just x1 exclusive all x3. All right, it's x1 + x3 mark two. Okay.
What, what, what we mean by U.x it's U.x mod two. So, this now this is fun, this is
the circuit that we have it takes input x it outputs f(x) and we want to try to use
this box to try to figure out what, what this parity mask U looks like. So,
classically this is, you know, this is sort of easy to figure out. What you would
do is, you'd give as input so you might first input one zero, zero, zero. What's
the output? Well, it's just U1. And then you could output zero one zero, zero,
zero, zero and the output would be U2. And so in, in such steps, you can figure out
U, which is U1 through U sub n. Can you do any better? Well, clearly not. Because
each time you run the circuit, you get only one bit of information. So, you can
conclude you need at least n steps. Because you need to reconstruct n bits of
information. So, that's a classical situation. What about in the quantum
world? Okay, in the quantum world, remember, what we do is take the circuit,
and make a quantum circuit out of it. So now, it takes as input x and also an input
b, which is the answer bit. And what th e quantum circ uit does, is it outputs x and
bx, or f(x). So, the output, the answer that gets toggled, if and only if f(x) =
one. I'm suppressing the work, work bits, because, you know, they are, they start at
zero and end at zero. Now, of course, quantumly, we can also input. We, we can
put x in superposition, so our input could be sum over x of alpha x. Get x.and the
output is now going to be sum over x alpha x ket x, but the, but then we have the
answer in superposition f(x), as well. Okay. So, so, can we do, can we
reconstruct U using fewer queries to f(x)? So, we needed n such queries in the
classical case, can we do it in fewer queries? And it turns out, the answer is
yes. There's a, there's a, there's an algorithm that, that does this using as
few as one query to, to, do this do this circuit for computing, for computing f in
the quantum case. And so, the, the, the strange part here, the, the
counter-intuitive part here is that even though the circuit is outputting one bit
on one bit of information we seem to be getting n bits out of it. Okay. So, how
does this, how does this algorithm work? So, it works by first setting up a, a
particular kind of superposition, which is a superposition of all n bit strings x of
x with this, with this phase -one, with the phase of -one if and only if f(x) =
one. Okay, so, this is, this we call the phase state. And now, what you do is you
do for a sampling and you obtain U. So, let me first explain why this second step
works. You see, because, because f(x) is just U.x so this superposition is just one
/ two^n/2, sum over all x - one^u.x x. Now remember, what is, what is this state?
Well, this state is exactly what you get if you do the Hadamard transform on input
U. So, if that's, if that's your input, then this is what your output is. Okay.
So, so, what we want to do is we want to run this circuit backwards. We want to run
the Hadamard circuit backwards. Because we want this as input, and we want that as
output. So, how do we do that? Well, remember, the Hadamard transfor m is its
own inverse. So, all we have to do is, is we have to put this, this input through
the Hadamard transform again. We'll get this as output, and then we just measure.
And we'll, we'll obtain, obtain the, this hidden view that we were looking for. So
the, the only thing we have to do now is to figure out how to set up this
superposition. Okay. So, so, how do we set up this superposition? Well, this is, this
is actually not that difficult to do. So, what do we do? Well, we star with n bits
in the zero state, we perform a Hadamard transform on them. So, so now, if you
start with zero^n, we perform the Hadamard transform. What do we get? We get sum over
all n bit strings x of x with amplitude one / two^n/2. Now, what we do is, we set
up the answer bit in the state minus. Okay. So, so, the answer bit b, is in the
state minus, which is one / square root 2,0 - one /square root 2,1. Now, if the
answer, okay. So, what, what happens if f(x) = zero? Remember, the answer bit
becomes b, x or f(x) so, so what's b exclusive or f(x) in this case? Well, it
just stays minus, right, because, because when you x or zero into something, it does
nothing. So, it just stays one /square root of zero minus one / square root of
one. What happens if f(x) = one? Then b, x, or f(x) is just, well, you toggle it,
right? So, you get one / square root 2,1 minus one /square root 2,0 which is just,
you pick up a phase of -one. So, that's what we're doing. We, we set up the answer
beta as a minus, and then, we are running the circuit for computing f. So, remember
the input to the circuit is a superposition over all x, and what happens
when we, when we compute, compute f(x) with the output bit? The answer bit set
as, as minus? Well, whenever the, whenever, for those x such that f(x) =
zero, the phase doesn't change. And for those x such that f(x) = one, the phase ,
changes to -one. Okay, so, so what's another way of saying it? So, at this
point, our superposition was sum over all x, one / two^n/2 plus, sorry, x. And our,
answer bit was set as m inus. And now, when we compute use of f, wll go to sum
over all x, one / two^n/2 And then, we get, we still get x. We still get minus.
Except that whenever f(x) = one, we pick up a phase of -one. So, we get -one^f(x),
okay? But this is always minus, so this is always a tensor product state. And so, if
you look at these qubits, the first n qubits, we've got the desired phase state,
which is that. And now, if we do another Hadamard transform we end up with our,
with, with, with U. Okay, so this gives us this is really the, the algorithm. We, we,
we set up n qubits, the zero state, answer qubit in the minus state, we perform
Hadamard transform, perform U and now, we give, set up the phase state, we do
Hadamard transform on the first n qubits and we will recover U, so we mention.
Okay, so, this, this algorithm was, was really the, the base case of a recursive
algorithm. You know, this recursive algorithm is called Recursive Fourier
Sampling. I'll just give you a very short sketch of it not really enough to explain
it to you, but just a little, you know, the basic idea. So, in this recursive
version, we solve a recursive version of this, this same parity problem. And now,
we are trying to amplify this difference between classical and quantum. In the
classical case, you needed n queries. In the quantum case, you needed only a
constant number of queries. And so, so what you do is, in the recursive version
of the of the, of the, of the, of the, of the problem, classical algorithms satisfy
the recursion that time to solve a problem of size n is at least n times the time to
solve a problem of size n/2 + order n, where this n, is the number of queries
required to solve the parity problem. If you solve this recursion, you get t(n) is,
grows at least like n^log n. So this is, superpolomial. If you work through the
quantum algorithm for this, for the, for the recursive problem, it satisfies the
recursion t(n) = two t(n) / two + order n whose solution is t(n) = n log n This is
like the recursion for the, for mergesort, and so you get a polynomial time quantum
algorithm. And so, this gives y ou already a glimpse of this power of Fourier
sampling. That it gives you a super polynomial speed up for a certain kind of
problem. Okay. So, in the next video, we will see, how to use, sampling in, in an
even more dramatic way.