Details: free algebra

A free algebra is a polynomial ring in noncommutative variables. Variables are standard Scala objects and can bear indices and flags. Those objects must exist in an object inheriting free.MonoDef, and themselves inherit Op.

Free algebras are defined as monoid rings over a free monoid (with little added mathematical structure, see below); the ring we use is the field of cyclotomic numbers.

Definitions

We return to our CHSH example, but removing the syntactic sugar present in the simple example:

import net.alasc.symdpoly._
import math.Phase
import defaults._

object Free extends free.MonoDef(cyclotomicOrder = 2) {
  case class A(x: Int) extends Op {
	def adjoint: Op = this
  }
  object A extends OpFamily {
	val allInstances = Seq(A(0), A(1))
  }
  case class B(y: Int) extends Op {
    def adjoint: Op = this
  }
  object B extends OpFamily {
    val allInstances = Seq(B(0), B(1))
  }
  val families = Seq(A, B)
}
import Free.{A, B}

scala> (A(0)*B(0)).adjoint
res0: net.alasc.symdpoly.freebased.Mono[Free.type,Free.Free] = B(0) A(0)

We can also represent non-Hermitian variables:

object Free1 extends free.MonoDef(cyclotomicOrder = 4) {
  case class X(i: Int, isAdjoint: Boolean = false) extends Op {
    override def toString = if (isAdjoint) s"X($i)*" else s"X($i)"
    def adjoint: Op = X(i, !isAdjoint)
  }
  object X extends OpFamily {
    val allInstances = Seq(X(0), X(1), X(2), X(0).adjoint, X(1).adjoint, X(2).adjoint)
  }
  val families = Seq(X)
}
import Free1.X

scala> (X(0)*X(1)).adjoint
res1: net.alasc.symdpoly.freebased.Mono[Free1.type,Free1.Free] = X(1)* X(0)*

Note that Scala’s type system prevents us from mixing operators coming from different free monoids:

scala> X(0)*A(0)
<console>:24: error: overloaded method value * with alternatives:
  (rhs: net.alasc.symdpoly.generic.MonoLike[Free1.Free])Free1.Free#MonoType <and>
  (rhs: cyclo.Cyclo)Free1.Free#PolyType <and>
  (rhs: spire.math.Rational)Free1.Free#PolyType <and>
  (rhs: Int)Free1.Free#PolyType <and>
  (rhs: Free1.Free#PolyType)Free1.Free#PolyType <and>
  (rhs: net.alasc.symdpoly.math.Phase)(implicit d: DummyImplicit)net.alasc.symdpoly.free.PhasedOp[Free1.Free]
 cannot be applied to (Free.A)
       X(0)*A(0)
           ^

Syntactic sugar

To ease the boilerplate of defining allInstances and the adjoint method for Hermitian operators, we can use the following shortcuts.

object FreeSimplified extends free.MonoDef(2) {
  case class A(x: Int) extends HermitianOp // defines an `adjoint` method that is the identity
  object A extends HermitianOpFamily1(0 to 1)  // enumerates the instances from a given Range, if the operator has a single index
  case class B(y: Int) extends HermitianOp
  object B extends HermitianOpFamily1(0 to 1)
  val families = Seq(A, B)
}

The same holds for non-Hermitian variables.

object Free1Simplified extends free.MonoDef(4) {
  case class X(i: Int, isAdjoint: Boolean = false) extends Op {
    override def toString = if (isAdjoint) s"X($i)*" else s"X($i)"
    def adjoint: Op = X(i, !isAdjoint)
  }
  object X extends OpFamily1(0 to 2)
  val families = Seq(X)
}

scala> Free1Simplified.X.allInstances
res3: Seq[Free1Simplified.Op] = Vector(X(0), X(0)*, X(1), X(1)*, X(2), X(2)*)

Additional structure compared to free monoids

Compared to standard *-free monoids, we already include the following structure at the level of our free monoids.

Our free monoids are `*`-monoids

Our monoids have an involution compatible with multiplication.

scala> val x = X(0)*X(1).adjoint
x: Free1.Free#MonoType = X(0) X(1)*

scala> val y = X(1)*X(0)
y: Free1.Free#MonoType = X(1) X(0)

scala> (x*y).adjoint
res4: net.alasc.symdpoly.freebased.Mono[Free1.type,Free1.Free] = X(0)* X(1)* X(1) X(0)*

scala> (y.adjoint)*(x.adjoint)
res5: net.alasc.symdpoly.freebased.Mono[Free1.type,Free1.Free] = X(0)* X(1)* X(1) X(0)*

Self-adjoint elements are handled

Instead of defining an equivalence rule X(0) ~ X(0).adjoint at the level of the quotient monoid, we already have an identity between operator variables and their adjoints when the variable is Hermitian.

scala> A(0).adjoint
res6: Free.Op = A(0)

Our free monoids are binoids

Binoids are monoids with an absorbing element, which we denote by zero (see the thesis of Simone Boettger). This absorbing element is unique.

scala> Free1.zero * X(0)
res7: Free1.MonoType = 0

scala> X(0) * Free1.zero
res8: Free1.Free#MonoType = 0

scala> Free1.zero * Free1.zero
res9: net.alasc.symdpoly.freebased.Mono[Free1.type,Free1.Free] = 0

Polynomials over free monoids

First and foremost, we can have polynomials whose monomials are elements of a free monoid (excluding zero):

scala> val p = A(0) * B(0) + A(1) * B(0) + A(0) * B(1) - A(1) * B(1)
p: Free.PolyType = A(0) B(0) + A(0) B(1) + A(1) B(0) - A(1) B(1)

scala> p * p - p
res10: Free.PolyType = - A(0) B(0) - A(0) B(1) - A(1) B(0) + A(1) B(1) + A(0) B(0) A(0) B(0) + A(0) B(0) A(0) B(1) + A(0) B(0) A(1) B(0) - A(0) B(0) A(1) B(1) + A(0) B(1) A(0) B(0) + A(0) B(1) A(0) B(1) + A(0) B(1) A(1) B(0) - A(0) B(1) A(1) B(1) + A(1) B(0) A(0) B(0) + A(1) B(0) A(0) B(1) + A(1) B(0) A(1) B(0) - A(1) B(0) A(1) B(1) - A(1) B(1) A(0) B(0) - A(1) B(1) A(0) B(1) - A(1) B(1) A(1) B(0) + A(1) B(1) A(1) B(1)

Due to syntax issues in the Scala programming language, you must multiply by scalars on the right, or either use the left multiplication *: operator.

scala> p * sqrt(2)
res11: Free.PolyType = sqrt(2) A(0) B(0) + sqrt(2) A(0) B(1) + sqrt(2) A(1) B(0) - sqrt(2) A(1) B(1)

scala> sqrt(2) *: p
res12: net.alasc.symdpoly.freebased.Poly[Free.type,Free.Free] = sqrt(2) A(0) B(0) + sqrt(2) A(0) B(1) + sqrt(2) A(1) B(0) - sqrt(2) A(1) B(1)

Due to the same syntax issue, constant terms must be added from the right:

scala> p - sqrt(2)*2
res13: Free.PolyType = - 2*sqrt(2) 1 + A(0) B(0) + A(0) B(1) + A(1) B(0) - A(1) B(1)

or use a cumbersome syntax:

scala> Free.one*(sqrt(2)*2)
res14: Free.PolyType = 2*sqrt(2) 1

scala> Free.one*(sqrt(2)*2) - p
res15: Free.PolyType = 2*sqrt(2) 1 - A(0) B(0) - A(0) B(1) - A(1) B(0) + A(1) B(1)

This will fail:

scala> sqrt(2)*2 - p
<console>:25: error: overloaded method value - with alternatives:
  (rhs: cyclo.Cyclo)cyclo.Cyclo <and>
  (r: spire.math.Rational)cyclo.Cyclo
 cannot be applied to (Free.PolyType)
       sqrt(2)*2 - p
                 ^

as for binary operations, the left term handles the evaluation, and thus it should be the most complex type present.

Other objects on free monoids

Likewise Other objects include operators with a phase, used to define symmetries:

scala> A(0) -> -A(0)
res17: (Free.A, net.alasc.symdpoly.free.PhasedOp[Free.Free]) = (A(0),- A(0))

and monomials with a phase, useful to define substitution rules:

scala> X(0) * X(1) -> X(2) * Phase.minusI
res18: (Free1.Free#MonoType, net.alasc.symdpoly.free.PhasedOp[Free1.Free]) = (X(0) X(1),-i X(2))

When constructing the moment matrix, SymDPoly processes monomials with a phase.