WEBVTT

1
00:00:12.722 --> 00:00:15.129
- Okay so welcome to the computer science colloquium.

2
00:00:15.129 --> 00:00:17.624
It's a great pleasure today to have Richard Jozsa

3
00:00:17.624 --> 00:00:18.944
here to give the colloquium.

4
00:00:18.944 --> 00:00:22.134
Richard got his PhD from Oxford in 1981

5
00:00:22.134 --> 00:00:24.031
when he worked with Roger Penrose

6
00:00:24.031 --> 00:00:26.741
and after some construction work he

7
00:00:26.741 --> 00:00:28.893
was on the faculty at the University of Plymouth

8
00:00:28.893 --> 00:00:30.962
in the math and mathematical physics programs.

9
00:00:30.962 --> 00:00:34.386
He was then for ten years a professor of computer science

10
00:00:34.386 --> 00:00:36.571
at the University of Bristol and he's currently the

11
00:00:36.571 --> 00:00:40.266
lead travel professor of quantum physics at DAMTP.

12
00:00:40.266 --> 00:00:42.658
The Department of Applied Math and Theoretical Physics

13
00:00:42.658 --> 00:00:43.658
at Cambridge.

14
00:00:43.658 --> 00:00:47.483
Richard has really made a lot of important contributions

15
00:00:47.483 --> 00:00:49.932
to the study of quantum computing and quantum information

16
00:00:49.932 --> 00:00:51.159
processing.

17
00:00:51.159 --> 00:00:53.341
So I'll mention a few of them,

18
00:00:53.341 --> 00:00:55.081
with David Doitch in 92

19
00:00:55.081 --> 00:00:58.030
so even before the development of Shor's algorithm,

20
00:00:58.030 --> 00:01:00.751
he gave the first example of a problem

21
00:01:00.751 --> 00:01:02.522
that could be solved exponentially faster.

22
00:01:02.522 --> 00:01:05.130
With a quantum computer than with a classical one.

23
00:01:05.130 --> 00:01:07.428
Actually I presented this algorithm yesterday

24
00:01:07.428 --> 00:01:09.866
in my graduate course on quantum computing coincidentally.

25
00:01:09.866 --> 00:01:14.033
With Charlie Bennet, Joan Cussard, Claude Capeau,

26
00:01:14.568 --> 00:01:16.180
Atra Paris and the others

27
00:01:16.180 --> 00:01:18.558
he was one of the discovers of quantum teleportation.

28
00:01:18.558 --> 00:01:20.573
Which is a really important foundational idea

29
00:01:20.573 --> 00:01:22.030
in quantum information.

30
00:01:22.030 --> 00:01:24.421
The paper which describes this,

31
00:01:24.421 --> 00:01:27.415
it's concept has been cited I think more than 10,000 times.

32
00:01:27.415 --> 00:01:29.284
It's quite remarkable.

33
00:01:29.284 --> 00:01:32.180
He did some important early work on quantum information

34
00:01:32.180 --> 00:01:34.736
theory and recently has been studying

35
00:01:34.736 --> 00:01:38.284
the boundary between classical and quantum computing.

36
00:01:38.284 --> 00:01:39.807
Through trying to understand classical simulations

37
00:01:39.807 --> 00:01:41.621
of quantum computing.

38
00:01:41.621 --> 00:01:44.483
He'll tell us a bit about that idea today.

39
00:01:44.483 --> 00:01:47.432
Richard has received numerous prizes including

40
00:01:47.432 --> 00:01:50.063
the Naylor prize from the London Mathematical Society

41
00:01:50.063 --> 00:01:51.904
on the quantum communication award

42
00:01:51.904 --> 00:01:55.061
that's given as part of the QCMC conference.

43
00:01:55.061 --> 00:01:56.808
And today he's going to tell us about

44
00:01:56.808 --> 00:01:59.535
comparing classical and quantum complexity.

45
00:01:59.535 --> 00:02:01.079
- Well thank you very much Jerry.

46
00:02:01.079 --> 00:02:04.734
Okay so today I'd like to talk about quantum computing.

47
00:02:04.734 --> 00:02:06.641
That's not surprisingly

48
00:02:06.641 --> 00:02:10.235
and especially some fundamental aspects.

49
00:02:10.235 --> 00:02:12.194
Rather than practical aspects.

50
00:02:12.194 --> 00:02:14.033
If you people work on HTTP.

51
00:02:14.033 --> 00:02:16.981
And my aim is to try and be accessible

52
00:02:16.981 --> 00:02:19.355
to a broader computer science audience.

53
00:02:19.355 --> 00:02:22.858
Sort of people who are not necessarily specialists

54
00:02:22.858 --> 00:02:26.886
you know in the subject of quantum physics.

55
00:02:26.886 --> 00:02:29.005
So I know Maryland

56
00:02:29.005 --> 00:02:30.660
there is a very large number of experts

57
00:02:30.660 --> 00:02:32.064
in all aspects of the field.

58
00:02:32.064 --> 00:02:34.373
So apologies in advance to them

59
00:02:34.373 --> 00:02:35.954
if you sort of are here.

60
00:02:35.954 --> 00:02:38.803
And I would say that perhaps there's a

61
00:02:38.803 --> 00:02:40.983
different kind of pleasure to be had

62
00:02:40.983 --> 00:02:43.778
in listening to things you're very familiar with

63
00:02:43.778 --> 00:02:46.705
and perhaps seeing them from a slightly

64
00:02:46.705 --> 00:02:49.774
different perspective in some cases.

65
00:02:49.774 --> 00:02:51.519
Okay so to start

66
00:02:51.519 --> 00:02:55.236
as a kind of introduction to quantum computing.

67
00:02:55.236 --> 00:02:57.422
I perhaps like to present

68
00:02:57.422 --> 00:03:00.199
a kind of overview of the ingredients.

69
00:03:00.199 --> 00:03:02.797
The essential ingredients of quantum computing

70
00:03:02.797 --> 00:03:03.982
and the model.

71
00:03:03.982 --> 00:03:06.933
In a way that perhaps aligned with more familiar

72
00:03:06.933 --> 00:03:10.180
structures that you have in conventional

73
00:03:10.180 --> 00:03:13.041
classical computer science.

74
00:03:13.041 --> 00:03:16.039
Rather than the more physics based approaches.

75
00:03:16.039 --> 00:03:17.946
That you often get.

76
00:03:17.946 --> 00:03:21.297
So a good starting point here is

77
00:03:21.297 --> 00:03:24.297
classical probabilistic computation.

78
00:03:25.412 --> 00:03:28.866
So here w have a situation where

79
00:03:28.866 --> 00:03:32.389
a computer is described by its configurations.

80
00:03:32.389 --> 00:03:35.493
And they're updated by a sequence of computational steps

81
00:03:35.493 --> 00:03:38.039
which are probabilistic transitions like.

82
00:03:38.039 --> 00:03:40.823
You might think of a Turing machine

83
00:03:40.823 --> 00:03:42.913
and the configurations, you know the description

84
00:03:42.913 --> 00:03:44.168
of the whole Turing machine.

85
00:03:44.168 --> 00:03:45.901
And you have its probabilistic transition rules.

86
00:03:45.901 --> 00:03:49.490
Or in the circuit model of computing

87
00:03:49.490 --> 00:03:51.669
the configuration is the bit sting

88
00:03:51.669 --> 00:03:53.285
on all the lines in circuit.

89
00:03:53.285 --> 00:03:55.883
And it's update by probabilistic choices

90
00:03:55.883 --> 00:03:57.074
of boolean gates.

91
00:03:57.074 --> 00:04:00.478
And then you can think of the computation

92
00:04:00.478 --> 00:04:01.853
as a kind of tree,

93
00:04:01.853 --> 00:04:04.004
a branching tree of possibilities.

94
00:04:04.004 --> 00:04:05.387
You have your starting configuration

95
00:04:05.387 --> 00:04:09.180
and then you go with various probabilities

96
00:04:09.180 --> 00:04:11.423
to other configurations and so on.

97
00:04:11.423 --> 00:04:12.656
And you get this great big growing tree

98
00:04:12.656 --> 00:04:16.768
and to computer the probability of any configuration.

99
00:04:16.768 --> 00:04:19.385
Or in particular the final configuration

100
00:04:19.385 --> 00:04:20.709
which you're often interested in.

101
00:04:20.709 --> 00:04:23.148
You have this some over part rule that

102
00:04:23.148 --> 00:04:27.169
to compute the probability of this configuration

103
00:04:27.169 --> 00:04:31.301
you look at all the paths from the beginning to that thing.

104
00:04:31.301 --> 00:04:34.057
You multiply along the paths of probabilities

105
00:04:34.057 --> 00:04:35.782
and then you sum over all the paths.

106
00:04:35.782 --> 00:04:39.949
Okay so it's just very familiar probability theory.

107
00:04:40.036 --> 00:04:42.612
But it's interesting for us to represent this

108
00:04:42.612 --> 00:04:44.684
in a slightly different algebraic way.

109
00:04:44.684 --> 00:04:47.062
Where you represent the probabilities

110
00:04:47.062 --> 00:04:48.478
as a column vector.

111
00:04:48.478 --> 00:04:52.630
It's just really listing the probability distribution

112
00:04:52.630 --> 00:04:56.630
of each configuration in the state of that time.

113
00:04:58.026 --> 00:04:59.759
So the positions of a configurations

114
00:04:59.759 --> 00:05:01.726
and the entries of the probabilities.

115
00:05:01.726 --> 00:05:04.318
And more formally you can write and introduce names

116
00:05:04.318 --> 00:05:05.856
of the configurations.

117
00:05:05.856 --> 00:05:07.903
And I just put square graphics here

118
00:05:07.903 --> 00:05:10.681
for exactly if you describe this bit stream.

119
00:05:10.681 --> 00:05:11.932
And when you do this,

120
00:05:11.932 --> 00:05:13.917
you can think of this formal use of vector.

121
00:05:13.917 --> 00:05:15.296
Although it's just the way

122
00:05:15.296 --> 00:05:17.580
of encoding all those probabilities.

123
00:05:17.580 --> 00:05:21.186
Then the transition from one step to the next

124
00:05:21.186 --> 00:05:24.675
are always described by a suitable stochastic matrix.

125
00:05:24.675 --> 00:05:27.363
You know familiar sort of matrix

126
00:05:27.363 --> 00:05:29.430
and you know stochastic matrix

127
00:05:29.430 --> 00:05:32.971
is preserved the L1 norm of a vector.

128
00:05:32.971 --> 00:05:36.184
The sum of the absolute values of the entries.

129
00:05:36.184 --> 00:05:39.957
And that guarantees that you keep a bonafide probability

130
00:05:39.957 --> 00:05:41.114
distribution.

131
00:05:41.114 --> 00:05:44.591
Of these linear transformations if you like

132
00:05:44.591 --> 00:05:46.726
and the columns of this matrix

133
00:05:46.726 --> 00:05:49.031
are the transition probabilities

134
00:05:49.031 --> 00:05:52.120
for each individual configuration.

135
00:05:52.120 --> 00:05:55.243
The ice column tells you what the ice configuration

136
00:05:55.243 --> 00:05:56.306
is going to do.

137
00:05:56.306 --> 00:05:57.816
And then

138
00:05:57.816 --> 00:06:01.983
the virtue of this is that this kind of idea of summing

139
00:06:02.479 --> 00:06:05.078
over powers which have been multiplied along,

140
00:06:05.078 --> 00:06:08.715
translated precisely to matrix multiplication.

141
00:06:08.715 --> 00:06:11.285
Which is a nice algebraic thing.

142
00:06:11.285 --> 00:06:14.912
Okay so that's classical probabilistic computing

143
00:06:14.912 --> 00:06:17.592
and now to do quantum computing.

144
00:06:17.592 --> 00:06:20.342
We just generalize this slightly.

145
00:06:21.200 --> 00:06:25.367
So again we have this branching tree just like before and...

146
00:06:26.876 --> 00:06:28.679
Actually I should put some labels...

147
00:06:28.679 --> 00:06:31.178
So it's labeled again but I finished those labels.

148
00:06:31.178 --> 00:06:33.342
Before we had probabilities on the labels

149
00:06:33.342 --> 00:06:35.312
Now we're simply going to

150
00:06:35.312 --> 00:06:38.473
put arbitrary numbers on the labels.

151
00:06:38.473 --> 00:06:41.089
We call them probability amplitudes

152
00:06:41.089 --> 00:06:42.753
we just call them that.

153
00:06:42.753 --> 00:06:44.249
They're not probabilities.

154
00:06:44.249 --> 00:06:46.582
And they can even be complex

155
00:06:47.499 --> 00:06:50.728
they can be positive or negative reels or even complex

156
00:06:50.728 --> 00:06:52.019
more tropically.

157
00:06:52.019 --> 00:06:54.937
And they're required to have the property

158
00:06:54.937 --> 00:06:58.151
analogous to the sum of probabilities adding up to one.

159
00:06:58.151 --> 00:07:01.057
That the sum of the squares have to add up to one.

160
00:07:01.057 --> 00:07:05.137
So we're kind of going from the L1 norm being one

161
00:07:05.137 --> 00:07:07.285
just the absolute values to the squares.

162
00:07:07.285 --> 00:07:08.429
The L2 norm being what?

