1
00:00:00,000 --> 00:00:06,000
Okay, so in this video we will talk about
Quantum Complexity Theory.

2
00:00:06,000 --> 00:00:13,000
Now, Quantum Complexity Theory is a, is a
vast subject and you shouldn't expect to

3
00:00:13,000 --> 00:00:17,055
learn a lot about it in a, in a 15-,
20-minute video.

4
00:00:17,055 --> 00:00:22,099
So, I think of this video as a taste of
quantum complexity theory.

5
00:00:22,099 --> 00:00:28,082
It'll try to give you a picture of what,
you know, what the basic quantum

6
00:00:28,082 --> 00:00:34,066
complexity class s-, I-, classes, class
is, and how it relates to classical

7
00:00:34,066 --> 00:00:40,005
complexity classes.
Now, of necessity, this is, you know, this

8
00:00:40,005 --> 00:00:45,059
is, not a lecture that I expect you to
understand in detail, so, just, just think

9
00:00:45,059 --> 00:00:51,016
of this as something that'll give you,
that will whet your appetite, give you a

10
00:00:51,016 --> 00:00:57,060
picture of what Quantum Complexity theory
is all about, and, and if you, if you

11
00:00:57,060 --> 00:01:01,056
don't follow it don't worry too much about
it.

12
00:01:01,056 --> 00:01:04,043
Okay.
So, let's start by, by a, a brief

13
00:01:04,043 --> 00:01:07,072
introduction to classical complexity
theory.

14
00:01:07,072 --> 00:01:12,077
So, let's first talk about what a
computation problem is.

15
00:01:12,077 --> 00:01:18,017
So a computational problem is, is
something like, make, you know, you, you,

16
00:01:18,017 --> 00:01:22,005
you, you specified some input-output
relationship.

17
00:01:22,007 --> 00:01:28,008
And you want to try to achieve this
input-out relationship via a suitable

18
00:01:28,008 --> 00:01:29,009
algorithm.
Okay.

19
00:01:29,009 --> 00:01:34,001
So, here, here are examples.
So you might want to ma, multiply two

20
00:01:34,001 --> 00:01:36,008
matrices, M and N, which I've given to
you.

21
00:01:36,008 --> 00:01:41,003
You might want to test whether given
input, given number is a prime.

22
00:01:41,003 --> 00:01:46,054
You might want to solve the related
problem of actually producing a prime

23
00:01:46,054 --> 00:01:54,023
factorization of a given input number n.
Or you might want to test whether given

24
00:01:54,023 --> 00:02:01,085
boolean formula f is satisfiable by
actually producing a satisfying assignment

25
00:02:01,085 --> 00:02:04,002
x.
Okay, now we say that.

26
00:02:04,002 --> 00:02:09,074
A given computational problem is solvable
in polynomial time.

27
00:02:09,074 --> 00:02:16,028
If there's a, if there's a algorithm,
which on inputs of size n, holds in time,

28
00:02:16,028 --> 00:02:22,013
or n to the k for some constant k.
Meaning in time, it holds in time some

29
00:02:22,013 --> 00:02:27,018
bounded by some polynomial n, and it
outputs the correct answer.

30
00:02:27,018 --> 00:02:32,046
Now, in this course so far, we've been
talking about circuits.

31
00:02:32,046 --> 00:02:39,071
So, the corresponding statement for
circuits would be that on inputs of size

32
00:02:39,071 --> 00:02:47,035
N, you know, you have a circuit C, which
takes inputs of size N and outputs C of X.

33
00:02:47,035 --> 00:02:51,058
Which is the correct answer to this
problem.

34
00:02:51,058 --> 00:02:58,030
And the running time, instead of running
time.

35
00:02:58,030 --> 00:03:08,060
We'll talk about the size of C.
So we'll say you know, saying that there's

36
00:03:08,060 --> 00:03:14,040
a polynomial timed algorithm.
Corresponds to saying that there's a

37
00:03:14,040 --> 00:03:21,008
family of circuits C sub N, one for each
length N such that on inputs of, of, of

