Automorphism groups and equivalence testing

[awcross1]

What is the expected behavior?

The permutation automorphisms of stabilizer codes can be used to apply fault tolerant gates in a model where we can freely relabel the qubits. The local permutations of the Pauli operators on each coordinate can be used to apply transversal gates. Coordinate permutations and local Clifford gates together generate the automorphism group of the stabilizer code and enlarge the fault tolerant gate set. The order of the automorphism group is an indication of underlying symmetry. Finding these automorphism groups is therefore valuable.

How can we compute the automorphism group(s) of potentially large stabilizer codes?

There is another related problem. Two stabilizer codes are equivalent if they are related to one another by coordinate permutations and local single-qubit Clifford gates. For example, the XZZX surface code is equivalent to the standard surface code, but in other cases this is less obvious.

How can we decide if two potentially large stabilizer codes are equivalent and find the relationship between them?

Leon's algorithm computes automorphism groups of binary linear codes. There is an implementation contained in the GAP package GUAVA: https://github.com/gap-packages/guava/tree/master/src/leon/src

J. Leon, Computing automorphism groups of error-correcting codes, IEEE Trans. Inf. Theo., 28, 3, 1982.

A more recent paper by T. Feulner aims to classify linear codes over GF(q). His algorithm is comparable to Leon's algorithm in running time, but also computes a canonical representative of the code. It computes two different types of automorphism group.

T. Feulner, The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes, Advances in Mathematics of Communications 3(4): 363-383 2009.

We are interested in additive codes over GF(4), which is a larger family of codes than linear codes over GF(4). The original paper by Calderbank, Rains, Shor, and Sloane in 1996 suggests a method for reducing the problem for additive codes over GF(4) to binary linear codes. They apply a map from the elements of GF(4) to length-3 binary vectors to the coordinates of an additive code. This maps an additive code S to phi(S). They state that the automorphism group of S is isomorphic to the intersection of Aut(phi(S)) and Aut(phi(T)) where T = GF(4)^n.

In my earlier stabilizer code programs, I used a mapping from the stabilizer elements to a colored graph to (inefficiently) reduce the problems to equivalent problems on a graph, which could be solved by nauty. This approach does not extend much beyond about 16 qubits.

Finally we mention a recent paper about solving code equivalence problems over GF(q). This paper may not be directly relevant to our problem since it seems to out-perform existing algorithms only when q is large, but it offers another perspective.

W. Beullens, Not enough LESS: An improved algorithm for solving code equivalence problems over F_q, https://eprint.iacr.org/2020/801

Part of our discussion here should be whether or not open-source mathematics packages suffice. For example, it will not be hard to implement the CRSS approach in GAP. What size problems can we solve this way?

[awcross1]

This program actually works.

LoadPackage("GUAVA");

PhiFunction := function(M)
local phimat, dims;
dims := DimensionsMat(M);
phimat := NullMat(dims[1], 3*dims[2], GF(2));
for i in [1..dims[1]] do
  for j in [1..dims[2]] do
    if M[i,j] = Z(4)^0 then
      phimat[i,3*(j-1)+2] := Z(2)^0;
      phimat[i,3*(j-1)+3] := Z(2)^0;
    elif M[i,j] = Z(4) then
      phimat[i,3*(j-1)+1] := Z(2)^0;
      phimat[i,3*(j-1)+3] := Z(2)^0;
    elif M[i,j] = Z(4)^2 then
      phimat[i,3*(j-1)+1] := Z(2)^0;
      phimat[i,3*(j-1)+2] := Z(2)^0;
    fi;
  od;
od;
return phimat;
end;

# Four qubit code XXXX, ZZZZ
GS:=[[0*Z(4), 0*Z(4), 0*Z(4), 0*Z(4)],[Z(4),Z(4),Z(4),Z(4)],[Z(4)^0,Z(4)^0,Z(4)^0,Z(4)^0],[Z(4)^2,Z(4)^2,Z(4)^2,Z(4)^2]];
S:=ElementsCode(GS, GF(4));
PhiS:=ElementsCode(PhiFunction(GS), GF(2));
A1:=AutomorphismGroup(PhiS);

# All of the 4 qubit Paulis
T:=WholeSpaceCode(4, GF(4));
Tprime:=ElementsCode(AsSortedList(T), GF(4));
TprimeMat:=NullMat(Size(Tprime), 4, GF(4));
for i in [1..Size(Tprime)] do
  TprimeMat[i] := VectorCodeword(CodewordNr(Tprime, i));
od;
PhiTprime:=ElementsCode(PhiFunction(TprimeMat), GF(2));
A2:=AutomorphismGroup(PhiTprime);

A:=Intersection(A1, A2);
Order(A);

[awcross1]

Selected output:

gap> S:=ElementsCode(GS, GF(4));
a (4,4,1..4)2..3 user defined unrestricted code over GF(4)
gap> PhiS:=ElementsCode(PhiFunction(GS), GF(2));
a (12,4,1..12)5..6 user defined unrestricted code over GF(2)
gap> A1:=AutomorphismGroup(PhiS);
<permutation group of size 82944 with 16 generators>
gap> T:=WholeSpaceCode(4, GF(4));
a cyclic [4,4,1]0 whole space code over GF(4)
gap> Tprime:=ElementsCode(AsSortedList(T), GF(4));
a (4,256,1..4)0 user defined unrestricted code over GF(4)
gap> PhiTprime:=ElementsCode(PhiFunction(TprimeMat), GF(2));
a (12,256,1..12)2..4 user defined unrestricted code over GF(2)
gap> A2:=AutomorphismGroup(PhiTprime);
<permutation group of size 31104 with 18 generators>
gap> A:=Intersection(A1, A2);
Group([ (7,10)(8,11)(9,12), (4,7,10)(5,8,11)(6,9,12), (2,3)(5,6)(7,10)(8,12)(9,11), (1,2,3)(4,5,6)(7,11,9,10,8,12), 
  (1,4)(2,6)(3,5)(7,10)(8,12)(9,11) ])
gap> Order(A);
144

The order of Aut(S) is the order of the symmetric group on 4 elements (24 possible coordinate permutations) times the order of the symmetric group on 3 elements (6 possible permutations of Pauli operators XXXX, YYYY, ZZZZ).

[awcross1]

Follow up questions:

1. How can we compute A2 without generating all of the elements of the Pauli group? Ideally we want A2 for any number of qubits.
2. Can we write a function to map the generators of A to qubit coordinate permutations and Clifford gates?
3. How can we compute the subgroups of Aut(S) consisting of only coordinate permutations or only Clifford gates?
4. How does the time to compute Aut(S) scale with number of qubits?

[awcross1]

This method answers question (1) above.

WholeSpaceAutGroup := function(n)
local i, j, plist, generators;
generators := [];
plist := [];
# Pauli permutations
for j in [0..n-1] do
  i := 3*j+1;
  Append(generators, [(i, i+1, i+2)]);
  Append(generators, [(i, i+1)]);
od;
# coordinate permutations
for j in [0..3*n-1] do
  Append(plist, [RemInt(j+3, 3*n)+1]);
od;
Append(generators, [PermList(plist)]);
if n > 1 then
  Append(generators, [(1, 4)(2, 5)(3, 6)]);
fi;
return Group(generators);
end;

[awcross1]

Here is everything together:

LoadPackage("GUAVA");

# Phi is a morphism from GF(4)-additive codes to binary linear codes.
# If a, b are vectors in the GF(4)-additive code then phi(a+b) = phi(a) + phi(b).
PhiFunction := function(M)
local PhiM, dims;
dims := DimensionsMat(M);
PhiM := NullMat(dims[1], 3*dims[2], GF(2));
for i in [1..dims[1]] do
  for j in [1..dims[2]] do
    if M[i,j] = Z(4)^0 then  # 1 -> 011
      PhiM[i,3*(j-1)+2] := Z(2)^0;
      PhiM[i,3*(j-1)+3] := Z(2)^0;
    elif M[i,j] = Z(4) then  # omega -> 101
      PhiM[i,3*(j-1)+1] := Z(2)^0;
      PhiM[i,3*(j-1)+3] := Z(2)^0;
    elif M[i,j] = Z(4)^2 then  # omega^2 -> 110
      PhiM[i,3*(j-1)+1] := Z(2)^0;
      PhiM[i,3*(j-1)+2] := Z(2)^0;
    fi;
  od;
od;
return PhiM;
end;

# The automorphism group of the whole space code is S_3 semidirect S_n.
# We compute the generators of this group in terms of their
# action on the image of Phi.
WholeSpaceAutGroup := function(n)
local i, j, plist, generators;
generators := [];
plist := [];
# Pauli permutations
for j in [0..n-1] do
  i := 3*j+1;
  Append(generators, [(i, i+1, i+2)]);
  Append(generators, [(i, i+1)]);
od;
# coordinate permutations
for j in [0..3*n-1] do
  Append(plist, [RemInt(j+3, 3*n)+1]);
od;
Append(generators, [PermList(plist)]);
if n > 1 then
  Append(generators, [(1, 4)(2, 5)(3, 6)]);
fi;
return Group(generators);
end;

