Stabilizer quantum codes via the CWS framework
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Alternative Title |
| |
| Title of Series | ||
| Number of Parts | 48 | |
| Author | ||
| License | CC Attribution - NonCommercial - NoDerivatives 3.0 Germany: You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/35298 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
12
23
24
29
31
37
38
00:00
Element (mathematics)Commutative propertyCodeGraph (mathematics)Representation (politics)Machine codeQuantumSoftware frameworkQuicksortComplex (psychology)Multiplication signBitFehlererkennungscodeMachine codeLattice (order)Software frameworkGeometryGraph theoryResultantError messagePotenz <Mathematik>AdditionProcess (computing)Category of beingCASE <Informatik>Computer animation
01:29
Machine codeElectric generatorSpacetimeAbelsche GruppeLocal GroupOperator (mathematics)Basis <Mathematik>Linear subspaceQuantumCommutative propertyElement (mathematics)Error messageState of matterQuicksortGroup actionOperator (mathematics)Slide ruleElectric generatorComputer animation
02:10
Electric generator19 (number)SpacetimeBasis <Mathematik>Machine codeDatabase normalizationOperator (mathematics)Error messageMeasurementTotal S.A.3 (number)Multiplication signMachine codeMachine codeNetwork topologyBit rateQubitResultantExecution unitSurfaceComputer animation
02:42
State of matterGraph (mathematics)Electric generatorAbelsche GruppeAdjacency matrixWeightMaxima and minimaElement (mathematics)Machine codeDistanceSuperposition principleEquals signSign (mathematics)Ring (mathematics)State of matterElectric generatorMatrix (mathematics)Form (programming)Graph (mathematics)Total S.A.Power (physics)Phase transitionDistanceSuperposition principleDiagonalWeightGamma functionElement (mathematics)Adjacency matrixCASE <Informatik>Graph theoryQuantum entanglementOperator (mathematics)Standard deviationGrass (card game)ForestComputer animation
03:53
Basis <Mathematik>Vector graphicsQuantumOperator (mathematics)Inheritance (object-oriented programming)Smith chartPermutationGraph (mathematics)Standard deviationCodeVector spaceError messageBinary codeMachine codeWordMachine codeAlgorithmTexture mappingPower (physics)Condition numberCommutative propertyClassical physicsDistanceWeightVertical directionMaxima and minimaCASE <Informatik>Machine codeMachine codeVector spaceBinary codeMaxima and minimaDistanceLattice (group)CommutatorElement (mathematics)Power (physics)FehlererkennungWordBitSoftware frameworkDot productGraph (mathematics)Error messageQuicksortMappingVertex (graph theory)Level (video gaming)Basis <Mathematik>Term (mathematics)QuantumState of matterBound stateDegree (graph theory)Operator (mathematics)FehlererkennungscodeRing (mathematics)Classical physicsDevolution (biology)Electric generatorAlgorithmBounded variationQubitCondition numberProduct (business)Graph theorySpacetimeWeightCanonical ensembleSystem callKeyboard shortcutSocial classFlagGraph (mathematics)Correspondence (mathematics)Open setBit rateForm (programming)DivisorMusical ensembleNeuroinformatikComputer animation
10:28
CodeSoftware frameworkMachine codeGraph (mathematics)Electric generatorMachine codeWeightMachine codeQubitGraph (mathematics)CommutatorBinary codeCorrespondence (mathematics)Machine codeDistanceProduct (business)Electric generatorOperator (mathematics)QuicksortVertex (graph theory)WordLie groupVortexGraph theoryGenderComputer animation
11:44
Software frameworkCodeMachine codeGraph (mathematics)Electric generatorMachine codeSymmetry (physics)Zyklische MatrixBinary codeMachine codeGraph (mathematics)WordElectric generatorSymmetry (physics)Ring (mathematics)DatabaseComputer animation
12:21
Machine codeOperator (mathematics)Commutative propertyMatrix (mathematics)Binary codeGraph (mathematics)Representation (politics)OrthogonalityOrthogonalityAdjacency matrixMappingCommutatorOperator (mathematics)BitQuicksortGraph (mathematics)Correspondence (mathematics)Machine codeError messageInsertion lossVector spaceSummierbarkeitMatrix (mathematics)Parity (mathematics)Electric generatorData structureObservational studyMachine codeHelmholtz decompositionCondition numberPower (physics)Product (business)QuantumSymplectic vector spaceGraph (mathematics)Binary codeExpressionRow (database)ResultantAdditionComputer animation
14:02
Machine codeBinary codeGraph (mathematics)Bit rateQuicksortMachine codeBound stateFinitismusQuantumMachine codeDistanceGraph (mathematics)Bit rateTheory of relativityState of matterLimit (category theory)Strategy gameClassical physicsPoint (geometry)Goodness of fitParameter (computer programming)Data structureRevision controlForcing (mathematics)Category of beingDivisorBuildingField (computer science)ResultantComputer animation
15:44
Database normalizationLattice (group)Graph (mathematics)Machine codeMachine codeNumerical analysisCodeSquare numberMachine codeMachine codeCircleGraph (mathematics)Shift operatorFinitismusVertex (graph theory)Numeral (linguistics)InfinityFamilyQubitWeightQuicksortClassical physicsDistanceLattice (group)Maxima and minimaCombinational logicGreatest elementCubeComputer animation
17:04
Shift operatorMachine codeZyklische MatrixMatrix (mathematics)PolynomialCodeDivisorSymmetric matrixQuantumMaxima and minimaBinary codeMachine codeSymmetry (physics)Revision controlBinary codePolynomialStandard deviationElectric generatorOffice suiteQuicksortMultiplicationShift operatorCASE <Informatik>Cycle (graph theory)Level (video gaming)Statement (computer science)Zyklische MatrixQuantumMathematical analysisNichtlineares GleichungssystemMobile appCondition numberOrthogonalityGraph coloringParity (mathematics)MathematicsBitInfinityOperator (mathematics)Social classSound effectZyklischer CodeGoodness of fitMachine codeCorrespondence (mathematics)Matrix (mathematics)AdditionIrreduzibles PolynomLattice (group)Computer animation
19:39
Standard deviationElectric generatorQuantumWeightClassical physicsExistenceProof theoryBCH codeCodeProof theoryExistenceCategory of beingParameter (computer programming)Process (computing)System callMachine codeMachine codeBound stateQuantumComputer animation
20:17
Electric generatorCodeWeightMachine codeQuicksortMereologyMachine codePlanningStudent's t-testFamilyMachine codeQubitComputer animation
20:44
Binary codeMachine codeMachine codeBit rateQuantumSocial classElectric generatorGreatest elementMultiplication signDistanceDifferent (Kate Ryan album)FinitismusWeightRight angleQuicksortHelmholtz decompositionSlide ruleObservational studyLecture/Conference
Transcript: English(auto-generated)
00:00
AWS framework. Thanks very much. All right. Thank you. So I learned about these codes, actually, last time on this meeting in 2007. And I sort of was suddenly fascinated by them. And I thought, this is something that I should be able to think about, because graphs I like.
00:21
And there are sort of geometrical properties to them that are sort of very natural. And I just like them. And so one thing we did was try to come up with a way to error correct these codes. And basically, we failed. So there are typically non-additive codes.
00:41
And I'll tell a little bit more about them. But if you try to error correct them, its exponential complexity, even in the classical case, you can come up with tricks that actually seem to be working and give you exponential speedup of this exponentially slow process, but still not fast enough.
01:01
So you still get exponential complexity to decode the general CWS codes. And so the work that I'm going to be talking about is trying to come up with actually stabilizer codes just by using this framework. And so I'll start with a little introduction talking
01:24
about these codes in general. And then sort of give you our results. So well, this is sort of the slide that shouldn't probably be here on this conference. And basically, I just want to remind you
01:40
about the stabilizer states. So in an n-qubit Pauli group, if you have n-commutant operators that don't include minus. A group that includes n-commutant operators generators don't include minus 1. The reason, they will always stabilize a unique stabilizer. And so you can come up with that
02:01
if you have some stabilizer code, but you can come up to such states in a different way. And so the quintessential example, of course, is the 5.13 stabilizer code. And I will be talking about such codes, about this particular code a couple of times today in a couple of examples.
02:21
And so what you should remember is that the, well, it's the smallest code ever. You know, there is a 5-qubit code just on 3, and it encodes 1-qubit. And so one of our results, we came up with a torus. We came up with a way to map this to surface codes.
02:42
This is sort of in the way to NTCU. So you know, what's the graph states? The graph states is yet another way to encode the stabilizer states, or you can think of this as just the standard form of a state. And so a graph state is generated by these operators.
03:04
So you have one x operator, and then a bunch of z's that are to the power of this C matrix matrix gamma that forms adjacency matrix of a graph. And so for example, it doesn't have the diagonal. And so important for this talk will
03:23
be the notion of a distance of a graph state. And this is the minimum weight of an element of the graph stabilizer. And so now for this case, one of the simplest graph states is this 3-qubit graph. This is just a ring. And so the generators are x, and then neighboring zz,
03:41
and then xzz, and then xzz. So there are a total of three generators. And so the graph state is actually a entangled state, which is an equal superposition of all of two to three states with some phases. Now, the code for stabilized codes invented in 2007.
04:01
The paper came out a couple of years later. So there were lots of references to the preprint instead of the actual papers. And so basically, these codes are specified by a graph, which gives you the graph state, and the classical code.
04:22
And the classical code can be additive or non-additive. Basically, you start with the graph state, and you generate the basis vectors of the code by this code word operators, which are just products of z's to raise to the power of each code word.
04:42
And so the beautiful thing about these codes is that any error can be mapped to a binary vector. And so the mapping is you just take an error, which is a product of x's and z's, and you multiply it by graph state stabilizers, which
05:00
have the corresponding x to it. And so this adds this additional z's. But at the end, you only have error that is only z operator. And so we have a classical code. The code words are specified in terms of these classical vectors. And we also have the classical errors. And so this is the map.
05:21
This basically gives you an idea of why these codes are simplified. And so one canonical example, this is the 5-6-2 code. This is non-additive code. So it is generated from the five ring with these generators.
05:42
And then you just add the six classical code words. And so you have this six-dimensional code space, which is more than one qubit, or I guess more than two qubits, but less than three qubits. So this is somewhere in between. And then now the problem is, again, to repeat myself,
06:02
is that there are no non-efficient algorithms to decode non-additive CWS codes. And so what we're doing, we're trying to find additive codes which are equivalent to the stabilizer codes. So this framework includes all of the stabilizer codes.
06:21
And so before I go on, I have to explain sort of the error correction or error detection condition for these codes. And so basically, the general error detection condition that if you have an error, and if you have vectors that form the code space, the span of these vectors
06:44
is the code, this product, this matrix element should be constant, which depends on the error itself times the Kronecker delta with respect to the code. And basically, this current code is either left untouched, or it is moved to the orthogonal space.
07:02
And this is what we're after. This is why we can correct the errors. And so for these CWS codes, there are actually two cases. One case is the non-degenerate case where the error takes you basically to 0. This matrix element is 0. The constant C is 0.
07:20
And then for these errors, you can just use the classical code. And you can just correct them classically. So the stabilizer that you would measure would be a classical binary stabilizer. And then you can sort of do it very easily. And then the second case is degenerate, where this error is not 0.
07:42
And of course, this corresponds to the classical map of the error being exactly 0. And so in the quantum case, if you are trying to construct a code, this error must actually commute with every w over. And that means that this binary scalar products of the binary code vectors
08:01
and the vector v that determines the error should be 0. So there are sort of simple bounds that you can come up with for CWS codes. Well, first of all, if you talk about the error that only involves z operators, this is just a classical error.
08:27
And so this error should be corrected by the classical code. So the graph stabilizer elements are not involved in using that error. And so basically, there is a simple bound that the quantum code that you get out
08:40
of a classical code, the distance is always less or equal to the classical code. Now, if you have a non-degenerate CWS code, then you can also show that its distance does not need the distance of the graph state that I defined earlier.
09:01
This is the minimum weight of the stabilizer. However, in the case of degenerate CWS codes, the situation becomes interesting. And so basically, you can show that if there is a bit that is involved in the classical code, and that means one of the code vectors is non-zero on that bit, then the distance of this code
09:24
cannot exceed the weight of the corresponding stabilizer. And so if you combine these two, then you sort of understand that if you have a graph with vertices of a given degree r,
09:41
then the distance of a code does not exceed r plus 1. And so these are all vertices of the same degree. And so if you are looking at codes that are generated by some nice lattices, like, for example, scotches, for a squared lattice, there are four neighbors, so the weight of this S
10:01
operator is 5. And so the distance of a CWS code that you can get out of squared lattice can never exceed 5. And so then typically, if you want to find codes of large distance, then you would be looking at sort of varied graphs with lots and lots of legs.
10:20
And then also, the distance cannot be bigger than the minimum weight of the stabilizer. And I'll just give you sort of a few examples to give you a feeling on these codes. So the 5-1-3 code is generated by this graph. And then the only code word is just 1-1-1-1.
10:42
So the classical code is the repetition code. And the graph stabilizer generator are these. And then, of course, this is repetition code, so the corresponding stabilizer generators are the commute with the binary code. And then now, there are two 6-1-3 codes.
11:03
One, you just add an empty qubit to the 5-1-3 code, and that corresponding graph has one disconnected vertex. And sort of that qubit basically is not used in the code. But the second 6-1-3 code is generated by this binary code and this graph.
11:21
And so this code is degenerate. So if you take the product of these two stabilizer generators, I believe they share all of their neighbors. And so the product has just weight. This is just weight two operator. And so the code is degenerate above this graph distance two,
11:42
but the actual distance of the code is three. And then this 16-7-1-3 code is generated by this code word and this graph. And so it is interesting that whereas the code actually has cyclic symmetry, if you shift the stabilizer generators
12:05
cyclically, it obeys this. Those would also be members of the stabilizer group. Nevertheless, there is no explicit graph that obeys this symmetry. And there is no binary code that
12:21
is also symmetric with respect to translations. And so now we are looking for additive codes. And so I'll just sort of review a little bit this GF4 maps of the stabilizer codes. And basic picture is that you have an error which is z to some power, x to some power.
12:41
And then you map it to a couple binary vectors and further to GF4 vector, which has this omega. And then the two operators commute if and only if the trace product of the corresponding vectors is zero.
13:01
And this is really symplectic products. And so one of the result is that if you are constructing an additive CWS code from a stabilizer code in some graph, there is a very simple expression for the corresponding generator matrix of this additive CWS
13:20
code. And remember, generator matrix, the rows of the generator matrix corresponds to the generators of the stabilizer of the code. So you have a parity check matrix. And then you have graph adjacency matrix. And it is very easy to check that the graph adjacency matrix is symmetric. So this is a simple graph.
13:41
Then it's very easy to check that corresponding trace product is actually zero just because of the structure of it. So the beauty of this decomposition is that you have a diction that is automatically orthogonal. And so one of the biggest problem in searching quantum codes is ensuring the orthogonality
14:01
condition. And so one thing we came up with, so suppose you have a graph. And it has big enough distance so that you can try to come up with code. And so how likely it is that you can get a good quantum code out of it? And so basically, it turns out that for all of the codes
14:23
that you can generate out of a given graph, you can prove a Gilbert-Varshanov bound. You can come up with a counting argument that the codes that can be generated from a given graph just satisfy this quantum Gilbert-Varshanov bound. And of course, so this means that you can come up with codes.
14:41
You can always come up with codes that are better than this, assuming that the upper limit on the distance is satisfied. And what's nice about it is, of course, in some sense, 8 is a simpler code than any stabilizer code. And so you can always come up with a graph state which has distance bigger than this.
15:03
And therefore, as a result, this is sort of the divide-and-conquer strategy for finding stabilizer codes. You first come up with a graph with a suitable distance. And then you try to come up with a code which has sort of built in on the graph structure.
15:21
And well, let me sort of, you know, so this is the classical Gilbert. So this is code rate. This is distance rate. And this is sort of classical Gilbert-Varshanov bound. This is quantum Gilbert-Varshanov bound. And this is quantum Gilbert-Varshanov bounds for CSS codes. But anyway, so what's the point of this is trying to find codes which have, you know,
15:40
good properties, namely finite relative distance and finite rate. And so now, of course, the easiest way to come up with codes is sort of start with a simple graph and that codes which you can generate on a lattice. And so on a finite square lattice, and this is five by five example,
16:01
you can actually very easily come up with a code. And so the maximum distance of the code that involves all of the qubit is four because of the edges. And so you can actually very easily come up with simple families that satisfy this. So this shows the cartoon of code 2544.
16:22
So these three red circles represent one of the classical. So each vertex is a qubit. And the four red circles represent the classical code. So this is the generator of the classical code. And then you shift it up, shift it left, shift it right.
16:42
And you can prove that the weight of any linear combinations is smaller than four just because you always have top, bottom, left, right edges. And so you can do it on any size lattice. It's an infinite family of codes. And then if you try to find numerical codes, then, of course, you can do better than that. But those codes still are relatively simple.
17:04
And this construct also generalizes to an infinite lattice. Now, we looked at cyclic codes. And, of course, cyclic codes you generate from this cyclic-circulant matrix. And the basic idea is that the generators of a stabilizer can be changed cyclically.
17:23
You take the n-th operator and move it to the first place. And then it still be a member of the stabilizer group. And so the standard map for cyclic codes, you go from circulant matrix to polynomial. And then these polynomials are invariant on the shifts.
17:48
For classical cyclic codes, this polynomial has to be under, oh, not really invariant. The shift corresponds to this multiplication by the x.
18:01
And so for an additive CWS code, you have this matrix. And if both P and R are circulant matrices, then you can write both of them as polynomials. And then the symmetry of this circulant matrix correspond to this condition on the polynomial. And so, again, this guarantees the orthogonality.
18:22
And, of course, 5-1-3 code, the polynomial P is 1 plus x. This is the parity check polynomial of the repetition code. And then the R of x is x plus x to the 4. This is symmetric with respect to this condition.
18:40
Now, you can think about more general cyclic codes. And in the paper on GF codes over GF4, there is a statement that generators have two generators. So this is a degenerate case. It turns out that there are one generator of cyclic codes which have to satisfy this condition.
19:00
And they are given just by the same equation, just by a little bit less restrictive condition on R. So you have to multiply it by P. And so this class turned out to be very broad. And so there are lots of good codes inside of it. And so what you can come up with is lower Gilbert-Varshanov bound again for cyclic quantum codes, because there are not so many
19:21
binary codes to look for, binary cyclic codes. It's easier to actually start with the binary code and then look for a polynomial. And so we can only prove it for irreducible polynomials and then two versions of it, depending on whether or not the polynomial is symmetric or not.
19:41
And so then you can do existence proofs. And so there are lots of codes that you can get out of the repetition code or generalized repetition to have this property. And these quantum codes satisfy exactly the same bound. And then there are lots of codes that correspond to binary BCH codes.
20:02
And so these codes actually, provably, either saturate or possibly, what we proved is that they have parameters that are better than any codes that are known so far, or same or better. And then sort of the last example
20:21
is a cyclic toric-like code. I promised you to show why 5.1.3 code is a torus. And so basically, if you enumerate qubits like this, one, two, three, four, five, and so this is qubit one, this is two, three, four, five, then you can map this qubit on a plane. And so this will take me to my conclusions.
20:41
And so there are families of such codes, and we have a poster talking about them. And so these are conclusions. Time for one question, two questions.
21:04
So in the last slide, you showed at the bottom this very wide class of codes with many different distances. I was wondering if you could comment on some of the trade-offs that come into play when you start looking at these larger distance codes.
21:20
So one trade-off for sure is if you are looking for codes that don't have small rate but have a finite rate, even binary codes get the penalty. So you cannot have finite rate but small rate of the stabilizer. These are codes that are easy to measure.
21:40
Toric code is example, of course, and stuff. So one trade-off is that by having bigger rate codes, it turns out you have to avoid stabilizer generators. There is no way out. We don't have the bound on that, but this is something that definitely plays out in the binary code. And then by this decomposition, you
22:02
can also show that this has to be true also for the quantum codes, although it's probably even slightly worse. So any finite rate code which k over n, d over n remains finite will definitely have stabilizers
22:21
of upper generators of weight bigger than 4. So this is one of the trade. These actually are quite big stabilizer rate. Let's thank our speaker one more time.