1
00:00:00,000 --> 00:00:06,097
So, just to remember what we, what we
already said is, in order to carry out

2
00:00:06,097 --> 00:00:14,014
right, carry this out efficiently,
quantumly what we do is we put even inputs

3
00:00:14,014 --> 00:00:21,058
sorry, plus three we put even inputs here,
the even numbers its here, odd numbers

4
00:00:21,058 --> 00:00:29,032
inputs sorry odd number inputs here we do
the ffts and [inaudible] on top and the

5
00:00:29,032 --> 00:00:34,087
bottom, what we do is.
The Jth of output on the top is, is this

6
00:00:34,087 --> 00:00:41,049
Jth output from the, you know you take the
sum of the Jth output from the, from the,

7
00:00:41,049 --> 00:00:45,085
from the top, FFT.
And you take the Jth output from the

8
00:00:45,085 --> 00:00:50,095
bottom, NFT multiplied by omega to the J,
and you add the two up.

9
00:00:50,095 --> 00:00:57,028
For the bottom, what you do is you, take
the, take the difference, but now.

10
00:00:57,028 --> 00:01:03,098
Again you take the J type from the top,
the J from the bottom, but multiply by

11
00:01:03,098 --> 00:01:10,015
omega to the J, and then you subtract.
Okay so we want to carry this out

12
00:01:10,015 --> 00:01:16,024
quantumly, so how do we do this?
Okay, so first remember what happens in

13
00:01:16,024 --> 00:01:23,002
the, in the quantum case well we only
instead of two to the little n inputs we

14
00:01:23,002 --> 00:01:30,023
now only have little n inputs and we want
to carry out a quantum Fourier transform.

15
00:01:30,023 --> 00:01:33,066
So.
So the first thing to observe is that, in

16
00:01:33,066 --> 00:01:40,023
separating out these intputs into the even
numbered ones and the aught numbered ones,

17
00:01:40,023 --> 00:01:44,018
all we need to do.
Is.

18
00:01:44,073 --> 00:01:48,062
Separate them out according to the least
significant bits.

19
00:01:48,062 --> 00:01:51,079
Right?
So we want to take everything with least

20
00:01:51,079 --> 00:01:56,003
significant bit= to zero.
And we want to apply a quantum Fourier

21
00:01:56,003 --> 00:02:00,088
transform to, to those inputs.
And take everything with least significant

22
00:02:00,088 --> 00:02:05,013
bit, bit = to one, and apply a quantum
Fourier transform to those.

23
00:02:05,013 --> 00:02:09,084
But remember, all we have to do,
quantumly, in order to make this happen

24
00:02:09,084 --> 00:02:12,094
is.
We just take the least significant bit and

25
00:02:12,094 --> 00:02:17,059
lead it out of this circle.
And we apply quantum Fourier transform to

26
00:02:17,059 --> 00:02:19,094
these m-1 cubits.
And automatically.

27
00:02:19,094 --> 00:02:25,047
This [inaudible] transform get, gets
applied, seperately in super position.

28
00:02:25,047 --> 00:02:31,060
Do everything where the least significant
bit is zero, because these cannot

29
00:02:31,060 --> 00:02:36,050
interfere with those where the least
significant bit is one.

30
00:02:36,050 --> 00:02:41,047
To make sure you understand this fact.
So what we're doing is.

31
00:02:41,047 --> 00:02:49,007
Just by putting the least significant bit
aside and applying upon the Fourier

32
00:02:49,007 --> 00:02:55,088
transform to these m - one bits.
That applies the qfd sub two to the m -

33
00:02:55,088 --> 00:03:01,024
one, which is qfd sub M/2 to these little
m - one q bits.

34
00:03:01,024 --> 00:03:07,071
In superposition it applies it.
In parallel to the, to, to, to the zero,

35
00:03:07,071 --> 00:03:13,029
to the even numbered ones and separately
to the odd numbered ones.

36
00:03:13,029 --> 00:03:18,045
Okay, this is fantastic.
Okay, this is, you know, because, because,

37
00:03:18,045 --> 00:03:25,005
this is the quantum magic coming in.
Now what's the, what's the next thing that

38
00:03:25,005 --> 00:03:30,029
we want to do?
The next thing we want to do is, remember

39
00:03:30,029 --> 00:03:37,057
we want to, we want to the, take the jet
output from here and the jet output from

40
00:03:37,057 --> 00:03:41,020
there, add it.
To get the.

41
00:03:41,020 --> 00:03:42,081
To, to get.
This answer.

42
00:03:42,081 --> 00:03:47,041
And subtract to get that answer.
So how do we do this quantumly?

43
00:03:48,000 --> 00:03:51,007
It turns out, in the simplest possible
way.

44
00:03:51,007 --> 00:03:55,053
All we do is take the three significant
bit that we left out.

45
00:03:55,053 --> 00:04:00,080
And we apply a harder map transform to it.
And that does the right thing.

46
00:04:00,080 --> 00:04:04,074
It takes.
Remember what it does.

47
00:04:04,074 --> 00:04:13,021
It, it takes, the zero output.
Yeah so, so the aptitude of zero out here

48
00:04:13,021 --> 00:04:19,050
for, for this cubit is, is one over square
root of zero plus one and for one it's one

49
00:04:19,050 --> 00:04:25,012
over square root of zero minus one.
And so what it ends up doing is exactly