163
00:07:08.429 --> 00:07:11.706
And it's this apparently innocuous

164
00:07:11.706 --> 00:07:13.706
or you know rather slick

165
00:07:14.700 --> 00:07:16.629
tiny mathematical change.

166
00:07:16.629 --> 00:07:19.630
That had hugely immense implications

167
00:07:19.630 --> 00:07:21.731
you know that we'll see.

168
00:07:21.731 --> 00:07:24.834
But and again so these amplitudes

169
00:07:24.834 --> 00:07:28.577
have for us here no direct physical significance

170
00:07:28.577 --> 00:07:29.736
computationally.

171
00:07:29.736 --> 00:07:32.512
But we have the same rule for

172
00:07:32.512 --> 00:07:35.674
for computing what the amplitude of some

173
00:07:35.674 --> 00:07:37.228
final configuration should be.

174
00:07:37.228 --> 00:07:38.813
We look at all the powers

175
00:07:38.813 --> 00:07:40.855
from the beginning to the end.

176
00:07:40.855 --> 00:07:43.136
We multiply the amplitudes and we add them up.

177
00:07:43.136 --> 00:07:44.384
So just like probabilities

178
00:07:44.384 --> 00:07:48.451
these things are sometimes called probability amplitudes.

179
00:07:48.451 --> 00:07:51.392
And then the bottom line is to come back to reality again.

180
00:07:51.392 --> 00:07:54.232
The probability is deemed to be,

181
00:07:54.232 --> 00:07:55.689
defined to be

182
00:07:55.689 --> 00:07:57.624
the square of this amplitude.

183
00:07:57.624 --> 00:07:59.412
Okay that's a rule.

184
00:07:59.412 --> 00:08:01.091
I mean it's totally stupid

185
00:08:01.091 --> 00:08:04.724
I'm sure if you haven't seen quantum physics before

186
00:08:04.724 --> 00:08:06.774
from computer science to floor

187
00:08:06.774 --> 00:08:08.486
is absolutely ridiculous right?

188
00:08:08.486 --> 00:08:09.895
As a model of computing.

189
00:08:09.895 --> 00:08:14.062
But again we can do the same kind of algebraic thing

190
00:08:14.931 --> 00:08:17.501
and to emphasize that it is kind of silly

191
00:08:17.501 --> 00:08:20.246
we use a silly notation for vectors.

192
00:08:20.246 --> 00:08:23.236
We have this asymmetrical bracket notation.

193
00:08:23.236 --> 00:08:26.619
Cause I gather I'm not a mathematician

194
00:08:26.619 --> 00:08:28.275
but I gather in computer science.

195
00:08:28.275 --> 00:08:31.336
Computer scientists are unable to parse expressions

196
00:08:31.336 --> 00:08:34.108
that they're non matching brackets.

197
00:08:34.108 --> 00:08:35.467
(laughing)

198
00:08:35.467 --> 00:08:36.755
So it makes it really difficult.

199
00:08:36.755 --> 00:08:38.903
But anyhow so we just use that

200
00:08:38.903 --> 00:08:41.244
you know it's called a bracket notation

201
00:08:41.244 --> 00:08:44.708
but for us it's nothing more than just the notation.

202
00:08:44.708 --> 00:08:47.047
And now we have the amplitude

203
00:08:47.047 --> 00:08:50.725
so it kind of, just a way of including amplitude.

204
00:08:50.725 --> 00:08:54.892
And now the transitions before preserve this probability

205
00:08:55.758 --> 00:08:59.319
condition we want to preserve this L2 norm condition.

206
00:08:59.319 --> 00:09:02.228
So it's like rotations for real numbers,

207
00:09:02.228 --> 00:09:04.669
it preserves the length by some of the squares.

208
00:09:04.669 --> 00:09:06.994
So they're unitary in complex cases.

209
00:09:06.994 --> 00:09:09.628
They're now unitary instead of stochastically

210
00:09:09.628 --> 00:09:10.795
and that's it.

211
00:09:12.515 --> 00:09:14.267
So those are gonna be our transitions

212
00:09:14.267 --> 00:09:15.325
and this is how we get probabilities.

213
00:09:15.325 --> 00:09:18.233
Now there are lots of things

214
00:09:18.233 --> 00:09:20.260
just a glimpse of something here

215
00:09:20.260 --> 00:09:22.761
is that when you have a stochastic matrix

216
00:09:22.761 --> 00:09:26.512
the columns tell you where all the individual

217
00:09:26.512 --> 00:09:29.040
configurations go and they can be arbitrary

218
00:09:29.040 --> 00:09:31.973
different probability distributions.

219
00:09:31.973 --> 00:09:33.552
What any columns you like in a stochastic matrix.

220
00:09:33.552 --> 00:09:37.719
But for unitarity you get this bizarre thing

221
00:09:38.023 --> 00:09:41.549
that a matrix is unitary requires its columns

222
00:09:41.549 --> 00:09:44.094
not only to have length one.

223
00:09:44.094 --> 00:09:47.016
But to actually be off the normal to each other

224
00:09:47.016 --> 00:09:48.023
the Earth orbital.

225
00:09:48.023 --> 00:09:50.648
So you get this bizarre global extra condition

226
00:09:50.648 --> 00:09:53.290
coming in which has no classical analog.

227
00:09:53.290 --> 00:09:56.593
That the transitions out of different configurations

228
00:09:56.593 --> 00:10:00.745
have to somehow be coordinated to be Earth orbital

229
00:10:00.745 --> 00:10:02.265
in this depth of sense.

230
00:10:02.265 --> 00:10:03.777
Which is just totally strange

231
00:10:03.777 --> 00:10:07.883
and no one really knows what's going on here right so.

232
00:10:07.883 --> 00:10:10.158
Okay so that's our model

233
00:10:10.158 --> 00:10:12.599
in terms of our computational process.

234
00:10:12.599 --> 00:10:14.766
And just to recap slightly

235
00:10:16.251 --> 00:10:17.720
there's a few extra ingredients.

236
00:10:17.720 --> 00:10:19.507
If you come for the moment

237
00:10:19.507 --> 00:10:21.347
but just to kind of solidify this.

238
00:10:21.347 --> 00:10:23.792
The very simplest possible example here

239
00:10:23.792 --> 00:10:26.807
in a classical case here's a stochastic matrix

240
00:10:26.807 --> 00:10:30.974
for zero and one going to equal 50, 50 the zero and one.

241
00:10:32.422 --> 00:10:34.829
Zero goes to those and one goes to those.

242
00:10:34.829 --> 00:10:36.511
So here we are,

243
00:10:36.511 --> 00:10:38.209
here's a process of applying this twice

244
00:10:38.209 --> 00:10:42.079
and the probability of seeing zero at the end.

245
00:10:42.079 --> 00:10:44.242
Is you look at the two paths,

246
00:10:44.242 --> 00:10:45.980
you multiply and add, so on.

247
00:10:45.980 --> 00:10:47.781
Basically that's all completely trivial and obvious

248
00:10:47.781 --> 00:10:49.215
and in terms of vectors.

249
00:10:49.215 --> 00:10:52.061
The zero state is the first basic step to the one zero

250
00:10:52.061 --> 00:10:54.561
and the one state is zero one.

251
00:10:56.113 --> 00:10:57.992
The second, you know that's the way we label them.

252
00:10:57.992 --> 00:10:59.607
And it goes to this step then

253
00:10:59.607 --> 00:11:01.435
the half each of zero and one

254
00:11:01.435 --> 00:11:03.323
and then it stays there on the second.

255
00:11:03.323 --> 00:11:04.790
So that's really simple.

256
00:11:04.790 --> 00:11:07.371
And although you have this tree

257
00:11:07.371 --> 00:11:10.242
you can simulate this process by

258
00:11:10.242 --> 00:11:14.409
probabilistic choice of a single path through the tree.

259
00:11:16.310 --> 00:11:19.310
You just toss a coin and go zero one

260
00:11:20.190 --> 00:11:22.249
and toss another coin. You don't have to

261
00:11:22.249 --> 00:11:24.452
kind of look at the tree locally.

262
00:11:24.452 --> 00:11:27.968
In particular if you have bigger trees

263
00:11:27.968 --> 00:11:31.074
they can grow exponentially with depth

264
00:11:31.074 --> 00:11:34.686
and to sample the final distribution of the tree.

265
00:11:34.686 --> 00:11:36.634
You can do it efficiently

266
00:11:36.634 --> 00:11:39.318
you just walk through the tree tossing,

267
00:11:39.318 --> 00:11:40.816
you know making probabilistic choices.

268
00:11:40.816 --> 00:11:43.103
Even though it's an exponential big thing.

269
00:11:43.103 --> 00:11:47.270
So that's a feature of classical probabilistic theory.

270
00:11:47.724 --> 00:11:49.090
Now in a quantum case

271
00:11:49.090 --> 00:11:51.215
according to the rules I've already mentioned.

272
00:11:51.215 --> 00:11:53.826
The simplest analog of what we've just been talking about

273
00:11:53.826 --> 00:11:56.154
is this unitary transformation.

274
00:11:56.154 --> 00:11:58.554
Because you see if I've got zero

275
00:11:58.554 --> 00:12:00.905
if I want the amplitudes to be equal

276
00:12:00.905 --> 00:12:03.497
they have to be one over root two now.

277
00:12:03.497 --> 00:12:06.267
Because I have it square it and add up to one.

278
00:12:06.267 --> 00:12:07.600
And then the one

279
00:12:09.273 --> 00:12:11.633
the transition for one has to be our formula to that.

280
00:12:11.633 --> 00:12:13.445
To be a unitary matrix

281
00:12:13.445 --> 00:12:15.775
so I have to put a minus sign in here.

282
00:12:15.775 --> 00:12:19.942
So one goes to zero and one with plus and minus

283
00:12:20.132 --> 00:12:22.078
one over root two amplitudes.

284
00:12:22.078 --> 00:12:24.047
Which is slightly bizarre

285
00:12:24.047 --> 00:12:26.187
you don't sort of get this in probabilities

286
00:12:26.187 --> 00:12:28.641
and now if you apply our rules.

287
00:12:28.641 --> 00:12:32.231
The probability you get is zero is a half times a half

288
00:12:32.231 --> 00:12:35.565
which is one and the probability you get to one is zero.

289
00:12:35.565 --> 00:12:37.514
It should get a cancellation.

290
00:12:37.514 --> 00:12:41.097
Even though they're a non zero single parts

291
00:12:43.711 --> 00:12:44.976
from zero to one.

292
00:12:44.976 --> 00:12:46.674
The transition is forbidden,

293
00:12:46.674 --> 00:12:48.365
which is very strange.

294
00:12:48.365 --> 00:12:51.698
Probabilistically this can never happen.

295
00:12:52.846 --> 00:12:55.860
So what that means is that somehow

296
00:12:55.860 --> 00:12:57.875
in some real physical sense in this model.

297
00:12:57.875 --> 00:13:02.003
Both of these zeros and ones have to be present

298
00:13:02.003 --> 00:13:05.137
in the intermediate thing in order to

299
00:13:05.137 --> 00:13:08.673
be able to produce this to have to cancel it.

300
00:13:08.673 --> 00:13:11.581
You can't just go along one old thing by some choice.

301
00:13:11.581 --> 00:13:14.776
Lets say they're present in super position

302
00:13:14.776 --> 00:13:18.021
and they interfered destructively at the end.

303
00:13:18.021 --> 00:13:20.789
And so it's, when you've got a tree like this

304
00:13:20.789 --> 00:13:24.773
you cannot simulate it by just looking at some single

305
00:13:24.773 --> 00:13:26.853
part through the tree.

306
00:13:26.853 --> 00:13:28.536
You've gotta somehow embrace the whole thing

307
00:13:28.536 --> 00:13:32.036
and when you get a big tree of some depth.

308
00:13:32.904 --> 00:13:34.666
An exponentially big thing

309
00:13:34.666 --> 00:13:38.124
you're looking at a process that runs in say linear time

310
00:13:38.124 --> 00:13:40.784
but it's doing something exponentially complicated.

311
00:13:40.784 --> 00:13:44.389
So this model, see the magic word of exponential

312
00:13:44.389 --> 00:13:48.101
verses polynomial is coming in here which is undermines

313
00:13:48.101 --> 00:13:50.061
all of complexity theory.

314
00:13:50.061 --> 00:13:52.144
So it kind of sneaked in.

315
00:13:53.779 --> 00:13:56.589
Kind of very unrealistic exponential benefit here

316
00:13:56.589 --> 00:13:59.146
and in fact from computer science point of view.

317
00:13:59.146 --> 00:14:02.480
This is like a bizarre kind of non deterministic

318
00:14:02.480 --> 00:14:04.994
cause you know in computer science

319
00:14:04.994 --> 00:14:07.818
you have probabilistic computing trees, description.

320
00:14:07.818 --> 00:14:10.832
But you also have non deterministic

321
00:14:10.832 --> 00:14:12.852
which is not the same as probabilistic.

322
00:14:12.852 --> 00:14:16.739
That's where all the parts exist in reality.

323
00:14:16.739 --> 00:14:20.250
So for classes like MP and other non deterministic classes.

324
00:14:20.250 --> 00:14:22.990
So it's where you have a tree where