38
00:03:21,008 --> 00:03:24,065
length N, C sub N outputs the correct
answer.

39
00:03:24,065 --> 00:03:31,079
And moreover the size of C sub N, C sub N,
the number of gates in C sub N, is bound

40
00:03:31,079 --> 00:03:37,038
by some polynomial in N.
There's also a, you know, some sort of

41
00:03:37,038 --> 00:03:43,079
uniformity condition which says that the
circuit C can be, C sub N can be

42
00:03:43,079 --> 00:03:50,053
efficiently computed given N as input.
But that's, we, we won't get into the, the

43
00:03:50,053 --> 00:03:54,036
details of these definitions.
Okay, so.

44
00:03:54,036 --> 00:04:05,043
So now, the class P or polomial time, is a
class of all computational problems, with

45
00:04:05,043 --> 00:04:16,062
polomial time algorithms.
So, in our, in our, in our example, Matrix

46
00:04:16,062 --> 00:04:20,003
multiplication as polynomial time,
solvable.

47
00:04:20,003 --> 00:04:25,001
It's in the class P.
But we don't think factoring is, and we

48
00:04:25,001 --> 00:04:30,005
certainly don't think satisfiability is.
What about primality testing?

49
00:04:30,005 --> 00:04:36,006
Well primality testing is sort of.
It's, it's very, it comes very close to

50
00:04:36,006 --> 00:04:41,001
being in the class P.
What it isn't is the class VPP, which

51
00:04:41,001 --> 00:04:46,008
corresponds to polynomial time on a, for a
randomized algorithm.

52
00:04:46,008 --> 00:04:54,000
See here's what we mean by that, what we
mean is that there's some circuit which

53
00:04:54,000 --> 00:05:01,002
takes as input X, but it also takes as
input some random bits R.

54
00:05:01,002 --> 00:05:08,006
And now, what we, what we want is that c
of xr, is the correct answer, with high

55
00:05:08,006 --> 00:05:11,074
probability.
So we might say, well, it's correct, say,

56
00:05:11,074 --> 00:05:14,074
with probability, at least, three
quarters.

57
00:05:14,074 --> 00:05:21,006
But now if we want to boost the chance of
success, all we have to do is run the, run

58
00:05:21,006 --> 00:05:27,003
the circuit many times with, independent
random bits, and take the majority answer.

59
00:05:27,003 --> 00:05:32,033
And we can boost the success probability
from three quarters to, something

60
00:05:32,033 --> 00:05:36,034
arbitrarily close to one.
Okay.

61
00:05:36,034 --> 00:05:41,061
So, our mantra is that polynomial time is
good, exponential time is bad.

62
00:05:41,061 --> 00:05:46,052
Why is exponential time bad?
Well, we've seen this already.

63
00:05:46,052 --> 00:05:52,096
Exponential time grows so quickly if the
exponential function grows so quickly,

64
00:05:52,096 --> 00:05:58,092
that already for even small values of n,
exponential in n is larger than, number of

65
00:05:58,092 --> 00:06:02,041
particles in the universe, or age of the
universe.

66
00:06:02,041 --> 00:06:05,056
And that, that cannot be a good time
bound.

67
00:06:05,056 --> 00:06:08,042
Okay.
So that's our basic distinction between

68
00:06:08,042 --> 00:06:12,081
polynomial and exponential.
Now, there's a, there's a question that we

69
00:06:12,081 --> 00:06:17,005
beg, which is, how did we decide our model
of computation?

70
00:06:17,005 --> 00:06:21,003
Why was it circuits or Turing machines or
algorithms?

71
00:06:21,003 --> 00:06:26,009
How did we decide, what, you know, what
model we are going to run our algorithms

72
00:06:26,009 --> 00:06:30,000
on?
And this is a very important

73
00:06:30,000 --> 00:06:34,002
consideration.
This, the you know, this is what the,

74
00:06:34,004 --> 00:06:41,004
foundations of complexity theory are built
on, and it's called the extended Church

