1
00:00:00,000 --> 00:00:07,002
Okay. So, now let's try to understand a
little more what, what quantum algorithms

2
00:00:07,002 --> 00:00:14,002
and quantum circuits look like. Okay. So
what's our basic model of, of computing?

3
00:00:14,002 --> 00:00:28,006
Well, our basic model looks like this now.
So we have N qubits, here which are

4
00:00:28,006 --> 00:00:36,004
initially, let's say in this state zero.
These we think of as the inputs to the

5
00:00:36,004 --> 00:00:42,007
circuit. And what I draw here these, these
lines, these are wires and each wire

6
00:00:42,007 --> 00:00:49,002
carries a qubit of information. Okay? So,
so, let's think of each of these wires as

7
00:00:49,002 --> 00:00:54,046
our electron in the hydrogen atom. You
know, whether it's in the ground or

8
00:00:54,046 --> 00:01:00,096
excited state, or in a superposition of
the two. And of course, as we go along,

9
00:01:00,096 --> 00:01:06,086
these wires will get entangled. The qubits
get entangled, right? Okay. Now, now what

10
00:01:06,086 --> 00:01:13,092
do we actually do? Well, a quantum circuit
is a sequence of gates. So it consists of

11
00:01:13,092 --> 00:01:21,006
a sequence of gates so you might have,
have some kind of quantum gate that acts

12
00:01:21,006 --> 00:01:32,029
on these two qubits, and outputs two
qubits. They could be also single qubit

13
00:01:32,029 --> 00:01:48,023
gates. So, so this might be the Hadamard,
this might be z. Okay. Whatever, right? So

14
00:01:48,023 --> 00:01:53,040
there are, there are some sort of gates.
This might be a controlled naught, we

15
00:01:53,040 --> 00:02:01,005
don't know. Okay. But, but a quantum
circuit is, is just a sequence of gates.

16
00:02:03,003 --> 00:02:09,039
Maybe this one just goes right through.
Perhaps there's another gate here, etc.

17
00:02:09,039 --> 00:02:18,083
So, so quantum circuit is consists of
these n wires that just go through left to

18
00:02:18,083 --> 00:02:37,070
right all the way to the end and then
maybe there are other gates back here.

19
00:02:37,070 --> 00:02:57,093
This whole thing is called a quantum
circuit. These are the outputs of the, of

20
00:02:57,093 --> 00:03:04,091
the quantum circuit. And now what we might
want to do is, we might want to measure

21
00:03:04,091 --> 00:03:11,034
these, these bits. We, we either you know,
it could be that we only measure some of

22
00:03:11,034 --> 00:03:18,031
these, these qubits. So, so we, we select,
some of these qubits, maybe, maybe these

23
00:03:18,031 --> 00:03:28,087
ones and we put in a measuring apparatus.
And then, as output we get a classical

24
00:03:28,087 --> 00:03:41,013
string. Okay? So that's, that's a quantum
circuit. Now, there's a question. What

25
00:03:41,013 --> 00:03:47,023
kind of gates should be allowed in this
quantum circuit? Well so, let's look at,

26
00:03:47,023 --> 00:03:54,037
look at the corresponding question on the
classical side. So if you have a classical

27
00:03:54,037 --> 00:04:00,061
circuit, what kind of gates should one
allow? Well, there are many kinds of gates

28
00:04:00,061 --> 00:04:07,018
one can, one can come up with nands, ors,
nor, etc., etc. But, but there's, there's

29
00:04:07,018 --> 00:04:15,020
a you know, there's this very simple but
very, very beautiful fact about classical

30
00:04:15,020 --> 00:04:23,063
circuits which is that, you don't have to
allow for, for a very rich set of gates.

31
00:04:23,063 --> 00:04:32,095
In fact, all you need is a Nand gate. A
nand gate takes as input two, two bits and

32
00:04:32,095 --> 00:04:43,084
outputs one bit and it's the naught of the
and, right? So, so the output is, is one

33
00:04:43,084 --> 00:04:53,033
unless x equal to y, equal to one, in
which case the output is zero. So, so the

34
00:04:53,033 --> 00:04:59,084
claim is that no matter how complicated
the circuit you are trying to create, you

35
00:04:59,084 --> 00:05:04,078
can always assume that your building
blocks are. You have only one kind of

36
00:05:04,078 --> 00:05:10,094
building block which is a Nand gate. Okay.
So, so the way one, one says this is by

37
00:05:10,094 --> 00:05:17,032
you know, expresses this fact is by saying
that the Nand gate is universal for

38
00:05:17,032 --> 00:05:24,038
classical computation. So now we can ask,
is something like this true also for

39
00:05:24,038 --> 00:05:31,099
quantum computing? Is there a universal
family of quantum gates? And it turns out

40
00:05:31,099 --> 00:05:37,074
that there is, so there are various
families of quantum gates that are, that

41
00:05:37,074 --> 00:05:43,099
are universal but for our purposes, the,
the gates that we saw CNOT, Hadamard, X, Z

42
00:05:43,099 --> 00:05:49,094
together with the pi by eight rotation. So
if you have, if you have just these five