325
00:14:22.990 --> 00:14:25.034
when you have this branching process.

326
00:14:25.034 --> 00:14:26.189
You don't have labels

327
00:14:26.189 --> 00:14:28.319
but the computer duplicates itself

328
00:14:28.319 --> 00:14:31.614
and then you get into two computations going on.

329
00:14:31.614 --> 00:14:33.466
And then duplicates again and so on.

330
00:14:33.466 --> 00:14:36.936
So it's usually regarded as physically unrealistic

331
00:14:36.936 --> 00:14:39.911
that kind of model but useful in theory

332
00:14:39.911 --> 00:14:42.730
for like definition of MP and so on.

333
00:14:42.730 --> 00:14:43.914
But here

334
00:14:43.914 --> 00:14:46.943
we've got this bizarre ingredient

335
00:14:46.943 --> 00:14:49.052
that the model actually is offering us.

336
00:14:49.052 --> 00:14:52.659
Real non determinism in this strangely weighted manner

337
00:14:52.659 --> 00:14:55.326
with the previously rural though

338
00:14:57.437 --> 00:15:00.345
for finally getting probability there at the end.

339
00:15:00.345 --> 00:15:02.001
Okay so,

340
00:15:02.001 --> 00:15:05.917
this comes already comes out of this very strange model.

341
00:15:05.917 --> 00:15:07.866
So more specifically

342
00:15:07.866 --> 00:15:10.009
now if you think of certain model.

343
00:15:10.009 --> 00:15:12.002
Which is what we're always doing here

344
00:15:12.002 --> 00:15:14.668
just no comedy on computing.

345
00:15:14.668 --> 00:15:15.928
In a classical case

346
00:15:15.928 --> 00:15:17.345
we have out stage

347
00:15:18.677 --> 00:15:20.158
which is described by its probability distribution.

348
00:15:20.158 --> 00:15:23.816
And it's updated by these local stochastic choices of

349
00:15:23.816 --> 00:15:24.983
boolean gates.

350
00:15:26.358 --> 00:15:28.598
And to find the final distribution

351
00:15:28.598 --> 00:15:31.817
we sample individual distributions along the way

352
00:15:31.817 --> 00:15:35.012
and carry along just a single computational power.

353
00:15:35.012 --> 00:15:38.644
Where as quantumly, we're actuating now by local

354
00:15:38.644 --> 00:15:41.741
unitary gates just like these stochastic things.

355
00:15:41.741 --> 00:15:44.684
And to sample the final distribution

356
00:15:44.684 --> 00:15:48.851
you can't do it by just retaining some small description.

357
00:15:50.319 --> 00:15:53.697
You need generally to carry the full exponentially

358
00:15:53.697 --> 00:15:56.538
varying description of the entire state.

359
00:15:56.538 --> 00:15:59.056
Because unlike probabilistically where

360
00:15:59.056 --> 00:16:01.563
only one of them is really present physically.

361
00:16:01.563 --> 00:16:05.730
Here is some strange sense they're all present

362
00:16:06.057 --> 00:16:08.981
and they have to be to interfere

363
00:16:08.981 --> 00:16:10.395
to give you the right answer.

364
00:16:10.395 --> 00:16:11.679
To possibly interfere.

365
00:16:11.679 --> 00:16:15.334
So you get this very very strange situation

366
00:16:15.334 --> 00:16:18.590
coming out of this rather harmless tweaking

367
00:16:18.590 --> 00:16:20.783
of the initial model.

368
00:16:20.783 --> 00:16:24.533
There's one extra ingredient in the model now

369
00:16:26.125 --> 00:16:28.748
which is a last aspect

370
00:16:28.748 --> 00:16:30.447
which we need to know about.

371
00:16:30.447 --> 00:16:33.553
So this looks to good to be true

372
00:16:33.553 --> 00:16:37.089
we're given exponential parallelism

373
00:16:37.089 --> 00:16:38.805
in some real sense.

374
00:16:38.805 --> 00:16:41.162
It's non determinism for free

375
00:16:41.162 --> 00:16:44.001
but it's not quite as good as that

376
00:16:44.001 --> 00:16:45.859
because there's another issue

377
00:16:45.859 --> 00:16:47.869
with reading out the results.

378
00:16:47.869 --> 00:16:48.864
So I haven't really mentioned before.

379
00:16:48.864 --> 00:16:51.201
So I've said already that if we have a state

380
00:16:51.201 --> 00:16:52.751
with all these amplitudes

381
00:16:52.751 --> 00:16:54.327
for all these different configurations.

382
00:16:54.327 --> 00:16:56.650
The probability of seeing

383
00:16:56.650 --> 00:16:58.139
if you measure them all,

384
00:16:58.139 --> 00:17:00.167
the whole identity configuration.

385
00:17:00.167 --> 00:17:01.566
The probabilities,

386
00:17:01.566 --> 00:17:04.653
it's the square of corresponding amplitude just like that.

387
00:17:04.653 --> 00:17:08.820
But an extra rather awkward thing happens

388
00:17:08.843 --> 00:17:11.463
if you make that measurement.

389
00:17:11.463 --> 00:17:13.791
After the measure the state is no longer that,

390
00:17:13.791 --> 00:17:16.541
it collapses to the thing you saw

391
00:17:19.718 --> 00:17:23.097
and afterwards you've only got a single configuration there.

392
00:17:23.097 --> 00:17:26.558
Now this is just like probabilistically

393
00:17:26.558 --> 00:17:28.553
so if you've got a probability distribution.

394
00:17:28.553 --> 00:17:30.234
You sample it, you see what it is

395
00:17:30.234 --> 00:17:33.152
and that the point is it always that before.

396
00:17:33.152 --> 00:17:36.454
It's not as though you've kind of made it that

397
00:17:36.454 --> 00:17:38.203
you've just seen what it is.

398
00:17:38.203 --> 00:17:40.547
And if you look at it again you'll see the same thing.

399
00:17:40.547 --> 00:17:42.854
But quantumly I've just been arguing

400
00:17:42.854 --> 00:17:46.090
that there's supposed to all be there.

401
00:17:46.090 --> 00:17:48.825
But still when you look at it you destroy all that

402
00:17:48.825 --> 00:17:50.899
and this axiomatic in the theory.

403
00:17:50.899 --> 00:17:54.440
And you're back to the same old classical type situation

404
00:17:54.440 --> 00:17:56.533
where there's only one left

405
00:17:56.533 --> 00:17:59.166
and if you look again you will always see that.

406
00:17:59.166 --> 00:18:00.942
You'll never see one of the other ones anymore.

407
00:18:00.942 --> 00:18:03.176
So that's rather bizarre

408
00:18:03.176 --> 00:18:06.787
and the same thing happens if you only measure

409
00:18:06.787 --> 00:18:08.952
half of these bits.

410
00:18:08.952 --> 00:18:10.582
So if you measure the first bit

411
00:18:10.582 --> 00:18:12.641
you basically you kill off

412
00:18:12.641 --> 00:18:16.503
all the terms except the ones consistent

413
00:18:16.503 --> 00:18:18.989
with whether you've got zero or one.

414
00:18:18.989 --> 00:18:20.236
So you know for the first bit

415
00:18:20.236 --> 00:18:23.643
and then the whole state really normalizes itself

416
00:18:23.643 --> 00:18:25.684
to have length one.

417
00:18:25.684 --> 00:18:28.574
Because you've pulled out part of that state.

418
00:18:28.574 --> 00:18:29.407
So this is

419
00:18:32.651 --> 00:18:35.626
unavoidable disturbance to your measurement.

420
00:18:35.626 --> 00:18:37.792
If you look at something and read it

421
00:18:37.792 --> 00:18:38.878
you have to destroy it.

422
00:18:38.878 --> 00:18:40.628
You can't do anything

423
00:18:41.577 --> 00:18:43.099
that's axiomatic in the rule.

424
00:18:43.099 --> 00:18:45.266
And suddenly all the parts

425
00:18:46.460 --> 00:18:49.367
are you consistent with what we saw just go away.

426
00:18:49.367 --> 00:18:53.534
So basically you see you get this probabilistic information

427
00:18:55.064 --> 00:18:59.231
now when you read things but the thing you kind of

428
00:19:01.180 --> 00:19:02.839
destroy lots of stuff and so basically

429
00:19:02.839 --> 00:19:05.011
although you have this wonderful

430
00:19:05.011 --> 00:19:09.123
non deterministic simultaneous presence of everything

431
00:19:09.123 --> 00:19:10.264
exponentially many three.

432
00:19:10.264 --> 00:19:12.738
If you try and read out what's there

433
00:19:12.738 --> 00:19:15.374
nature is only going to let you

434
00:19:15.374 --> 00:19:18.334
get a tiny amount of information about it.

435
00:19:18.334 --> 00:19:21.021
Cause when you look you kill off

436
00:19:21.021 --> 00:19:23.989
everything except what you asked about basically.

437
00:19:23.989 --> 00:19:27.177
So this is a huge amount of information

438
00:19:27.177 --> 00:19:30.141
being processed with these unitary processes.

439
00:19:30.141 --> 00:19:32.196
In this non deterministic fashion

440
00:19:32.196 --> 00:19:36.029
but at the end of the day we can't read it you

441
00:19:37.368 --> 00:19:39.539
which is kind of strange really.

442
00:19:39.539 --> 00:19:41.136
And that's the end of the model,

443
00:19:41.136 --> 00:19:42.370
that's the whole model.

444
00:19:42.370 --> 00:19:43.419
I haven't left anything out

445
00:19:43.419 --> 00:19:47.114
that is quantum computing basically,

446
00:19:47.114 --> 00:19:49.843
and of course the whole thing is completely ludicrous

447
00:19:49.843 --> 00:19:52.092
from a computer science point of view.

448
00:19:52.092 --> 00:19:54.478
No one would possibly take this

449
00:19:54.478 --> 00:19:56.789
seriously at all for a moment.

450
00:19:56.789 --> 00:19:58.681
Except for the fact that

451
00:19:58.681 --> 00:20:00.185
to the best of our knowledge.

452
00:20:00.185 --> 00:20:04.097
This really is the model that nature presents us with

453
00:20:04.097 --> 00:20:08.264
and I think it's fair to say that nobody knows why.

454
00:20:09.179 --> 00:20:12.054
Nobody knows where it comes from,

455
00:20:12.054 --> 00:20:16.221
and nobody really understands what's going on here.

456
00:20:16.353 --> 00:20:18.936
In any reasonable further sense

457
00:20:20.862 --> 00:20:24.230
and I think from that point of view to me that

458
00:20:24.230 --> 00:20:27.571
the single greatest most fundamental challenge

459
00:20:27.571 --> 00:20:29.704
of the whole subject of quantum computing

460
00:20:29.704 --> 00:20:32.430
is to shed light on just this issue.

461
00:20:32.430 --> 00:20:35.066
I think it's the most important thing we can do.

462
00:20:35.066 --> 00:20:38.190
But another important challenge

463
00:20:38.190 --> 00:20:40.419
which I guess a lot of other people would think

464
00:20:40.419 --> 00:20:42.402
is probably the most important challenge.

465
00:20:42.402 --> 00:20:44.215
Is of a more practical nature

466
00:20:44.215 --> 00:20:45.842
is given this strange model

467
00:20:45.842 --> 00:20:48.509
which we're stuck with it seems.

468
00:20:49.948 --> 00:20:52.041
It's not very intuitive

469
00:20:52.041 --> 00:20:54.758
how can we exploit it and use it

470
00:20:54.758 --> 00:20:57.324
to do interesting computational things.

471
00:20:57.324 --> 00:20:59.437
I meant it's not very hard to see that

472
00:20:59.437 --> 00:21:02.877
you can do all of classical computing

473
00:21:02.877 --> 00:21:04.323
as a special case of this.

474
00:21:04.323 --> 00:21:05.925
Might not be immediately obvious

475
00:21:05.925 --> 00:21:07.743
but it's actually not very hard to see.

476
00:21:07.743 --> 00:21:10.828
And so we're kind of interested in what more you can do,

477
00:21:10.828 --> 00:21:13.857
what do we get from this more powerful event

478
00:21:13.857 --> 00:21:17.805
that transcends the possibilities of classical computing

479
00:21:17.805 --> 00:21:18.964
and there are lots of things.

480
00:21:18.964 --> 00:21:21.261
But that's not really what I'm gonna talk about in this talk

481
00:21:21.261 --> 00:21:24.769
specifically I'm not gonna give sort of accounts of

482
00:21:24.769 --> 00:21:26.319
algorithms and things.

483
00:21:26.319 --> 00:21:30.486
But that second issue respects very much on the first issue

484
00:21:30.555 --> 00:21:34.490
because if you understand something about

485
00:21:34.490 --> 00:21:38.176
the limitations and possibilities of these crazy rules.

486
00:21:38.176 --> 00:21:41.464
It might give you some idea as to why they are as they are.

487
00:21:41.464 --> 00:21:45.258
Why the rules have that form just in some way.

488
00:21:45.258 --> 00:21:48.099
So that's very helpful too.

489
00:21:48.099 --> 00:21:50.766
So if you want to use this model

490
00:21:52.542 --> 00:21:54.423
the first obvious thing to do