75
00:06:41,004 --> 00:06:45,006
Turing thesis.
What this thesis asserts is that it

76
00:06:45,006 --> 00:06:50,002
doesn't much matter what your model of
computation is.

77
00:06:50,005 --> 00:06:58,005
Your running times will work out to being.
Essentially the same to within polynomial

78
00:06:58,005 --> 00:07:01,008
factors.
So, if you're talking about polynomial

79
00:07:01,008 --> 00:07:06,004
time competition.
It's robust against changes in models, the

80
00:07:06,004 --> 00:07:11,002
model of computation.
So this another reason we like polynomial

81
00:07:11,002 --> 00:07:15,000
time.
Because it's a robust notion of, running

82
00:07:15,000 --> 00:07:18,003
time.
So what the extended Church-Turing thesis

83
00:07:18,003 --> 00:07:24,006
actually says is that, any reasonable
model of computation can be simulated on a

84
00:07:24,006 --> 00:07:30,002
probabilistic Turing machine with, at
most, polynomial simulation overhead.

85
00:07:30,002 --> 00:07:34,076
What does this mean?
It means, for example, that if you have,

86
00:07:34,076 --> 00:07:43,023
if you have a running time of T steps on
some model of computation that you've,

87
00:07:43,023 --> 00:07:49,061
that you invented, which you think is
reasonable, reasonable meaning you can

88
00:07:49,061 --> 00:07:55,062
implement it in principle.
Physically implementable in principle,

89
00:07:55,062 --> 00:08:05,013
then you can also run this algorithm.
Say, in order, t squared steps, or some

90
00:08:05,013 --> 00:08:11,062
polynomial and t steps on a Turing
machine, on the simplest model of them

91
00:08:11,062 --> 00:08:14,041
all.
Now, where does this Extended

92
00:08:14,041 --> 00:08:19,008
Church-Turing thesis come from?
What, how do you interpret it?

93
00:08:19,008 --> 00:08:24,033
Well, one interpretation for this Extended
Church-Turing Thesis was.

94
00:08:24,033 --> 00:08:31,002
That a touring machine describes the set
of all functions, that are computable by a

95
00:08:31,002 --> 00:08:35,000
mathematician.
So you think of the touring tape, as being

96
00:08:35,000 --> 00:08:40,059
an infinite supply of paper..
And you think of the finite state control

97
00:08:40,059 --> 00:08:44,024
as your mathematician, and the read-write
head as a pencil.

98
00:08:44,024 --> 00:08:49,092
So you, so you have a mathematician armed
with infinite supply of pencils, infinite

99
00:08:49,092 --> 00:08:53,047
supply of paper.
And you want to know, what can this

100
00:08:53,047 --> 00:08:56,029
mathematician compute?
What are the functions?

101
00:08:56,029 --> 00:09:00,095
What are the problems that this
mathematician can solve in a reasonable

102
00:09:00,095 --> 00:09:03,095
amount of time?
Well, that's what polynomial time

103
00:09:03,095 --> 00:09:08,061
describes in this one interpretation.
The second interpretation of, of this

104
00:09:08,061 --> 00:09:17,002
thesis is that the class polynomial time
represents what can be physically computed

105
00:09:17,002 --> 00:09:22,006
in this, in this universe in a reasonable
amount of time.

106
00:09:22,006 --> 00:09:33,096
And the rationale for this, is that Turing
machines can simulate cellular automata

107
00:09:33,096 --> 00:09:39,081
with, with polynomial overhead.
Right there polynomially equivalent to

108
00:09:39,081 --> 00:09:44,071
cellular automata.
And some of the arguments is that cellular

109
00:09:44,071 --> 00:09:50,062
automata represents everything that you
can compute in the, in the, in the

110
00:09:50,062 --> 00:09:53,036
classical universe.
Okay.

111
00:09:53,036 --> 00:09:57,073
Remember we are talking about classical
complexity theory so far.

112
00:09:57,073 --> 00:10:00,068
So why is it, that, that a cellular
automaton.

