1
00:00:00,000 --> 00:00:06,009
Okay. So, so now why do we want to remove
this junk? Well the reason it's important

2
00:00:06,009 --> 00:00:19,002
to remove this junk is because it prevents
quantum interference. So let's see an

3
00:00:19,002 --> 00:00:31,095
example of this. So suppose that we had a
quantum, we had a circuit that on input x,

4
00:00:31,095 --> 00:00:42,057
just outputs x. So x is a bit and the
circuit just does nothing to it, it

5
00:00:42,057 --> 00:00:50,025
outputs x as is. So of course, if we, if
this is was a quantum circuit and we input

6
00:00:50,025 --> 00:00:58,092
summation of x, x then the output is also
summation of x, x because it does nothing

7
00:00:58,092 --> 00:01:07,068
to the, to the output. Okay, so, so now,
suppose that we have this quantum circuit,

8
00:01:07,068 --> 00:01:16,009
and then further we feed the output into a
Hadamard gate, okay? And let's say that we

9
00:01:16,009 --> 00:01:23,010
set up the input to this circuit to be in
the plus state. So, so, lets say that

10
00:01:23,010 --> 00:01:29,045
input was one over square root two zero
plus one over square root two one. And

11
00:01:29,045 --> 00:01:36,073
now, so the output of the, the, the first
circuit is also in the plus state and when

12
00:01:36,073 --> 00:01:45,002
this is fed into the Hadamard, out pops
the zero state. So if we measure, if we

13
00:01:45,002 --> 00:01:52,058
were to measure this output, we'll see
zero with probability one. Okay. So, this

14
00:01:52,058 --> 00:02:00,069
is what we wanted to happen. Okay. But now
instead, let's say we started with this

15
00:02:00,069 --> 00:02:09,029
classical circuit which on input x,
outputs x. So this was a classical

16
00:02:09,029 --> 00:02:18,096
circuit. We convert this into, into a
reversible circuit. So R sub c. And let's

17
00:02:18,096 --> 00:02:25,011
say that the process of converting it into
a reversible circuit, the following

18
00:02:25,011 --> 00:02:31,012
happens to it. So it takes as input x as
well as some clean bits zero and it

19
00:02:31,012 --> 00:02:37,099
outputs the correct answer, but it also
creates some junk. And let's say the junk

20
00:02:37,099 --> 00:02:44,040
it creates is a function of x and in fact,
it's x itself. So it just makes another

21
00:02:44,040 --> 00:02:52,010
copy of this input bit. Okay, now since
this is a reversible circuit, all the

22
00:02:52,010 --> 00:03:01,039
gates are reversible, we go ahead and make
this out of quantum gates. Maybe our

23
00:03:01,039 --> 00:03:08,029
universal family, maybe, maybe using just
the c swap as a, including c swap and now

24
00:03:08,029 --> 00:03:18,026
you know as the family. So now it takes as
input two, two cubits, outputs two cubits

25
00:03:18,026 --> 00:03:27,072
where now what we'd like is to, is to
understand what happens when we feed the

26
00:03:27,072 --> 00:03:34,062
output into a Hadamard gate, right? So we,
we take as input the plus state one over

27
00:03:34,062 --> 00:03:43,043
square root two zero plus one over square
root two one and this, and this clean bit.

28
00:03:43,043 --> 00:03:51,038
And now the output of this, of this
circuit is one over square root two zero,

29
00:03:51,038 --> 00:03:58,023
zero plus one over square root two zero
one. And now what happens when we actually

30
00:03:58,023 --> 00:04:06,070
do a Hadamard of the first qubit? Well,
this part goes to one over two zero, zero

31
00:04:06,070 --> 00:04:17,067
plus one over two one zero, and this gets
transformed to one over two zero one plus

32
00:04:17,067 --> 00:04:27,097
one over two one, one. So we get all four
strings. And now what happens is when we,

33
00:04:27,097 --> 00:04:36,047
when we measure the first, first qubit, we
see zero and one with equal probability

34
00:04:36,047 --> 00:04:42,065
which is different from what we had here.
So let's see. What, what happened here?

35
00:04:42,065 --> 00:04:49,005
When you see, what happened here is that,
when we did a Hadamard transform on this,

36
00:04:49,005 --> 00:04:56,072
on this on this first qubit so, so, lets,
lets say we, we do a Hadamard transform

37
00:04:56,072 --> 00:05:03,049
here. Okay. So, so lets see first what
happened when we did the Hadamard here

38
00:05:03,049 --> 00:05:11,014
without the junk qubits. Well, so one over
square root two is zero after the Hadamard