491
00:21:54.423 --> 00:21:57.923
is to try and exploit this non determinism

492
00:21:59.378 --> 00:22:01.598
exactly as we do in classical theory.

493
00:22:01.598 --> 00:22:05.250
Like for NP if you want to solve satisfiability

494
00:22:05.250 --> 00:22:08.672
well what do you do, you non deterministically

495
00:22:08.672 --> 00:22:10.989
compute all the values of the function

496
00:22:10.989 --> 00:22:12.906
and see if there's a one right.

497
00:22:12.906 --> 00:22:15.266
So we could actually do that here you see.

498
00:22:15.266 --> 00:22:17.394
So that's what we do,

499
00:22:17.394 --> 00:22:19.549
we can if we have boolean function

500
00:22:19.549 --> 00:22:21.926
that's say sufficiently computable and this one bit.

501
00:22:21.926 --> 00:22:24.869
Then it's very easy quantumly to set up or register that

502
00:22:24.869 --> 00:22:27.568
in a unique super position of equal amplitudes

503
00:22:27.568 --> 00:22:30.931
of all possible two to the N extremes.

504
00:22:30.931 --> 00:22:32.977
It's this exponentially big tree of just

505
00:22:32.977 --> 00:22:36.115
and linear number of splittings so here it is

506
00:22:36.115 --> 00:22:39.010
this H operator of simple have a nine

507
00:22:39.010 --> 00:22:41.269
as I mentioned before.

508
00:22:41.269 --> 00:22:43.052
And then you just feed that into the function

509
00:22:43.052 --> 00:22:46.546
and you get this state of the computer

510
00:22:46.546 --> 00:22:50.253
that physically genuinely embodies and then codes

511
00:22:50.253 --> 00:22:51.776
all the values of the function.

512
00:22:51.776 --> 00:22:53.594
All explaining of them

513
00:22:53.594 --> 00:22:56.772
and the cost of one evaluation

514
00:22:56.772 --> 00:22:59.938
of the function on your computer so that's pretty good.

515
00:22:59.938 --> 00:23:02.998
And we knows however unfortunately that

516
00:23:02.998 --> 00:23:05.408
we can't get lots of information

517
00:23:05.408 --> 00:23:07.001
about this state.

518
00:23:07.001 --> 00:23:10.720
Intuitively so I'm jut sort of talking intuitively here.

519
00:23:10.720 --> 00:23:13.935
But we can get small amounts of information about it.

520
00:23:13.935 --> 00:23:18.102
And the point now is this small amount of information

521
00:23:18.284 --> 00:23:20.020
about this whole state can be joint information

522
00:23:20.020 --> 00:23:23.603
about all the values rather than asking say

523
00:23:24.588 --> 00:23:27.883
for a particular value or something.

524
00:23:27.883 --> 00:23:32.050
So for example satisfiability is just one bit of information

525
00:23:32.166 --> 00:23:35.593
it just asks is there a one in the list or isn't there.

526
00:23:35.593 --> 00:23:36.679
Yes or no.

527
00:23:36.679 --> 00:23:39.133
That's a small amount of information about exponential stuff

528
00:23:39.133 --> 00:23:41.390
but classically it's hard to get.

529
00:23:41.390 --> 00:23:43.112
You know as we all think.

530
00:23:43.112 --> 00:23:45.445
However unfortunately for us

531
00:23:47.256 --> 00:23:49.378
it's the wrong kind of information

532
00:23:49.378 --> 00:23:50.378
with our fancy quantum model.

533
00:23:50.378 --> 00:23:53.461
We can't get that information either.

534
00:23:54.450 --> 00:23:56.783
I mean the point is although

535
00:23:57.961 --> 00:23:59.473
we can get small amounts of information,

536
00:23:59.473 --> 00:24:01.646
we can't get any kind of information at all.

537
00:24:01.646 --> 00:24:03.762
There's rather subtle restrictions on

538
00:24:03.762 --> 00:24:05.441
what we're able to do

539
00:24:05.441 --> 00:24:08.029
and this is the blackout of designing

540
00:24:08.029 --> 00:24:10.617
quantum algorithms or exploiting them for models

541
00:24:10.617 --> 00:24:12.496
to try and understand them.

542
00:24:12.496 --> 00:24:14.821
And in fact in this case it's satisfiability

543
00:24:14.821 --> 00:24:16.843
there's simple provers,

544
00:24:16.843 --> 00:24:18.448
quantum searching algorithm

545
00:24:18.448 --> 00:24:22.047
or in a matching lower bound which

546
00:24:22.047 --> 00:24:24.409
basically all put together say that.

547
00:24:24.409 --> 00:24:27.696
If you use the function as just a black box

548
00:24:27.696 --> 00:24:30.330
and evaluate super positions of values.

549
00:24:30.330 --> 00:24:33.044
And don't look at the structure of the function

550
00:24:33.044 --> 00:24:34.846
through more complicated things

551
00:24:34.846 --> 00:24:38.929
then any quantum process what so ever of the sort

552
00:24:40.542 --> 00:24:43.272
like described must use the box

553
00:24:43.272 --> 00:24:45.619
about root two to the n times.

554
00:24:45.619 --> 00:24:49.337
So you do get, and you can do it with that many times.

555
00:24:49.337 --> 00:24:52.611
So you can solve satisfiability

556
00:24:52.611 --> 00:24:54.920
with a quadratics speed up mover

557
00:24:54.920 --> 00:24:56.869
classical algorithms.

558
00:24:56.869 --> 00:24:59.488
But not at exponential speed

559
00:24:59.488 --> 00:25:01.566
you can't exploit this

560
00:25:01.566 --> 00:25:04.399
you know this exponential parallel

561
00:25:06.918 --> 00:25:09.268
this non determinism that we seem to have been given

562
00:25:09.268 --> 00:25:10.906
because we can't read it out.

563
00:25:10.906 --> 00:25:13.787
There are other kinds of information

564
00:25:13.787 --> 00:25:17.080
that are better and I haven't written them down here.

565
00:25:17.080 --> 00:25:19.648
Perhaps the most famous example is if

566
00:25:19.648 --> 00:25:22.435
you have a periodic function in a more general context

567
00:25:22.435 --> 00:25:25.372
you have lots of values of the function.

568
00:25:25.372 --> 00:25:27.270
And it's period is one number

569
00:25:27.270 --> 00:25:29.457
so it's a small matter of information that long

570
00:25:29.457 --> 00:25:32.994
and that you can get the period about quantumly,

571
00:25:32.994 --> 00:25:37.161
exponentially faster that any known possible method.

572
00:25:39.264 --> 00:25:42.514
For example so the problem here is that

573
00:25:43.462 --> 00:25:46.823
this is too unstable under small changes.

574
00:25:46.823 --> 00:25:49.248
If you have a function that's uniquely satisfiable

575
00:25:49.248 --> 00:25:53.415
if you flip a single bit the answer changes.

576
00:25:53.632 --> 00:25:56.149
But if you have a periodic function

577
00:25:56.149 --> 00:25:58.978
and you mess around with a few of its values

578
00:25:58.978 --> 00:26:00.678
you'll still see the period.

579
00:26:00.678 --> 00:26:03.711
It's like pattern recognition that's still there.

580
00:26:03.711 --> 00:26:06.680
It takes a lot of effort to destroy the pattern.

581
00:26:06.680 --> 00:26:10.175
So you need that kind of stability obviously.

582
00:26:10.175 --> 00:26:12.603
Okay but on a more general

583
00:26:12.603 --> 00:26:15.533
so this issue and I just want to say a few kind of

584
00:26:15.533 --> 00:26:16.603
intuitive words about this.

585
00:26:16.603 --> 00:26:19.177
Which is not often raised actually in subject

586
00:26:19.177 --> 00:26:21.582
is we're all scrambling around

587
00:26:21.582 --> 00:26:23.526
looking for good quantum algorithms

588
00:26:23.526 --> 00:26:25.048
but how do we go about doing this?

589
00:26:25.048 --> 00:26:26.987
And I'm not really sure myself,

590
00:26:26.987 --> 00:26:29.511
how do you find, how do you use this model?

591
00:26:29.511 --> 00:26:33.360
And it seems to me it's completely different

592
00:26:33.360 --> 00:26:35.917
from looking for new classical algorithms.

593
00:26:35.917 --> 00:26:38.915
It's not the same problem at all.

594
00:26:38.915 --> 00:26:41.879
It seems to be what typically has happened

595
00:26:41.879 --> 00:26:43.763
is you use these lucky coincidences

596
00:26:43.763 --> 00:26:47.763
between well known bits of nice pure mathematics

597
00:26:48.798 --> 00:26:52.234
and the mathematical form of the physical theory.

598
00:26:52.234 --> 00:26:53.983
Because roughly speaking

599
00:26:53.983 --> 00:26:57.279
computational problems are formulated mathematically

600
00:26:57.279 --> 00:26:59.103
in later pure mathematics

601
00:26:59.103 --> 00:27:03.013
and then mature mathematics also feeds it's physics

602
00:27:03.013 --> 00:27:05.231
by the equation of physics

603
00:27:05.231 --> 00:27:08.005
and then physics goes out and implements that quantumly.

604
00:27:08.005 --> 00:27:10.593
So this provides a link from computational tasks

605
00:27:10.593 --> 00:27:12.747
all the way over to the physics.

606
00:27:12.747 --> 00:27:16.341
The really good example of this is

607
00:27:16.341 --> 00:27:18.223
that the street forecast for

608
00:27:18.223 --> 00:27:20.671
which has been known hundreds of year.

609
00:27:20.671 --> 00:27:22.815
It's this beautiful construction

610
00:27:22.815 --> 00:27:24.405
in street mathematics.

611
00:27:24.405 --> 00:27:27.722
And it's a linear, it's a matrix.

612
00:27:27.722 --> 00:27:28.990
Linear transformation

613
00:27:28.990 --> 00:27:30.588
and it's unitary, magical,

614
00:27:30.588 --> 00:27:32.892
that sort of sets all the lights on for us

615
00:27:32.892 --> 00:27:36.722
because quantumly unitary things that are quantum evolution.

616
00:27:36.722 --> 00:27:40.128
So this is gonna be good for quantum algorithms

617
00:27:40.128 --> 00:27:41.131
in fact it really is.

618
00:27:41.131 --> 00:27:44.230
And it's good to have it for quantum evolution

619
00:27:44.230 --> 00:27:47.255
and it's this coincidence that gives us Shor's

620
00:27:47.255 --> 00:27:48.368
factory model basically.

621
00:27:48.368 --> 00:27:51.163
So the problem of factoring an integer

622
00:27:51.163 --> 00:27:55.224
you know just very briefly using some very old number theory

623
00:27:55.224 --> 00:27:57.432
what was known for 200 years from the genre.

624
00:27:57.432 --> 00:28:01.427
You can burst that into a problem of periodicity

625
00:28:01.427 --> 00:28:03.523
of a function of integers.

626
00:28:03.523 --> 00:28:06.833
And then it's well known that for a transforms

627
00:28:06.833 --> 00:28:09.771
in classical image processing all that good for instructing

628
00:28:09.771 --> 00:28:13.314
date, information about periodic data.

629
00:28:13.314 --> 00:28:15.568
And you use that here in quantum speculating

630
00:28:15.568 --> 00:28:18.712
and you get your period out once you get your flat rate.

631
00:28:18.712 --> 00:28:21.105
So it's that coincidence that works

632
00:28:21.105 --> 00:28:24.587
but on the other hand if you are required to find the new

633
00:28:24.587 --> 00:28:26.581
classical factoring algorithm.

634
00:28:26.581 --> 00:28:28.021
What would you do?

635
00:28:28.021 --> 00:28:30.667
Well you'd probably go to the library

636
00:28:30.667 --> 00:28:34.834
and or online as these days and look at all the latest

637
00:28:34.963 --> 00:28:37.020
research journals in London theorem

638
00:28:37.020 --> 00:28:40.353
and see what the latest theorem about this module

639
00:28:40.353 --> 00:28:42.766
is that is and try and...

640
00:28:42.766 --> 00:28:45.080
You need mathematics basically

641
00:28:45.080 --> 00:28:47.345
which is completely different approach.

642
00:28:47.345 --> 00:28:51.512
So it's totally different from scopic stereo system

643
00:28:51.788 --> 00:28:53.371
out to use of soap.

644
00:28:54.292 --> 00:28:58.218
A notable feature about these quantum beneficial

645
00:28:58.218 --> 00:29:02.139
that we mentioned which is worth emphasizing.

646
00:29:02.139 --> 00:29:06.306
It's important that the computational data we're processing,

647
00:29:06.437 --> 00:29:10.604
it needs to be coded in a kind of quantum forms amplitudes.

648
00:29:12.373 --> 00:29:15.026
And not in a familiar classical form

649
00:29:15.026 --> 00:29:19.193
which results in exponentially smaller physical system.

650
00:29:19.573 --> 00:29:23.717
So by that I mean that if you think again about our ability

651
00:29:23.717 --> 00:29:25.109
and function to n bits.

652
00:29:25.109 --> 00:29:27.594
If you wanna represent the values of that function

653
00:29:27.594 --> 00:29:29.461
classically it's a great big bits string

654
00:29:29.461 --> 00:29:33.628
of exponential length, two to the n of all the values.