113
00:10:00,068 --> 00:10:06,024
By the way this is, this is a cellular
automaton that's, that's simulating what's

114
00:10:06,024 --> 00:10:10,050
called The Game of Life.
Like Conway's Game of Life.

115
00:10:10,050 --> 00:10:17,019
Okay, so, so what is it about a cellular
automaton that it makes it such a

116
00:10:17,019 --> 00:10:24,020
convincing model for anything that can be
computed in the, in the classical

117
00:10:24,020 --> 00:10:29,003
universe?
So, so, in a cellular automaton, each cell

118
00:10:29,003 --> 00:10:34,099
looks at its, its small neighborhood, the
cells around it and its new state, you

119
00:10:34,099 --> 00:10:39,001
know.
It's in one of a finite number of states.

120
00:10:39,001 --> 00:10:42,009
And its new state is a function of its,
you know?

121
00:10:42,009 --> 00:10:48,006
The states of all the cells in a small
neigh-, you know, its, its neighbors.

122
00:10:48,006 --> 00:10:51,007
Okay.
Now, this is directly analogous to

123
00:10:51,007 --> 00:10:58,087
something in, in physics.
It says that, so classical physics is

124
00:10:58,087 --> 00:11:13,000
described by local differential equations.
Which means that, what you're saying is

125
00:11:13,000 --> 00:11:17,004
that, you know?
If you want to know how some quantity

126
00:11:17,004 --> 00:11:20,092
changes over time, electricity, magnetism,
whatever.

127
00:11:20,092 --> 00:11:25,085
Then, you, wh-, what you, what you have to
say is that, you know?

128
00:11:25,085 --> 00:11:31,046
The, the value of that, that physical
quantity at, at a certain point.

129
00:11:31,046 --> 00:11:37,073
At, you know, at t plus delta t is
determined by, sort of, you know, that,

130
00:11:37,073 --> 00:11:43,098
that point just looks at an infinitesimal
neighborhood around it.

131
00:11:43,098 --> 00:11:51,012
And, based on the value at time t in this
infinitesimal neighborhood, you can

132
00:11:51,012 --> 00:11:58,008
determine the value of, at, at this
particular point at time t plus delta t.

133
00:11:59,009 --> 00:12:15,007
Okay, but now so you can see that, that
cellular automaton, These are, these are

134
00:12:15,007 --> 00:12:24,027
discreet discretizations of local
differential equations.

135
00:12:24,027 --> 00:12:29,010
And you can argue that if you want to
compute.

136
00:12:29,010 --> 00:12:35,016
Then your, you, your computer has to be
fault tolerant.

137
00:12:35,016 --> 00:12:42,035
That, you know, it cannot be that, that
you assume infinite precision in your

138
00:12:42,035 --> 00:12:45,034
model.
And so you have to discretize it.

139
00:12:45,034 --> 00:12:56,055
You have to have a digital abstraction.
And once you take your local differential

140
00:12:56,055 --> 00:13:02,062
equations and you, and you subject them to
a digital abstraction you, you get

141
00:13:02,062 --> 00:13:06,079
cellular automata.
So that's the argument that polynomial

142
00:13:06,079 --> 00:13:12,051
time is the limit of what you can compute
in the physical world classically.

143
00:13:12,051 --> 00:13:16,011
And so.
Quantum computation is the only model of

144
00:13:16,011 --> 00:13:20,058
computation that violates this extended
Church-Turing thesis.

145
00:13:20,058 --> 00:13:23,097
It's the only reasonable, model of
computation.

146
00:13:23,097 --> 00:13:29,099
Which cannot be simulated in polynomial
time on, on a Turing machine, on your

147
00:13:29,099 --> 00:13:34,068
classical Turing machine.
So what's our evidence for this?

148
00:13:34,068 --> 00:13:40,059
Well, we have two kinds of evidence that
it violates the extended Church-Turing

149
00:13:40,059 --> 00:13:43,093
thesis.
One is a black box sep-, separations.

150
00:13:43,093 --> 00:13:48,036
So we already saw these examples of, of
algorithms.