# G is an n-k by n matrix over GF(4) that generates
# the GF(4)-additive code, i.e. the code is all GF(2) linear combinations
# of the rows of G.
GF4AdditiveAutGroup := function(G)
local PhiC, dims, AC, AW;
dims := DimensionsMat(G);
PhiC := GeneratorMatCode(PhiFunction(G), GF(2));  # a linear code
AC := AutomorphismGroup(PhiC);
AW := WholeSpaceAutGroup(dims[2]);
return Intersection(AC, AW);
end;

We use it like this:

# Generators XXXX and ZZZZ of the four qubit code
G:=[[Z(4)^0,Z(4)^0,Z(4)^0,Z(4)^0],[Z(4),Z(4),Z(4),Z(4)]];
A:=GF4AdditiveAutGroup(G);
Order(A);

which gives the output:

gap> A:=GF4AdditiveAutGroup(G);
Group([ (4,7)(5,8)(6,9), (4,7,10)(5,8,11)(6,9,12), (2,3)(4,7,10)(5,9,11,6,8,12), (1,2,3)(4,8,12)(5,9,10)(6,7,11), 
  (1,4,7,10)(2,6,8,12)(3,5,9,11) ])
gap> Order(A);
144

[awcross1]

This gives an answer to (2) and (3):

LoadPackage("GUAVA");

# If a, b are vectors in the GF(4)-additive code then phi(a+b) = phi(a) + phi(b).
PhiFunction := function(M)
local PhiM, dims;
dims := DimensionsMat(M);
PhiM := NullMat(dims[1], 3*dims[2], GF(2));
for i in [1..dims[1]] do
  for j in [1..dims[2]] do
    if M[i,j] = Z(4)^0 then  # 1 -> 011
      PhiM[i,3*(j-1)+2] := Z(2)^0;
      PhiM[i,3*(j-1)+3] := Z(2)^0;
    elif M[i,j] = Z(4) then  # omega -> 101
      PhiM[i,3*(j-1)+1] := Z(2)^0;
      PhiM[i,3*(j-1)+3] := Z(2)^0;
    elif M[i,j] = Z(4)^2 then  # omega^2 -> 110
      PhiM[i,3*(j-1)+1] := Z(2)^0;
      PhiM[i,3*(j-1)+2] := Z(2)^0;
    fi;
  od;
od;
return PhiM;
end;

# The automorphism group of the whole space code is S_3 semidirect S_n.
# We compute the generators of this group in terms of their
# action on the image of Phi.
WholeSpaceAutGroup := function(n)
local i, j, plist, generators;
generators := [];
plist := [];
# Pauli permutations
for j in [0..n-1] do
  i := 3*j+1;
  Append(generators, [(i, i+1, i+2)]);
  Append(generators, [(i, i+1)]);
od;
# coordinate permutations
for j in [0..3*n-1] do
  Append(plist, [RemInt(j+3, 3*n)+1]);
od;
Append(generators, [PermList(plist)]);
if n > 1 then
  Append(generators, [(1, 4)(2, 5)(3, 6)]);
fi;
return Group(generators);
end;

# The permutation automorphism group of the whole space code
# is S_n.
WholeSpacePermAutGroup := function(n)
local i, j, plist, generators;
generators := [];
plist := [];
# coordinate permutations
for j in [0..3*n-1] do
  Append(plist, [RemInt(j+3, 3*n)+1]);
od;
Append(generators, [PermList(plist)]);
if n > 1 then
  Append(generators, [(1, 4)(2, 5)(3, 6)]);
fi;
return Group(generators);
end;

# Subgroup in S_3^n
WholeSpaceS3nAutGroup := function(n)
local i, j, generators;
generators := [];
# Pauli permutations
for j in [0..n-1] do
  i := 3*j+1;
  Append(generators, [(i, i+1, i+2)]);
  Append(generators, [(i, i+1)]);
od;
return Group(generators);
end;

# G is an n-k by n matrix over GF(4) that generates
# the GF(4)-additive code, i.e. the code is all GF(2) linear combinations
# of the rows of G.
GF4AdditiveAutGroup := function(G)
local PhiC, dims, AC, AW;
dims := DimensionsMat(G);
PhiC := GeneratorMatCode(PhiFunction(G), GF(2));  # a linear code
AC := AutomorphismGroup(PhiC);
AW := WholeSpaceAutGroup(dims[2]);
return Intersection(AC, AW);
end;

GF4AdditivePermAutGroup := function(G)
local PhiC, dims, AC, AW;
dims := DimensionsMat(G);
PhiC := GeneratorMatCode(PhiFunction(G), GF(2));  # a linear code
AC := AutomorphismGroup(PhiC);
AW := WholeSpacePermAutGroup(dims[2]);
return Intersection(AC, AW);
end;