655
00:29:33.820 --> 00:29:35.427
Just about three long.

656
00:29:35.427 --> 00:29:39.344
But quantumly we only have n or n+1 cubics

657
00:29:40.656 --> 00:29:43.120
in our space, exponentially smaller so.

658
00:29:43.120 --> 00:29:45.599
What I'm thinking about is this state

659
00:29:45.599 --> 00:29:48.008
there are n bits here

660
00:29:48.008 --> 00:29:49.972
and another single bits.

661
00:29:49.972 --> 00:29:53.275
So it's n plus so this system is only this big

662
00:29:53.275 --> 00:29:54.552
whereas exponential is much bigger right.

663
00:29:54.552 --> 00:29:57.371
So it's exponentially smaller

664
00:29:57.371 --> 00:29:59.705
than the classical representation

665
00:29:59.705 --> 00:30:03.405
and the way I've represented my values

666
00:30:03.405 --> 00:30:05.422
is by eliminating some terms.

667
00:30:05.422 --> 00:30:08.268
It's all to do with whatever is a zero or

668
00:30:08.268 --> 00:30:10.851
the one over two to the n here.

669
00:30:11.698 --> 00:30:13.635
I've only kept those n+1 bit strings

670
00:30:13.635 --> 00:30:17.779
where the last bit is the correct value of the previous bit.

671
00:30:17.779 --> 00:30:20.612
So the information is somehow been

672
00:30:21.488 --> 00:30:24.325
represented non deterministically.

673
00:30:24.325 --> 00:30:27.107
I only need one little register

674
00:30:27.107 --> 00:30:30.599
but I can represent non deterministically

675
00:30:30.599 --> 00:30:33.053
exponentially any possibilities in there.

676
00:30:33.053 --> 00:30:37.220
And this is a very important feature of quantum computing

677
00:30:38.262 --> 00:30:39.822
and registers.

678
00:30:39.822 --> 00:30:43.989
Because a gentle state then cubics has all of these general

679
00:30:44.602 --> 00:30:48.372
amplitudes here and there's exponentially many of them.

680
00:30:48.372 --> 00:30:51.467
And this goes onto the name of entanglement

681
00:30:51.467 --> 00:30:55.056
verses for example a product state.

682
00:30:55.056 --> 00:30:59.139
So in this state the individual cubics themselves

683
00:31:01.654 --> 00:31:03.902
don't even have a definite quantum state

684
00:31:03.902 --> 00:31:05.860
for what we're talking about.

685
00:31:05.860 --> 00:31:08.381
If they did each one would just be zero or one

686
00:31:08.381 --> 00:31:12.005
with some amplitudes and so here they are all

687
00:31:12.005 --> 00:31:14.907
stuck next to each other.

688
00:31:14.907 --> 00:31:18.681
The various parameters is linear here is two n,

689
00:31:18.681 --> 00:31:21.061
whereas here it's exponential.

690
00:31:21.061 --> 00:31:23.410
So this corresponds to all factors

691
00:31:23.410 --> 00:31:27.182
special case this is factorized the simple product state.

692
00:31:27.182 --> 00:31:30.349
So the moral here is quantum mechanics

693
00:31:31.645 --> 00:31:34.823
the whole is much greater than the sum of the parts

694
00:31:34.823 --> 00:31:38.899
whereas in classical physics the whole is nothing more

695
00:31:38.899 --> 00:31:39.963
than the sum of the parts.

696
00:31:39.963 --> 00:31:44.130
Any classical, physical, definite state of a composite

697
00:31:44.261 --> 00:31:46.975
system will always looks like this.

698
00:31:46.975 --> 00:31:49.976
It's always a definite state of all the separate systems

699
00:31:49.976 --> 00:31:51.174
stuck next to each other.

700
00:31:51.174 --> 00:31:54.599
But quantumly you get this much richer structure

701
00:31:54.599 --> 00:31:57.185
of these kind of internal correlations

702
00:31:57.185 --> 00:31:59.654
between there's all sorts of mysterious

703
00:31:59.654 --> 00:32:01.751
quantum correlations built into this state.

704
00:32:01.751 --> 00:32:04.632
Which gives you this exponential complexity.

705
00:32:04.632 --> 00:32:07.465
So you can get this more entangled

706
00:32:08.483 --> 00:32:10.650
more often just like that.

707
00:32:16.002 --> 00:32:18.585
So now shifting gears slightly.

708
00:32:20.359 --> 00:32:23.062
Instead of trying to describe some specific algorithms

709
00:32:23.062 --> 00:32:24.812
that are of interest.

710
00:32:26.717 --> 00:32:28.935
Using this new model,

711
00:32:28.935 --> 00:32:30.834
I've kind of got a more abstract way of

712
00:32:30.834 --> 00:32:33.565
studying its relationship to classical computing

713
00:32:33.565 --> 00:32:35.024
which we're very interested in

714
00:32:35.024 --> 00:32:39.191
is to study the extent to which these quantum processors

715
00:32:40.641 --> 00:32:43.579
can be simulated on a classical computer.

716
00:32:43.579 --> 00:32:46.299
How much computing effort is required.

717
00:32:46.299 --> 00:32:49.380
Perhaps in various restrictive situations.

718
00:32:49.380 --> 00:32:52.380
And that will give us a kind of idea

719
00:32:54.265 --> 00:32:56.136
and if we restrict situations

720
00:32:56.136 --> 00:32:59.124
where sometimes it's easy to simulate.

721
00:32:59.124 --> 00:33:03.259
Then we can ask which quantum feature should we add in

722
00:33:03.259 --> 00:33:04.581
to make the parts simulate.

723
00:33:04.581 --> 00:33:08.372
And it gives you some idea of the kind of quantum

724
00:33:08.372 --> 00:33:10.649
ingredients needed to get computing power.

725
00:33:10.649 --> 00:33:12.739
So it's this very interesting things

726
00:33:12.739 --> 00:33:15.159
and this is something I think made me

727
00:33:15.159 --> 00:33:16.603
interested in a long time.

728
00:33:16.603 --> 00:33:18.339
So which is why I wanted to talk about it.

729
00:33:18.339 --> 00:33:21.035
To formalize a bit more,

730
00:33:21.035 --> 00:33:23.169
the issue here is given.

731
00:33:23.169 --> 00:33:25.417
So we think of a circuit now

732
00:33:25.417 --> 00:33:27.274
which is like boolean gates that live out

733
00:33:27.274 --> 00:33:29.898
as unitary operations these matrices.

734
00:33:29.898 --> 00:33:32.518
So it's a list of gates

735
00:33:32.518 --> 00:33:34.965
and you're told which lines they act on

736
00:33:34.965 --> 00:33:36.090
on n cubic lines.

737
00:33:36.090 --> 00:33:38.699
The input could be just a bit string

738
00:33:38.699 --> 00:33:41.793
or will generally product state.

739
00:33:41.793 --> 00:33:44.207
Which is only polynomial complex anyhow

740
00:33:44.207 --> 00:33:46.927
that's usually a reasonable thing to do.

741
00:33:46.927 --> 00:33:49.262
It's still a manageable thing.

742
00:33:49.262 --> 00:33:52.501
And the output could be a single line for a decision problem

743
00:33:52.501 --> 00:33:54.413
yes or no question.

744
00:33:54.413 --> 00:33:57.580
Or could be many lines for situations.

745
00:33:58.537 --> 00:34:01.476
And the circuit has some sides,

746
00:34:01.476 --> 00:34:04.144
number of cases which is usually polynomial

747
00:34:04.144 --> 00:34:05.949
in the number of light.

748
00:34:05.949 --> 00:34:08.799
So we have a polysized circuit light,

749
00:34:08.799 --> 00:34:10.882
polynomial time quantum computation.

750
00:34:10.882 --> 00:34:13.397
And this is all classical data

751
00:34:13.397 --> 00:34:15.225
you write all this down on a piece of paper.

752
00:34:15.225 --> 00:34:19.058
So and you can give it to a quantum technician

753
00:34:21.122 --> 00:34:23.282
to take down to the lab and implement it

754
00:34:23.282 --> 00:34:24.822
to tell you the answer right.

755
00:34:24.822 --> 00:34:27.735
But what we're interested in doing it classically

756
00:34:27.735 --> 00:34:30.622
given this classical description of the quantum contest

757
00:34:30.622 --> 00:34:34.272
we want to simulate this weak simulation strong simulation.

758
00:34:34.272 --> 00:34:38.439
So weak simulation is where you ask simply for a sample

759
00:34:39.066 --> 00:34:41.987
of the output distribution that it produces.

760
00:34:41.987 --> 00:34:43.880
But you want to produce this sample

761
00:34:43.880 --> 00:34:46.095
only by classical means and classical rampant forces.

762
00:34:46.095 --> 00:34:50.262
Or strong simulation asks you to actually calculate

763
00:34:51.564 --> 00:34:54.442
the output probability so it's asking for more.

764
00:34:54.442 --> 00:34:57.199
Any output or orbit marginal distribution.

765
00:34:57.199 --> 00:35:01.366
And these simulations we could ask the computer coefficient.

766
00:35:02.802 --> 00:35:05.806
So we want them to be in polynomial time

767
00:35:05.806 --> 00:35:07.286
in the size of the circuit.

768
00:35:07.286 --> 00:35:10.900
So that means that it's only a polynomial

769
00:35:10.900 --> 00:35:14.159
overhead in the time that the actual quantum

770
00:35:14.159 --> 00:35:15.876
process itself runs as well.

771
00:35:15.876 --> 00:35:20.043
But cake is obviously all the rules of quantum computing

772
00:35:20.753 --> 00:35:22.336
that I mentioned in the beginning.

773
00:35:22.336 --> 00:35:23.664
They are all computable

774
00:35:23.664 --> 00:35:26.585
you know you can actually work them all out.

775
00:35:26.585 --> 00:35:29.049
But that it may take exponential time

776
00:35:29.049 --> 00:35:32.397
as I sort of described about the exponential

777
00:35:32.397 --> 00:35:35.553
complexity of these vectors we have to carry along

778
00:35:35.553 --> 00:35:37.653
in this computation.

779
00:35:37.653 --> 00:35:40.326
So in a strong simulation we will cover these things

780
00:35:40.326 --> 00:35:42.326
and so a few remarks is.

781
00:35:49.173 --> 00:35:52.183
That strong simulation requires weak simulation

782
00:35:52.183 --> 00:35:53.479
if you calculate probability

783
00:35:53.479 --> 00:35:55.281
if you can sample.

784
00:35:55.281 --> 00:35:56.966
Now that's not immediately obvious

785
00:35:56.966 --> 00:35:59.924
because if you've got probabilities or n bit strings.

786
00:35:59.924 --> 00:36:01.719
There're exponentially many of them

787
00:36:01.719 --> 00:36:04.254
and if you can calculate each one in poly time.

788
00:36:04.254 --> 00:36:06.917
How do you sample a distribution?

789
00:36:06.917 --> 00:36:10.929
And for that you need the marginals to do that

790
00:36:10.929 --> 00:36:12.929
there's a trick to do that if you've got the marginals

791
00:36:12.929 --> 00:36:14.796
as well if you can calculate them.

792
00:36:14.796 --> 00:36:18.963
But if you threw out the marginals you can't do that.

793
00:36:19.988 --> 00:36:21.830
The other way if you can sample

794
00:36:21.830 --> 00:36:25.596
it does not imply that you can strongly simulate

795
00:36:25.596 --> 00:36:27.181
the quantum process.

796
00:36:27.181 --> 00:36:28.847
Or at least in the sense if it did,

797
00:36:28.847 --> 00:36:32.477
if you could strongly simulate and weakly simulate

798
00:36:32.477 --> 00:36:33.482
those quantum process.

799
00:36:33.482 --> 00:36:35.026
It's pretty easy to see

800
00:36:35.026 --> 00:36:38.750
that implies that P = NP or even sharp P.

801
00:36:38.750 --> 00:36:40.481
It's a very drastic thing

802
00:36:40.481 --> 00:36:42.590
so you certainly don't expect that.

803
00:36:42.590 --> 00:36:44.777
On the other hand a weak simulation is

804
00:36:44.777 --> 00:36:48.631
what we're really interested in physically

805
00:36:48.631 --> 00:36:51.903
because if you run the quantum process itself

806
00:36:51.903 --> 00:36:54.070
in your quantum lab.

807
00:36:54.070 --> 00:36:56.929
It only gives you a sample at the end anyhow

808
00:36:56.929 --> 00:36:58.257
you don't calculate probability.

809
00:36:58.257 --> 00:37:02.424
So the weak simulation is what the quantum process gives you

810
00:37:02.723 --> 00:37:06.890
and it's that which you're trying to replicate classically.

811
00:37:07.752 --> 00:37:11.167
And if you can match that with polynomial overhead

812
00:37:11.167 --> 00:37:13.660
it means your quantum process is lame

813
00:37:13.660 --> 00:37:15.970
as far as computing power is concerned.

814
00:37:15.970 --> 00:37:18.746
It's just as good as the corresponding,

815
00:37:18.746 --> 00:37:19.746
it's no better that.

816
00:37:19.746 --> 00:37:22.339
So if given all these ideas

817
00:37:22.339 --> 00:37:26.267
it's interesting to then find situations