151
00:13:48,036 --> 00:13:56,028
You know, such as the recursive Fourier
sampling problem or Simon's problem, where

152
00:13:56,028 --> 00:14:02,040
we said there is no polynomial time.
You, you know, you, you can solve these

153
00:14:02,040 --> 00:14:10,005
problems in polynomial time on a quantum
Turing machine or with a quantum circuit,

154
00:14:10,005 --> 00:14:16,055
but there is no corresponding polynomial
time solution to these problems.

155
00:14:16,055 --> 00:14:21,033
Classically, is in the classical
algorithm.

156
00:14:21,033 --> 00:14:29,006
We also saw that, that there are problems
that we strongly believe to be difficult

157
00:14:29,006 --> 00:14:33,003
classically.
In fact, we believe that are, we believe

158
00:14:33,003 --> 00:14:36,008
this so strongly that we base cryptography
on it.

159
00:14:36,008 --> 00:14:40,009
These are problems like factoring and
discrete logarithms.

160
00:14:41,003 --> 00:14:48,000
And for these problems we know that there
is a polynomial time quantum algorithm but

161
00:14:48,000 --> 00:14:52,003
we strongly believe that it takes
exponential time to.

162
00:14:52,006 --> 00:14:59,000
To solve them classically or at least.
All the algorithms that we know of so far

163
00:14:59,000 --> 00:15:03,004
take exponential time.
So these are the two kinds of evidence

164
00:15:03,004 --> 00:15:07,064
that we have that quantum computers
violate this extended Church-Turing

165
00:15:07,064 --> 00:15:11,018
thesis.
Now, you could ask, why are we messing

166
00:15:11,018 --> 00:15:16,048
around with this kind of evidence?
Why don't we just flat out prove that

167
00:15:16,048 --> 00:15:20,077
quantum computers violate this extended
Church-Turing thesis?

168
00:15:20,077 --> 00:15:27,097
Well the answer has to do with, with this.
Okay, let's, let's first define this class

169
00:15:27,097 --> 00:15:32,096
BQB, Bounded Error Probabilistic Bonham
Milton.

170
00:15:32,096 --> 00:15:39,005
Bounded Error, Sorry.
Quantum polynomial time.

171
00:15:40,001 --> 00:15:45,004
Right it's, it's the class of
computational problems which have

172
00:15:45,004 --> 00:15:52,000
polynomial time quantum algorithms that
I'll put the correct answer with high

173
00:15:52,000 --> 00:15:56,004
probability.
So for example factoring belongs to BQP.

174
00:15:56,004 --> 00:16:02,008
Now Okay, so.
The, you, you can show this inclusion

175
00:16:02,008 --> 00:16:08,002
that, that P, polynomial time is in BPP,
probabilistic polynomial time, which is

176
00:16:08,002 --> 00:16:12,000
contained in BQP.
So BQP is, is this class that we are

177
00:16:12,000 --> 00:16:15,008
interested in showing is so much larger
than P or BPP.

178
00:16:15,008 --> 00:16:19,002
But then you can also show further
containments.

179
00:16:19,002 --> 00:16:24,007
You can also show that this is contained
in something called P to the sharp P,

180
00:16:24,007 --> 00:16:27,004
which is contained in P space.
P space.

181
00:16:27,004 --> 00:16:33,004
Is a class of problems that you can solve
using not a polynomial amount of time but

182
00:16:33,004 --> 00:16:38,002
polynomial amount of space.
So you can, you can, you know, if you have

183
00:16:38,002 --> 00:16:44,000
only a polynomial, polynomial amount of
memory in your algorithm, but you can keep

184
00:16:44,000 --> 00:16:47,001
using this memory, well then that's p
space.

185
00:16:47,001 --> 00:16:54,007
Now the interesting here is that.
P versus P space whether or not P equal to

186
00:16:54,007 --> 00:17:01,004
P space this is one of the major open
questions in complexity theory.

187
00:17:01,004 --> 00:17:08,004
So, this is an open question in complexity
theory.