39
00:05:11,014 --> 00:05:19,055
went to one over two zero plus one over
two one whereas one over square root two

40
00:05:19,055 --> 00:05:28,051
one after the Hadamard went to one over
two zero minus one over two one. And so

41
00:05:28,051 --> 00:05:34,070
when you start with the superposition of
these two, you have to add these two and

42
00:05:34,070 --> 00:05:41,002
this part cancels, so that's destructive
interference. This part reinforce each

43
00:05:41,002 --> 00:05:46,006
other in constructive interference. And
you get as outcome, half plus a half,

44
00:05:46,006 --> 00:05:57,052
which is one times zero. What happens
here? Well here, this piece gets mapped to

45
00:05:57,052 --> 00:06:08,063
that and this piece gets mapped to that.
But, but see before, in this case, this

46
00:06:08,063 --> 00:06:17,028
minus should have cancel that one. And so
you should have been left only with the

47
00:06:17,028 --> 00:06:22,000
first qubit equal to zero. But now, the
second qubit doesn't allow these two

48
00:06:22,000 --> 00:06:26,006
pieces to interfere with each other
because these two are different, different

49
00:06:26,006 --> 00:06:31,003
states. These are orthogonal states. They
can't interfere with each other. And so

50
00:06:31,003 --> 00:06:36,003
the presence of this junk here, junk of x,
actually prevents an interference pattern

51
00:06:36,003 --> 00:06:43,000
from happen ing and so we get the wrong
results in our quantum computation. Okay.

52
00:06:43,000 --> 00:06:49,009
So, you can still ask, well, can't we just
throw away the junk qubits? The answer is

53
00:06:49,009 --> 00:06:56,006
no. You can't throw away the junk qubits.
You see, because, remember what, you know,

54
00:06:56,006 --> 00:07:04,086
we had, we had we had a state when we fed
in one over square root two zero plus one

55
00:07:04,086 --> 00:07:11,074
over square root two one, and a zero here,
what we got out is one over square root

56
00:07:11,074 --> 00:07:16,055
two zero, zero plus one over square root
two one, one which you might recognize as

57
00:07:16,055 --> 00:07:25,027
the Bell State. So now in the Bell State
if you throw away one of the qubits,

58
00:07:25,027 --> 00:07:30,087
right? Throw it away you know, send it to,
send it, send it to the other part of the,

59
00:07:30,087 --> 00:07:36,008
of the city, send, send it across the
country, doesn't matter, they're still

60
00:07:36,008 --> 00:07:41,008
entangled, right? You, you can't just
throw it away. You can't change the state

61
00:07:41,008 --> 00:07:46,008
of these two qubits to intense the product
state just by throwing away the qubit. In

62
00:07:46,008 --> 00:07:52,008
fact, when you throw away the qubit, it's
as though you measured it. Okay? So this

63
00:07:52,008 --> 00:07:58,005
really doesn't help at all. What we have
to do is somehow make sure, change the

64
00:07:58,005 --> 00:08:04,000
circuit so that the junk qubits are not
created. It turns out there's a very

65
00:08:04,000 --> 00:08:09,006
elegant way of doing this. So what do you
do? Well, let's remember, this was our

66
00:08:09,006 --> 00:08:15,003
reversible circuit. It takes as input x, a
bunch of zeroes it outputs C of x, the

67
00:08:15,003 --> 00:08:21,020
correct answer. But then it also outputs
this junk which is, which may be a

68
00:08:21,020 --> 00:08:27,056
function of x. So what are we going to do?
Well, remember we have, it's a reversible

69
00:08:27,056 --> 00:08:34,002
circuit, so we could, we could apply the
reverse of the circuit, okay? So, so we

70
00:08:34,002 --> 00:08:42,061
could, we could, we have the inverse of,
of, of the circuit and if we apply it, it

71
00:08:42,061 --> 00:08:52,033
gets rid of the junk. And restore all
these, all these bits back to zero. But of

72
00:08:52,033 --> 00:09:00,084
course, there's a problem because it also
takes the answer C of x and it restores it

73
00:09:00,084 --> 00:09:07,097
to x. So, that's not very good. It's, you
know, we've thrown out the baby with the

74
00:09:07,097 --> 00:09:15,023
bathwater. So, how can we get rid of the
junk, but also keep the answer bits

75
00:09:15,023 --> 00:09:25,008
around? Well the answer is simple, all we
do is copy it. So, what we do is, is

76
00:09:25,008 --> 00:09:33,061
before we, we ap ply the inverse circuit,
we just, we just start with some, some

77
00:09:33,061 --> 00:09:42,058
fresh bits where we, where we set y to be
all zeroes and then we do a CNOT from each