818
00:37:26.267 --> 00:37:29.082
which are classically efficient and simulatable.

819
00:37:29.082 --> 00:37:32.832
Given all these exponential kind of ingredients

820
00:37:32.832 --> 00:37:34.027
in the model.

821
00:37:34.027 --> 00:37:37.749
So they're very important for many situations.

822
00:37:37.749 --> 00:37:41.286
Perhaps though more interestingly

823
00:37:41.286 --> 00:37:45.453
given such a class perhaps some restricted class of circuits

824
00:37:46.212 --> 00:37:50.024
that are simulatable, what extra features suffices to regain

825
00:37:50.024 --> 00:37:53.607
full universal quantum computing.

826
00:37:53.607 --> 00:37:57.607
And this extra ingredient in some definite sense

827
00:37:58.511 --> 00:38:01.777
the candidate for this mystery quantum resource

828
00:38:01.777 --> 00:38:05.944
that gives you super classical computing power.

829
00:38:06.272 --> 00:38:08.365
So a lot of these things have been studied

830
00:38:08.365 --> 00:38:11.365
so I just listed a few results here.

831
00:38:12.431 --> 00:38:16.594
This idea of calculating probabilities being

832
00:38:16.594 --> 00:38:19.293
there's one obvious thing you can do.

833
00:38:19.293 --> 00:38:21.015
I've been emphasizing that

834
00:38:21.015 --> 00:38:23.595
these unitary things that just matrices

835
00:38:23.595 --> 00:38:25.246
and do matrix computation.

836
00:38:25.246 --> 00:38:27.821
So a circuit to compute what happens in it

837
00:38:27.821 --> 00:38:30.356
you just multiply, you just do matrix multiplication

838
00:38:30.356 --> 00:38:32.878
to compute the evolving state of the thing.

839
00:38:32.878 --> 00:38:35.798
But the trouble is each time you add an extra cubic in

840
00:38:35.798 --> 00:38:39.965
the size of the vector, the number of dimensions doubles.

841
00:38:40.276 --> 00:38:44.052
So you get exponential growth on the size of the vector

842
00:38:44.052 --> 00:38:48.219
cause you go along and hence you suffer an exponential

843
00:38:49.016 --> 00:38:51.581
slow down in this simulation and it's not efficient.

844
00:38:51.581 --> 00:38:55.748
Unless the states are actually all products states

845
00:38:55.802 --> 00:38:59.687
by acquittal bad fortune and then if you apply a local

846
00:38:59.687 --> 00:39:02.984
unitary gate to some part of this product.

847
00:39:02.984 --> 00:39:06.202
You only have to update that local bit of it

848
00:39:06.202 --> 00:39:08.928
and that's just the poly time calculation.

849
00:39:08.928 --> 00:39:12.433
Rather than having to carry all the extra information.

850
00:39:12.433 --> 00:39:16.600
So in that sense the presence of entanglement is a key

851
00:39:16.771 --> 00:39:20.938
resource that's necessary for computational benefit.

852
00:39:20.976 --> 00:39:23.329
But that it's not sufficient

853
00:39:23.329 --> 00:39:27.496
so you could get more mileage out of this idea of

854
00:39:28.161 --> 00:39:31.723
of just ordinary multiply matrices together.

855
00:39:31.723 --> 00:39:34.590
Because if you like they're all formulas and stuff

856
00:39:34.590 --> 00:39:36.912
you see that the output probabilities

857
00:39:36.912 --> 00:39:38.782
according to our quantum laws

858
00:39:38.782 --> 00:39:41.141
are just contractions of tenser networks.

859
00:39:41.141 --> 00:39:43.919
Where the tenses are the gates,

860
00:39:43.919 --> 00:39:45.801
the matrices in the circuit.

861
00:39:45.801 --> 00:39:48.494
You could stay then apply pressure.

862
00:39:48.494 --> 00:39:52.333
And it's not very hard to see if you kind of write

863
00:39:52.333 --> 00:39:56.111
all that down that you get this result that any low depth

864
00:39:56.111 --> 00:40:00.260
quantum circuit. With gates that act only on bounded range,

865
00:40:00.260 --> 00:40:04.427
like US neighbor gates or most three lines apart.

866
00:40:05.085 --> 00:40:08.585
Any log that's bound to range gate circuit

867
00:40:09.641 --> 00:40:12.499
and with any product state equal

868
00:40:12.499 --> 00:40:15.302
can be classically strongly simulated.

869
00:40:15.302 --> 00:40:17.454
So you get no computing power there

870
00:40:17.454 --> 00:40:20.584
and this is rather interesting because

871
00:40:20.584 --> 00:40:23.773
if you look back at Shor's stacking algorithm.

872
00:40:23.773 --> 00:40:27.940
Described in detail it rests on this completely transformed

873
00:40:29.197 --> 00:40:31.848
and it was shown that in 2000

874
00:40:31.848 --> 00:40:35.874
that the whole factoring algorithm can actually be presented

875
00:40:35.874 --> 00:40:37.145
as a low depth circuit.

876
00:40:37.145 --> 00:40:40.442
It's whole probability can be logged x.

877
00:40:40.442 --> 00:40:44.609
But the gates are not of bounded range in that description.

878
00:40:45.411 --> 00:40:48.287
If they were it would be classically simulatable

879
00:40:48.287 --> 00:40:51.182
and you get a classical factoring algorithm out of this.

880
00:40:51.182 --> 00:40:55.349
So from this point of view you get this rather annoying idea

881
00:40:56.486 --> 00:40:59.838
that the whole power of Shor's confactoring algorithm

882
00:40:59.838 --> 00:41:03.505
derives from the ability of a two cubic gate

883
00:41:04.580 --> 00:41:06.034
to activate a distance.

884
00:41:06.034 --> 00:41:09.388
Rather than the US neighbor which is kind of trivial.

885
00:41:09.388 --> 00:41:11.971
So there are other examples too

886
00:41:13.221 --> 00:41:16.388
I guess I'm slowly running out of time here.

887
00:41:16.388 --> 00:41:19.041
So I just want to list through a few

888
00:41:19.041 --> 00:41:21.461
just to give you a flavor without describing

889
00:41:21.461 --> 00:41:22.703
too many details.

890
00:41:22.703 --> 00:41:25.489
If you restrict your dates in some way

891
00:41:25.489 --> 00:41:27.118
that you're allowed to use.

892
00:41:27.118 --> 00:41:29.786
Then you get further results varying the breaker.

893
00:41:29.786 --> 00:41:32.758
So there's an important class of circuits called

894
00:41:32.758 --> 00:41:33.874
physics circuits.

895
00:41:33.874 --> 00:41:36.165
You have this hanmar gate that we've seen before.

896
00:41:36.165 --> 00:41:38.902
You have this simple one cubic gate

897
00:41:38.902 --> 00:41:42.801
which just introduces an I in front of the one state

898
00:41:42.801 --> 00:41:44.907
in the amplitude.

899
00:41:44.907 --> 00:41:48.223
And the familiar classical controlled not gate

900
00:41:48.223 --> 00:41:51.348
which negates, it's a two cubic gate

901
00:41:51.348 --> 00:41:54.576
which negates the second, first bit of one

902
00:41:54.576 --> 00:41:56.941
and doesn't do anything to seal it.

903
00:41:56.941 --> 00:41:58.904
So the first bit's the control switch

904
00:41:58.904 --> 00:42:01.395
as to whether you apply the not operational.

905
00:42:01.395 --> 00:42:04.398
And this extends by limiting (inaudible) to vectors

906
00:42:04.398 --> 00:42:06.721
so you have this quantum gate.

907
00:42:06.721 --> 00:42:08.883
And then you have further possible ingredients

908
00:42:08.883 --> 00:42:11.571
you can allow general product's state inputs.

909
00:42:11.571 --> 00:42:15.599
You can allow measurements within the body of the circuit.

910
00:42:15.599 --> 00:42:18.698
And the measurements can either be adaptive

911
00:42:18.698 --> 00:42:19.723
or not adaptive.

912
00:42:19.723 --> 00:42:22.430
Meaning that after you've done a measurement

913
00:42:22.430 --> 00:42:25.298
you can adapt the choice of laser gates

914
00:42:25.298 --> 00:42:27.768
to depend on the outcome of measurement.

915
00:42:27.768 --> 00:42:30.003
Or you might ignore the outcome and just give a fixed choice

916
00:42:30.003 --> 00:42:31.678
that's not adaptive.

917
00:42:31.678 --> 00:42:34.898
And one thing it's not hard to see

918
00:42:34.898 --> 00:42:36.696
but I won't get into details.

919
00:42:36.696 --> 00:42:40.114
That if you have non adaptive circuits

920
00:42:40.114 --> 00:42:41.752
within it's immediate measurements.

921
00:42:41.752 --> 00:42:43.713
It's equivalent to not having any measurements at all

922
00:42:43.713 --> 00:42:45.778
you can get rid of the intermediary measurements

923
00:42:45.778 --> 00:42:48.900
by the kind of trick to reduce them at a non case.

924
00:42:48.900 --> 00:42:50.650
But in this situation

925
00:42:52.664 --> 00:42:55.747
you get this interesting theorem here

926
00:42:57.165 --> 00:42:59.767
for different circuits, those gates I just mentioned.

927
00:42:59.767 --> 00:43:03.704
With produce state inputs and intermediary measurements

928
00:43:03.704 --> 00:43:05.936
and only a single bit output.

929
00:43:05.936 --> 00:43:07.836
So you just for decision problems.

930
00:43:07.836 --> 00:43:12.003
There's a simple theorem which says that if the measurements

931
00:43:12.437 --> 00:43:14.935
are non adaptive or equivalent that you don't have any

932
00:43:14.935 --> 00:43:17.665
measurements then it's classically

933
00:43:17.665 --> 00:43:21.020
always strongly simulatable for such circuits.

934
00:43:21.020 --> 00:43:24.853
So that's very kind of classical in that sense

935
00:43:26.663 --> 00:43:28.494
for weakly as well.

936
00:43:28.494 --> 00:43:31.494
But if the measurements are adaptive

937
00:43:34.581 --> 00:43:37.566
then the strong simulation becomes very hard.

938
00:43:37.566 --> 00:43:39.485
The classical computation of the sharp P

939
00:43:39.485 --> 00:43:41.606
cause that's how much harder

940
00:43:41.606 --> 00:43:45.425
and weak simulation is still what I call

941
00:43:45.425 --> 00:43:47.162
quantum computing power.

942
00:43:47.162 --> 00:43:50.512
In a sense that with adaptive choices

943
00:43:50.512 --> 00:43:54.345
you can represent universal quantum computing.

944
00:43:56.023 --> 00:43:59.534
Even though these circuits can generate lots of entanglement

945
00:43:59.534 --> 00:44:01.958
the contraption arbitrary method

946
00:44:01.958 --> 00:44:03.961
that I've previously described doesn't work.

947
00:44:03.961 --> 00:44:07.983
The proof relies on special algebraic properties

948
00:44:07.983 --> 00:44:09.886
of the gates that I chose.

949
00:44:09.886 --> 00:44:12.494
But this is essentially my favorite example of

950
00:44:12.494 --> 00:44:15.826
such a situation with extra ingredients.

951
00:44:15.826 --> 00:44:19.012
So I just want to spell out why I like it so much.

952
00:44:19.012 --> 00:44:20.679
So just to reiterate

953
00:44:22.000 --> 00:44:23.900
and to try and give you a better picture

954
00:44:23.900 --> 00:44:26.770
of all the definitions we just had.

955
00:44:26.770 --> 00:44:28.801
So you've got different circuits

956
00:44:28.801 --> 00:44:30.507
so lets take a look at then kind of gates.

957
00:44:30.507 --> 00:44:33.390
Arbitrary product stage inputs,

958
00:44:33.390 --> 00:44:34.390
single layout output,

959
00:44:34.390 --> 00:44:35.877
and you allow intermediate measurements.

960
00:44:35.877 --> 00:44:37.910
If the measurements are not adaptive

961
00:44:37.910 --> 00:44:39.878
it's all classically simulatable.

962
00:44:39.878 --> 00:44:42.008
If they're adaptive

963
00:44:42.008 --> 00:44:44.882
you have full universal quantum computing power.

964
00:44:44.882 --> 00:44:48.049
So here you have some different gates,

965
00:44:49.194 --> 00:44:52.407
if MIY means measure the ice fly

966
00:44:52.407 --> 00:44:53.972
and get your I's outcome.

967
00:44:53.972 --> 00:44:58.139
So you do still unitary gates, you do a measurement.

968
00:44:58.232 --> 00:45:00.716
You do some more unitary gates another measurement.

969
00:45:00.716 --> 00:45:04.781
But if it's adaptive the subsequent gates after the

970
00:45:04.781 --> 00:45:08.345
measurements are allowed to depend on the outcome of

971
00:45:08.345 --> 00:45:09.354
the measurement.

972
00:45:09.354 --> 00:45:13.521
And going from A to B, is a purely classical ingredient.

973
00:45:15.082 --> 00:45:17.190
It simply adaptive choice of gates

974
00:45:17.190 --> 00:45:20.305
the measurements, the quantum operations done in both cases.

975
00:45:20.305 --> 00:45:24.305
And so now we have a purely classical reason for