188
00:17:08,004 --> 00:17:11,006
We strongly believe that P is not equal to
P space.

189
00:17:11,006 --> 00:17:15,001
But we don't know for sure.
We don't know how to prove it.

190
00:17:15,001 --> 00:17:21,005
So now you can see, if we could show that
BQP is strictly larger than P and BPP.

191
00:17:21,005 --> 00:17:25,003
Then we'd have shown that P is not equal
to P space.

192
00:17:25,003 --> 00:17:31,009
Thus, solving this major open question.
And this is why we have to deal with this

193
00:17:31,009 --> 00:17:37,007
sort of evidence, that BQP really, that
quantum polynomial time is larger.

194
00:17:37,007 --> 00:17:42,002
That quantum computers violate this
[inaudible] thesis.

195
00:17:43,007 --> 00:17:48,006
And's what's B, what's sharp B?
Well sharp B.

196
00:17:50,008 --> 00:17:57,009
This is so called counting clause.
It's a complexity class having to do with

197
00:17:57,009 --> 00:18:01,003
counting.
So let's say you have a, you have a

198
00:18:01,003 --> 00:18:10,003
circuit.
See here we have some function'f, ' which

199
00:18:10,003 --> 00:18:17,000
maps'x' in'y' to'f' of'xy'.
Okay.

200
00:18:17,000 --> 00:18:23,000
Now we can, we can define accounting
problem associated with this.

201
00:18:23,000 --> 00:18:27,005
We can say, the count of X, is the sum
over all Y.

202
00:18:27,009 --> 00:18:36,003
Of F of XY.
You see so.

203
00:18:38,001 --> 00:18:44,008
So, what, what, what this is saying is, if
you were given x and y, you could of

204
00:18:44,008 --> 00:18:51,006
course compute f of xy quickly because f
is implemented by a polynomial size

205
00:18:51,006 --> 00:18:56,002
circuit.
But now what you want to do is you want to

206
00:18:56,002 --> 00:19:02,007
sum up f of xy over exponentially many
different y's and this is now much more

207
00:19:02,007 --> 00:19:08,002
complicated problem.
It turns out that if you could solve this

208
00:19:08,002 --> 00:19:13,009
problem than you can actu, actually solve,
you know, then you can, then you can

209
00:19:13,009 --> 00:19:17,004
simulate any quantum computation that you
want.

210
00:19:17,004 --> 00:19:22,007
And the way you reduce a quantum
computation to this sort of counting

211
00:19:22,007 --> 00:19:26,004
problem is.
It's reminiscent of Feynman's path

212
00:19:26,004 --> 00:19:29,008
integrals.
So, in fact, in some sense, what Feynman

213
00:19:29,008 --> 00:19:34,000
came up with was a way of showing that BQP
is in P to the sharp P.

214
00:19:34,000 --> 00:19:38,007
It's actually not a very difficult proof,
it's, it's a simple proof.

215
00:19:38,007 --> 00:19:41,008
But I really don't want to get into this
now.

216
00:19:41,008 --> 00:19:44,009
It's, you know, we don't really have the
time.

217
00:19:44,009 --> 00:19:49,001
And, or, or, you know, it's, it's, it
wouldn't be appropriate.

218
00:19:49,001 --> 00:19:54,001
We couldn't really do it justice in this,
in this [inaudible] setting.

219
00:19:55,007 --> 00:20:03,005
Okay, so now.
We could try to understand, you know, our

220
00:20:03,005 --> 00:20:18,006
complexity classes A little bit better.
So, here we have P of polynomial time.

221
00:20:18,006 --> 00:20:27,002
And then remember there was this class NP.
It contained many of the problems that

222
00:20:27,002 --> 00:20:34,000
we'd like to solve.
Like satisfiability.

223
00:20:34,000 --> 00:20:41,003
Now if you take a problem which is in MP
like satisfiability.

224
00:20:41,003 --> 00:20:45,002
You could also look at the compliment of
it.

225
00:20:45,002 --> 00:20:51,086
And you get, get this class, co NP, which
contains problems like, not satisfiable.

