WEBVTT
1
00:00:05.060 --> 00:00:16.040
Marius Junge: it's a distinctive pleasure for me to announce the next speaker and he went from the maybe he will we tell us where you from Columbia University, of course.
2
00:00:16.460 --> 00:00:26.660
Marius Junge: And he will talk about him I P star equals R E and we're very happy happy to have him here because i'm an incredible event you're going to talk about.
3
00:00:27.740 --> 00:00:28.130
Marius Junge: Go ahead.
4
00:00:29.090 --> 00:00:29.480
Okay.
5
00:00:30.740 --> 00:00:35.420
Henry Yuen: yeah thanks for the introduction, Maurice and thanks for the invitation to speak at this workshop.
6
00:00:37.640 --> 00:00:48.530
Henry Yuen: So i'm going to talk about MIT sorry cool sorry, which is a theorem that was proved with these amazing collaborators Jing Jing JI on in natarajan Toma Vedic and john right.
7
00:00:49.820 --> 00:01:07.520
Henry Yuen: And one of the things that makes this theorem so interesting, at least in my point of view is that there's many different angles, from which to understand it, and today i'm going to talk about this result, through a specific angle, which is that of proofs and proof checking.
8
00:01:14.660 --> 00:01:15.410
Henry Yuen: Okay, so.
9
00:01:16.640 --> 00:01:27.080
Henry Yuen: let's jump right into it and i'll start by defining what MIT star, is it refers to a model of multi proven interactive proofs with entangled movers.
10
00:01:27.950 --> 00:01:39.740
Henry Yuen: And in this model, there is a classical polynomial time verify this person in the middle and this verify or interacts with too computationally unbounded pruners were depicted by these wizards here.
11
00:01:40.850 --> 00:01:50.540
Henry Yuen: The communication between the verified and approvals is classical and the providers during this interaction cannot communicate with each other, but they only talk with a very fire.
12
00:01:51.980 --> 00:01:55.760
Henry Yuen: But the proof is can use quantum entanglement to coordinate their responses.
13
00:01:57.470 --> 00:01:58.400
Henry Yuen: To the verify.
14
00:02:00.230 --> 00:02:01.190
Henry Yuen: So that's the model.
15
00:02:02.330 --> 00:02:09.290
Henry Yuen: And MIT star is a complexity class consisting of decision problems l that emit such.
16
00:02:10.580 --> 00:02:24.350
Henry Yuen: That can be verified using such an interactive protocol so in the protocol to verify will get input X and the verified wants to decide whether X is in this language l or is is not in the language l.
17
00:02:25.970 --> 00:02:43.610
Henry Yuen: And if X is an l, then there is a entangled proven strategy that the that the previous can use to convince the verifiers to accept with high probability, whereas if X is not an elder, no matter what the previous say, no matter what quantum entanglement they use.
18
00:02:44.720 --> 00:02:47.720
Henry Yuen: The verify will reject with high probability.
19
00:02:48.890 --> 00:02:53.870
Henry Yuen: And so, so l is an MIT started if it if there's a protocol satisfying this property.
20
00:02:56.660 --> 00:03:06.860
Henry Yuen: Okay, so that's MIT start what sorry it stands for recursive Lee innumerable decision problems, and this is a complexity class that's absolutely enormous.
21
00:03:07.340 --> 00:03:16.250
Henry Yuen: It contains basically all decipherable problems and then some so you know, not only as P and P exponential time.
22
00:03:16.760 --> 00:03:33.770
Henry Yuen: beat up, and you know all of the favorite complexity classes, that we usually think about are they contained in our E, but it also contains problems like the halting problem which is famously in undecidable problem, and this was shown by turning back in his original paper in the 1930s.
23
00:03:38.600 --> 00:03:49.730
Henry Yuen: Okay, so the quality MIT star equals R he gives a characterization of the complexity of languages that have entangled.
24
00:03:51.020 --> 00:04:02.870
Henry Yuen: interactive proofs so What this means is that every problem that can be decided by an MIT star Protocol can be reduced to the healthy problem, and vice versa, every problem.
25
00:04:03.560 --> 00:04:12.920
Henry Yuen: That is, in our eat, including the halting problem has an MIT star protocol that decides it and there's a number of surprising and unexpected consequences of this equality.
26
00:04:14.000 --> 00:04:14.780
Henry Yuen: For example.
27
00:04:16.160 --> 00:04:18.440
Henry Yuen: It implies that there is no algorithm.
28
00:04:19.940 --> 00:04:24.350
Henry Yuen: to approximate the maximum success probability in non local games.
29
00:04:26.000 --> 00:04:30.050
Henry Yuen: It implies a negative answer to Cyril sins problem for mathematical physics.
30
00:04:31.640 --> 00:04:36.350
Henry Yuen: It implies a negative answer to something known as constant bedding problem from operator how's your pros.
31
00:04:38.060 --> 00:04:47.690
Henry Yuen: And you know that is the sort of the focus of the sock is is that it implies that there's an interactive proof for the halting problem in the entangled previous model.
32
00:04:49.190 --> 00:04:56.090
Henry Yuen: And that's you know i'm not going to sort of explain the the first three implications but rather i'll focus on this last one.
33
00:04:57.320 --> 00:05:06.170
Henry Yuen: So you know let's unpack what it means to have an interactive proof for the halting problem so.
34
00:05:07.520 --> 00:05:21.470
Henry Yuen: You know in this setup the verifiers going to receive a description of some turing machine and Okay, and the verify wants to know if I took this turing machine and turned it on and ran it will it eventually stop.
35
00:05:22.550 --> 00:05:29.960
Henry Yuen: And this turing machine m might take an enormous number of steps to run far beyond whatever time budget the verify or has.
36
00:05:30.860 --> 00:05:44.630
Henry Yuen: so that you know the verified by itself won't be able to determine this approvals, on the other hand, since we're assuming them to be computationally omniscient you know they we can assume that they know whether the target machine and helps or not.
37
00:05:46.010 --> 00:05:53.240
Henry Yuen: And the verified just wants to be convinced by the improvers about the the truth of the halting are not helping of em.
38
00:05:54.440 --> 00:05:55.010
Henry Yuen: So.
39
00:05:56.390 --> 00:06:08.840
Henry Yuen: This protocol will have the property that you know the very far I will talk to the movers and if n actually does halt in some amount of time, then there is some strategy for the providers to convince the verify of this fact, for the probability one.
40
00:06:10.430 --> 00:06:21.980
Henry Yuen: But on the other hand, if and never halts, no matter what the previous say the verify or will accept with very, very small probability let's say 1%.
41
00:06:22.850 --> 00:06:33.410
Henry Yuen: And really the The remarkable thing about this protocol is that the complexity of the verify, which means you know how much computation time it takes to to run this Protocol.
42
00:06:34.070 --> 00:06:42.590
Henry Yuen: This complexity is going to be polynomial in the description length of em but it's independent of the running time of em.
43
00:06:43.160 --> 00:06:56.870
Henry Yuen: Right so m can take you know many lifetimes of the universe, to finally terminate but the amount of work that the verify or has to put in only depends polynomial on the you know, the number of lines of the source code of em.
44
00:06:58.040 --> 00:07:08.270
Henry Yuen: So, at the end of the interaction the verify or may still have no idea what is even a reasonable upper bound on the time it takes for me to halt if it actually does hold.
45
00:07:13.640 --> 00:07:20.360
Henry Yuen: Okay, so when talking to people about this results i've often encountered the question of you know what does it.
46
00:07:21.350 --> 00:07:28.070
Henry Yuen: You know, does this mean quantum computers can solve the halting problem, so I want to emphasize that this result is not imply that.
47
00:07:28.670 --> 00:07:34.160
Henry Yuen: We know that quantum computers cannot solve the halting problem right, and you know, and this is because.
48
00:07:34.640 --> 00:07:39.440
Henry Yuen: classical computers can simulate quantum computers with that most an exponential slow down.
49
00:07:40.100 --> 00:07:54.410
Henry Yuen: But since classical computers cannot solve the halting problem with any amount of time, neither can can quantum computers MIT start equals R Us not about solving the halting problem, but instead it's about the efficient verify ability of it.
50
00:07:56.120 --> 00:08:05.630
Henry Yuen: You know so again the we're assuming the previous our mission, so they can solve any problem they like, but the challenge for them is to be able to convince a.
51
00:08:07.220 --> 00:08:10.040
Henry Yuen: bounded verify of the correct answer.
52
00:08:11.840 --> 00:08:16.430
Henry Yuen: And so that that's why this is, you know really a result about proofs and proof checking.
53
00:08:20.210 --> 00:08:26.990
Henry Yuen: So still it's pretty counterintuitive that you know in this MIT star model which is pretty well motivated.
54
00:08:27.620 --> 00:08:39.110
Henry Yuen: You know it's a reasonably defined modeled interactive proofs even in this model that they're unsolvable problems that can be verified so so this talk is going to explore how this is possible.
55
00:08:40.850 --> 00:08:48.470
Henry Yuen: And you know my goal today is to try to shed some light on these questions, you know how can there be an interactive proof undecidable problem.
56
00:08:49.640 --> 00:09:01.430
Henry Yuen: what's the role of proofs and proof checking and MIT start equals sorry, you know what is the role of entanglement you know somehow quantum unlocks this amazing verification power, and how does it do that.
57
00:09:02.240 --> 00:09:09.170
Henry Yuen: And at the end, if I have a little bit of time i'd like to describe some questions that emerged, out of all of these considerations.
58
00:09:09.860 --> 00:09:20.960
Henry Yuen: And these questions form an area that I like to call non commutative property testing, and you know these are motivated by some of the phenomena that occurs at the core of.
59
00:09:22.070 --> 00:09:25.250
Henry Yuen: My piece articles already so we'll see if I have time to get to that.
60
00:09:28.940 --> 00:09:33.380
Henry Yuen: Alright, so let's get into how one can prove that attorney machine eventually halts.
61
00:09:38.240 --> 00:09:44.000
Henry Yuen: So let's consider a slightly easier version of the halting problem, and this is called the bounded halting problem.
62
00:09:44.450 --> 00:09:58.070
Henry Yuen: So here imagine that someone walks up to you with the turing machine and they claim that at halts in a specific time T so they also provide a time bound that you know they want to know if it helps in that time.
63
00:09:59.180 --> 00:10:00.500
Henry Yuen: How do you verify this claim.
64
00:10:02.000 --> 00:10:02.570
Henry Yuen: So.
65
00:10:03.860 --> 00:10:07.880
Henry Yuen: That you know this person can provide you with an execution trace of em.
66
00:10:09.260 --> 00:10:17.960
Henry Yuen: A step by step record of the computation of this turing machine up to time to have to T number of steps, and if this person gives you this execution trace.
67
00:10:18.830 --> 00:10:24.560
Henry Yuen: You can verify their claim by just scanning through it line by line and checking that it's a valid execution trace.
68
00:10:25.430 --> 00:10:30.650
Henry Yuen: And so that's fine, but you know, the thing about this is it you know this takes says, at least as.
69
00:10:30.890 --> 00:10:41.240
Henry Yuen: Much time as it takes to run the turing machine for time T, so you just might as well run the turing machine yourself right there's no difference between execution trace and just running the turing machine right.
70
00:10:43.610 --> 00:10:45.680
Henry Yuen: But it turns out that you can be much more efficient.
71
00:10:47.030 --> 00:10:55.910
Henry Yuen: If you allow your verification process to be randomized then it's possible to perform what's called a probabilistic Lee checkup proof or a PCP.
72
00:10:57.350 --> 00:11:16.580
Henry Yuen: So someone can write down a string that's a polynomial length it's going to be polynomial and T length, but you as a verified you don't have to scan through the whole string you can just pick a few number of spots from the string and based on the symbols that you see in these.
73
00:11:17.720 --> 00:11:35.330
Henry Yuen: chosen locations, you can verify with high probability whether the proof is a valid proof of halting or not, and furthermore the amount of computation time that you took is only poly logarithmic can T so there's an exponential savings in the complexity of verification.
74
00:11:37.220 --> 00:11:38.180
Henry Yuen: that's pretty remarkable.
75
00:11:40.520 --> 00:11:41.390
Henry Yuen: So in pictures.
76
00:11:42.470 --> 00:11:43.370
Henry Yuen: This is what it looks like.
77
00:11:44.390 --> 00:12:03.860
Henry Yuen: You know, some someone will write down this this long proof stream Okay, we call it pie this PCP has polynomial and T length, but you as the very fire you just sample a few locations in this long string you take a look at the symbols in those locations and you accept or reject.
78
00:12:06.170 --> 00:12:13.850
Henry Yuen: Right, and you know this this this type of proof checking has a property that you know, similar to what we've discussed before.
79
00:12:14.720 --> 00:12:25.430
Henry Yuen: The turing machine does halts, then you know, there is some proof string that this person can write down to convince you with probability one, otherwise you accept with very small probability.
80
00:12:30.890 --> 00:12:36.410
Henry Yuen: Okay, so you know that there's a couple of different types of proof checking.
81
00:12:37.130 --> 00:12:47.540
Henry Yuen: models that have thrown at you one is this multi server interactive proof model and one is this, you know PCP model and it turns out that classically these are equivalent.
82
00:12:47.990 --> 00:13:02.090
Henry Yuen: So the fact that there's a PCP for checking whether turing machine hulton time T This is equivalent to the existence of a interactive proof between a verified and to omniscient prefers.
83
00:13:04.160 --> 00:13:09.950
Henry Yuen: To solve the same thing and the verified complexity is probably logarithmic and tea.
84
00:13:12.140 --> 00:13:21.950
Henry Yuen: And in the classical setting here we're assuming there's no entanglement between the movers and you know this is a well known result from classical complexity theory that these two models of proof checking in or equivalent.
85
00:13:24.770 --> 00:13:35.990
Henry Yuen: And in the classical setting it's known that to check this claim that this turing machine halston time T the verified complexity must depend on tea right there you cannot.
86
00:13:37.370 --> 00:13:43.940
Henry Yuen: get around this Okay, but the whole point of MIT start equals R E is that we can get this.
87
00:13:45.650 --> 00:13:52.610
Henry Yuen: Proof checking to be done with complexity that's independent of tea so So how do we, how do we get get this independence.
88
00:13:57.980 --> 00:13:58.580
Henry Yuen: So.
89
00:14:00.200 --> 00:14:10.910
Henry Yuen: You know let's let's try to explore this let's engage in some wishful thinking right so again at the top let's imagine that we have a PCP.
90
00:14:12.170 --> 00:14:22.460
Henry Yuen: That supposedly claims that this turing machine m halts in some time T right, so the PCP is of length polynomial and T right, just like before.
91
00:14:23.870 --> 00:14:44.240
Henry Yuen: But we're going to get a little greedy and we're going to say let's try to verify this proof using a verify that doesn't just run in log TEE time, but how about log log TEE time, so it, you know why what what is it double log time something right is such a verification procedure possible.
92
00:14:46.580 --> 00:14:59.510
Henry Yuen: And it's it's not hard to see that you know, this is not possible in the way he described it, because you know, first of all, this mini verify, which we will call the mini.
93
00:15:01.370 --> 00:15:08.630
Henry Yuen: It since it runs in log log T time the number of random bits that it can flip is, of course, only log log T.
94
00:15:09.560 --> 00:15:21.950
Henry Yuen: But that means the number of different locations, that it can index into right when it tries to make queries to this long proof string you can only make queries to at most log two different locations right.
95
00:15:23.180 --> 00:15:37.460
Henry Yuen: And so it such a mini verify or cannot even refer to all the possible locations as proof string so we can only see a very small segment of it and it won't be able to by itself verify this this proof stream.
96
00:15:38.780 --> 00:15:45.950
Henry Yuen: So that's you know, in the classical world that's it that's the end of the story, so you know you cannot have such a hyper efficient verification procedure.
97
00:15:48.020 --> 00:15:48.980
Henry Yuen: But you know let's.
98
00:15:50.600 --> 00:15:55.400
Henry Yuen: not let something like this to tourists, maybe let's just continue along this road of wishful thinking.
99
00:15:59.060 --> 00:16:08.840
Henry Yuen: We know that there is a from the PCP results that are described, there is a log to verify or that does you know, is able to.
100
00:16:09.860 --> 00:16:23.630
Henry Yuen: check this proof string uses log T randomness, so this is a you know this this verified, we had before, but you know this very fire, what is it it's just another turing machine right it performs some computation to do these checks.
101
00:16:24.770 --> 00:16:38.630
Henry Yuen: This turing machine takes us input some randomness to to help it choose its queries and it also gets as input, the corresponding symbols from this proof stream right so that's all it is and.
102
00:16:39.080 --> 00:16:51.590
Henry Yuen: We just want to check whether this verify your turing machine, the one in the middle, if it received a random string and it received corresponding proof symbols, whether it accepts or rejects in polyglot T.
103
00:16:52.640 --> 00:17:03.980
Henry Yuen: So the national ideas, why don't we just replace this middle verify it with a PCP that describes its execution.
104
00:17:06.200 --> 00:17:12.140
Henry Yuen: Right, so we can imagine having another proof pi prime that describes this.
105
00:17:13.220 --> 00:17:17.240
Henry Yuen: middle there fire this proof pie prime has length polyglot tea.
106
00:17:18.590 --> 00:17:26.360
Henry Yuen: And now we're you know this proof is in the regime where we can this mini verify has enough time to check this intermediate proof.
107
00:17:29.450 --> 00:17:29.990
Henry Yuen: So.
108
00:17:31.100 --> 00:17:41.000
Henry Yuen: What we can imagine, is this mini verify is going to flip just a tiny number of random bits log log T number of random bits to check this intermediate proof and verify that this proof.
109
00:17:42.260 --> 00:17:53.480
Henry Yuen: describes the behavior of the middle verify, which in turn check this larger proof right so it's kind of like checking a proof by proxy using another proof okay.
110
00:17:56.660 --> 00:18:03.200
Henry Yuen: So so here we're kind of like going beyond the classical model, a little bit and what assumptions are we making.
111
00:18:04.580 --> 00:18:15.650
Henry Yuen: we're assuming that this the queries made by this middle verify are random queries and then the this intermediate proof pi prime.
112
00:18:17.660 --> 00:18:24.950
Henry Yuen: You know, refers to like sort of the contents of this intermediate proof is consistent with the contents of the top number proof.
113
00:18:26.090 --> 00:18:28.820
Henry Yuen: And if both of those assumptions hold.
114
00:18:29.960 --> 00:18:37.430
Henry Yuen: Then this V mini by checking this intermediate proof is also essentially checking the validity of the proof at the top.
115
00:18:39.350 --> 00:18:43.100
Henry Yuen: All the while only using a small amount of randomness in a small amount of time.
116
00:18:45.080 --> 00:18:50.120
Henry Yuen: And this, this idea is is not new, I mean this is something that actually comes.
117
00:18:51.470 --> 00:18:52.040
Henry Yuen: From.
118
00:18:53.510 --> 00:18:56.120
Henry Yuen: PCP literature so there's known as PCP composition.
119
00:18:56.720 --> 00:19:10.070
Henry Yuen: And once you have this idea, you say well why stop there, why don't we just continue iterating you know, instead of having a mini verify or why don't we have a micro verify that runs an even smaller amount of time that, and you know we can imagine this this.
120
00:19:10.940 --> 00:19:17.060
Henry Yuen: You know recursive proof checking where he have proofs verifying larger proofs are fine larger proofs.
121
00:19:19.790 --> 00:19:24.320
Henry Yuen: And you can sort of imagine, at least at some high level that if we reverse this process.
122
00:19:25.670 --> 00:19:40.250
Henry Yuen: And you know at each level we we maintain the assumptions that all the queries that all the levels are chosen randomly and all the proofs between the different levels are consistent, then our bottom most verified, which takes you know essentially.
123
00:19:41.300 --> 00:19:49.610
Henry Yuen: Essentially Constantine you know, roughly speaking, it can check this top level proof that's you know still polynomial at length.
124
00:19:51.290 --> 00:19:52.550
Henry Yuen: So this is the wishful thinking.
125
00:19:55.880 --> 00:20:01.220
Henry Yuen: But, of course, how do we make ensure that these these assumptions are satisfied.
126
00:20:04.760 --> 00:20:17.810
Henry Yuen: And really the main bottleneck, the main challenge to ensuring that this is this can work is to certify that all of the queries at each of these levels are chosen randomly.
127
00:20:18.500 --> 00:20:26.240
Henry Yuen: And this is, this is not possible classically right like you know, no one can write down a classical string.
128
00:20:26.720 --> 00:20:38.270
Henry Yuen: and enhance the string to you and say look the string is is a random string right that just doesn't make sense right and here's a kind of a famous well known dilbert cartoon that that kind of drives home this point.
129
00:20:40.730 --> 00:20:45.980
Henry Yuen: But if if you somehow knew that some strings were random then actually that.
130
00:20:47.240 --> 00:20:54.440
Henry Yuen: The that would actually make this recursive proof composition workout, and this is where the quantum entanglement comes in.
131
00:20:55.070 --> 00:21:01.850
Henry Yuen: Right, the quantum entanglement is going to be the thing that allows this randomness certification to be done in an extremely efficient manner.
132
00:21:02.690 --> 00:21:16.100
Henry Yuen: And once you do that, then, then you can make this proof composition thing work, and you can really verify using a very, very small verify that they're the proof of halting is actually valid.
133
00:21:21.470 --> 00:21:26.030
Henry Yuen: Okay, so so we've reduced it to the problem, how do we certify that.
134
00:21:28.610 --> 00:21:44.750
Henry Yuen: Some randomness a large amount of randomness has been generated using a very small complexity verify and that brings me to the next part of this talk, which is something called the quantum loaded retest and it's an efficient MIT star protocol for certifying.
135
00:21:45.980 --> 00:21:52.850
Henry Yuen: The generation of entanglement and ensuring, therefore, the generation of genuine randomness.
136
00:21:56.120 --> 00:22:10.100
Henry Yuen: This quantum lot of your tests, this is a very important part of MIT started cool sorry what I won't talk about and I won't have time to talk about is how do you combine the quantum load tests with this recursive composition, to get an MIT start protocol for the halting problem.
137
00:22:11.420 --> 00:22:13.280
Henry Yuen: i'm just going to focus on the A, B tests.
138
00:22:18.530 --> 00:22:20.240
Henry Yuen: Are there any questions.
139
00:22:21.500 --> 00:22:23.420
Marius Junge: So far, yes there's a question about Brian.
140
00:22:25.010 --> 00:22:27.110
Marius Junge: Brian do what go post this yourself.
141
00:22:27.650 --> 00:22:39.320
Bryan Clark: Sure, I was just wondering, so I mean the way you described it, it sounded like the key obstacle sort of in the console case was not having a global trustworthy source of randomness So if I just supplement.
142
00:22:40.490 --> 00:22:41.900
Bryan Clark: sort of classical computing with.
143
00:22:41.900 --> 00:22:49.940
Bryan Clark: Such a thing randomness from the sky that everyone trust and believe does that actually significantly increase the power of even sort of standard classical IP.
144
00:22:51.980 --> 00:23:04.370
Henry Yuen: I think, so I mean I haven't thought this through, but I think there's a reasonable classical model or you have some large trusted source of randomness in the sky, I guess, one issue is that.
145
00:23:06.500 --> 00:23:15.080
Henry Yuen: You know if you have like a micro verify it's still can't directly access all of the locations of all the random bits.
146
00:23:16.640 --> 00:23:17.720
Henry Yuen: So somehow.
147
00:23:21.140 --> 00:23:23.870
Henry Yuen: yeah it's not 100% I mean I guess there's some.
148
00:23:27.560 --> 00:23:34.880
Bryan Clark: But if you're careful with a model and say Oh, the river has to use the random good next five random bits or something coming from the sky and it's the golden.
149
00:23:35.600 --> 00:23:40.400
Henry Yuen: yeah then, then I think that would actually I mean that's that's essentially how this MIT star thing, where he said.
150
00:23:41.060 --> 00:23:43.700
Bryan Clark: Essentially, just translates exactly the costco case.
151
00:23:44.090 --> 00:23:48.260
Bryan Clark: there's there's nothing else about sort of quantum that is sort of sneakily going on.
152
00:23:49.880 --> 00:23:50.570
Henry Yuen: Right yeah.
153
00:23:51.920 --> 00:24:01.370
Henry Yuen: Exactly I think that's the right way of looking at it it's once you have the certified randomness and also that the access into this randomness is the is like the way you you think it is then.
154
00:24:02.240 --> 00:24:04.760
Bryan Clark: yeah great great thanks yeah.
155
00:24:05.150 --> 00:24:06.020
Bryan Clark: Good great question.
156
00:24:09.860 --> 00:24:10.640
Henry Yuen: Okay, so.
157
00:24:11.900 --> 00:24:21.620
Henry Yuen: So right, so the kind of the magic part is, you know how do you efficiently verify the existence of this entanglement and therefore randomness so.
158
00:24:22.910 --> 00:24:24.050
Henry Yuen: So let's uh.
159
00:24:25.970 --> 00:24:28.280
Henry Yuen: You know, go back to a simple example.
160
00:24:30.560 --> 00:24:42.830
Henry Yuen: So so let's think about the following constraint satisfaction problem Okay, I have it's it's a constraint satisfaction problem on nine binary variables right pi wanted to pi n pi at nine.
161
00:24:43.940 --> 00:24:45.890
Henry Yuen: And they're arranged in a three by three grid.
162
00:24:47.000 --> 00:24:55.850
Henry Yuen: And the constraints are that all rows and columns must select a zero MOD to except for the very last column, which is some to one so that i've highlighted it in.
163
00:24:57.080 --> 00:24:59.660
Henry Yuen: Whatever color, this is a green or something.
164
00:25:01.760 --> 00:25:05.870
Henry Yuen: So it's not too hard to see that this is an unsatisfying system of equations.
165
00:25:08.330 --> 00:25:17.360
Henry Yuen: And we can turn this constraint satisfaction problem into an interactive game, so this is known in the quantum information community has a magic square game.
166
00:25:19.490 --> 00:25:28.730
Henry Yuen: And how does this game work, so the very fire is going to pick a random equation a random constraint like so either a random row or a random column.
167
00:25:29.630 --> 00:25:39.470
Henry Yuen: And it's going to pick a random variable from this constraint so as an example, maybe the verified picks the middle column, and it picks pi five.
168
00:25:40.820 --> 00:25:41.480
Henry Yuen: As the variable.
169
00:25:42.650 --> 00:25:45.380
Henry Yuen: So the very first going to send.
170
00:25:46.400 --> 00:25:54.380
Henry Yuen: The equation to one prefer and the variable to the other, and the thing to notice that you know, for example, the variable proven doesn't know what equation.
171
00:25:55.460 --> 00:26:01.160
Henry Yuen: Was was chosen it's either the row containing that variable or the column continue that variable.
172
00:26:02.750 --> 00:26:08.450
Henry Yuen: And the movers are supposed to respond with assignments to either the equation, they were given or the variable.
173
00:26:09.560 --> 00:26:15.470
Henry Yuen: And the verify will accept if that equation player gives an assignment that satisfies that equation.
174
00:26:16.880 --> 00:26:21.830
Henry Yuen: And that assignment is consistent with what the variable player reported.
175
00:26:25.580 --> 00:26:36.500
Henry Yuen: So, again just you know, for the same reason classical proves cannot win perfectly, because otherwise it would imply the existence of a satisfying assign it to this.
176
00:26:37.520 --> 00:26:38.510
Henry Yuen: System of equations.
177
00:26:40.820 --> 00:26:49.790
Henry Yuen: But kind of the remarkable thing about quantum is that if the previous share entanglement they can win perfectly, and this is by using.
178
00:26:51.590 --> 00:27:02.000
Henry Yuen: entangled strategy where the previous share to APR pairs so each of them have to cubits and they measure poly observable on their API printers corresponding to this table.
179
00:27:03.530 --> 00:27:08.000
Henry Yuen: And you know thing to notice is this thing is called an operator solution to the.
180
00:27:09.320 --> 00:27:11.780
Henry Yuen: constraints satisfaction problem instead of assigning.
181
00:27:12.890 --> 00:27:16.010
Henry Yuen: zero or one values to the variables, we know assign them.
182
00:27:17.180 --> 00:27:24.200
Henry Yuen: operators in this case suffer joint unitary operators and they will satisfy these equations.
183
00:27:26.210 --> 00:27:35.420
Henry Yuen: And that's why there's a perfect quantum strategy for this game, and you know this is also one way of proving this famous bells theory.
184
00:27:36.980 --> 00:27:43.700
Henry Yuen: there's no classical satisfying assignment, but using a quantum strategy that you know these rumors can always win.
185
00:27:49.010 --> 00:27:50.870
Henry Yuen: Okay, so so that's kind of a neat game.
186
00:27:52.910 --> 00:27:59.660
Henry Yuen: And one observation is that suppose you, you know you play this magic square game with some improvers maybe they're entangled maybe they're not.
187
00:28:00.290 --> 00:28:16.400
Henry Yuen: But you play with them a bunch of times and you notice that they're winning with probably that's very, very close to one, and you know, maybe they've just you play it like you know 100 times 1000 times and they just win all the Games right and the first thing that you want to conclude.
188
00:28:17.450 --> 00:28:24.500
Henry Yuen: That you're forced to conclude, even if you don't believe in quantum mechanics is that their responses must be random.
189
00:28:26.240 --> 00:28:41.840
Henry Yuen: right there their responses have to contain entropy, and the reason that this is the case is because if they weren't random if they were responding deterministic Lee then they would just be classical movers and we know that they you know cannot win with probability one.
190
00:28:43.130 --> 00:28:59.630
Henry Yuen: Okay, so one way of thinking about this is that this magic square game is an interactive proof for randomness generation right it's not an interactive proof for a decision languages which, which is like the typical setting but really This is like an interactive proof for some.
191
00:29:00.710 --> 00:29:02.360
Henry Yuen: Physical property this case.
192
00:29:03.470 --> 00:29:12.710
Henry Yuen: The generation of randomness and this observation I should mention has you know led to this field of something called device independent cryptography.
193
00:29:15.170 --> 00:29:25.460
Henry Yuen: We know the basic idea is that by playing such games with untrusted quantum hardware, you can actually certify many cool things like random number generation.
194
00:29:26.000 --> 00:29:40.640
Henry Yuen: Secure key distribution even full fledged quantum computation just by playing a series of these games with these prefers you can certify that that there you know, for example, solving a some quantum computation.
195
00:29:47.450 --> 00:29:52.880
Henry Yuen: But we can say more, though, you know not just you know if you're playing this magic square game with these improvers.
196
00:29:54.500 --> 00:30:02.900
Henry Yuen: And if you're willing to assume that quantum mechanics is a valid description of nature, then you can actually guaranteed more about the structure of.
197
00:30:03.410 --> 00:30:18.440
Henry Yuen: The strategy that the players are using if they're winning with very, very high probability, so the following theorem mix expresses this it says that any perfect quantum strategy for the magic square game must be locally equivalent.
198
00:30:20.120 --> 00:30:21.470
Henry Yuen: To using this.
199
00:30:22.760 --> 00:30:31.040
Henry Yuen: To EP our state and poly measurement strategy that I described right, so this is essentially there's a you know up to local.
200
00:30:33.380 --> 00:30:39.050
Henry Yuen: You know, local changes of bases there's essentially a unique optimal strategy for this magic square game.
201
00:30:41.660 --> 00:30:54.020
Henry Yuen: And so, this is an even stronger statement, and so one way to look at this is that the magic square game is an interactive proof for a specific quantum property of the the movers.
202
00:30:54.740 --> 00:31:07.370
Henry Yuen: So, for example, if they're winning with probability one, then the variable players measurements, corresponding to say the first and fifth variables must anti compute.
203
00:31:09.440 --> 00:31:10.430
Henry Yuen: Right, this is.
204
00:31:11.690 --> 00:31:22.460
Henry Yuen: You know this is kind of a interesting thing to say, because you know the in know cases and know situations do you when playing this game do ask the the.
205
00:31:23.420 --> 00:31:35.510
Henry Yuen: proven to measure, both you know pie one and pie five yet by playing this game, and you know winning with high probability we do that there's some algebraic relation between their measurements.
206
00:31:37.460 --> 00:31:42.350
Henry Yuen: You know, we also reduce the number of key bits of entanglement is that these two and so on.
207
00:31:44.180 --> 00:31:47.180
Henry Yuen: And randomness certification is a corollary of of this.
208
00:31:48.620 --> 00:31:49.520
Henry Yuen: Of this.
209
00:31:50.690 --> 00:31:53.270
Henry Yuen: of you know certifying the existence of these quantum properties.
210
00:31:57.920 --> 00:31:58.820
Henry Yuen: Okay, so.
211
00:31:59.990 --> 00:32:17.540
Henry Yuen: So that's pretty cool but by itself, this magic square game is not going to be useful for us for the task of randomness testing and that's because the complexity and the randomness usage of the verify or in this magic square game is commensurate with the amount of.
212
00:32:18.800 --> 00:32:27.200
Henry Yuen: randomness that you've certified right, you know how many bits of randomness does the verify or need to sample a random equation and and random variable.
213
00:32:27.770 --> 00:32:40.280
Henry Yuen: Well it's going to be at least I don't know think it's like at least two bits of randomness but the amount of randomness a you get out from the improvers is going to be at most two right so you're not coming out ahead here.
214
00:32:44.990 --> 00:32:58.400
Henry Yuen: So what we want is a more efficient tests, for you know not just random hospital entanglement So what we want is an interactive proof for T cubits of entanglement so T is some large number.
215
00:32:59.660 --> 00:33:12.500
Henry Yuen: And we'd like the interactive proof to have an efficiency property, so the verified complexity should be much, much smaller than the amount of entanglements that you're certifying so verify complex, they should be say polly long T.
216
00:33:13.730 --> 00:33:29.840
Henry Yuen: We also want this interactive proof to be a robust so that means that any proof of strategy that succeeds with probability say one minus epsilon must be delta epsilon close to having Tiki that's an entanglement so delta epsilon is some robustness parameter that.
217
00:33:30.890 --> 00:33:32.780
Henry Yuen: You know you try to make as good as possible.
218
00:33:37.100 --> 00:33:51.380
Henry Yuen: Designing interactive proofs that satisfied just one of these properties is much easier than getting ones that satisfy both of them, so in the past, people designed interactive proofs that say her efficient, but not robust or are robust, but not efficient.
219
00:33:54.740 --> 00:34:00.170
Henry Yuen: And the challenges to get both of these properties so that's what the quantum law degree test accomplishes.
220
00:34:02.330 --> 00:34:11.930
Henry Yuen: it's a interactive proof for Tiki was entanglement verified complexity is probably a lot of tea, as desired the robustness it's not exactly independent of tea.
221
00:34:12.710 --> 00:34:23.630
Henry Yuen: But it has a very mild dependence on to, and this is something that we're willing to live with, so if the prove or 60s with probability one minus epsilon than what we know is.
222
00:34:25.040 --> 00:34:28.910
Henry Yuen: The closeness to having tea cubism entanglement is this quantity.
223
00:34:30.500 --> 00:34:39.020
Henry Yuen: In particular, we get non trivial guarantees when this epsilon how close you are to winning with probability one is one over poly long T.
224
00:34:43.280 --> 00:34:45.650
Henry Yuen: So that's what the quantum law degree tests accomplishes.
225
00:34:48.170 --> 00:34:49.550
Henry Yuen: So, so what actually is it.
226
00:34:50.960 --> 00:35:03.170
Henry Yuen: And the easiest way to explain it is to say it's the magic square game plus something, known as the classical loader B test and the classical the degree test is something that comes from classical complexity theory.
227
00:35:04.670 --> 00:35:05.180
Henry Yuen: it's.
228
00:35:06.710 --> 00:35:16.310
Henry Yuen: has nothing to do with quantum it's an efficient and robust interactive proof that the previous responses are consistent with some low degree polynomial.
229
00:35:17.300 --> 00:35:26.570
Henry Yuen: Right and it's the this classical that are the test is motivated by the following question, which is very natural so you know suppose that you're given some function F.
230
00:35:27.590 --> 00:35:28.790
Henry Yuen: that's defined over.
231
00:35:30.230 --> 00:35:35.000
Henry Yuen: After the ember F is a finite field, and it maps after the m to F.
232
00:35:37.640 --> 00:35:42.080
Henry Yuen: So you know you're given some some function like this as a black box.
233
00:35:42.680 --> 00:35:51.170
Henry Yuen: And suppose that you knew that this function agrees with a low degree polynomial on those lines right, so you pick a random line in this vector space F to them.
234
00:35:51.500 --> 00:36:01.490
Henry Yuen: And you have examine the values of this function along this line, and you see Lo and behold on those lines it agrees with a universal law degree polynomial.
235
00:36:02.900 --> 00:36:11.540
Henry Yuen: and based on this local feature of this function F you'd like to do some global structure of this function.
236
00:36:12.770 --> 00:36:20.450
Henry Yuen: That you were given and the the classical load of your test essentially says, if you know locally it agrees with low to be polynomials.
237
00:36:21.710 --> 00:36:24.050
Henry Yuen: Global globally, it must also agree with a.
238
00:36:25.070 --> 00:36:25.940
Henry Yuen: lot of people in them.
239
00:36:27.200 --> 00:36:31.580
Henry Yuen: And this cost of a low degree test has is extremely important to.
240
00:36:33.500 --> 00:36:37.040
Henry Yuen: Things like the PCP theorem and I P equals annex.
241
00:36:38.120 --> 00:36:44.960
Henry Yuen: And in the study of algebraic property testing so there's a long history of work on this load up test.
242
00:36:48.920 --> 00:36:49.520
Henry Yuen: and
243
00:36:51.020 --> 00:36:52.100
Henry Yuen: Okay, so.
244
00:36:53.210 --> 00:36:54.920
Henry Yuen: So, so what goes into this test.
245
00:36:56.210 --> 00:37:02.810
Henry Yuen: Well, you know we have this finite field let's pick D to be some degree bound let's think of D is something very small.
246
00:37:04.310 --> 00:37:08.390
Henry Yuen: And the verify and this test is going to pick a random point in this.
247
00:37:09.860 --> 00:37:17.720
Henry Yuen: vector space and it's going to pick a random line that goes through this point it's going to send the line to one improver and the point to the other over.
248
00:37:19.490 --> 00:37:26.840
Henry Yuen: The line proven is going to send a university degree the polynomial and the point proves just going to send a value be.
249
00:37:28.340 --> 00:37:38.960
Henry Yuen: In the verified is just going to accept if, when we evaluate this unit very polynomial G at the point X, corresponding to X than it agrees with the point proven.
250
00:37:40.190 --> 00:37:40.520
Okay.
251
00:37:43.850 --> 00:37:49.790
Henry Yuen: assume that we're in the classical case, so this second prove or P two is is some deterministic proven right.
252
00:37:50.300 --> 00:38:00.560
Henry Yuen: So it's going to respond with some assign you know, for every point X is going to give a value be right and we can collect all those values into some function F that's defined on the sector space.
253
00:38:03.410 --> 00:38:10.070
Henry Yuen: The guarantees of the classical interview test is that if these proves past with high probability let's say one minus epsilon.
254
00:38:10.670 --> 00:38:27.830
Henry Yuen: Then the point proves function like their responses must be close to some global degree D polynomial defined over the entire vector space so it's a multi very low degree polynomial and the closeness is you know essentially epsilon.
255
00:38:30.080 --> 00:38:35.570
Henry Yuen: Right, so this is the you know local to global structure theory that the load up test provides.
256
00:38:37.040 --> 00:38:39.020
Henry Yuen: This test is very efficient right so.
257
00:38:41.150 --> 00:38:43.880
Henry Yuen: You know, essentially, you know one way of thinking about it is that.
258
00:38:45.260 --> 00:38:48.350
Henry Yuen: The amount of time that this verify takes is going to be.
259
00:38:51.050 --> 00:38:56.270
Henry Yuen: logarithmic in the size of this vector space, you know, the number of points in this vector space.
260
00:38:58.010 --> 00:39:02.750
Henry Yuen: Yet it's still able to certify some global property of this function.
261
00:39:04.220 --> 00:39:15.650
Henry Yuen: And you know it's quite robust right if you pass with say 99% probability than your this function F is going to be roughly 1% close to being a degree de Palma.
262
00:39:16.880 --> 00:39:19.610
Henry Yuen: So this is a very good test of it is very good properties.
263
00:39:22.850 --> 00:39:23.330
Henry Yuen: and
264
00:39:24.530 --> 00:39:29.030
Henry Yuen: Okay, what but you know that wasn't The case of classical proves what happens when the proof is or quantum.
265
00:39:29.630 --> 00:39:40.430
Henry Yuen: things get more complicated because the approvals, are no longer responding with respect to some deterministic function but you still can make some structure here, and I think in the interest of time I sort of.
266
00:39:41.690 --> 00:39:52.070
Henry Yuen: I won't really explain the precise details of the statement but it roughly says that even with Kwan improvers when you perform the classical law degree test.
267
00:39:52.850 --> 00:40:05.180
Henry Yuen: If they win with high probability essentially they're you know they can't really be using their entanglements they have to be responding consistently, according to some, at least some probabilistic mixture of degree polynomial.
268
00:40:10.100 --> 00:40:12.410
Henry Yuen: Okay, so so now let's sort of put everything together.
269
00:40:13.610 --> 00:40:20.660
Henry Yuen: The quantum law degree test, as I mentioned, is the classical liberal pre test, plus the magic square game and so.
270
00:40:23.060 --> 00:40:37.970
Henry Yuen: In this quantum letter b tests to verify or is going to do the following with probability one third is going to play the classical, though, to be test in the Z basis it's going to tell the improvers hey we're playing the lottery test we're focusing on the Z basis let's do it.
271
00:40:39.140 --> 00:40:43.790
Henry Yuen: And so the play that game with the probability one third you'll do the same thing, but in the X faces.
272
00:40:45.530 --> 00:40:48.770
Henry Yuen: And then finally to sort of relate the the two games together.
273
00:40:49.790 --> 00:40:55.640
Henry Yuen: The verifiers going to play the magic square game which relates to X and Z bases.
274
00:40:56.900 --> 00:41:01.250
Henry Yuen: And sort of tie everything together okay so that's that's a very high level.
275
00:41:02.720 --> 00:41:03.770
Henry Yuen: picture of what's going on.
276
00:41:05.210 --> 00:41:07.070
Henry Yuen: it's, this is a very efficient.
277
00:41:09.470 --> 00:41:11.240
Henry Yuen: verifying verified it runs in.
278
00:41:12.470 --> 00:41:14.900
Henry Yuen: Such a logarithmic in after the m.
279
00:41:17.480 --> 00:41:37.430
Henry Yuen: And here are the guarantees that we get so suppose that quantum improvers pass this test with probability one minus epsilon, then what we produce is that the entanglement that they share has to be delta close to to to the mvp are pairs so an exponential number of EPI pairs.
280
00:41:38.660 --> 00:41:48.500
Henry Yuen: Right and and here's the thing to compare is you certify to to them APR Paris, but how much time that this verify or take only polynomial and right so very efficient.
281
00:41:50.210 --> 00:41:57.380
Henry Yuen: Furthermore, the measurements are also close to being a collection of politics and policy observable.
282
00:41:58.460 --> 00:42:01.850
Henry Yuen: And the robustness is is pretty good.
283
00:42:07.820 --> 00:42:17.930
Henry Yuen: Okay, so so just to zoom back out right this quantum loaded retest this is interactive proof of the presence of two to the end, a PR person and polly X and Z measurements on them.
284
00:42:18.860 --> 00:42:29.840
Henry Yuen: to verify runs and polynomial and time and you know what so what's going on this verifiers really just getting in some sense local views of these exponentially many APR pairs.
285
00:42:31.670 --> 00:42:33.620
Henry Yuen: But this test is designed so that.
286
00:42:34.820 --> 00:42:43.790
Henry Yuen: If the previous pass with high probability it really ensures that there are an exponential number of cubits behind the previous responses.
287
00:42:44.660 --> 00:42:56.210
Henry Yuen: So, so the very fire submits a poly ambit query it gets a poly and bit response but behind the scenes it's somehow certifies that they really must be these many PR pairs and that.
288
00:42:58.190 --> 00:43:04.430
Henry Yuen: The movers are performing some politics or policy measurements on all these EPI pairs and just post processing the outcomes.
289
00:43:07.490 --> 00:43:10.910
Henry Yuen: Okay, so I think in the last like one minute or so.
290
00:43:11.990 --> 00:43:12.740
Henry Yuen: Let me just.
291
00:43:14.090 --> 00:43:24.830
Henry Yuen: Briefly, explained, like, I think all of this, you know quantum low to retest and classical that express a low degree test point to an interesting subject which I call documented properly testing.
292
00:43:28.160 --> 00:43:37.220
Henry Yuen: So property testing is very well studied subject in theoretical computer science, I mean it's all about local to global phenomenon.
293
00:43:37.940 --> 00:43:45.110
Henry Yuen: Right and and the general format of the question is, you know if you have some common tutorial object that locally, has a property p.
294
00:43:45.830 --> 00:44:03.260
Henry Yuen: Most of the time, does that mean that object is close to having the property P globally right so some examples of questions are like is a function low degree, is a craft planar is a craft a colorful right, so these sorts of questions are studied a lot in the property testing literature.
295
00:44:05.180 --> 00:44:11.630
Henry Yuen: And in in the property testing model we can we can just imagine that you know this object is whether it's a graph or a function.
296
00:44:12.410 --> 00:44:26.720
Henry Yuen: You know it's represented as some black box and we just get to make local probes into this black box to get evaluations and based on that you want to do sort of globally what what this you know what's going on inside this black box.
297
00:44:31.190 --> 00:44:32.540
Henry Yuen: But in the quantum setting.
298
00:44:34.100 --> 00:44:43.640
Henry Yuen: You know, we can also take a similar model, but instead of having a deterministic black box what is inside this black box every time you submit a query it's performing some quantum measurement.
299
00:44:44.480 --> 00:44:52.970
Henry Yuen: Right and and I think this is a sort of the starting point for this non commutative property testing right, so we can imagine that.
300
00:44:53.990 --> 00:45:01.790
Henry Yuen: Someone walks up to you with a black box every time you plug in a query there's some internal hubert's hilbert space, maybe it's something like.
301
00:45:02.660 --> 00:45:14.720
Henry Yuen: An n dimensional space and for every query that you make there's some associated measurement that's being performed, and you can make a sequence of queries but because you know in quantum mechanics measurements.
302
00:45:15.740 --> 00:45:26.630
Henry Yuen: don't commute necessarily the sequence, in which you make some queries can matter like the order in which you make these queries and outcomes will be random right according to the laws of quantum mechanics.
303
00:45:27.980 --> 00:45:38.330
Henry Yuen: And so we can imagine you know, for example, you you submit your queries and it just performs the measurement on some internal state and it returns you outcomes, corresponding to the measurements.
304
00:45:41.660 --> 00:45:45.320
Henry Yuen: And I think if this model of some very clean property testing questions.
305
00:45:47.300 --> 00:45:55.190
Henry Yuen: can be extracted out from MIT star equals Ari without talking about proves or verifiers or you know entangled strategies.
306
00:45:57.980 --> 00:45:58.820
Henry Yuen: So, for example.
307
00:45:59.900 --> 00:46:02.060
Henry Yuen: You know this low degree test.
308
00:46:03.650 --> 00:46:17.840
Henry Yuen: This classical that are your test when you analyze it in the setting of quantum in this not computed property testing, you know the the thing that's proved about it can be formulated as a result, about testing the internal workings of this quantum black box.
309
00:46:21.140 --> 00:46:25.070
Henry Yuen: But there I think there's also many other questions that one can start to ask about this model.
310
00:46:26.210 --> 00:46:35.150
Henry Yuen: You can ask non competitive extensions of classical questions right like let's imagine that this black box you submit the name of a vertex and it outputs say.
311
00:46:35.570 --> 00:46:46.610
Henry Yuen: color But what if, to determine the color a measurement is performed right, and so you can ask is K color ability locally testable in this setting right.
312
00:46:47.690 --> 00:46:50.030
Henry Yuen: And you know what sort of guarantees can can you.
313
00:46:52.280 --> 00:46:59.090
Henry Yuen: formulate about the structure of these measurements, if you notice that you know the key color ability properties always preserved.
314
00:47:02.510 --> 00:47:07.280
Henry Yuen: Right, but you can also formulate new questions that you know that are not just extensions of classical questions.
315
00:47:08.990 --> 00:47:12.470
Henry Yuen: And you know, maybe I can talk more about that if people are interested.
316
00:47:13.820 --> 00:47:27.590
Henry Yuen: And, basically, I think you know the the summary is that this is a new model of property testing that really gets at the core of think what's the interesting stuff that's going on inside and I P star equals already in there, a lot of interesting questions to pursue.
317
00:47:30.590 --> 00:47:33.710
Henry Yuen: Okay, so this is the last slide sorry for running over time.
318
00:47:35.720 --> 00:47:42.320
Henry Yuen: In this talk, you know I talked about a blueprint for verifying the halting problem using recursive Lee compose PCP is.
319
00:47:43.970 --> 00:47:54.530
Henry Yuen: The bottleneck to doing this was you know how do you efficiently verify entanglement and randomness so we use this thing called the quantum law to retest and ensuring this low debris test suggest some.
320
00:47:55.760 --> 00:47:58.400
Henry Yuen: Some asteroid questions and non commutative property testing.
321
00:48:00.110 --> 00:48:01.790
Henry Yuen: Okay, so, so thank you very much.
322
00:48:03.440 --> 00:48:05.960
Marius Junge: yeah thanks for this many.
323
00:48:07.430 --> 00:48:09.380
Marius Junge: very interesting talk about them a question.
324
00:48:11.840 --> 00:48:12.200
Marius Junge: Right.
325
00:48:12.290 --> 00:48:13.700
Bryan Clark: I have a quick question.
326
00:48:15.650 --> 00:48:27.170
Bryan Clark: So i'm kind of confused about something somewhat basic so it seems that you've described interactive protocol to can miss someone whether the halting problem.
327
00:48:28.130 --> 00:48:37.490
Bryan Clark: Something is holding it or not, so what i'm confused about is it seems like I could then determine whether something holtz or not without the.
328
00:48:37.790 --> 00:48:53.900
Bryan Clark: Hoover is just by enter in your reading all possible conversations I might have had with the river and check whether each of these conversations would have convinced me or not, and again I can't do it upon the meal time but I can do it in some compatible time, so what what am I misunderstanding.
329
00:48:54.860 --> 00:49:05.450
Henry Yuen: Oh great question of the thing, so that the thing that this result implies is that there's no way of determining whether a given conversation is a valid one or not.
330
00:49:06.500 --> 00:49:11.390
Henry Yuen: Like could could this conversation have come out from some entangled strategy.
331
00:49:12.080 --> 00:49:20.600
Bryan Clark: I got it good so so given a conversation, you can determine whether you're convinced or not, but if I just enumerate all conversations their conversations that list that can't.
332
00:49:21.740 --> 00:49:24.500
Bryan Clark: Actually ever happened is what you're telling me is that is that.
333
00:49:25.130 --> 00:49:26.480
Henry Yuen: yeah, so I think.
334
00:49:28.040 --> 00:49:29.600
Henry Yuen: You know, given any fixed.
335
00:49:30.620 --> 00:49:37.670
Henry Yuen: conversation it's hard to say whether this could have occurred and really the thing you want to look at is like you want to look at.
336
00:49:39.170 --> 00:49:43.070
Henry Yuen: Strategies because you know conversations have occurred probabilistic Lee like because.
337
00:49:43.220 --> 00:49:53.330
Bryan Clark: I understand I could enumerate all bit strings right, and so, if I enumerate all the strings then like that enumerate all possible conversations I know which of those if they actually happened to convince me whether or not it's false it or not.
338
00:49:53.870 --> 00:49:57.410
Bryan Clark: you're just telling me I can't know whether some of them could have happened.
339
00:49:58.340 --> 00:50:14.060
Henry Yuen: Well, so it think what's more important is like the probability with which these conversations could have occurred so in no case if the turing machine didn't hold there's still some small probability that the movers could have convinced you that it helps so.
340
00:50:14.420 --> 00:50:19.490
Bryan Clark: Remember, these conversations don't happen bit string conversations don't happen uniformly or something so.
341
00:50:19.730 --> 00:50:24.410
Bryan Clark: I can't just count how many of these convinced me, yes or no, for that matter.
342
00:50:24.710 --> 00:50:24.980
Right.
343
00:50:26.030 --> 00:50:26.480
Okay.
344
00:50:27.770 --> 00:50:28.610
That makes sense.
345
00:50:32.060 --> 00:50:42.020
Marius Junge: Okay, we we had a little bit over time I have I have one more question, so I know this is a very theoretical without making you probably agree on this one, but.
346
00:50:42.470 --> 00:50:51.560
Marius Junge: This testing questions could this an end eventually to a device which tells us whether a search and new quantum device is as quantum SP think it is.
347
00:50:52.880 --> 00:50:53.330
Henry Yuen: yeah that's.
348
00:50:54.050 --> 00:51:02.510
Marius Junge: Practically I mean so So if you I mean maybe this is not near term, but if you really want to certify to a person you built the quantum computer.
349
00:51:03.440 --> 00:51:12.380
Marius Junge: Right and then such a past, which you know if you pass the test, then, then you know, this could have not been done with the cheap simulation right.
350
00:51:13.250 --> 00:51:14.810
Henry Yuen: Right, I think so.
351
00:51:16.070 --> 00:51:25.400
Henry Yuen: yeah I mean as a as a start, I mean when you're building clarify, so I guess, one of the first things you want to check is that is it capable of generating like highly entangled states.
352
00:51:26.090 --> 00:51:32.600
Henry Yuen: And enough entanglements so so something like this quantum lot of your test could be a way to to do that.
353
00:51:34.190 --> 00:51:34.580
Henry Yuen: and
354
00:51:36.650 --> 00:51:47.270
Henry Yuen: yeah I guess you know one thing that you know you have to ensures that somehow that you have these, at least with these types of tests, you have to ensure that there's two separated or non competing catering parts.
355
00:51:48.020 --> 00:51:55.100
Henry Yuen: of your chip like maybe that's a reasonable assumption, I mean I you know we don't think of these chips as being adversary really designed, I mean not always.
356
00:51:56.780 --> 00:51:57.650
Henry Yuen: So yeah I think.
357
00:51:58.520 --> 00:52:01.400
Marius Junge: I think there's a real I mean but, but on the other hand, is the.
358
00:52:01.460 --> 00:52:13.640
Marius Junge: classical test which you are describing actually that's a comment from from leg so So if you want to really test, something you have to also decide the input and output is classical for a certain way right, I mean.
359
00:52:14.420 --> 00:52:19.340
Marius Junge: If you want to certify that to a person on the street, who has no quantum capabilities.
360
00:52:20.690 --> 00:52:22.700
Marius Junge: The test has to be classical right.
361
00:52:23.720 --> 00:52:26.090
Henry Yuen: Right, I guess that's the more convincing yeah.
362
00:52:26.240 --> 00:52:28.640
Marius Junge: yeah and so that that's why you know you.
363
00:52:30.170 --> 00:52:30.440
Marius Junge: Right.
364
00:52:31.190 --> 00:52:37.880
Marius Junge: And you will still want to convince a buyer, who is the classical person that you have a quantum machine in your backyard right.
365
00:52:39.050 --> 00:52:47.870
Henry Yuen: Right, I mean, I guess, maybe you can imagine you say look I have these two quantum machines ones in one side of town, the others, on the other side of town and we.
366
00:52:47.900 --> 00:52:49.640
Henry Yuen: play this game and.
367
00:52:49.940 --> 00:52:55.220
Marius Junge: We have to do it as a join as a joint endeavor right, I mean you're you're showing that okay.
368
00:52:55.730 --> 00:53:13.130
Marius Junge: yeah Okay, the about that this is not okay good let's let's reconvene we can have this discussion and other time let's reconvene in actually we have a little bit of time we start with after lunch with Brian class talk at 130 so let's thank him again.
369
00:53:14.840 --> 00:53:15.200
Henry Yuen: Thank you.
370
00:53:15.920 --> 00:53:22.130
Marius Junge: And then you reconvene at 130 is Brian talks a little bit of free time for your intellect away.