976
00:45:26.463 --> 00:45:29.169
getting full point computing power out of something

977
00:45:29.169 --> 00:45:30.582
that's completely lame

978
00:45:30.582 --> 00:45:31.839
and to add insult to injury.

979
00:45:31.839 --> 00:45:36.006
Experimentally there's no difference between A and B.

980
00:45:36.807 --> 00:45:40.390
Because there are no new quantum processors

981
00:45:41.550 --> 00:45:43.147
the combine A and B.

982
00:45:43.147 --> 00:45:46.314
Because any adaptive sequence of gates

983
00:45:47.152 --> 00:45:49.353
could have occurred non adaptively.

984
00:45:49.353 --> 00:45:53.520
So for example if I'm the instructor telling the

985
00:45:53.683 --> 00:45:55.228
experimenter what to do.

986
00:45:55.228 --> 00:45:57.204
You know do this gate on the first line,

987
00:45:57.204 --> 00:45:59.114
do a measurement, tell me the answer.

988
00:45:59.114 --> 00:46:01.245
Now do this gate, now do another measurement

989
00:46:01.245 --> 00:46:04.782
what's the outcome? Now do another gate.

990
00:46:04.782 --> 00:46:06.192
The experimenter has no idea, cannot know

991
00:46:06.192 --> 00:46:08.480
if I'm adapting or not.

992
00:46:08.480 --> 00:46:10.900
So there's absolutely no difference in the laboratory

993
00:46:10.900 --> 00:46:13.352
answer to the client.

994
00:46:13.352 --> 00:46:15.863
Yet in one case you get universal quantum computing

995
00:46:15.863 --> 00:46:18.157
and in the other case it's classic considerable.

996
00:46:18.157 --> 00:46:19.998
So there are other examples

997
00:46:19.998 --> 00:46:22.165
so just very very quickly.

998
00:46:23.529 --> 00:46:25.356
These match gates

999
00:46:25.356 --> 00:46:27.654
just a particular class of two cubic gates.

1000
00:46:27.654 --> 00:46:30.593
So introduce my lesser valiance

1001
00:46:30.593 --> 00:46:32.760
inspired by these theorems

1002
00:46:34.003 --> 00:46:36.170
classic holographic algorithms

1003
00:46:36.170 --> 00:46:40.003
and it's related to the counting perfect match

1004
00:46:41.511 --> 00:46:44.754
and the way to describe and that kind of thing.

1005
00:46:44.754 --> 00:46:46.938
But physically it was found to be related to

1006
00:46:46.938 --> 00:46:49.460
quantum physics and important issues there.

1007
00:46:49.460 --> 00:46:50.692
Which I agree to.

1008
00:46:50.692 --> 00:46:53.396
And the theorem here is that for these particular gates

1009
00:46:53.396 --> 00:46:55.469
if you have any circuit of them.

1010
00:46:55.469 --> 00:46:57.675
Such that the gates act on numerous enabled lined

1011
00:46:57.675 --> 00:47:00.190
just immediately adjacent lines.

1012
00:47:00.190 --> 00:47:03.748
Then you can classically efficiently simulate it

1013
00:47:03.748 --> 00:47:07.788
but you can also show that if you allow the gates

1014
00:47:07.788 --> 00:47:09.954
to act on just one first line apart.

1015
00:47:09.954 --> 00:47:13.457
Next year's cable lines could become universal

1016
00:47:13.457 --> 00:47:14.733
for quantum computing.

1017
00:47:14.733 --> 00:47:18.277
So again this suggests that the relation between

1018
00:47:18.277 --> 00:47:20.395
classical and quantum computing power

1019
00:47:20.395 --> 00:47:24.291
is, may be rather delicate or interesting

1020
00:47:24.291 --> 00:47:25.986
which is kind of bizarre.

1021
00:47:25.986 --> 00:47:29.986
But on the other hand you can argue the opposite

1022
00:47:30.826 --> 00:47:33.159
point of view there are also

1023
00:47:34.095 --> 00:47:37.512
quantum processes which are a very simple

1024
00:47:39.666 --> 00:47:41.375
from a quantum physics point of view.

1025
00:47:41.375 --> 00:47:43.846
Extremely trivial looking processors

1026
00:47:43.846 --> 00:47:45.966
of this diagonal gates

1027
00:47:45.966 --> 00:47:47.963
which all commute with each other as well.

1028
00:47:47.963 --> 00:47:50.420
So we just call instantaneous multiplication.

1029
00:47:50.420 --> 00:47:53.190
And if you put these a row of hadema

1030
00:47:53.190 --> 00:47:56.130
these operations of C on all lines

1031
00:47:56.130 --> 00:47:59.417
then you do a bunch of these rather very simple gates.

1032
00:47:59.417 --> 00:48:01.934
And then do another bar of hadema

1033
00:48:01.934 --> 00:48:03.707
to measure some lines.

1034
00:48:03.707 --> 00:48:07.874
Then you can show that these can be very difficult

1035
00:48:08.630 --> 00:48:10.946
to classically simulate even though it's an extremely

1036
00:48:10.946 --> 00:48:13.080
simple quantum process.

1037
00:48:13.080 --> 00:48:17.247
So this suggests that there's a big difference between

1038
00:48:18.335 --> 00:48:21.122
classical computing and the opposite that would be before.

1039
00:48:21.122 --> 00:48:25.289
And the theorem or specifically is that if you measure

1040
00:48:25.612 --> 00:48:29.191
algorithmically linear what lines

1041
00:48:29.191 --> 00:48:33.155
you can weakly classically simulate that efficiently.

1042
00:48:33.155 --> 00:48:35.745
But if you measure more than algorithmically

1043
00:48:35.745 --> 00:48:37.618
like algorithm how the lines.

1044
00:48:37.618 --> 00:48:41.273
Then weak classical simulation implies

1045
00:48:41.273 --> 00:48:43.754
something catastrophically disastrous

1046
00:48:43.754 --> 00:48:45.662
in complexity theory.

1047
00:48:45.662 --> 00:48:48.713
Maybe not the they call the polynomial hierarchy

1048
00:48:48.713 --> 00:48:51.170
collapses towards further effect.

1049
00:48:51.170 --> 00:48:55.337
So these examples which I've only flashed in front of you

1050
00:48:58.457 --> 00:49:02.233
and not really explained are simply meant to

1051
00:49:02.233 --> 00:49:04.097
give you the impression.

1052
00:49:04.097 --> 00:49:07.239
That the interface between classical computing power

1053
00:49:07.239 --> 00:49:10.592
is very rich and interesting and delicate

1054
00:49:10.592 --> 00:49:13.290
and can be viewed from many different points of view.

1055
00:49:13.290 --> 00:49:17.373
It's gonna be interesting sort of area to explore

1056
00:49:19.193 --> 00:49:22.025
and it gives a lot of insight possibly into what's going on.

1057
00:49:22.025 --> 00:49:24.914
So finally now to come back to

1058
00:49:24.914 --> 00:49:29.059
the more kind of fundamental issues I started with.

1059
00:49:29.059 --> 00:49:32.809
Is can we really argue that complexity theory

1060
00:49:35.537 --> 00:49:37.546
or computer theory or computer science.

1061
00:49:37.546 --> 00:49:41.386
Is really an important ingredient for physics

1062
00:49:41.386 --> 00:49:42.685
that would be a great thing.

1063
00:49:42.685 --> 00:49:43.935
Cause after all

1064
00:49:44.921 --> 00:49:49.088
the whole of complexity theory is really a consequence

1065
00:49:52.475 --> 00:49:56.642
of the fact that physical laws have limited computing power.

1066
00:49:57.702 --> 00:50:01.869
See because complexity theory says that there are these

1067
00:50:02.077 --> 00:50:04.678
problems which take a lot of effort to compute

1068
00:50:04.678 --> 00:50:06.314
and other don't and which ones do, which ones don't.

1069
00:50:06.314 --> 00:50:07.720
That kind of stuff.

1070
00:50:07.720 --> 00:50:10.467
But any computational process

1071
00:50:10.467 --> 00:50:14.093
although in computing science you abstract your models

1072
00:50:14.093 --> 00:50:16.871
when you have a computer it's always a physical device.

1073
00:50:16.871 --> 00:50:20.974
So what's happening is restricted by the laws of physics

1074
00:50:20.974 --> 00:50:24.634
so complexity theory really arises.

1075
00:50:24.634 --> 00:50:27.978
Is really a study of the computational power

1076
00:50:27.978 --> 00:50:29.443
of the laws of physics.

1077
00:50:29.443 --> 00:50:32.159
So we want to turn that around now, see we want to ask

1078
00:50:32.159 --> 00:50:36.326
can things formulated in the language of complexity theory

1079
00:50:38.404 --> 00:50:42.251
be then required for provisions on physics

1080
00:50:42.251 --> 00:50:44.360
sort of constrain physical laws.

1081
00:50:44.360 --> 00:50:48.460
So in particular your NP the most kind of notorious class.

1082
00:50:48.460 --> 00:50:52.293
We all believe that classically we can't solve

1083
00:50:53.848 --> 00:50:55.984
at a poly time can we.

1084
00:50:55.984 --> 00:51:00.151
And quantumly it also despite this exponential parallelism

1085
00:51:01.223 --> 00:51:04.027
this non determinism we're give it,

1086
00:51:04.027 --> 00:51:07.614
I think it seems the case that quantum computing

1087
00:51:07.614 --> 00:51:10.113
also can't do NP in polynomial time.

1088
00:51:10.113 --> 00:51:12.778
Which is rather mysterious I think.

1089
00:51:12.778 --> 00:51:16.503
And you might elevate this sort of physical principle

1090
00:51:16.503 --> 00:51:20.014
and say that no physical process should be able

1091
00:51:20.014 --> 00:51:22.528
to compute NP problem within physical

1092
00:51:22.528 --> 00:51:24.802
contortion of result.

1093
00:51:24.802 --> 00:51:26.957
Poly consumption of physical result.

1094
00:51:26.957 --> 00:51:31.124
And this would be a constraint on the laws of physics.

1095
00:51:31.358 --> 00:51:33.737
It's a bit like conservation of energy

1096
00:51:33.737 --> 00:51:36.180
you're not allowed to have a physical law

1097
00:51:36.180 --> 00:51:37.876
that gives you perpetual motion

1098
00:51:37.876 --> 00:51:40.667
or just gives you energy for nothing and things like that.

1099
00:51:40.667 --> 00:51:44.315
So this would be on the same footing

1100
00:51:44.315 --> 00:51:46.075
it would be a fundamental physical principle

1101
00:51:46.075 --> 00:51:48.101
that would hugely constrain.

1102
00:51:48.101 --> 00:51:51.184
The possibility of the representation

1103
00:51:52.959 --> 00:51:56.410
and the mathematical formulation that fits the laws.

1104
00:51:56.410 --> 00:51:59.822
And it's absolutely amazing I think that it appears

1105
00:51:59.822 --> 00:52:02.019
to be true in both classical and quantum physics.

1106
00:52:02.019 --> 00:52:04.488
That even though the physics was developed

1107
00:52:04.488 --> 00:52:07.501
with no thought what so ever of any kind of complexity

1108
00:52:07.501 --> 00:52:08.764
theory right.

1109
00:52:08.764 --> 00:52:12.271
And despite the fact that both theories

1110
00:52:12.271 --> 00:52:13.586
when you first look at them,

1111
00:52:13.586 --> 00:52:17.753
nature is doing a massive amount of computing power.

1112
00:52:18.117 --> 00:52:22.284
Way more than you need even to solve NP problems.

1113
00:52:22.523 --> 00:52:26.690
But both theories nature somehow bizarrely restricts

1114
00:52:26.773 --> 00:52:30.360
our access to all this computations she's doing.

1115
00:52:30.360 --> 00:52:32.612
So what's the point of it

1116
00:52:32.612 --> 00:52:34.182
why is physics like that?

1117
00:52:34.182 --> 00:52:37.664
And in fact it's also known that if you

1118
00:52:37.664 --> 00:52:40.401
people sometimes consider modifying the quantum laws

1119
00:52:40.401 --> 00:52:41.559
in various ways.

1120
00:52:41.559 --> 00:52:45.726
Then it's very hard to modify the laws of physics

1121
00:52:45.742 --> 00:52:48.379
to not have immense computing power.

1122
00:52:48.379 --> 00:52:51.158
So it's very special that

1123
00:52:51.158 --> 00:52:54.199
classical and quantum physics have this limitation

1124
00:52:54.199 --> 00:52:57.830
of apparently not being able to do NP problems.

1125
00:52:57.830 --> 00:53:00.580
Which is really quite striking I think.

1126
00:53:00.580 --> 00:53:02.622
And this is being noticed before

1127
00:53:02.622 --> 00:53:06.385
in the past decades or so by several people.

1128
00:53:06.385 --> 00:53:08.944
So just to say it's a bit more

1129
00:53:08.944 --> 00:53:11.972
if classical physics or physical evolution updates

1130
00:53:11.972 --> 00:53:14.965
real numbers you know the states are labeled by position

1131
00:53:14.965 --> 00:53:16.567
and the mentor and that kind of stuff.

1132
00:53:16.567 --> 00:53:18.586
And certain infinite information processing.

1133
00:53:18.586 --> 00:53:20.559
You're updating all things

