# Discrepancy in definition of quantum reed muller codes

I'm reading through this paper and on page 14 they define quantum reed muller (QRM) codes using the classical versions. I've seen punctured RM codes used to define quantum CSS codes with good properties; but the paper's definition is with unpunctured codes. I checked the the $$X$$ and $$Z$$ stabilizers define a QECC; but the definition of the $$X$$ and $$Z$$ logicals doesn't seem right. For one, they don't have the same dimensions. They're also orthogonal...which also doesn't make sense. Is the paper wrong or did I miss something? (the motivation is that these codes allow some transversal non-clifford gates)

I converted the accepted answer to GAP. Here's my version :

    Qrm:=function(m,r)local s,mat,layers,Sx,Sz,Lx,Lz,mx,mz,kx,kz,check,verify,code;
mat:=Iterated(List([1..m],x->[[1,1],[0,1]]),KroneckerProduct); # 2^m x 2^m matrix = m-th tensor power of [[1,1],[0,1]]
layers:=List([0..m],x->Filtered(mat,y->Sum(y)=2^(m-x)));       # layer[r]=subset of rows with weight = 2^(m-r)
s:=m-r-2;
Sx:=Concatenation(layers{[1..r+1]});  mx:=Length(Sx);            # X satbilisers
Sz:=Concatenation(layers{[1..s+1]});  mz:=Length(Sz);            # Z satbilisers
Lx:=layers[r+2];                      kx:=Length(Lx);            # X logicals
Lz:=layers[s+2];                      kz:=Length(Lz);            # Z logicals

Print("n =",2^m," |Sx|=",mx," |Sz|=",mz," |Lx|=",kx," |Lz|=",kz,"\n");

check:="kx=kz=k; k=Binomial(m,r+1); k=n-(mx+mz);";verify:=kx=kz and kx=Binomial(m,r+1) and 2^m-(mx+mz)=kx;Print(verify," ",check,"\n");
check:="Sx*Sz=0; ";verify:=\mod(Sx*TransposedMat(Sz),2)=NullMat(mx,mz);Print(verify," ",check,"\n");
check:="Lx*Sz=0; ";verify:=\mod(Lx*TransposedMat(Sz),2)=NullMat(kx,mz);Print(verify," ",check,"\n");
check:="Lz*Sx=0; ";verify:=\mod(Lz*TransposedMat(Sx),2)=NullMat(kz,mx);Print(verify," ",check,"\n");
check:="Lx*Lz=I; ";verify:=\mod(Lx*TransposedMat(Reversed(Lz)),2)=IdentityMat(kz);Print(verify," ",check,"\n");

code:=rec();
code.Sx:=Sx;code.Sz:=Sz;code.Lx:=Lx;code.Lz:=Lz;
return code;
end;


I checked with a few other parameters :

gap> code:=Qrm(6,1);;
n =64 |Sx|=7 |Sz|=42 |Lx|=15 |Lz|=15
true kx=kz=k; k=Binomial(m,r+1); k=n-(mx+mz);
true Sx*Sz=0;
true Lx*Sz=0;
true Lz*Sx=0;
true Lx*Lz=I;
gap> code:=Qrm(6,2);;
n =64 |Sx|=22 |Sz|=22 |Lx|=20 |Lz|=20
true kx=kz=k; k=Binomial(m,r+1); k=n-(mx+mz);
true Sx*Sz=0;
true Lx*Sz=0;
true Lz*Sx=0;
true Lx*Lz=I;
gap> code:=Qrm(6,0);;
n =64 |Sx|=1 |Sz|=57 |Lx|=6 |Lz|=6
true kx=kz=k; k=Binomial(m,r+1); k=n-(mx+mz);
true Sx*Sz=0;
true Lx*Sz=0;
true Lz*Sx=0;
true Lx*Lz=I;


I don't find the paper that you cite the most accessible, although it's filled with good stuff!

As far as I can see, it works out, perhaps after a little muddling of whether you want the generator/parity check matrix of a given code (it seemed to be the opposite of what I was expecting). This possibly made my Mathematica code below more complex than necessary (attempting to extract logical operators from parity check matrices rather than generators!)