GF4AdditiveS3nAutGroup := function(G)
local PhiC, dims, AC, AW;
dims := DimensionsMat(G);
PhiC := GeneratorMatCode(PhiFunction(G), GF(2));  # a linear code
AC := AutomorphismGroup(PhiC);
AW := WholeSpaceS3nAutGroup(dims[2]);
return Intersection(AC, AW);
end;

StringsToGF4 := function(stringlist)
local M;
# assume Length(stringlist[i]) is the same for all i
M := NullMat(Length(stringlist), Length(stringlist[1]), GF(4));
for i in [1..Length(stringlist)] do
  for j in [1..Length(stringlist[1])] do
    if stringlist[i][j] = 'x' then
      M[i][j] := Z(4)^0;
    elif stringlist[i][j] = 'z' then
      M[i][j] := Z(4);
    elif stringlist[i][j] = 'y' then
      M[i][j] := Z(4)^2;
    fi;
  od;
od;
return M;
end;

reformat := function(A, n)
  local autgens, g, img, perm, sing, tup, permlist, lclist;
  autgens := GeneratorsOfGroup(A);
  permlist := [];
  lclist := [];
  for g in autgens do
    img := OnTuples([1..3*n], g);
    perm := [];
    sing := [];
    for i in [1..n] do
      Append(perm, [QuoInt(img[3*(i-1)+1]-1, 3)+1]);
      tup := [RemInt(img[3*(i-1)+1]-1, 3),
              RemInt(img[3*(i-1)+2]-1, 3),
              RemInt(img[3*(i-1)+3]-1, 3)];
      if tup = [0, 1, 2] then
        Append(sing, "i");  # *1
      elif tup = [1, 2, 0] then
        Append(sing, "b");  # *a^2 = *Z(4)^2 = b
      elif tup = [2, 0, 1] then
        Append(sing, "a");  # *a = *Z(4)
      elif tup = [1, 0, 2] then
        Append(sing, "3");  # exchange 1 and a, fix a^2
      elif tup = [0, 2, 1] then
        Append(sing, "1");  # exchange a and a^2, fix 1
      elif tup = [2, 1, 0] then
        Append(sing, "2");  # exchange 1 and a^2, fix a
      fi;
    od;
    Add(permlist, perm);
    Add(lclist, sing);
  od;
  return rec(permutations:=permlist, locals:=lclist);
end;

# Test
gens := ["xxxx", "zzzz"];
genmat := StringsToGF4(gens);
Print("genmat = ", genmat, "\n");
A := GF4AdditiveAutGroup(genmat);
Print("A = ", A, "\n");
Print("Order(A) = ", Order(A), "\n");
Print(reformat(A, 4), "\n");
Aperm := GF4AdditivePermAutGroup(genmat);
Print("Aperm = ", Aperm, "\n");
Print("Order(Aperm) = ", Order(Aperm), "\n");
Print(reformat(Aperm, 4), "\n");
Abit := GF4AdditiveS3nAutGroup(genmat);
Print("Abit = ", Abit, "\n");
Print("Order(Abit) = ", Order(Abit), "\n");
Print(reformat(Abit, 4), "\n");

# NanosecondsSinceEpoch();  # for timing

Here is the output from this example:

genmat = [ [ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ], [ Z(2^2), Z(2^2), Z(2^2), Z(2^2) ] ]
A = Group( [ (4,7)(5,8)(6,9), ( 4, 7,10)( 5, 8,11)( 6, 9,12), ( 2, 3)( 4, 7,10)( 5, 9,11, 6, 8,12), 
  ( 1, 2, 3)( 4, 8,12)( 5, 9,10)( 6, 7,11), ( 1, 4, 7,10)( 2, 6, 8,12)( 3, 5, 9,11) ] )
Order(A) = 144
rec(
  locals := [ "iiii", "iiii", "1111", "bbbb", "1111" ],
  permutations := [ [ 1, 3, 2, 4 ], [ 1, 3, 4, 2 ], [ 1, 3, 4, 2 ], [ 1, 3, 4, 2 ], [ 2, 3, 4, 1 ] ] )
Aperm = Group( [ ( 1, 4, 7,10)( 2, 5, 8,11)( 3, 6, 9,12), (1,4)(2,5)(3,6) ] )
Order(Aperm) = 24
rec(
  locals := [ "iiii", "iiii" ],
  permutations := [ [ 2, 3, 4, 1 ], [ 2, 1, 3, 4 ] ] )
Abit = Group( [ ( 2, 3)( 5, 6)( 8, 9)(11,12), ( 1, 2, 3)( 4, 5, 6)( 7, 8, 9)(10,11,12) ] )
Order(Abit) = 6
rec(
  locals := [ "1111", "bbbb" ],
  permutations := [ [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ] ] )

The four qubit code's automorphism group is generated by an order 24 = 4! subgroup of permutations and an order 6 = 3! subgroup of bitwise Clifford gates.