1
00:00:00,000 --> 00:00:07,009
Okay. So now, let's try to understand
Simon's algorithm, in a very different

2
00:00:07,009 --> 00:00:14,008
way, in a much more physical way. So, in
terms of something we talked about in the

3
00:00:14,008 --> 00:00:20,043
very first lecture, which was the
double-slit experiment. So remember, the

4
00:00:20,043 --> 00:00:27,058
double slit experiment, we had we had a
source of light a screen with a, with a

5
00:00:27,058 --> 00:00:34,002
slit in it. Another screen with two slits
a backdrop where we had a detector and

6
00:00:34,025 --> 00:00:40,051
when we had both slits open, even though
the light was turned down so that it was

7
00:00:40,051 --> 00:00:46,001
being emitted as single photons. We get,
got this interference pattern which,

8
00:00:46,001 --> 00:00:52,001
which, you know, the intensity of light
that was, that was hitting the probability

9
00:00:52,001 --> 00:00:58,001
that the photon ended up at point x was
given by this interference pattern. Okay,

10
00:00:58,001 --> 00:01:07,001
so, let me argue that you can, you can
view Simon's algorithm as a sophisticated

11
00:01:07,001 --> 00:01:14,003
kind of double-slit experiment. As a, as a
kind of interference experiment. So, okay,

12
00:01:14,003 --> 00:01:21,089
let, let's say, let's say that we have n
qubits. We do Hadamard transform, and then

13
00:01:21,089 --> 00:01:29,043
we do another Hadamard transform. So, and
let's say that instead of starting off in

14
00:01:29,043 --> 00:01:36,077
this, in this state all of them in this
state zero, let's say that we start in the

15
00:01:36,077 --> 00:01:43,052
state, in some particular state like, you
know, U1, U2 through Un. So, we have an n

16
00:01:43,052 --> 00:01:50,033
bit string, U1, U2 through Un . U = U1
through Un. So now, what's the, what's the

17
00:01:50,033 --> 00:01:57,049
superposition in the middle here? What,
what does this middle superposition look

18
00:01:57,049 --> 00:02:04,053
like? Well, remember, we, in the middle,
we are in a superposition over all the n

19
00:02:04,053 --> 00:02:15,052
bit strings. So, we are in a superposition
over all n bit strings, x. Where each and

20
00:02:15,052 --> 00:02:26,024
between x has amplitude plus or -one /
two^n/2 And whether, whether, whether it's

21
00:02:26,024 --> 00:02:34,049
in the plus or whether the phase is plus
or minus, it depends upon u.x, right? U1,

22
00:02:34,049 --> 00:02:46,075
X1, + U2, X2, plus so on. Okay. Now, what
happens when you do another Hadamard

23
00:02:46,075 --> 00:02:54,098
Transform here? Well, what happens is that
you, you knew Hadamard transform

24
00:02:54,098 --> 00:03:05,047
transforms this into summation over y beta
y , y . And what's beta sub y?. Okay, so

25
00:03:05,047 --> 00:03:17,042
let's compute beta sub y. Beta sub y i s
going to be sum over all x of the

26
00:03:17,042 --> 00:03:29,058
amplitude of X, which is -one^u.x /
two^n/2 times the amplitude of going from

27
00:03:29,058 --> 00:03:38,063
x to y when you do a Hadamard transform.
Okay. What's the, what's the amplitude

28
00:03:38,063 --> 00:03:49,070
with which you go from x to y? It's
-one^x.y / two^n/2. So now, there are two

29
00:03:49,070 --> 00:04:04,012
cases. Case one, y is equal to U. If y is
equal to U, then, this is equal to that,

30
00:04:04,012 --> 00:04:11,085
and so then, so then beta y is just a
summation of x of these minus ones, these,

31
00:04:11,085 --> 00:04:21,064
these two are exactly equal to the square
and, and you get one / two^n. They are

32
00:04:21,064 --> 00:04:29,060
exactly two^n x, so you get one. So, it's
completely constructive interference. All

33
00:04:29,060 --> 00:04:39,055
the two^n contributions line up and they
all give value +one. Case two, is y is not

34
00:04:39,055 --> 00:04:49,039
equal to U. In the case, y is not equal to
u. You should convince yourself that, for

35
00:04:49,039 --> 00:04:56,050
exactly half the values of x, these two
signs are equal. And for exactly half the

36
00:04:56,050 --> 00:05:03,094
values of x, these two signs are unequal.
So, you get +one-half the time -one-half

37
00:05:03,094 --> 00:05:12,064
the time. So, beta sub y ends up these
two, you know, half these values cancel

38
00:05:12,064 --> 00:05:19,007
with the other half and you, you get beta
sub y = zero. So, you get completely

39
00:05:19,007 --> 00:05:26,066
destructive interference. Right? So, this
is as though you had two^n virtual slits.

40
00:05:26,066 --> 00:05:34,097
And, you know, as your light goes through
this two^n virtual slits, then this, this