(*construct generator of classical RM code*)
RM[r_, m_] :=
If[r == 0, {Table[1, {2^m}]},
If[r == m, IdentityMatrix[2^m],
ArrayFlatten[{{RM[r, m - 1], RM[r, m - 1]}, {0,
RM[r - 1, m - 1]}}]]]
AX = RM[1, 6]; (*X stabilizers*)
excess = RM[2, 6];
positions =
Ordering[#, -1][] & /@
NullSpace[LinearSolve[Transpose[excess], #, Modulus -> 2] & /@ AX,
Modulus -> 2];
logicalX = excess[[positions]];
AZ = RM[3, 6]; (*Z stabilizers*)
excess = RM[4, 6];
positions =
Ordering[#, -1][] & /@
NullSpace[LinearSolve[Transpose[excess], #, Modulus -> 2] & /@ AZ,
Modulus -> 2];
logicalZ = excess[[positions]];
Print["Is definition of X stabilizer correct size? ",
Dimensions[logicalX] == {15, 64}]
Print["Is definition of Z stabilizer correct size? ",
Dimensions[logicalZ] == {15, 64}]
Print["Do logical Z commute with X stabilizers? ",
Count[Mod[RM[1, 6].Transpose[logicalZ], 2], 1, Infinity] == 0]
Print["Do logical X commute with Z stabilizers? ",
Count[Mod[RM[3, 6].Transpose[logicalX], 2], 1, Infinity] == 0]
Print["Do the anticommutations between logical X and logical Z have \
full rank (therefore defining correct number of qubits? ",
Abs[Det[Mod[logicalZ.Transpose[logicalX], 2]]] == 1]


Previous version (not relevant to question)

So, to define the 15 qubit triorthogonal code, we specify the $$X$$ stabilizers with the generators $$A_X=\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$$ Note that all the rows have even weight. This part of the code is easily seen to be distance 3 because all of the columns are distinct (so $$Z$$ errors will all have distinct syndromes).

The logical operators are $$X_L=X^{\otimes 15},\qquad Z_L=Z^{\otimes 15}.$$ These clearly anti-commute with each other, and commute with the X-type stabilizers (in the case of $$X_L$$ this is trivial. For $$Z_L$$ it's because of the even weight of the stabilizers).

The $$Z$$ stabilizers are then just selected to be what they have to be in order to define a code such that they all commute with the $$X$$ stabilizers and $$X_L$$. I don't remember what these are, but they're easily calculated (e.g. in Mathematica):

AX = Transpose[Rest[Tuples[{0, 1}, 4]]];
XL = Table[1, {15}];
AZ = NullSpace[Append[AX, XL], Modulus -> 2]


to find that $$A_Z=\begin{bmatrix} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}.$$ Again, every column is distinct, so the distance of this part of the code is at least 3 (I believe it's actually distance 7 for $$X$$ errors).

• This is a different construction; I'm familiar with it but it's based on punctured RM codes. There's a closed form definition of the $X$ and $Z$ stabilizers and logicals and I can generate this family already and everything checks out for it. Your example corresponds to punctured $RM(m=4,r=1)$; Steane code to $RM(3,1)$;...However all these codes have $k=1$; the codes in that paper are not punctured (so $n=2^m$ not $2^m-1$) and the logicals would have $k>1$ if the definition is correct. That's what got me interested; but it seems there's something wrong with the definition of the logicals. Jun 8, 2022 at 15:20
• Ah, sorry, I'd misunderstood. Jun 9, 2022 at 7:36
• Thanks for the very nice answer. It does seem to work; I think the problem in the paper is that they refer to the logicals as RM(m,x) but that really should be RM(m,x+1)-RM(m,x). I think the NullSpace calculations on "excess" in your code just removes RM(m,x). I ran your mma code and it does work; GAP is my preferred platform so I adapted your solution to GAP. I'll edit my question to add the GAP solution for reference. There's a lucky coincidence in that if you reorder the Z logicals the the X and Z logicals obey the expected commutation relations....thanks again. Jun 9, 2022 at 21:40
• as a side note, I like to calculate the destabilisers for the codes I'm looking at. Together with the stabilizers and logicals you get a full set of generators of the Pauli group. The encoding operation becomes an automoprhism of the group. I can get these through calculations similar to your Nullspace calculations but for these codes I have a feeling there's a closed form solution. Let me know if you see a quick way to get these destabilsers given the relationships between the different RM's... Jun 10, 2022 at 1:36