Details: symmetries

SymDPoly supports symmetry groups that are subgroups of the Generalized symmetric group, acting by permuting operator variables, possibly changing their phase. As, currently, support for complex formulations is incomplete in SymDPoly, so the elements we use correspond to signed permutations.

We show below the syntax used to define those generators, which uses Scala pattern matching.

import net.alasc.symdpoly._
import defaults._
import net.alasc.symdpoly.examples.quantum.CHSH.{Free, Quantum}
import Free.{A, B}

scala> val swapParties = Free.permutation {
     |   case A(i) => B(i)
     |   case B(i) => A(i)
     | }
swapParties: net.alasc.symdpoly.freebased.Permutation[net.alasc.symdpoly.examples.quantum.CHSH.Free.type,net.alasc.symdpoly.examples.quantum.CHSH.Free.type] = {A(0) -> B(0), A(1) -> B(1), B(0) -> A(0), B(1) -> A(1)}

scala> val inputSwapA = Free.permutation {
     |   case A(0) => A(1)
     |   case A(1) => A(0)
     |   case B(y) => B(y)
     | }
inputSwapA: net.alasc.symdpoly.freebased.Permutation[net.alasc.symdpoly.examples.quantum.CHSH.Free.type,net.alasc.symdpoly.examples.quantum.CHSH.Free.type] = {A(0) -> A(1), A(1) -> A(0)}

scala> val outputSwapA0 = Free.permutation {
     |   case A(0) => -A(0)
     |   case A(1) => A(1)
     |   case B(y) => B(y)
     | }
outputSwapA0: net.alasc.symdpoly.freebased.Permutation[net.alasc.symdpoly.examples.quantum.CHSH.Free.type,net.alasc.symdpoly.examples.quantum.CHSH.Free.type] = {A(0) -> - A(0)}

Note the minus sign in outputSwapA0, which multiplies the phase of A(0) by -1: and beware that the allowed phases are the roots of unity with a denominator dividing the cyclotomicOrder parameter of the free monoid.

Feasibility group

The feasibility group of a quotient monoid/algebra is a symmetry group whose action is compatible with the equivalence classes: it contains permutations g of the operators such that g(quotient(monomial)) = quotient(g(monomial)), and then the action of equivalency classes of the quotient is well defined.

The feasibility group can be defined from a permutation group on the free monoid. When using groupInQuotient, we check compatibility of the generators with the quotient structure: if some generators are incompatible, we look for the subgroup that preserves the quotient structure. The groupInQuotientNC method is unsafe and disables this check: you can use it when performance becomes critical and you have already proved that the given group preserves the quotient structure.

Note that the feasibility group can automatically be computed by calling Quantum.symmetryGroup.

scala> val feasibilityGroup = Quantum.groupInQuotient(Grp(swapParties, inputSwapA, outputSwapA0))
feasibilityGroup: net.alasc.finite.Grp[net.alasc.symdpoly.examples.quantum.CHSH.Quantum.PermutationType] = Grp({A(0) -> B(0), A(1) -> B(1), B(0) -> A(0), B(1) -> A(1)}, {A(0) -> A(1), A(1) -> A(0)}, {A(0) -> - A(0)})

scala> val feasibilityGroup1 = Quantum.groupInQuotientNC(Grp(swapParties, inputSwapA, outputSwapA0))
feasibilityGroup1: net.alasc.finite.Grp[net.alasc.symdpoly.examples.quantum.CHSH.Quantum.PermutationType] = Grp({A(0) -> B(0), A(1) -> B(1), B(0) -> A(0), B(1) -> A(1)}, {A(0) -> A(1), A(1) -> A(0)}, {A(0) -> - A(0)})

scala> val feasibilityGroup2 = Quantum.symmetryGroup
feasibilityGroup2: net.alasc.finite.Grp[net.alasc.symdpoly.examples.quantum.CHSH.Quantum.PermutationType] = Grp({A(0) -> A(1), A(1) -> A(0)}, {A(0) -> B(0), A(1) -> B(1), B(0) -> A(0), B(1) -> A(1)}, {A(1) -> - A(1)}, {B(0) -> B(1), B(1) -> B(0)}, {B(1) -> - B(1)})

Using the algorithms of Alasc, the group order is readily computed, as well as a small set of generators:

scala> feasibilityGroup.order
res0: spire.math.SafeLong = 128

scala> feasibilityGroup1.order
res1: spire.math.SafeLong = 128

scala> feasibilityGroup2.order
res2: spire.math.SafeLong = 128

scala> feasibilityGroup.smallGeneratingSet
res3: Seq[net.alasc.symdpoly.examples.quantum.CHSH.Quantum.PermutationType] = Vector({A(0) -> B(0), A(1) -> B(1), B(0) -> A(0), B(1) -> A(1)}, {A(0) -> A(1), A(1) -> A(0)}, {A(0) -> - A(0)})