1134
00:53:20.559 --> 00:53:23.008
so why can't we harness that to do

1135
00:53:23.008 --> 00:53:24.924
wonderful computations?

1136
00:53:24.924 --> 00:53:28.289
The trouble is this is essentially animal computation

1137
00:53:28.289 --> 00:53:31.168
it becomes unstable with the number of digits

1138
00:53:31.168 --> 00:53:33.525
down the real number.

1139
00:53:33.525 --> 00:53:36.473
And the higher on the digits well you expect to

1140
00:53:36.473 --> 00:53:39.052
require more effort to keep them under control.

1141
00:53:39.052 --> 00:53:42.018
But in fact it requires exponential effort

1142
00:53:42.018 --> 00:53:44.144
it could have only been polynomial effort,

1143
00:53:44.144 --> 00:53:46.612
it's not it seems to be exponential

1144
00:53:46.612 --> 00:53:49.233
and to control our parameters to n digits

1145
00:53:49.233 --> 00:53:51.723
you need exponential effort physically

1146
00:53:51.723 --> 00:53:54.627
or exponential physical resources

1147
00:53:54.627 --> 00:53:57.501
and that's what kills analog computation.

1148
00:53:57.501 --> 00:54:00.578
This whole idea and that's how nature gets around

1149
00:54:00.578 --> 00:54:01.964
giving to us.

1150
00:54:01.964 --> 00:54:04.819
So our response to that of course

1151
00:54:04.819 --> 00:54:06.969
is for n digits of information,

1152
00:54:06.969 --> 00:54:09.500
instead of using a single parameter

1153
00:54:09.500 --> 00:54:10.963
with n digits of accuracy.

1154
00:54:10.963 --> 00:54:13.106
Which requires exponential cast

1155
00:54:13.106 --> 00:54:15.462
we simply use order and systems

1156
00:54:15.462 --> 00:54:17.155
with just one or two digits each.

1157
00:54:17.155 --> 00:54:20.272
Each one of which requires a constant amount of

1158
00:54:20.272 --> 00:54:23.291
stabilization and it only grows linearly now

1159
00:54:23.291 --> 00:54:25.235
to stabilize our potential.

1160
00:54:25.235 --> 00:54:28.367
And what we've done here is precisely that digital

1161
00:54:28.367 --> 00:54:29.649
computational.

1162
00:54:29.649 --> 00:54:33.131
So what gave us stability at the expense of losing

1163
00:54:33.131 --> 00:54:37.206
this ability to process huge amounts of information locally.

1164
00:54:37.206 --> 00:54:40.754
So that's what happens in classical physics

1165
00:54:40.754 --> 00:54:43.760
and in quantum physics we've already seen that

1166
00:54:43.760 --> 00:54:47.927
entanglement we have this exponential non determinism

1167
00:54:50.714 --> 00:54:53.714
built into our model of computation.

1168
00:54:54.566 --> 00:54:57.093
For example representing all the values

1169
00:54:57.093 --> 00:54:59.695
but building a function in just a linear amount

1170
00:54:59.695 --> 00:55:01.946
of physical material registered.

1171
00:55:01.946 --> 00:55:04.758
And we can produce this in linear time.

1172
00:55:04.758 --> 00:55:08.279
But the measurement theory this bizarre collapsing

1173
00:55:08.279 --> 00:55:10.816
when we just get this probabilistic information

1174
00:55:10.816 --> 00:55:12.104
with destructive effects.

1175
00:55:12.104 --> 00:55:15.036
Seems to be finally balanced against this

1176
00:55:15.036 --> 00:55:18.181
massive amount of information sitting there

1177
00:55:18.181 --> 00:55:21.245
just right so that we can't get what we want.

1178
00:55:21.245 --> 00:55:24.800
We get all the classical stuff and maybe a little bit more

1179
00:55:24.800 --> 00:55:27.099
but not the full powered NP.

1180
00:55:27.099 --> 00:55:30.254
So this is very suggestive I think that

1181
00:55:30.254 --> 00:55:34.352
there's a fundamental significance for computational

1182
00:55:34.352 --> 00:55:37.015
complexity theory in foundations of physics itself.

1183
00:55:37.015 --> 00:55:39.755
Which I think is a very very exciting prospect.

1184
00:55:39.755 --> 00:55:43.672
I think that's for me the most novel ingredient

1185
00:55:44.603 --> 00:55:47.435
that the whole subject of quantum computing

1186
00:55:47.435 --> 00:55:49.123
has brought to physics.

1187
00:55:49.123 --> 00:55:50.690
It's just this completely new perspective on

1188
00:55:50.690 --> 00:55:54.478
the foundations of physics in terms of complexity

1189
00:55:54.478 --> 00:55:58.166
or specifically this precise kind of computational

1190
00:55:58.166 --> 00:55:59.717
complexity type issue.

1191
00:55:59.717 --> 00:56:02.945
And there's a lot more stuff to be understood there.

1192
00:56:02.945 --> 00:56:07.112
Yeah actually I've just finished on this slightly enigmatic

1193
00:56:07.635 --> 00:56:11.375
remark I think I'll just finish there

1194
00:56:11.375 --> 00:56:13.251
and thank you very much for you time..

1195
00:56:13.251 --> 00:56:15.501
(clapping)

1196
00:56:21.640 --> 00:56:24.973
- Some questions, I think there was one.

1197
00:56:36.487 --> 00:56:39.634
- What objective measurements or the more general?

1198
00:56:39.634 --> 00:56:40.707
- Go for it, actually.

1199
00:56:40.707 --> 00:56:42.814
I've only been talking about standard measurements but

1200
00:56:42.814 --> 00:56:46.250
in fact it seems true for general.

1201
00:56:46.250 --> 00:56:49.370
Completely general quantum measurements.

1202
00:56:49.370 --> 00:56:51.750
The theorem that what?

1203
00:56:51.750 --> 00:56:55.614
- That the same is true for generalized measurements.

1204
00:56:55.614 --> 00:56:57.275
- Yeah you don't get anything more.

1205
00:56:57.275 --> 00:56:58.108
- Why?

1206
00:56:59.197 --> 00:57:01.270
- Well because you can represent generalized measurement

1207
00:57:01.270 --> 00:57:05.437
as a standard measurement in that standard space I guess.

1208
00:57:07.274 --> 00:57:08.941
The dilation theorem

1209
00:57:11.023 --> 00:57:14.025
you can general the most general quantum measurement

1210
00:57:14.025 --> 00:57:18.192
can be thought of as a ordinary projective measurement

1211
00:57:18.450 --> 00:57:21.320
on a space where you're bringing an add

1212
00:57:21.320 --> 00:57:25.134
and you're doing it on a bigger space jointly.

1213
00:57:25.134 --> 00:57:28.134
So what can be represented formally.

1214
00:57:31.750 --> 00:57:35.917
- So you mentioned that the femur of classical analog

1215
00:57:36.182 --> 00:57:39.432
computation because basically of right?

1216
00:57:43.097 --> 00:57:45.164
You do order correct dot?

1217
00:57:45.164 --> 00:57:46.914
So and the remedy was

1218
00:57:48.793 --> 00:57:51.341
digital classical computation.

1219
00:57:51.341 --> 00:57:54.508
So how about why do analog computation

1220
00:57:55.417 --> 00:57:58.584
is it clear that we cannot correct it?

1221
00:57:59.704 --> 00:58:03.871
Do error correction, we can and then maybe we can solve

1222
00:58:06.696 --> 00:58:08.113
NP hard problems.

1223
00:58:09.245 --> 00:58:11.539
- But the measurement theories different.

1224
00:58:11.539 --> 00:58:12.956
You can stabilize

1225
00:58:14.328 --> 00:58:16.320
I mean in a sense quantum computing is analog

1226
00:58:16.320 --> 00:58:19.485
because the unitary the gates if you like

1227
00:58:19.485 --> 00:58:21.985
have got continual parameters.

1228
00:58:23.658 --> 00:58:26.969
In that sense so you need to stabilize that.

1229
00:58:26.969 --> 00:58:29.904
But because they're unitary you can,

1230
00:58:29.904 --> 00:58:32.212
the errors don't propagate in the same way

1231
00:58:32.212 --> 00:58:34.096
as they do classically.

1232
00:58:34.096 --> 00:58:37.632
So I think you can stabilize though.

1233
00:58:37.632 --> 00:58:41.506
But the quantum measurement theory is a different issue

1234
00:58:41.506 --> 00:58:45.396
it's not one of stabilizing the thing.

1235
00:58:45.396 --> 00:58:47.291
Even if you can stabilize it perfectly

1236
00:58:47.291 --> 00:58:49.781
or there are no errors to infinite precision.

1237
00:58:49.781 --> 00:58:52.160
You still can't do anything

1238
00:58:52.160 --> 00:58:53.628
because of the measurement theory.

1239
00:58:53.628 --> 00:58:57.795
It limits the amount of information you get out of it

1240
00:58:59.992 --> 00:59:01.742
in a technical sense.

1241
00:59:07.354 --> 00:59:09.917
- You mentioned that for both special hardware

1242
00:59:09.917 --> 00:59:13.408
boils down to having a non stable neighbor gates

1243
00:59:13.408 --> 00:59:16.408
and so does that mean if I implement

1244
00:59:18.121 --> 00:59:22.121
that only has these gates that the it goes away?

1245
00:59:25.202 --> 00:59:28.421
- No sorry, there's an extra ingredient.

1246
00:59:28.421 --> 00:59:30.195
It's log depth.

1247
00:59:30.195 --> 00:59:34.362
So you can implement Shor's algorithm with nuro stable gates

1248
00:59:34.534 --> 00:59:37.580
but it'll poly size our computation but it would be

1249
00:59:37.580 --> 00:59:39.118
poly depth.

1250
00:59:39.118 --> 00:59:42.579
Exactly because you know if you have distant gates

1251
00:59:42.579 --> 00:59:44.912
ordering apart in log depth.

1252
00:59:45.950 --> 00:59:48.159
You can use a ladder of swath operations

1253
00:59:48.159 --> 00:59:50.503
which is linear length letter

1254
00:59:50.503 --> 00:59:53.013
and so it becomes still poly depth

1255
00:59:53.013 --> 00:59:55.180
but not log depth anymore.

1256
01:00:00.695 --> 01:00:02.110
- I've just confused you sir.

1257
01:00:02.110 --> 01:00:05.110
For example function like that width

1258
01:00:06.388 --> 01:00:10.555
so actually you're really thanking the function

1259
01:00:10.901 --> 01:00:12.438
using a single pipe words.

1260
01:00:12.438 --> 01:00:14.294
That was expansion in many states.

1261
01:00:14.294 --> 01:00:18.044
- Yeah n + 1 cubic it's a linear number.

1262
01:00:23.697 --> 01:00:24.737
- How can you hide that there?

1263
01:00:24.737 --> 01:00:28.472
You have to have some priority to have that there.

1264
01:00:28.472 --> 01:00:30.752
- Well you can make that state.

1265
01:00:30.752 --> 01:00:34.618
- So it's to make like any internal state

1266
01:00:34.618 --> 01:00:37.715
you have to estimate your functioning for any times

1267
01:00:37.715 --> 01:00:40.298
so you have state in beginning.

1268
01:00:42.401 --> 01:00:44.684
- No you can make this state

1269
01:00:44.684 --> 01:00:47.101
with only a linear reference.

1270
01:00:49.797 --> 01:00:53.130
I mean like right at the very beginning.

1271
01:01:01.051 --> 01:01:04.386
So if you start with a state of all zeros

1272
01:01:04.386 --> 01:01:07.553
and if you apply this hadema operation

1273
01:01:09.607 --> 01:01:12.532
where it requires this thing here.

1274
01:01:12.532 --> 01:01:15.270
Each zero goes to zero + 1 over root two.

1275
01:01:15.270 --> 01:01:17.751
And so you do that n times

1276
01:01:17.751 --> 01:01:20.956
then you get zero + 1 over root two.

1277
01:01:20.956 --> 01:01:22.254
Zero + 1 over root two,

1278
01:01:22.254 --> 01:01:23.941
you multiple them all out.

1279
01:01:23.941 --> 01:01:27.524
You get this exponential super positionable

1280
01:01:28.552 --> 01:01:32.057
and it's strength and then you have the

1281
01:01:32.057 --> 01:01:36.077
computer program that computes the function on an input

1282
01:01:36.077 --> 01:01:38.812
and because the gates are all linear.

1283
01:01:38.812 --> 01:01:42.413
If you put in this linear super position state

1284
01:01:42.413 --> 01:01:45.360
it will manufacture that state for you

1285
01:01:45.360 --> 01:01:46.693
just in one row.

1286
01:01:47.814 --> 01:01:51.383
But they all go through, it's non determinism

1287
01:01:51.383 --> 01:01:53.720
all happening at the same place

1288
01:01:53.720 --> 01:01:55.177
for all the different values.

1289
01:01:55.177 --> 01:01:57.617
So you can genuinely make this the polynomial effort

1290
01:01:57.617 --> 01:01:59.450
linear effort in fact.

1291
01:02:09.251 --> 01:02:10.796
- Okay well that's thanks Richard again.

1292
01:02:10.796 --> 01:02:13.046
(clapping)