1
00:00:00,000 --> 00:00:07,005
Okay. So now, let's see how, how we can do
this, solve this period finding problem

2
00:00:07,005 --> 00:00:16,009
very efficiently if we had if we had a
quantum circuit for doing it. So remember

3
00:00:16,009 --> 00:00:23,007
our problem, we are, we are given a
function f. Sorry okay. So, we are, we are

4
00:00:23,007 --> 00:00:30,096
changing notation again. We are, we are
going from n to m. But that's okay. That's

5
00:00:30,096 --> 00:00:38,054
a small, small change. So, remember, we
have a function f which maps zero through

6
00:00:38,054 --> 00:00:45,068
m - one to sum set s. And F is periodic
with period r. So, r divides m and with,

7
00:00:45,068 --> 00:00:55,090
with the property that f(x) = f(x) + r,
for every x. And now, what we're trying to

8
00:00:55,090 --> 00:01:01,052
do is figure out what r is. So, here's
what our circuit for, for period finding

9
00:01:01,052 --> 00:01:06,011
looks like. And it's based on these
properties of the Quantum Fourier

10
00:01:06,011 --> 00:01:11,068
Transform that we've already studied. So,
what do we do? We start in the all, in the

11
00:01:11,068 --> 00:01:16,074
zero state and we apply the Quantum
Fourier Transform modem. So, remember,

12
00:01:16,074 --> 00:01:22,059
what, what the Quantum Fourier Transform
model will do to the, to the zero state.

13
00:01:22,084 --> 00:01:29,001
Zero state meaning, well, so, so let's
see, the QFTs of M, is what? One / square

14
00:01:29,001 --> 00:01:35,053
root M. And then, you have this matrix,
which is, which is ones along the first

15
00:01:35,053 --> 00:01:41,047
row, ones along the first column. Omega,
etc., Omega to n - one, and so on. But

16
00:01:41,047 --> 00:01:48,095
now, what's the zero state? It's, it's
this factor, right? It's, it has amplitude

17
00:01:48,095 --> 00:01:56,021
one for the, for when, when, when our,
when our quantum system is in the state

18
00:01:56,021 --> 00:02:03,087
zero and zero, otherwise. And so, so the
result of this is, is the is this state,

19
00:02:03,087 --> 00:02:13,017
right. So, it's, it's the first column,
which is, which is all ones, meaning we

20
00:02:13,017 --> 00:02:21,099
end up in a, out here in a superposition,
sum over all x with, with amplitude one /

21
00:02:22,031 --> 00:02:32,061
square root N, x = zero to n - one. Okay.
So, so now, when we apply our circuit for

22
00:02:32,061 --> 00:02:40,047
computing f to this superposition, of
course, what we get is sum of all x = zero

23
00:02:40,047 --> 00:02:51,005
to m - one where this register is in the
state x, and this answer register is in

24
00:02:51,005 --> 00:02:58,060
the state, f (x). So, these two get
entangled with each other now. But now, if

25
00:02:58,060 --> 00:03:04,080
we, if we, out here do a measurement, and
measure what f(x) is, we'll get some

26
00:03:04,080 --> 00:03:12,027
outcome. And, let's say, that t he outcome
is f(p) for sum value k. So now, we can

27
00:03:12,027 --> 00:03:19,063
ask, what's, what's the new state of this,
this, this register here? What are, what

28
00:03:19,063 --> 00:03:24,083
are, what's the state of these wires?
Well, the answer is it's going to be,

29
00:03:24,083 --> 00:03:30,087
remember what the rule of, rule of partial
measurement is? If you, if you measure

30
00:03:30,087 --> 00:03:36,037
these wires, and the outcome is something,
you, you, you sort of cross out all of

31
00:03:36,037 --> 00:03:42,063
those parts of the superposition that are
not consistent with this outcome. So, you

32
00:03:42,063 --> 00:03:48,043
cross out all those xs such that f(x) is
not equal to f(k). And then you

33
00:03:48,043 --> 00:03:54,096
re-normalize to get a unit vector,
meaning, what we will end up with is a

34
00:03:54,096 --> 00:04:01,061
superposition over all those xs such that
f(x) = f(k). But what are all those xs?

35
00:04:01,061 --> 00:04:07,058
Well, they are f of, they are k, k + r, k
+ 2r, and so on, because this is a

36
00:04:07,058 --> 00:04:26,033
periodic function with period r. So, at
this point, this superposition is going to

37
00:04:26,033 --> 00:04:49,077
be equal to k +, k + r + k + 2r + so on +
k + n - r. How many terms are there? Well,

38
00:04:49,077 --> 00:04:56,008
there are m / r of them, so you must
normalize by square root r / n, alright?

39
00:04:56,008 --> 00:05:03,092
Okay, so. This slide's getting a little
bit grungy. So, let's, let's remember

40
00:05:03,092 --> 00:05:10,012
this. Let's carry this over, and let's,
let's try to clean everything up. So, at

41
00:05:10,012 --> 00:05:17,097
this point, we're in the situation where
we made a measurement there, and, and this