226
00:20:51,086 --> 00:20:58,062
Is this formula not satisfiable?
And then, it turns out there's a, that

227
00:20:58,062 --> 00:21:07,017
there's a high, you know, so, so, there's
an, there's an infinite hierarchy of such

228
00:21:07,017 --> 00:21:12,054
classes.
Mp, Co-MP, what's called.

229
00:21:12,054 --> 00:21:19,057
Sigma 2P, etc.
Pi to P, etc.

230
00:21:19,057 --> 00:21:27,010
And these, You know this, this entire
class of problems.

231
00:21:27,010 --> 00:21:32,097
Sort of forms what's called the polynomial
hierarchy.

232
00:21:32,097 --> 00:21:40,024
And all this, you know, this entire
structure sits in inside.

233
00:21:40,024 --> 00:21:54,097
P to the sharp P.
And which finally sits inside P space.

234
00:21:54,097 --> 00:22:05,069
So now you could ask.
Well, you know, we've already said that we

235
00:22:05,069 --> 00:22:11,065
believe that BQP, the, that you cannot
solve the NP-complete problems.

236
00:22:11,065 --> 00:22:18,016
So the problems right here, we, we cannot
solve them in polynomial time.

237
00:22:18,016 --> 00:22:25,016
I-, so in, in polynomial time on so, so
this is, let's say, the NP-complete

238
00:22:25,016 --> 00:22:29,056
problems.
And, we believe that this cannot be solved

239
00:22:29,056 --> 00:22:33,070
in polynomial time on a quantum computer.
Right?

240
00:22:33,070 --> 00:22:39,011
So.
What does this class BQP look like in this

241
00:22:39,011 --> 00:22:43,076
picture?
So, is it contained inside of MP?

242
00:22:43,076 --> 00:22:51,005
Well, we already have a hint.
What, the, the, the hint that we have is

243
00:22:51,005 --> 00:23:01,044
that this, this, this problem recursive
Fourier sampling, we can show that in the,

244
00:23:01,044 --> 00:23:08,094
in the black-box model, this does not
belong to MA, Merlin-Arthur, which is the

245
00:23:08,094 --> 00:23:15,004
probabilistic generalization of NP.
So it lies outside of this NP but, not

246
00:23:15,004 --> 00:23:21,004
only does it lie outside of NP, but it
even lies outside the probabilistic

247
00:23:21,004 --> 00:23:26,002
generalization of NP.
We can show this, you know, like, like all

248
00:23:26,002 --> 00:23:30,003
of these results, we can show this
unconditionally.

249
00:23:30,003 --> 00:23:40,006
This is in a black-box model.
Or, also called an oracle model or

250
00:23:40,006 --> 00:23:42,005
setting.
Okay.

251
00:23:42,005 --> 00:23:49,000
So, so now, what should we think about,
about, BQP?

252
00:23:49,000 --> 00:23:57,076
So, the idea is that BQP somehow, it
doesn't contain the MP complete problems.

253
00:23:57,076 --> 00:24:04,023
It, instead, is some sort of complexity
clause which, which heads out like this.

254
00:24:04,023 --> 00:24:07,077
And it contains recursive Fourier
sampling.

255
00:24:07,077 --> 00:24:14,083
And how far it heads out into this whole
thing we, we don't quite, you know, we

256
00:24:14,083 --> 00:24:20,012
don't yet understand.
So we could ask, how, how far outside of

257
00:24:20,012 --> 00:24:24,013
MP are these problems that BQP might
contain?

258
00:24:24,013 --> 00:24:31,075
And could it be that in fact it even
extends outside of the polynomial

259
00:24:31,075 --> 00:24:35,040
hierarchy and contains some problems out
here.

260
00:24:35,040 --> 00:24:38,094
And the conjecture, which is very long
standing.

261
00:24:38,094 --> 00:24:44,089
It goes back almost twenty years.
Says that in fact the foray sampling

262
00:24:44,089 --> 00:24:50,091
problem should be one such example, which
is not in the [inaudible] hierarchy.