41
00:05:34,097 --> 00:05:42,044
Hadamard transform makes them refocus and,
and what happens? Well, you get completely

42
00:05:42,044 --> 00:05:50,002
constructive interference at y = U, and
destructive interference everywhere else.

43
00:05:50,002 --> 00:05:56,098
Of course, you can see this by just
observing that the Hadamard transform has

44
00:05:56,098 --> 00:06:02,052
its own inverse. And so, if you start from
U, you apply the Hadamard twice, you get

45
00:06:02,052 --> 00:06:08,003
back U. Okay. So, what does this have to
do with Simon's algorithm? Well, what we'd

46
00:06:08,003 --> 00:06:14,020
like to do is we'd like to somehow change
the slit pattern in the middle. So, that

47
00:06:14,020 --> 00:06:19,062
the pattern of slits in the middle is
determined by the input to the problem

48
00:06:19,062 --> 00:06:25,007
that we are trying to solve. And then, we
are going to see where the constructive

49
00:06:25,007 --> 00:06:31,087
interference happens. And that's going to
give us the answer to the problem. Okay.

50
00:06:31,087 --> 00:06:39,079
So, remember what, what, what Simon's
problem is, you're given a, a two to one f

51
00:06:39,079 --> 00:06:46,016
unction, f, wher e there's a secret
string, s, such that f ( x ),, = f ( x ),,

52
00:06:46,016 --> 00:06:54,006
+ s. So now, what do we do? Well, remember
the, the, Simon's algorithm looks like

53
00:06:54,006 --> 00:07:01,020
this. You have these two Hadamard
transforms which is, very much like what

54
00:07:01,020 --> 00:07:07,081
we were, what we were doing in the, in our
previous slide. But then in the middle, we

55
00:07:07,081 --> 00:07:15,052
put in this quantum circuit for computing
f. And what does this quantum circuit for

56
00:07:15,052 --> 00:07:22,098
computing f do? Remember, okay. So, at
this point, we had, we had a super

57
00:07:22,098 --> 00:07:33,068
position over all x, and with strings of
X. Alright? At this point, what we do is,

58
00:07:33,068 --> 00:07:43,039
imagine just, just moving this measurement
on these qubits back here. So, what do we

59
00:07:43,039 --> 00:07:51,076
end up with? Well, we measure these
qubits, and now, the first n cubits are

60
00:07:51,076 --> 00:08:02,062
in, in some superposition one / square
root 2r + one / square root 2r + s. Right?

61
00:08:02,062 --> 00:08:17,049
So, it's as though, out of the two^n
virtual slits, we've picked out exactly

62
00:08:17,049 --> 00:08:24,040
two of them. Which two? Well, each of them
by themselves looks random, but they are

63
00:08:24,040 --> 00:08:30,028
related to each other in this very special
way that they differ by exactly s. So,

64
00:08:30,028 --> 00:08:36,043
what we've done is we've picked out two
random slits, two slits which, which are

65
00:08:36,043 --> 00:08:42,030
randomly positioned among, among these
exponentially many. But they differ by

66
00:08:42,030 --> 00:08:49,054
exactly s. And now, when we, now when we
look at the interference pattern, the

67
00:08:49,054 --> 00:08:56,000
interference pattern is interesting,
there's constructive interference on

68
00:08:56,000 --> 00:09:01,063
exactly half the two, half of the two^n
and the strings, and completely

69
00:09:01,063 --> 00:09:07,050
destructive interference on the other
half. But if you, and so when we, when we

70
00:09:07,050 --> 00:09:13,035
do our measurement we, we'd see a random
one of these two^n and minus one strings

71
00:09:13,035 --> 00:09:19,040
on which there's constructive
interference. But the interesting thing

72
00:09:19,040 --> 00:09:27,015
that we said is that, if we sample any one
of them, so if y is a string that is

73
00:09:27,015 --> 00:09:35,035
constructing interference, then it
satisfies this condition that y.s is zero.

74
00:09:35,035 --> 00:09:44,081
And this gives us a linear equation that s
must satisfy. Okay. So, you could see

75
00:09:44,081 --> 00:09:55,012
Simon's algorithm, as this very
interesting double-slit experiment. Okay,

76
00:09:55,012 --> 00:10:04,063
the slits are virtual and they reflect the
input to the problem that we are trying t

77
00:10:04,063 --> 00:10:09,082
o s olve. And then, when we look at the
output, we look at, well, you know, when,

78
00:10:09,082 --> 00:10:15,044
when we do a measurement, we pick out one
of the, one of the strings at which

79
00:10:15,044 --> 00:10:21,055
there's constructive interference, and
then random such string. But that random

80
00:10:21,055 --> 00:10:28,010
string yields a linear equation which,
which gives us a constraint on the secret

81
00:10:28,010 --> 00:10:36,074
string s that we are trying to find. Okay.
And these linear equations allow us to

82
00:10:36,074 --> 00:10:39,004
reconstruct this.