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.