263
00:24:50,091 --> 00:24:55,064
This has proved to be remarkably, to, you
know to, to resolve.

264
00:24:55,064 --> 00:25:02,005
And a few years ago, Scott Erinson came up
with a, with a simplified problem which,

265
00:25:02,005 --> 00:25:07,065
which, Which he conjected is also not in
the polomial hierarchy, but with which can

266
00:25:07,065 --> 00:25:10,075
be solved, in polomial time on a quantum
computer.

267
00:25:10,075 --> 00:25:14,053
And this is called, the Fourier checking
problem.

268
00:25:14,053 --> 00:25:21,031
So here's a, here's a, here's a, a pointer
to the, to a paper that discusses this

269
00:25:21,031 --> 00:25:25,011
problem.
But it's actually a very simple problem.

270
00:25:25,011 --> 00:25:28,071
It's, it's very simply stated and very
elegant.

271
00:25:28,071 --> 00:25:35,044
So, let's say BMW are random unit vectors
in real n-dimensional vectors where, where

272
00:25:35,044 --> 00:25:41,087
capital n is two to the little n.
So it's, these are exponential dimensional

273
00:25:41,087 --> 00:25:46,040
real vectors.
And now given such a real vector, you can,

274
00:25:46,040 --> 00:25:50,043
you can.
Think of it as defining.

275
00:25:50,043 --> 00:25:54,052
A boulion function.
Okay.

276
00:25:54,052 --> 00:25:58,034
So its a, its a function which, you know,
for.

277
00:25:58,034 --> 00:26:05,001
So, so in other words, you have this, you
have this exponential dimensional vector

278
00:26:05,001 --> 00:26:11,016
where, each entry is a real number.
So this, this, this real number, let's say

279
00:26:11,016 --> 00:26:14,077
is R sub K.
And now you could think of this as

280
00:26:14,077 --> 00:26:20,045
defining a bullion function for you, where
maps K to the, sign of K.

281
00:26:20,045 --> 00:26:25,030
Right?
So it, it, it maps an N bit number to +one

282
00:26:25,030 --> 00:26:30,033
or -one.
Okay, so, so now, since you have two such,

283
00:26:30,033 --> 00:26:36,041
such, such vectors that define two
different functions.

284
00:26:36,041 --> 00:26:42,092
F and G, which are bullion functions on
little N bits.

285
00:26:42,092 --> 00:26:52,011
So what we want to do is distinguish.
So we are given two, two, two such

286
00:26:52,011 --> 00:26:56,079
functions.
Either we are given F equal to sine of V,

287
00:26:56,079 --> 00:27:02,066
and G equal to sine of W.
You know, the, these, the sine functions

288
00:27:02,066 --> 00:27:10,001
defined by these two random vectors.
Or, we are given F is equal to sine of V.

289
00:27:10,001 --> 00:27:15,093
And g equal to sine of h Dove..
So, so, instead of wv, now you use the

290
00:27:15,093 --> 00:27:20,019
same vector v.
Once as it is, and once having applied the

291
00:27:20,019 --> 00:27:25,008
Hadamard transform to it.
And we want to be able to distinguish

292
00:27:25,008 --> 00:27:31,004
these two situations from each other.
And the, the, the point is that there's a

293
00:27:31,004 --> 00:27:36,065
very simple quantum algorithm that will
distinguish this situ-, the first

294
00:27:36,065 --> 00:27:40,053
situation from the second one.
But the conjecture is.

295
00:27:40,053 --> 00:27:46,058
That you cannot do this distinction
anywhere in the program with hierarchy.

296
00:27:46,058 --> 00:27:50,013
Okay.
So, I should mention that this is one of

297
00:27:50,013 --> 00:27:54,090
the central open questions in quantum
complexity theory.

298
00:27:54,090 --> 00:28:00,022
Understanding the power of BQP, Quantum
Polynomial Time.

299
00:28:00,022 --> 00:28:04,004
And this is completely wide open as, as we
speak.