43
00:05:49,094 --> 00:05:56,056
types of gates, then they claim that you
can implement any quantum circuit that you

44
00:05:56,056 --> 00:06:01,071
want. Okay. Let me say just a couple of
more words about it to make this a little

45
00:06:01,071 --> 00:06:07,064
more precise for those of you who are
interested. So what does it mean that this

46
00:06:07,064 --> 00:06:18,049
gate set is universal? So, what we'd like
it to mean is that, if you have any, let's

47
00:06:18,049 --> 00:06:24,001
say that, that somebody came along and
they said, you know, there's this

48
00:06:24,001 --> 00:06:31,000
particular unitary transformation, you
know, there's this particular gate that I

49
00:06:31,000 --> 00:06:36,064
have in mind you know, I'm going to, it,
it, it's really quite magical. This gate

50
00:06:36,064 --> 00:06:41,063
has the property that it will simplify
every quantum computation. You know, you

51
00:06:41,063 --> 00:06:46,075
only have t o implement this gate, and
then you know, everything is going to be

52
00:06:46,075 --> 00:06:51,098
so much faster you won't even believe it.
Okay. And what does this gate look like?

53
00:06:51,098 --> 00:06:59,017
Maybe, maybe it takes as input four
qubits, outputs four cubits and implements

54
00:06:59,017 --> 00:07:07,043
some unitary u on these four qubits. So
it's, it's represented by a sixteen by

55
00:07:07,043 --> 00:07:17,053
sixteen matrix, complex matrix. Okay so,
so now the fact that these five gates are

56
00:07:17,053 --> 00:07:27,038
universal allows us to say, you know, it
cannot be the case that your, your, your,

57
00:07:27,038 --> 00:07:33,076
your gate, your favorite gate u is, could
be that powerful because it can't be more

58
00:07:33,076 --> 00:07:41,007
powerful than these because what we show
you is how to implement u using these five

59
00:07:41,007 --> 00:07:49,032
gates. And moreover, to implement u, we'll
do it pretty efficiently. Okay, now there

60
00:07:49,032 --> 00:07:55,093
is one problem we cannot of course
implement u with, with perfect precision

61
00:07:55,093 --> 00:08:02,080
because, because u after all is, is, is
represented by a sixteen by sixteen

62
00:08:02,080 --> 00:08:10,043
complex matrix and you need, you need
infinitely many digits to specify this to

63
00:08:10,043 --> 00:08:19,001
perfect precision. So, instead what we
will do is, for any given epsilon, we'll

64
00:08:19,001 --> 00:08:26,009
implement an approximation use of epsilon,
which epsilon close to you. And it turns

65
00:08:26,009 --> 00:08:34,009
out that if the, if u is given by d by d
matrix and you want to be epsilon close to

66
00:08:34,009 --> 00:08:41,002
the answer, the, the number of these
elementary gates that we need scales

67
00:08:41,002 --> 00:08:47,002
roughly like well it you know, it has to
scale like you know, it might be some

68
00:08:47,002 --> 00:08:54,073
polynomial in d, lets say order d squared
times in polynomial in one over epsilon,

69
00:08:54,073 --> 00:09:01,057
log one over epsilon. So, certainly log
cubed works and maybe even well, well,

70
00:09:01,057 --> 00:09:08,063
let's, let's say log cubed just to be on
the safe side. So the dependence on d and

71
00:09:08,063 --> 00:09:14,065
epsilon is mild. Now a claim that, that
something like this dependence on d, d

72
00:09:14,065 --> 00:09:19,079
squared is really necessary because,
because just by counting argument there

73
00:09:19,079 --> 00:09:24,094
are lots of, lots of unitary
transformations which are, which are d by

74
00:09:24,094 --> 00:09:31,056
d and, and these are only five gates, so
how can you express all of them unless you

75
00:09:31,056 --> 00:09:37,046
pay such an, such an overhead. So, okay.
So what's, what's the upshot of all these?

76
00:09:37,046 --> 00:09:43,042
The upshot of all these is what we are
claiming is, we are going to be

77
00:09:43,042 --> 00:09:51,011
implementing this, this circuit use of
epsilon where if you look inside, what it

78
00:09:51,011 --> 00:09:59,072
consists of is, CNOT gates and Hadamards,
and, and X gates, and Z gates, and so on.

79
00:09:59,072 --> 00:10:09,015
And moreover, this, this circuit use of
epsilon behaves almost the same as you in

80
00:10:09,015 --> 00:10:17,049
the sense that if you look at these two
transformations u and u epsilon, they are

81
00:10:17,049 --> 00:10:25,004
epsilon close in operator norm. So u minus
u epsilon in operator norm is at most

82
00:10:25,004 --> 00:10:32,064
epsilon, okay? Which means that, this is
another way of saying that if you apply

83
00:10:32,064 --> 00:10:39,052
both of these, these, these circuits to,
to the same quantum state, the state that

84
00:10:39,052 --> 00:10:46,072
results in the two cases, these two states
are going to be epsilon close to each

85
00:10:46,072 --> 00:10:49,004
other in Euclidian norm.