50
00:04:25,012 --> 00:04:28,093
adding and subtracting the appropriate
[inaudible].

51
00:04:32,027 --> 00:04:40,026
And for the final thing what we want to do
is, we want to apply the appropriate

52
00:04:40,026 --> 00:04:43,010
phrases right.
So, so if this.

53
00:04:43,036 --> 00:04:50,075
If, if, if these wires.
If what this number is, is, is J, then we

54
00:04:50,075 --> 00:04:56,091
want to.
And if this, if this cubit happens to be a

55
00:04:56,091 --> 00:05:04,088
one, then we want to apply a phase of
omega to the J All right.

56
00:05:04,088 --> 00:05:10,042
Okay.
So how do you apply, you know, how do you

57
00:05:10,042 --> 00:05:15,084
do that?
Well, what you do is, you, you, you now

58
00:05:15,084 --> 00:05:23,096
write J as the bits of J.
So remember there are little M minus one

59
00:05:23,096 --> 00:05:30,061
bits, so let's call them J sub, J sub, M
minus one.

60
00:05:30,061 --> 00:05:34,080
J sub M minus two.
Up to J sub one.

61
00:05:39,048 --> 00:05:46,077
Okay, so maybe I should have started at,
at zero to say that that's the least

62
00:05:46,077 --> 00:05:50,073
significant bit.
So n minus two minus three.

63
00:05:50,073 --> 00:05:58,012
Okay, so these, these are the bits of, of
g so these are, each of these are zero or

64
00:05:58,012 --> 00:05:58,095
one.
Okay?

65
00:05:58,095 --> 00:06:05,023
And okay, so, so what is this?
Well this is exactly omega to the power.

66
00:06:05,023 --> 00:06:11,059
This is, this is the m minus 2f bit, so
it's two to the, it, it's place value is

67
00:06:11,059 --> 00:06:17,086
two to the m minus two, so what you want
is, you'd want to apply omega to the

68
00:06:17,086 --> 00:06:25,020
[inaudible] of m minus two.
Times two to the M-2 right.

69
00:06:25,020 --> 00:06:34,009
If, if, if this is one then you want to,
then you want to it to be omega two to the

70
00:06:34,009 --> 00:06:39,013
omega m-2 otherwise you want it to be
omega-0.

71
00:06:39,013 --> 00:06:47,037
Times, omega to the gsl m-1 and so m-3 to
do m-3 so on to omega [inaudible].

72
00:06:47,037 --> 00:06:51,067
J not times two to the zero.
Okay.

73
00:06:51,067 --> 00:07:00,000
So, so, but, but you want to.
But, but now, you see what this says is

74
00:07:00,000 --> 00:07:05,087
you want to apply the conditional phase
gate.

75
00:07:05,087 --> 00:07:12,051
Where if this is a one, if this happens to
be a one.

76
00:07:15,016 --> 00:07:24,054
And if this happens to be a one.
Then you apply a phase of omega.

77
00:07:24,095 --> 00:07:30,068
Okay, so this should be.
Think maybe I'll write it out here.

78
00:07:30,068 --> 00:07:35,021
Should be omega to the two to the M minus
two.

79
00:07:35,021 --> 00:07:43,001
And so on, all the way up to two here.
And the conditional case is just omega to

80
00:07:43,001 --> 00:07:49,002
the two to the zero.
So, omega to the two to the zero is omega

81
00:07:49,002 --> 00:07:52,087
squared.
No, sorry, omega to the one.

82
00:07:52,087 --> 00:07:56,076
Sorry.
So omega to the two to the zero is just

83
00:07:56,076 --> 00:08:01,056
omega to the one.
So you just apply conditional omega grate

84
00:08:01,056 --> 00:08:05,054
and so on.
So you apply, you know, to each of these,

85
00:08:05,054 --> 00:08:11,097
you apply the appropriate conditional
phase, two to the, omega to the two to the

86
00:08:11,097 --> 00:08:17,017
M minus two, two to the M minus three, and
so on, up to just omega.

87
00:08:17,017 --> 00:08:23,027
And then do you, you do a Hadamard.
So what does this tell us about the size

88
00:08:23,027 --> 00:08:24,074
of the circuit?
So.

89
00:08:24,074 --> 00:08:30,088
So what we have is the size of the circuit
you started of with, we have, we had n

90
00:08:30,088 --> 00:08:37,065
wires coming in all together.
Is the size of the circuit with M minus

91
00:08:37,065 --> 00:08:43,064
one Y is coming in.
Class, how many gates are these.

92
00:08:43,064 --> 00:08:48,028
Well, this is, this is bigger of N.
Right.

93
00:08:48,028 --> 00:08:53,041
And if you.
What's the, what does this [inaudible]

94
00:08:53,041 --> 00:08:58,034
solve to?
It solves to S of N equal to big of M

95
00:08:58,034 --> 00:09:02,080
squared.
Right, so, remember what we are carrying

96
00:09:02,080 --> 00:09:07,018
out.
We are carrying out the key [inaudible] of

97
00:09:07,018 --> 00:09:14,081
capital M where capital M was too to the
little m and so the size of a circuit is

98
00:09:14,081 --> 00:09:20,068
little low of M2 which is little.
Little m2, which is low square

99
00:09:20,068 --> 00:09:25,053
[inaudible].
I'd say it's exponentially better than our

100
00:09:25,053 --> 00:09:26,089
classical circuit.