Merken
General Principles of FaultTolerance
Automatisierte Medienanalyse
Diese automatischen Videoanalysen setzt das TIBAVPortal ein:
Szenenerkennung — Shot Boundary Detection segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.
Texterkennung – Intelligent Character Recognition erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.
Spracherkennung – Speech to Text notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.
Bilderkennung – Visual Concept Detection indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).
Verschlagwortung – Named Entity Recognition beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.
Erkannte Entitäten
Sprachtranskript
00:00
OK let's make a start my great pleasure to introduce a new Gossman will be talking about general principles of full toss so thanks Austin and thanks to the organizers for inviting me although when they asked if I had any preferences as to when to speak I mean should that's when the Banquet was but thank you all for coming anyway I so I was working on this talk a bit late last night so it came out maybe a little bit backwards so I'm going to start with the open questions and let me make it completely clear up front that I'm not going to answer any of these questions but have what I would like to do in this talk is to kind is discuss some of the kind of unifying principles of faulttolerant constructions and freckled results and kind of maybe give you some some some new ways of thinking about these things and and unifying of old ways that that might help us as answer these and other questions so of course a lot of these questions we heard about yesterday or were other points in the conference on batik quantum computation but of course always this talk about better freckled rates we hear about self correcting codes a bet and those of course could still be improved from what we have now of some in really care about like optimizing a photon protocols depending on the the physical gates sets against at a little bit about that and were were maybe loop about experimentalist desire get better for the dates and a little bit about specific noise models 1 thing we we really didn't have much of this conference is not CCITT protocols and I think that's an area that's a very fertile and could see lots and lots of maybe not so much for the the error rates but for the the types of magic states we can distill and the devil I don't think any any work on getting the efficiency of magic state critical side and probably that that could be something that could be improved quite a lot of I just through this and you know what we heard a lot about surface codes and and fault tolerance in 2 dimensions but 1 dimension is also kind of interesting architecturally and and right now the the default on protocols and 1 measure and a good probably that's an inherent limitation never going to be as good as in 2 D but but maybe it could be improved a lot of what we have now but Brazil I think that they're the biggest and probably most important open question fault tolerance is reducing the overhead on time overhead you can you can tend to get pretty low if you if that's really you're you're you're goal but space overhead well we all know that's that's quite large and so 1 of the things I wanna talk about is to what extent and we can get that down so now that Antony opens let's say move on to the summary
03:03
conclusions on so this I and and also do something in this talk that I very rarely do what his talk about multiple separate topics as a normal and I have an outlined but this time I decided it was probably a good idea to put 1 up there so that you'd have will be totally surprised when I I jumped from topic to topic in the middle so those 3 basic topics that I wanna talk about so 1 of them is a kind of unifying properties of faulttolerant dates what the different kinds of fault on gay constructions we we know so far have in common and I think there's an underlying principle there that that all faulttolerant gates have to satisfy and then a rather different topic you'll use maybe a couple of those ideas but mostly separate which is suppose as a compressible suggest yesterday you wanna come up with a new family of codes that gives a threshold need in order to do that what is really that the critical properties that family could family has to have and then finally I have this question of overhead so again I can answer that question of what can you do the overhead but and maybe I'll kind of kind of pushed and see what the ultimate limits of overhead that you might conceivably reach with AppleTalk protocols what are that and as a see there's not much in the way of of limits I mean based on what we know now OK so 1st topic unifying copies of fault gates so there's but you can guess I didn't I didn't I didn't quite make this consistent size industry 3 classes but really there's 3 classes plus a grab bag of some other constructions but the main 3 classes I think we all know those they were introduced in in through land also a tutorial part on there's transversal gates of course have you know to code blocks and you like the qubits into 2 gates between them there a happy states and topological Koja the obvious example of that where you you for instance take 2 defects and you move them through a path in such a way that they bring around each other during the fault tolerant gay on encoded subspace and then there's a Seoulbased instructions with magic state constructions being the the most obvious predominant 1 of those and as they said there's a a couple of other a kind of random other constructions that it don't fit very well into these categories but as you'll see there is still the same kind of the basic underlying principles that that have and of course there's you know these gates these types of games have have different advantages and disadvantages probably the nicest in most respects the transversal gates on but of course we have Canton University it's using just transversal gets that's result by by Eastern in of and that and the other thing about and Russell Gates' well there's some codes have lots and lots of friends Russell Gates like the the 7 Cubitt code has spent the whole prefer group can be done conversely was other codes have very few transversal gates and it turned out that any stabilizer could have used a few friends wrestled it's but but there may be some months Yukos' don't have any at all and then packed states they're they're kind of nice I very at their kind of slow if you take a few try stimulate them in the circuit model because you have to to move the defects around slowly and and and make sure that you stay in the code space the whole time but but they don't really require many execute to do whereas this and so constructions while you have to make them solid that's a very hard thing to do you need to have some big as olfactory that's that's churning them out in distilling on edge so that they're ready for the computation 1 you stop and so there's you know none of these is really a perfect solution but I knew like if we could to get along just transversal gates but you know we can dig a universe all you have to after 1 of these things and voice exactly a set of gates everyone use depends a lot on her so I suppose we do come up with some new code and we like to to start doing fault tolerance with it well silly some general constructions we can use of and I'll discuss those little that later but I listen understand 1st what kind of really the options and and what these different types of of faulttolerant constructions have in common so I 1st let's start
07:52
with with topological gets so tublike Colgate said we we we think of them as as moving some defects around but we can also simulate that in a circuit model on if the if the code is like a surface code something else is implemented as an few that's with kind of explicit cats that were doing to to keep it in code space and what is what is is breeding look like that well so the basic model here is we we start with some defects and his mark them red and blue so that you can you can tell which ones of which and we start to move the defects so that so that there are starting to to move around each other and eventually you know go to a loop and get back to where we started but something nontrivial as happened in meanwhile and the there's been included did so what does it mean when we think in the circuit model to say you wanna move 1 of these defects well that defects are realized you know as as holes in some right with shacks along lattice and moving a defects means that you you may be destroyed by the were ignore that the parity checks in defect and create new ones behind it and as the effective of shifting the defect over spot for that and then you do this again and again and again and you can move the defect from 1 spot to another just read through you know a single qubit operations of course you want using parallel so that you can you can move it relatively quickly on but but that's a perfectly valid circuit there so what we're doing is about were were actually changing the code when we move the defect right with changing it from a code that has party text over here to 1 that has any checks over here and not over here of and they're very similar could have you know the same number of defects in them and the facts about the same distance apart because if triggered we haven't moved free far so it has high basically the same error correction properties original code it's it's it's maybe depending on him Quillen said may or may not be equivalent to the original code out but it's it's really a very similar Cook regret and then this whole process of braiding means that we move to a series of codes and eventually get the and when we get the defects back into the river of lifted will back to the original code right and of course the process of doing this We've done some logical operations on the encoded state so that's how we can think these topological codes as really another construction in circuit model OK so the next so so 4 top level codes we like to think of these these you code deformation as the weighted to gates and for a further other kinds of block codes what preferences to the transversal gates so why is it that transversal gates are good for a U.S. standard blocked minimum distance codes worse co deformation is is good for topological well I know that that the basic principle here is that the the type of data 1 use has to be matched to the type of errors that the code is designed to correct so in particular that a standard block code you say well this code can as distance d so it can correct errors of weight about you over to and the advantage of transversal gates is that if there some preexisting errors on the code and then we do a transversal K L though the weight of the errors don't increase release the weight within a single block obviously if control not like this can spread in error from 1 block to another but if there is only 1 error in the 1st block the now this 1 it's still only 1 error in the 1st block is also maybe 1 of the 2nd block OK so transversal gates of the property that they don't change the weight of errors that and that's why the good for regular dates for regular codes that that had the a minimum distance I now topological gates will remember there were created by by by breaking stabilizer generators and creating new ones so they actually can change the weight of errors if there was a preexisting error in the vicinity of a defect it can grow slightly larger and I see the process of moving it can automatically create some errors because you know the new stabilizer generous is nothing to constrain they're not create them OK now that's not a big problem because you know if they if the number of errors is is not very large elsewhere the code you can say well I I know there was gonna be error here anyway because I just created this stabilizer generator and so I could match up with the boundary defect and and get rid of it very quickly that way but of course if you're in a situation where you're you're very very near the threshold the percolation fretful this of this code that at the error could tend to take you over yet for that but that the property the main property of these topological dates is that the errors that you create all these local 3rd there the near the defects that you moving OK and so this process of moving a defect it can increase the number of errors unlike a transversal gates but only increases them locally MetLife here if you're not you know just wide at the threshold this is acceptable thing to do because topological codes vector handle local errors now I hope no 1 wants to press the on exact definition of local areas because of course they're fine if you have you know a little bit of error over here a little bit of over here and basically lets it doesn't take up you know too much of the the the space and the code but but nevertheless this this basic property of topological dates
14:17
that that it only creates kind of nearby spread of errors physically nearby is is matched to a property of the code that it's robust against you know local deformations of the geometry OK and I mean so I probably this is not really new to you but when you start to think about codes for instance to to work on different error models this principle becomes incredibly important 1 and so for instance if you want to come up with a code that corrects phase gates as as we've heard about in in a talk a few days ago but you need to use diagonal case because diagonal gates are the ones which that maps user's phases if you try to had a on code that corrective phase errors will change a phase error into a bit flip error regret and then your code would not working and and this vast of that is what makes it so hard to come up with codes that that will deal with kind of general error models as opposed to the generic model so you you know like people say well OK we should look at what types of errors are in the in the in the computer and design a faulttolerant particle that works that way and you can do that that's great but it's very hard and the reason it's very hot is because this very limited choice of gates that don't change the but OK so that select a little bit more about this difference between a transversal gates of Watergate different brussel gates as I said they they keep the weight of the error the same was topological gates they actually increase the number errors slightly of and I this creates a kind difference in how the use again if you think of it and circuit models so transversal gate well in principle you can you can take not a series of transversal gates all in a row and the product is still a transversal gate so there's no rule that says we have to stop and you are correct I mean if you doing that progress control not did he really do want stop and you're correction because you're spreading errors between different blocks of the code but you know it depending on your circuit that that may not really be a big issue at worst topological codes well you know as you move the defects so if you don't stop and you are correct you creating more and more errors along the path of the fact that you're moving or they end up if you if you don't do any errorcorrection all you move defect all the way around another defect well then you would have done a controllable date you just created an right because you have you have spread there all along the path is defect would be at a topologically nontrivial loop so if you want is a circuit model you actually have to to move a little bit and stop and you are correct and move a little bit and stop and you're corrections some more and you have to keep on doing this all around the path to that end you know for the existence of all torrent that's not a problem at all but it's 1 of these things I was getting to toplevel gates on the basis that the slowness is 1 of the things that makes a kind of slow when you think of it in the circuit so they compare differences of so now if we as we start to think of other kinds of gay you can see that that this property of an increase in the number of error and stopping you errorcorrection doesn't have to be constrained to topological it does of course have to you have to restrict attention to close the correct more than 1 error because you know of 1 becomes due errors in a commonly corrects 1 error then you're in trouble but once you have a code that has a reasonable distance released a reasonable tolerance to typical errors then it's OK to to have gates that have a property that are harder than or called spread and so what spread is is well if you start with and with the same 1 error then I do a faulttolerant gate that has some finite spread will a number of errors will increase but only increased by this constant factor which is the spread of the construction different and you have agenda spread to date that 1 error so I spread to didactic faulttolerant did than this 1 error could become 2 hours and then obviously don't a bunch of of dates with with finite spread all together right away because then you and other such data to Earth become for errors and then would coming errors and pretty soon you run out of errorcorrecting capability to handle this but if after 168 stopping you error correction while that will reset the procedure and of course there might be a meaning ideally if the errorcorrection a perfectly give all the errors but there might be some new new error that occurs during your written procedures so then you might have an error and then maybe you another it spread to date and and I have 2 hours again do correction again and so on and so in principle this is a perfectly good with data to construct faulttolerant dates I mean it's not as good as transversal gates and the reason it's not all is well these 2 reasons I guess 1 of them is that you need to stop and you're correction but another rather important a property is that it means that your code is robust against errors because you know if before you had a code corrected to errors now you can get to errors even if there's only 1 thing that happened 1 gate that's wrong right 1 1 error that occurred originally or that and if you add to hours originally then the spread to gate is going to kill your code to not really using the error correction capability of the code to the greatest possible extent nascent effort you're you're at your threshold value for instance if you have 1 of and but you know if if you have a really good code that's that's desirable in other ways it's maybe so worth considering this type of gaze particularly if it only you know 1 type of data that works that way and you needed to compete complete universal that so I so they so another it now that's that no think again about these
20:46
transversal gates and start to see if we can we can find ways with the the more similar public forget so out 1 thing that that we should note is that as experimentalists will tell us is not enough to just press a button and have a unitary date implemented immediately right actually what happens is there's some laser that goes on some Baltic that's applied or something like that that causes a Hamiltonian to turn on and that will gradually transforms though that the initial state into the state with the unitary on gradually of course you know is a is a relative term a could be over very short time scale but still it was continuously from the original state to state with the unitary on and getting back to this condition that the the gates after the match to the type of error that the code corrects this creates an additional constraint because not just the overall unitary that has to match the the the type of error but actually the infinite at all times you don't want convert phase there isn't a bit Laperrouze if your code only corrects phases for that of Mathematics again important for this for these codes that that correct phase errors fall colors propose a accord phases because well like this not for instance doesn't convert phases to bit flip there's right as z tensor Ivester's tensor I items this is it has so you might think that you could use you knots on the east coast but really this you can and the reason is because there's no way to generate the C not without going through some gate along the way that does I mean you Terylene generates in not not going to send way that does convert phase errors into that the parents were entangles the 2 or something like that great where you actually have to restrict yourself to dialog it's because died will to be generated you know as a the exponential of the diagonal Hamiltonian and and that that will have a problem OK so then it means if you if you're trying to think of a code that correct some some other different model this is a very important constraint to take into account and of course if add so top now going back to the similarity between topological transversal gets will top 1 Colgate's well it's kind of obvious how work generating those infinitesimally right we're taking defect and removing it infinitesimally and keep on moving in moving in moving into we get back to research of but you know friend Russell Gates we can also think of that way so if reversal gates and the nice thing and 1 of the night is many nice things about the food is the 1 of the nice things that that means that we still really do have this property that they don't increase number of errors that for the brothel dates the tensor product of things and therefore they can be generated by tensor product is work on other days so I so you know we want we want rotate the blocks sphere here in this direction and so that means we can just rotate them all separately but simultaneously and will eventually get to where we are to a 2 1 go for that and that so that's that's a nice thing that means from gates can be a tensor product of infinitesimal it but it but we start to think about it this way you realize that that that the that the picture of what's happened the transversal gate out slightly different normally when we think about it for Russell Gate is or will wanna try find reversal gay for code we say well what is that we can do transversal that will take this subspace of the orbit space as corresponds to the code and and map it into itself but that's not really what happens when it implements a transversal data the tessellate atoms if you start with this code space you do some infinitesimal operation and that will automatically take you out of the code space will take you to different subspace and then you keep on going going to get back to you results substates at the end of the transversal operation OK and this is this is not something that people usually think about we think about reversal usually just say what is that you start a new and in the code but it's always done by going out of the code space and coming back of and
25:28
so really what's happening it is you're doing a kind of co deformation Evista co deformation by local unitary operation so that inference in particular this infinitesimal transversal gates local unitary operations and what that means they're sold themselves so they have this property that they don't increase the number of errors and under any kind of transversal gay and K D quantum error correcting code is going to be mapped to a different while at the same or different and K. 1 errorcorrecting code so this series of subspaces that we go through 1 during the infinitesimal gates they're all equivalent kind by definition to reveal code but in particular they encode the same number of qubits and they had the same errorcorrecting capability OK and that so it's it's an interesting thing to think about taking the the the whole set of possible subspaces of dimension K and dividing them up under local unitary equivalence that this has been done a lot in the theory of entangling people study a lot on seeing what different classes states you get or occasionally subspaces you get when you do the subdivision and so I've I've kind of gone up schematically some of the examples here when you have 5 qubits in a 2 dimensional subspace so for instance 1 1 sec component is going to be the subspace that that takes arbitrary thing on the 1st few that and the other qubits all have some fixed value so for instance 1 of the subspaces here is the 1st year tensor 0 0 0 0 0 0 0 on the other 4 qubits but as the dual unit carries while the local unitary on the 1st few bet that doesn't change the subspace it this changes the state in the subspace if you do looking at is other qubits while you think the values but the 1st you that most of the other for half that so this that components whatever you will communities i it's always in on entangled state or and then deciding when investors like this 1 generated by all zeros in all ones so this subspace contains some on internal states but also contains entangled states because it contains then the cat state 0 0 0 0 0 plus 1 1 1 1 1 day and therefore we do local unit cherries on it you get other subspaces things generated by you know 2 orthogonal locally orthogonal product states and it done the same property that the hubble basis that's tensor product states and also contain entangled states OK now this the code is good is a repetition code I mean it cracks 5th bearers it doesn't correct phases of course is totally it's getting more warble twophase art then then then uncoated state and because we're thing about general local unit cherries but that's a property does not very well maintained over because the before there's from phasers and vise versa so while all these other codes all these other 2 dimensional subspaces in this component will have an the capability correct some kind of error well there's always some other kind of error that they they don't correct well and exactly what those errors or will differ from such that this subspace substance but then we can move to the component that intensified CuO and fight code I was lacking in the fighting because unique but that there might be some permutation so there might be no more than 1 a couple of components that that look like this and the fighting the code and really does correct aristocrats 1 general and therefore all the local unitary rotations we do that code will also correct 1 error that so I could say that that this this kind of picture is is some work that's done with them so on let's examine blood is said to be a lot of work in time a theory on classifying different offices we get this way but that's not really what I'm interested it really what I'm interested in is doing transversal dates and what that means is that we wanna look at the structure of this particular component right in the figure cases not with point doing that I mean there's might is nothing new to be learned Backus Russell gave you already know that Connes Russell gets the fight bicubic but again it's a picture a kind of conceptual tool that that maybe at some point will will help somebody come up with new transversal gates were were better but design simple taught purple so OK so let's look at the
30:34
structure of this component that contains a 5 you and so we have these components and they consist of a bunch of subspace and this some sponsored subspaces their true closer to 2 other subspaces and some the further right because this a small local unitary that only kT cube a little bit and it's big loping alteration that things a lot and what that means is we can put destructive a manifold on on this component and we can say well locally we have the 5 cubic codon have code so very small rotations of the fight to code and then further off there's some some other types of things that wasn't drawn as a twodimensional manifold because you know the screen is only twodimensional but really it's a very highdimensional thing even for the 5 cubic OK and so let's think about what happens then when we do an actual transversal gate on this like CuO well I'm like I said we start out with the 5 key because we do will infinitesimal but transversal gates we moved code and we go through a series of such codes and eventually get back to the original code so that means that transversal gate corresponds to some sort of loops on this manifold and we can actually think this manifold put some use some additional structure think of a vector bundle so what that means that's mathematical terminology is on group theory I know but might still be frightening so that the the vector bundle says well what would attack vector space to every point on this manifold OK and obvious vector space to pack in this case is the quote they're corrected code as a 2 dimensional subspace or more generally K dimensional subspace right so at every point as manifold we attached to it that the the code correspond to that point and then at nearby points we can line up this vector spaces by seeing what the local unitary customers right so suppose you pick basis vectors at 1 point and we say locus last Friday apply a small local unitary transformations that will take us over here 2 different code at same time rotate these basis vectors slightly and so what that does the lines up the vector space over here the vector space over here at and so if we go to a path we can we can see how the vectors in in in 1 location get mapped to took 2 vectors in other locations that's a process called parallel transport and that the kind of the the mathematical structure that does that is called the connection will get on so that for those who you know what I'm talking about the the in in terms of different for geometry the natural thing to ask which of connection is what is the curvature this connection regret but it turns out that very small loop in this space what that means that you've only deform the cones codes very slightly and we know from well for instance from this eastern no result but I don't think you need it's is kind of full power here that the the the set of friends Russell gates for any code that has distance at least 2 is going to be discrete to a small loop that tend to do any of any kind of nontrivial operation on on the on the the the vector space tax to the to the based pointer we started with so if you start phrases and 5 the the code you very small loop what does the rotation but eventually he get back we started and the vectors have to line up to what they were before and so what is small loop is trivial that means that the connection has no curvature this is this manifold is actually flap so again this is kind of a technical thing about it I mean if you think back us most people would say Torres less obviously curved right you know it has person but that's a mathematically at Torres does have a flat connection because you can go around these little loops without changing the the vectors of the tangent vectors they they get back to where it started and and that that can be realized by the fact that in the in the kind of the the usual of asteroids geometry of poor code where you can just write flat on a plane and identify foresight anyways is a higher dimensional manifold has kind same property but what that means is that when we actually do a nontrivial friends Russell Gate on a code it means that it has to be a topological effect means that that there have to be these holes in the manifold and then we when we go around the loop and do a transversal gates of for instance we could do for instance that the logical xk is the 5 CuO that can be done is a tensor product of axes will generate infinitesimally go around this path and that half has to be long constructible Pa because were contractible then by this argument it would have to be trivial on the included units OK so so this is kind of very deep connection between topological gates and from Bristol gets really transversal gates Orica's topological the topological bypassed on this big manifold of equivalence locally unit local unitary covered subspaces the curve in effect and of course this this manifold is going to have a lot more structured I mean there's there's going to be some loops that we can do better nontrivial but still don't do well log cooperation differences for the 5 GB code there the stabilizer generators are things without transversal day to go out of the coma come back to the code and they don't do anything to be encoded state and for those I think our that nontrivial loops but the logical operation is is trivial but it but then for the the fi code we know there's a kind of really interesting but nontrivial loops that you do something to be encoded space there's logical so these acts and Z and and Y log Y were around both of these holes and then there is that the logical a colorful you did it so this is an underwater 3 care group gave that takes x 2 y z and z goes back tax because it takes of the access the block sphere and and Primus' subsequently so so so actually so if you I know a lot about that the 5 cubic codons Traverso gates that tells us a lot about the topology of this particular component the local unitary equivalence subspace of OK so so now think
37:53
about when it's a or get to know think about about
37:58
the other kinds of constructions magic state constructions on another kind of instructions that use so constructions use and so well you can think about them the same way right again those might say constructions you throw it and so then you have to use a miniature gates and maybe some measurements let's just imagined doing the measurements coherently so we have to worry about that and so the picture so that we say is just the 1st step is we take this manifold and the embedded in some larger metaphor really a highdimensional manifold by adjoining this magic state and so these data manifold while it has you know a similar but more complicated structure and so then I would say constructed it consists of taking a path that goes outside the real manifold into this big a manifold and but again I have to do the same thing go through a nontrivial loops and we get back to we started having done but topological data in this more general sense on the encoded state right and I think that's not even fair I guess but we don't necessarily have to get back to we started because we don't really care about keeping the magic States but in order to make it to make it simple and pose loop you can say well what we're gonna do is we're going to to to move around the magazine gets destroyed but then create a new magic state to replace the old 1 and that we really do and the backward search OK so so this can give you at least some some kind of idea for had a cradle unified picture of faulttolerant gates because all about our gates can be can be seen in its most general sense as topological gets there is you know what's a tublike Colgate's art work this way you have some manifold of axis it is not is not the obvious manifold you're you're you're in order to get to put this picture you have to look at that the manifold of manifolds that are equivalent to the original 1 but you do some moves that that a nontrivial they correspond to the modulus manifold reversal Gateses' I showed you hate they could be viewed this way it's nice day constructions review this way and then there's a few oddball constructions like for instance the part of the MIT or at polynomial codes and the talk we gate is done why you do a transversal profligate that changes the degree of the code selected different different code but it's a related so the family code but it's it actually different code when it started it and then you have to do some degree reduction procedure to go back to the original code so there you can see it's it's again behind this big picture you leave the code space and then you move around in you go back to the code space is just there is an explicit way point in the middle that's that's interesting that they discussed OK and I I think this Thursday that every fall construction that we know that I am pretty sure you you could say that every fullcolor construction that can exist have to fit into the same general picture that you you take the code you go through a series of other code some of which may be interesting some of which may not be interesting and eventually get back to the original code having done some nontrivial operation includes this OK so that's that's a kind of fertile area to think of new kinds of data structures by thinking of explicit way points of I'll will go to this code in Unicode and write really get back and then eventually back to the original so on number you move to the next topic the ideas of a lot of my time ready at this 1 it should be relatively quick so that the next topic is well suppose we have a new family of codes when is it can frightful what we need to come up with a family of codes that has a well so on is the 1st thing is we need this family of codes to to correct lots of errors because the goal you arbitrary long computations and during his for long obligations you can be well lots and lots of errors more and more as the fall the length time taking its very so in particular on the codes are going to have to have an arbitrarily low as you go to large examples the family for a low logical failure because it particularly for the if for simulating the gates 1 by 1 venue each is that have a lot of failure rate and that's to be multiplied by the total number of gates in a circuit were trying to to simulate fault or so we need to get that life where it down as far as possible and that together fairly low we can do before long conditions we need before leaving and these clothes have to be good in the sense that they correct a constant fraction of errors because that's the kind of definition of the threshold here and really they should have an efficient decoding over them because as you get a very big codes it's unacceptable if the the classical processing you have to do is going the exponential the code size the the decoding algorithm in the determining of the of whatever happens and say something that should be polynomial and and hopefully better if you like linear OK now that I have a threshold is not actually necessary that the distance a constant fraction of of an and in fact is not true for Europe concatenated codes for pork really this is the thing that the typical errors they occur randomly and to the code for correct that well that's was needed and that that that can be true even though this distance is decreasing with them and now if you look at the poor code and the concatenated codes you might say well in order to to have this property we have to get lower and lower logical a rate k encoded you that's divided by N. number physical qubits if you look at these 2 examples you might say that that is Europe but that's not true I mean we least we don't know it it has to be true it is just a matter of coming up with codes that have these other properties and yet had a good break probably probably this is possible whether it's a no viable with with a good family because I don't know but but I think you could you could probably come up with something to to show this is possible as well OK so but
44:59
so what else we need for a freckled well we need to have a full set of fault tolerant gates because time knocking go to the details but basically for CSS codes that pre straightforward it's united transversal measurements of transversal everything else you can do with Magic states with the stabilizer codes you can also do pre well with 9 states using no error correction and and so as to relitigate construction the measurement that's not gonna be that the stumbling block but the the cactus that did is nicer constructed you need and so as a many need to be bid and so is encoded in the same code sesame Connect again as in an errorcorrection had new errorcorrection will this reknown known methods of portal errorcorrection there's for error correction so that users cat states and the size the cat state has to be as big as the parity checks on the code regret so if the code has very big parity checks for a big stabilizer generators for error correction is out because as big cat states that ousted little that you can give them with a family of LDPC codes where the stabilizer granted all have a weight bench work reckoners is back in the running death and that's something very very interesting to think about as all mention briefly can but rather codes out we take each worker can study at the state errorcorrecting Renewal'' correction and those work fine of 4 CSS codes and stabilizer codes respectively on but again the constraint is that we need big and so as the need to be encoded using the same code so what
46:37
that means is that I get to do of photon protocol it all comes down to preparing states of this code OK even just start the competition into creating 0 states that you are correct and the gates need other states encoded in big blocks of this code a or before large as in the strengthening sustained operation is usually done in 2 steps there encoding step and then there's some sort of distillation step we test the states that that we made and of course you probably know about my state distillation but you can be distillation for a for other kinds of states is just easier and again this is something that probably can be done for pretty much any stabilizer codes so that the main the main barrier therefore is encoding state in such a way that the logical error rate and this is where rate it is not too far if it's you know moderately high then we can use just listen to get down but if it's too wide and distillation procedure work then a really big code block and we just use a really big encoded circuit while the chance of having errors along the way is incredibly high and the decoding encoding circuit itself might not be fault tolerance so that could produce a logical error as of just a big big block the the chance of successfully doing that without having any kind of logical error is very small and the back is the barrier would prevent us from just say well here's any code but user for fault or OK so this is where we get to the real constraint
48:11
that says what a family of codes for a time a threshold what do we need as what we need is some call progressive encoder so that for the 2 families of codes we know for concatenated codes and we do this encoding and we solve this problem in a big block with many levels of encoding well we start with 1 level we do not conservator at 1 level and then we do error correction to to test it will be due another level of encoding to make a 2nd level than we do our correction to test and then keep on going like this OK so we're stopping at various points in doing error correction before continuing on to make a bigger could block topological could you can do something very similar we start with a small code we do our correction on that's that's not their life where it's not too wide and then we grow it and we can stop into errorcorrection debt and keep on growing and that the we get a big block right so again it has its progressive encoding will we we make a small clothes you're Krattenmaker slightly bigger code we do our part and we keep on going like that and if your family of codes has the property and it also has the other properties so it's CSS
49:28
stabilizer code crest account effective like the errors of public life where goes to 0 as the family gets bigger as in decoding of and has this progressive encoding back and I think you should be able to use that family of codes to get a threshold it will be good threshold of Africa all depends of course on on you know a lot of other things but but at least it will be there and that's something to to to look for and to study OK I OK so I only a few minutes so the final topic what is that the minimal overhead of his face a few words so that the basic goal that I wanted to have a look here is seed is there the the a maximum were so a minimum a minimum overhead that we need to have a fault tolerance OK so for instance if we can come up with a family of codes that's that's great that satisfies all properties of previous page has a very good ratio OK over and so very good encoded rate is it possible that we could do so federal approaching that rate and the answer as far as I can tell is is quite possibly if it's the right family of codes so what is a family of codes the well let's think about it that the pieces we need to go into this but while Shorenstein sites 15 and no error correction were very good in in in the general case but they're never gonna let us approach this rate and the reason is of any big and so as encoded in that the same code and so the rate is always connect divide by 2 were by 3 FIL needs you're 2 blocks of the codon and stay in 1 is 1 at time OK and so if we use Steno on yellow errorcorrection were never gonna get up to the rate of the code in terms of so that means that I really wanna get very very good rate we have teeth for our crops and as I said you can be sure unless you have an LDPC code for Baker so that we need a new family of LDPC codes that are going on and but it
51:47
turns out that that's really all that you need there's some that you can do to to get rid of the auto to kind of reduced to 2 sublinear water of all the other overhead that's involved and yes so
52:03
it's the that and so
52:05
so it turns out that if you had an LDPC code that has basically all the properties that I said before class is lowdensity project and another technical phase is you need an error correction procedure that's robust against a single errors missing from that but then you can prove a threshold that has a constant overhead in fact the overhead would be the rate late of the rate of the code or 1 of the rare to us so when the other way that so that's kind of a remarkable thing I mean that's saying that I not only to new in principle due to a fault tolerance with constant overhead as opposed to the examples we have now with the overhead grows with size but that overhead could in principle be verified if there if the rate of the quotas for it of and of course that the captain all this is we don't even know that there exists a a good quantum LTB seekers' family but 1 of the meeting but this is 1 reason why I think it's extremely interesting if we can find some you know that there exists LDPC codes right surface codes or LDPC but they they're not asymptotically could figure they don't have an asymptotic good right that so often it's on I had these 3 topics
53:39
that the the first one of course topological dates and from Gates' really thing everything is topological all full told gates on in principle you can in order to to have a family of codes no threshold all you really need is is progressive encoding you you can stop at various stages and and solely build up a beer code block and if we had an LDPC code good family of PC codes then we could get a thresholds Europe with really good overhead with very little overhead I I guess I did that I was going fast I do say the other copy out about this this is assuming that possible complications or not count against your so you have measurements in a fast possible competitions that were but thanks actions but when you said that you need to get synthetically good quantum codes the length of the code goes larger and larger which need that which would have I fission decoding on these you mean classical decode along with this it's OK to have a a syndrome measurement and after that simple because classical because the small way you meant something else I don't know what else it could be an I guess I guess if if they were good if they were bad if you know good class globin with a good quantum algorithm that that would be an interesting question but but this is the gate of health go that has simple classical the good old is to have measurements quantum porters measure syndrome enough to see with the classical is this is enough yet I fight and and even if you're your computer does it have measurement you can always simulate the the the classical decoding algorithm using Q that's and repetition code OK so you don't know it is a classical decoding algorithm then this classical call tolerance is straightforward so you might have implement that incubates if you don't have to have quick measurement but you know in principle I can be done to still have a threshold now it is that if the decoding remembers quantum there and it becomes more complicated because you need to make that quantum fault tolerant and then utterance OK and the leadership in 1 of the previous slides you've said the code should be robust against errors in syndrome measurement right the apps using rover Altes use and rumors on was that the last for this last topic but the LDPC codes because you for error correction and there is a possibility that any individual bit of the system can go wrong and the problem is we don't repeat the same the measurement will deduce Aronson from and I could be totally wrong error and those could be individuals and political wrong or multiple thing from this that that don't match the actual central but now probably what you can do is you can you can max seen from 2 different times like give for surface codes and figure out from there with decreasing the mayor's words in the errors art but it would be hard to analyze that not having actual examples of codes to to look at yeah I really need several hours yeah I mean a a a constant fraction missing from that can go wrong yes and the gym picture you have the sterilizer and logical operator being as though but the on old so is actual difference between because both the saliva and logical 1 seems like a nontrivial look bright at right so yet so so the thing is that we do these nontrivial loops as to encoded state depends on the exact so basically there's you know quite a lot of different what kinds of loops nontrivial loops in this code and some of them will get some of them will do block operations some them a lot and wanted to block operations will obviously be different logical operation so I don't I mean you know somehow you knew what the topology of this this manifold war I don't know of a good way to instantly say these the interesting this season on interesting you can you can put some group 3 on it and make some slightly stronger statement than that but that's that's something for the study so it is possible to study some I could properties like a distance of the code with some other properties based on this that I could of between yes to actually that's so that's but that's more in a matter of what's already been done actually on the for classifying the different the different connected components so that the theory of invariants i is is 1 of the main things it's used to class finds difference of spaces so you look at at properties of 4 invariant under local unitary it's so for instance you can come up with some polynomial function of the of the subspace that's invariant and those those polynomials are connected to the properties of the Coase like the distance and if you look at the way the numerators for instance that's so that's a good example of that so in your talk is suggested that faulttolerance schemes path that beasties should have worse thresholds among the EU's transversal base case because they allow virus to propagate but of course we the surface those have a very high threshold when use could every action of as we try to use them in a concatenated fashion threshold drops quite a bit we try to implement them would react so I mean it's it uses we reconcile and what is other considerations basically well its effect so I so 1st of all I this there's lots of copies of CO yet take into account right and you have take into account the the the actual error inherent our faults of these codes that take into account all the other data you during that didn't come bureaucratic procedure that's that that's a big thick and actually that's that's really seems to be what makes this the surface cos better than concatenated codes for threshold is that the error correction procedure is much simpler and error correction takes up a lot of the resources and the fault or protocol and creates a lot of the your budget so that I could have a bad error correction procedure compared to the Surface codes and that kind of overwhelms the extra hours a creep in during dates for the surface just a quick comment to close off with this topological is in general you can trace space and time didn't have to take a long time you can you the fact that instantly yeah and it was this
00:00
Resultante
Bit
Punkt
Selbst organisierendes System
HausdorffDimension
Physikalismus
Geräusch
RaumZeit
Fehlertoleranz
Loop
Informationsmodellierung
Flächentheorie
Datentyp
Inverser Limes
Schwellwertverfahren
Maßerweiterung
Default
Einflussgröße
Umwandlungsenthalpie
Konstruktor <Informatik>
Gruppe <Mathematik>
Protokoll <Datenverarbeitungssystem>
Quantencomputer
Bitrate
Verknüpfungsglied
Flächeninhalt
Menge
Offene Menge
Codierung
Overhead <Kommunikationstechnik>
Fehlermeldung
Aggregatzustand
03:02
Resultante
Bit
Diagonale <Geometrie>
Prozess <Physik>
Extrempunkt
Familie <Mathematik>
Gruppenkeim
Computerunterstütztes Verfahren
Extrempunkt
RaumZeit
Übergang
Eins
Fehlertoleranz
Netzwerktopologie
Font
Regulärer Graph
Typentheorie
Randomisierung
Konstruktor <Informatik>
Nichtlinearer Operator
Schwellwertverfahren
Datentyp
Kategorie <Mathematik>
Kardinalzahl
Stellenring
Reihe
Ähnlichkeitsgeometrie
Nummerung
pBlock
Codierung
Unterraum
Arithmetisches Mittel
Transversalschwingung
Reihe
Randwert
Generator <Informatik>
Kritischer Punkt
Verknüpfungsglied
Menge
Verbandstheorie
Gerade Zahl
Rechter Winkel
Verknüpfungsglied
Perkolation
Ordnung <Mathematik>
Overhead <Kommunikationstechnik>
Computerunterstützte Übersetzung
Standardabweichung
Fehlermeldung
Aggregatzustand
Instantiierung
Stabilitätstheorie <Logik>
Subtraktion
Decodierung
Gewicht <Mathematik>
Klasse <Mathematik>
Verzerrungstensor
Code
Multiplikation
Informationsmodellierung
Gewicht <Mathematik>
Spieltheorie
Flächentheorie
Datentyp
Inverser Limes
Abstand
Grundraum
Widerspruchsfreiheit
Trennungsaxiom
Qubit
Fehlermeldung
Fehlererkennungscode
Protokoll <Datenverarbeitungssystem>
Datenmodell
Einfache Genauigkeit
Vektorraum
Inverser Limes
Flächeninhalt
Blockcode
Digitaltechnik
Mereologie
Gamecontroller
Codierung
Overhead <Kommunikationstechnik>
Modelltheorie
14:17
Stellenring
Bit
Diagonale <Geometrie>
Computer
Eins
Existenzsatz
Auswahlaxiom
Phasenumwandlung
Schwellwertverfahren
Datentyp
Kategorie <Mathematik>
Kardinalzahl
Reihe
Nummerung
pBlock
Biprodukt
Teilbarkeit
Algorithmische Programmiersprache
Codierung
Arithmetisches Mittel
Transversalschwingung
Verknüpfungsglied
Rechter Winkel
Verknüpfungsglied
pBlock
Diagonale <Geometrie>
Fehlermeldung
Instantiierung
Subtraktion
Gewicht <Mathematik>
Code
Verzerrungstensor
Loop
Informationsmodellierung
Datensatz
Gewicht <Mathematik>
Arithmetische Folge
Datentyp
Inverser Limes
Abstand
Maßerweiterung
Gammafunktion
Fehlererkennungscode
Fehlermeldung
Finitismus
Schlussregel
Mapping <Computergraphik>
Digitaltechnik
Basisvektor
Codierung
Gamecontroller
Partikelsystem
Modelltheorie
20:44
Resultante
Stellenring
Bit
Umsetzung <Informatik>
Punkt
Inferenz <Künstliche Intelligenz>
Drehung
RaumZeit
Richtung
Eins
Netzwerktopologie
Komponente <Software>
Einheit <Mathematik>
Reverse Engineering
Unitäre Gruppe
Vorwärtsfehlerkorrektur
Figurierte Zahl
Phasenumwandlung
Zentrische Streckung
Nichtlinearer Operator
Äquivalenzklasse
Permutation
Multifunktion
Cracker <Computerkriminalität>
Exponent
Kategorie <Mathematik>
Reihe
Stellenring
Ähnlichkeitsgeometrie
Nummerung
pBlock
Biprodukt
Codierung
Tensorprodukt
Unterraum
Transversalschwingung
Reihe
Verknüpfungsglied
Menge
Rechter Winkel
Konditionszahl
Phasenumwandlung
Computerunterstützte Übersetzung
Aggregatzustand
Fehlermeldung
Instantiierung
Nebenbedingung
Subtraktion
Decodierung
HausdorffDimension
Mathematisierung
Klasse <Mathematik>
Gruppenoperation
Diagramm
Ordinalzahl
EMail
Äquivalenzklasse
Term
Physikalische Theorie
Code
Informationsmodellierung
Unitäre Gruppe
Kugel
Tensor
Datentyp
Vererbungshierarchie
Quantisierung <Physik>
Zusammenhängender Graph
Fünf
Operations Research
Datenstruktur
Qubit
Fehlermeldung
Knoten <Mathematik>
Matching <Graphentheorie>
Mathematik
Einfach zusammenhängender Raum
Orthogonale Funktionen
OfficePaket
Unendlichkeit
Verschränkter Zustand
Basisvektor
Codierung
FibonacciFolge
Kantenfärbung
30:33
Resultante
Bit
Punkt
Prozess <Physik>
Mengentheoretische Topologie
Gruppenkeim
Tangentialraum
Drehung
Extrempunkt
Login
RaumZeit
Netzwerktopologie
Einheit <Mathematik>
Gefangenendilemma
Unitäre Gruppe
Kurvenanpassung
Gerade
Parametersystem
Addition
Nichtlinearer Operator
Multifunktion
Krümmung
Kategorie <Mathematik>
Stellenring
Reihe
pBlock
Codierung
Tensorprodukt
Unterraum
Transversalschwingung
Generator <Informatik>
Verknüpfungsglied
Menge
Würfel
Rechter Winkel
Gruppentheorie
Vektorraumbündel
Identifizierbarkeit
URL
Schlüsselverwaltung
Instantiierung
Ebene
Stabilitätstheorie <Logik>
Subtraktion
Decodierung
Mathematische Logik
Unitärer Operator
Basis <Mathematik>
Äquivalenzklasse
Topologische Mannigfaltigkeit
Mathematische Logik
Räumliche Anordnung
Term
Kubischer Graph
Code
Überlagerung <Mathematik>
Hypermedia
Loop
Unitäre Gruppe
Kugel
Datentyp
COM
Zusammenhängender Graph
Abstand
Operations Research
Zeiger <Informatik>
Datenstruktur
Struktur <Mathematik>
Parallele Schnittstelle
Topologische Mannigfaltigkeit
Drucksondierung
Leistung <Physik>
Touchscreen
Einfach zusammenhängender Raum
Soundverarbeitung
Mathematik
Vektorraum
QuickSort
Loop
Codierung
37:56
Prozess <Physik>
Punkt
Polynom
Dichte <Physik>
Gewichtete Summe
Familie <Mathematik>
Kartesische Koordinaten
Zählen
RaumZeit
Fehlertoleranz
Algorithmus
Reverse Engineering
Kontrollstruktur
Qubit
Einflussgröße
Konstruktor <Informatik>
Nichtlinearer Operator
Bruchrechnung
Dicke
Schwellwertverfahren
Exponent
Kategorie <Mathematik>
Seidel
Reihe
Nummerung
pBlock
Bitrate
Codierung
Algorithmische Programmiersprache
Transversalschwingung
Konstante
Generator <Informatik>
Polynom
Verknüpfungsglied
Menge
Einheit <Mathematik>
Rechter Winkel
Gerade Zahl
Konditionszahl
Gerade Zahl
Kategorie <Mathematik>
Messprozess
pBlock
Ordnung <Mathematik>
Computerunterstützte Übersetzung
Fehlermeldung
Aggregatzustand
Instantiierung
Größenordnung
Nebenbedingung
Stabilitätstheorie <Logik>
Decodierung
Mathematische Logik
Gewicht <Mathematik>
Total <Mathematik>
Physikalismus
Code
Open Source
Loop
Gewicht <Mathematik>
Schwellwertverfahren
Generator <Informatik>
Abstand
Datenstruktur
Topologische Mannigfaltigkeit
Gammafunktion
Qubit
Algorithmus
Videospiel
Fehlermeldung
Fehlererkennungscode
Ordnungsreduktion
Minimalgrad
Flächeninhalt
Digitaltechnik
Mereologie
Demoszene <Programmierung>
Codierung
EinsteinPodolskyRosenParadox
46:37
Nebenbedingung
Stabilitätstheorie <Logik>
Decodierung
Punkt
Familie <Mathematik>
Aggregatzustand
Mathematische Logik
Code
Übergang
Fehlertoleranz
Arithmetische Folge
Schwellwertverfahren
Feuchteleitung
Softwaretest
Videospiel
Nichtlinearer Operator
Fehlermeldung
Schwellwertverfahren
Fehlererkennungscode
Protokoll <Datenverarbeitungssystem>
Kategorie <Mathematik>
Logische Schaltung
Systemaufruf
pBlock
Bitrate
Codierung
QuickSort
Algorithmische Programmiersprache
Verknüpfungsglied
Rechter Winkel
Mereologie
Digitaltechnik
Codierung
Aggregatzustand
Fehlermeldung
49:25
Stabilitätstheorie <Logik>
Web Site
Mathematische Logik
Decodierung
Extrempunkt
Wasserdampftafel
Familie <Mathematik>
Term
Code
Homepage
Fehlertoleranz
Schwellwertverfahren
Soundverarbeitung
Videospiel
Schwellwertverfahren
Fehlererkennungscode
Kategorie <Mathematik>
Güte der Anpassung
pBlock
Bitrate
Teilbarkeit
Existenzsatz
Rechter Winkel
Verknüpfungsglied
Codierung
LowDensityParityCheckCode
Overhead <Kommunikationstechnik>
pBlock
Overhead <Kommunikationstechnik>
Bitrate
Fehlermeldung
Instantiierung
52:00
Mathematische Logik
Dichte <Physik>
Klasse <Mathematik>
Familie <Mathematik>
Code
Fehlertoleranz
Flächentheorie
Konstante
Quantisierung <Physik>
Schwellwertverfahren
Bruchrechnung
Phasenumwandlung
Algorithmus
Fehlererkennungscode
Schwellwertverfahren
Fehlermeldung
Kategorie <Mathematik>
Güte der Anpassung
Bitrate
Algorithmische Programmiersprache
Konstante
Verbandstheorie
Rechter Winkel
Codierung
Gerade Zahl
LowDensityParityCheckCode
Projektive Ebene
Overhead <Kommunikationstechnik>
Overhead <Kommunikationstechnik>
Bitrate
Fehlermeldung
53:36
Bit
Familie <Mathematik>
Gruppenkeim
Computer
Kardinalzahl
RaumZeit
Netzwerktopologie
Fehlertoleranz
Algorithmus
Unitäre Gruppe
Figurierte Zahl
Einflussgröße
App <Programm>
Bruchrechnung
Nichtlinearer Operator
Dicke
Schwellwertverfahren
Befehl <Informatik>
Kategorie <Mathematik>
Güte der Anpassung
Klassische Physik
Stellenring
Systemaufruf
Nummerung
pBlock
Algorithmische Programmiersprache
Unterraum
Rechenschieber
Transversalschwingung
Polynom
Verknüpfungsglied
Rechter Winkel
LowDensityParityCheckCode
Overhead <Kommunikationstechnik>
Ordnung <Mathematik>
Ablaufverfolgung
Instantiierung
Fehlermeldung
Aggregatzustand
Subtraktion
Computervirus
Invarianz
Klasse <Mathematik>
Gruppenoperation
Mathematische Logik
Code
Physikalische Theorie
Loop
Multiplikation
Flächentheorie
Quantisierung <Physik>
Abstand
MinkowskiMetrik
Beobachtungsstudie
Soundverarbeitung
Fehlererkennungscode
Matching <Graphentheorie>
Protokoll <Datenverarbeitungssystem>
Physikalisches System
Codierung
Wort <Informatik>
Metadaten
Formale Metadaten
Titel  General Principles of FaultTolerance 
Serientitel  Second International Conference on Quantum Error Correction (QEC11) 
Autor 
Gottesman, Daniel

Lizenz 
CCNamensnennung  keine kommerzielle Nutzung  keine Bearbeitung 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nichtkommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. 
DOI  10.5446/35308 
Herausgeber  University of Southern California (USC) 
Erscheinungsjahr  2011 
Sprache  Englisch 
Inhaltliche Metadaten
Fachgebiet  Informatik, Mathematik, Physik 
Abstract  I will discuss the available techniques used the construction of faulttolerant protocols and the general principles behind them. I will also analyze the properties needed for a family of codes to be useable to have a threshold for faulttolerance. 