42
00:05:17,097 --> 00:05:25,070
superposition is, happens to be, right?
So, this is k + k + r, k + 2r, and k + 3r,

43
00:05:25,070 --> 00:05:32,068
and so on. Okay. So now, what happens when
we perform a Fourier Transform on this?

44
00:05:32,068 --> 00:05:39,093
What happens when we do a Quantum Fourier
Transform sub m of this? Well, remember,

45
00:05:39,093 --> 00:05:46,008
what, what are we planning to do? Well, we
are planning to do a Quantum Fourier

46
00:05:46,008 --> 00:05:52,025
Transform, and then do a measurement.
Okay, so, the two rules that we had about

47
00:05:52,025 --> 00:05:59,057
Quantum Fourier Transforms followed by,
you know, so the first was, if you were to

48
00:05:59,057 --> 00:06:06,023
cyclically shift the superposition, then
the only thing it'll, that, that, that

49
00:06:06,023 --> 00:06:11,068
will change in a Quantum Fourier Transform
is the phases. So, if you are planning to

50
00:06:11,068 --> 00:06:17,030
do a measurement right afterwards anyway,
those phases are not going to make any

51
00:06:17,030 --> 00:06:22,045
difference to us. So, we may a s well get
rid of this c yclic shift, because it's

52
00:06:22,045 --> 00:06:27,063
not going to make any difference to the
Fourier sampling that we are going to do.

53
00:06:27,063 --> 00:06:33,011
Okay, but now, what are we left with? We
are left with this periodic superposition,

54
00:06:33,011 --> 00:06:38,049
which is what we were looking at before.
This is, this, this is our periodic

55
00:06:38,049 --> 00:06:47,065
superposition with period r. So, what's
the Quantum Fourier Transform? It's just a

56
00:06:47,065 --> 00:06:56,052
superposition l m / r, right? Where l
ranges from zero to r -one, we have

57
00:06:56,052 --> 00:07:04,043
normalization one / square root r. Okay.
So, so, what do we end up getting? We end

58
00:07:04,043 --> 00:07:11,085
up, when we do a measurement we see a
random multiple of m / r. Okay. So, so,

59
00:07:11,085 --> 00:07:19,063
here's the upshot. What we did was we've
managed to come up with a, with a quantum

60
00:07:19,063 --> 00:07:26,084
circuit which is efficient because our
Quantum Fourier Transformer is efficient,

61
00:07:26,084 --> 00:07:34,002
our circuit for computing f is efficient.
And every time we run the circuit, we make

62
00:07:34,002 --> 00:07:44,052
a measurement here, and we see a random
multiple of m / r. So, we see some, some s

63
00:07:44,052 --> 00:08:02,003
m / r, where s is a random number is s is
a random number between zero and r - one,

64
00:08:02,004 --> 00:08:10,003
okay? So now, what are we going to do? How
do we figure out m / r from, from this

65
00:08:10,003 --> 00:08:21,041
random multiple of m / r. Well, we just
repeat this a few times. So, you repeat

66
00:08:21,041 --> 00:08:31,002
and you compute the, the greatest common
divisor of all the samples that you get.

67
00:08:31,002 --> 00:08:40,003
And the claim is that pretty soon, you
will, you know, the GCD of, of these

68
00:08:40,003 --> 00:08:48,064
numbers will be equal to m / r. Because,
you know, are, these are random numbers

69
00:08:48,064 --> 00:08:54,074
between zero and r - one. If you pick
random numbers several times and you take

70
00:08:54,074 --> 00:09:01,003
the GCD, you are, you are very likely to
get one. Because you know, this is an easy

71
00:09:01,003 --> 00:09:06,040
argument, because what's the chances that,
that, that all these s are divisible by

72
00:09:06,040 --> 00:09:11,086
two? Well, it's, you know, it's the, the,
the, the chance that, that the first of

73
00:09:11,086 --> 00:09:17,023
these S's is even is, is a, a half. The
chance that the second time it's even is a

74
00:09:17,023 --> 00:09:23,020
half, and so on. So, if you, if you repeat
a few times the chance that you'll get two

75
00:09:23,020 --> 00:09:27,037
as a factor of the GCD is going to be
very, very small, and now. You can repeat

76
00:09:27,037 --> 00:09:31,094
it with every possible factor and, y ou
know, the chance of havin g that common

77
00:09:31,094 --> 00:09:36,060
factor falls off exponentially, in the
number of factor in the number of

78
00:09:36,078 --> 00:09:42,079
repetitions. And so, you know, this shows
you that the G, the, the, that if you take

79
00:09:42,079 --> 00:09:49,088
these samples. And you take the GCD, it's
very likely that, that the GCD is going to

80
00:09:49,088 --> 00:09:56,037
be m / r. But once you know m / r, of
course, you can computer r because you

81
00:09:56,037 --> 00:10:03,050
know m. Okay, so that's period finding.
And that's basic primitive that you are

82
00:10:03,050 --> 00:10:07,005
going to use next time to, to factor.
Okay.