78
00:09:42,058 --> 00:09:50,008
of these answer bits into these, into
these y bits. Okay. So we, if, if y is

79
00:09:50,008 --> 00:09:56,009
zero then, then we get a copy of the
answer bits, the output of the circuit.

80
00:09:56,009 --> 00:10:03,007
And now we are free too run the inverse of
this, of this circuit. And so what it does

81
00:10:03,007 --> 00:10:10,002
is it erases the junk, erases the answer,
restores the input. And so what we have

82
00:10:10,002 --> 00:10:16,007
finally is what we were looking for. We
have, we have a circuit where we gave as

83
00:10:16,007 --> 00:10:22,059
input x, bunch of zeroes, maybe y's also
zeroes. Now what do we get as output? We

84
00:10:22,059 --> 00:10:29,015
get a bunch of zeroes, we get, we get x.
So, so the input is copied over, this is

85
00:10:29,015 --> 00:10:34,061
important for their visibility, and then
we get the out, actual output we are

86
00:10:34,061 --> 00:10:41,030
looking for, okay? And now the point is
that this is, there's, there's no junk,

87
00:10:41,030 --> 00:10:49,038
there, there, there, there's no junk
associated with the, with the, with the

88
00:10:49,038 --> 00:10:58,058
input. And so, this circuit, if you now
write as a quantum circuit, it actually,

89
00:10:58,058 --> 00:11:04,035
it actually does what we want. And it
doesn't prevent interference. Okay. So, so

90
00:11:04,035 --> 00:11:09,081
what's the upshot of what we, what, what
I, what I've been saying so far? The

91
00:11:09,081 --> 00:11:16,063
upshot is, if you are given any classical
circuit, if you give me any classical

92
00:11:16,063 --> 00:11:25,088
circuit C which takes as input x and
outputs C of x. What I can do is,

93
00:11:25,088 --> 00:11:37,028
transform this into quantum circuit. Let's
call it use of C which states as input x

94
00:11:37,028 --> 00:11:53,022
and a whole bunch of zeroes. And what it
does is it outputs x, C of x, and zeroes.

95
00:11:53,022 --> 00:12:03,033
Okay? Now, because this is a quantum
circuit, you could also give it as input,

96
00:12:03,033 --> 00:12:12,053
a superposition sum over x alpha x, x. And
in the second register we have a bunch of

97
00:12:12,053 --> 00:12:19,034
zeroes. Now what's the output when you
apply this circuit to it? You get

98
00:12:19,034 --> 00:12:26,058
superposition over x, alpha x, x in this
first register, C of x in the second

99
00:12:26,058 --> 00:12:33,082
register, and a bunch of zeroes in the
third register. Right? You remember the

100
00:12:33,082 --> 00:12:42,007
notation that we have, right? The, the
notation was if you write down x, y this

101
00:12:42,007 --> 00:12:51,011
is the same thing as writing x tensor y,
and we even can write it as x, y its all

102
00:12:51,011 --> 00:12:57,036
the same. Its just notation for saying
yeah, this many qubits, the, these are in

103
00:12:57,036 --> 00:13:03,083
the state x, these are in the state y, its
a tensor product, okay? Okay. So, this our

104
00:13:03,083 --> 00:13:10,078
basic theorem, it says given any classical
circuit you can convert it into a quantum

105
00:13:10,078 --> 00:13:16,060
circuit, okay? It turns out that, okay. So
historically, the initial interest in

106
00:13:16,060 --> 00:13:21,086
quantum computations started not with
trying to show that quantum computers

107
00:13:21,086 --> 00:13:27,064
could be much more powerful than classical
computers. It actually started with, with,

108
00:13:27,064 --> 00:13:32,043
people who wondered, could it be that
quantum mechanics imposes further

109
00:13:32,043 --> 00:13:37,097
constraints on what can and cannot be
computed? So could it be that this fact

110
00:13:37,097 --> 00:13:43,064
that, quantum mechanics is unitary and so
reversible? Does this mean that not

111
00:13:43,064 --> 00:13:48,085
everything that you can compute
classically could be is allowed by quantum

112
00:13:48,085 --> 00:13:54,005
mechanics? So maybe there are some
constraints that we weren't aware of so

113
00:13:54,005 --> 00:13:59,056
far. And of course, this shows that there
are no such constraints and, and it shows

114
00:13:59,056 --> 00:14:04,093
that given any classical circuit you can
actually make a corresponding quantum

115
00:14:04,093 --> 00:14:11,070
circuit. Okay? And this will turn out to
be a very useful primitive as we move

116
00:14:11,070 --> 00:14:15,003
forward into quantum algorithms.