The mmgroup API reference¶

Introduction¶

The mmgroup package is a python implementation of Conway’s construction [Con85] of the monster group $$\mathbb{M}$$. In mathematics the monster group $$\mathbb{M}$$ is the largest sporadic finite simple group. The group $$\mathbb{M}$$ has order

$$2^{46} \cdot 3^{20} \cdot 5^9 \cdot 7^6 \cdot 11^2 \cdot 13^3 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 41 \cdot 47 \cdot 59 \cdot 71$$ = $$\small 808.017.424.794.512.875.886.459.904.961.710.757.005.754.368.000.000.000$$ .

It has a rational representation $$\rho$$ of dimension $$196884$$ with coefficients in $$\mathbb{Z}[\frac{1}{2}]$$, see [Con85]. So we obtain a modular representation $$\rho_p$$ of $$\mathbb{M}$$ by reducing the rational representation $$\rho$$ modulo an arbitrary odd number $$p$$. The current version of the mmgroup package supports the representations $$\rho_p$$ of $$\mathbb{M}$$ for $$p = 3, 7, 15, 31, 127, 255$$.

The mmgroup package uses highly optimized C programs for calculating in the representations of $$\rho_p$$ of $$\mathbb{M}$$, which are most efficient if $$p+1$$ is a small power of two. Most of these C programs have been generated automatically by a program code generator which is also part of this project, but not part of the public interface described in this document.

In the description of the mmgroup package we use the notation in [Sey20], where an explicit description of the representations $$\rho(g), g \in G$$ is given for a generating subset $$G$$ of $$\mathbb{M}$$.

Installation¶

Installation on 64-bit Windows¶

For installing the mmgroup package on a 64-bit Windows system you simply type:

pip install mmgroup


32-bit Windows systems are not supported.

Installation on Linux¶

There is experimantal support for installing the mmgroup package on a Linux system from a source distribution. Details are given in the guide for developers.

Basic structures¶

The Golay code and its cocode¶

We deal with the Golay code and its cocode.

Let $$\tilde{\Omega}$$ be the set of integers $$\{ i \in \mathbb{Z} \mid 0 \leq i < 24\}$$ of size $$24$$ and construct the vector space $$\mathcal{V} = \mathbb{F}_2^{24}$$ as $$\prod_{i\in \tilde{\Omega}} \mathbb{F}_2$$. In this document elements of $$\mathcal{V}$$ are called bit vectors. We represent bit vectors as instances of class GcVector.

We identify the power set of $$\tilde{\Omega}$$ with the vector space $$\mathcal{V} = \mathbb{F}_2^{24}$$ by mapping each subset of $$\tilde{\Omega}$$ to its characteristic function, which is a bit vector in $$\mathcal{V}$$. So we may talk about union and intersection of bit vectors in a natural way and use the python operators | and & for these operations as usual. We use the + operator for vector addition of bit vectors. Bit vectors are numbered from 0 to 0xffffff, with bit i of that number corresponding to the i-th unit vector.

The Golay code $$\mathcal{C}$$ is a $$12$$-dimensional linear subspace of $$\mathcal{V}$$ such that a nonzero vector in $$\mathcal{C}$$ has weight at least $$8$$. This characterizes the Golay code up to permutation. In this package we chose a specific basis of the Golay code that satisfies the requirements in [Sey20], see The basis of the Golay code and of its cocode for details. We represent Golay code words as instances of class GCode. Golay code words of weight $$8$$ and $$12$$ are called octads and dodecads, respectively.

We stress that class GCode is not a subclass of class GcVector. Instances of these two classes are numbered in a different way. Golay code words are numbered from 0 to 0xfff with bit i of that number corresponding to the i-th basis vector of the Golay code. See The basis of the Golay code and of its cocode for the chosen basis of the Golay code.

The Golay cocode $$\mathcal{C}^*$$ is the 12-dimensional quotient space $$\mathbb{F}_2^{24} / \mathcal{C}$$. For any $$\delta \in \mathcal{C}^*$$ the weight of $$\delta$$ is the weight of its lightest representative in $$\mathbb{F}_2^{24}$$. That weight is at most 4. There is a unique lightest representative it the weight is less than 4, and there are six mutually disjoint lightest representatives of an element of weight 4. A partition of $$\mathbb{F}_2^{24}$$ given by such a set of disjoint representatives is called a tetrad. We represent elements of the cocode of the Golay code as instances of class Cocode. Cocode elements are numbered from 0 to 0xfff with bit i of that number corresponding to the i-th basis vector of the cocode. Our basis of the cocode is the reciprocal basis of the basis of the Golay code, see The basis of the Golay code and of its cocode for details.

The scalar product of a Golay code word and a cocode element is the parity of the intersection of the Golay code word and any representative of the cocode element. If g is an instance of class GCode and d is an instance of class Cocode then g & d is an instance of class Parity. Here class Parity models an integer modulo 2, which is also considered as the parity of a bit vector. Standard operations, e.g. (-1)**p, work as expected for an instance p of class Parity.

The standard function len(x) returns the (minimal) weight |x| of an instance x of class GcVector, GCode or Cocode. For instances g1, g2, g3 of class GCode, the expression g1 & g2 is an instance of class Cocode and g1 & g2 & g3 an instance of class Parity; these values have a natural interpretations as bitwise intersections. g1/4 is a shorthand for Parity(len(g1)/4); and (g1 & g2)/2 is a shorthand for Parity(len(g1 & g2)/2). These two expressions are called the power map and the commutator, respectively, in [Asc86]; and g1 & g2 & g3 is called the associator in [Asc86].

The numbering of the Golay code words and of the cocode elements is important for indexing some generators of $$\mathbb{M}$$ and also some basis vectors in the representations $$\rho_p$$ of $$\mathbb{M}$$.

class mmgroup.GCode(value)

This class models a code word of the Golay code.

The Golay code is a binary [24, 12, 8] code. So there are $$2^{12}$$ code words, each word is $$24$$ bit long, and the Hamming distance between two different code words is at least $$8$$.

The $$2^{12}$$ Golay code words are numbered from 0 to 0xfff. Bit i in that number refers to the coefficient of the i-th basis vector of the Golay code, which may be $$0$$ or $$1$$.

Parameters

value (see table below for legal types) – This is the value of the Golay code word to be returned.

Returns

A Golay code vector

Return type

an instance of class GCode

Raise
• TypeError if type(value) is not in the table given below.

• ValueError if value cannot be converted to an instance of class GCode.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class GCode

type

Evaluates to

int

Here the code word with number value is returned. 0 <= value < 0x1000 must hold.

list of int

A list of integers 0 <= i < 24 is interpreted as a list of bit positions to be set in a bit vector. The Golay code word corresponding to that bit vector is returned. Up to 3 erroneous bits are corrected.

class GCode

A deep copy of parameter value is returned.

class PLoop

The Parker loop element value is converted to a Golay code word (by dropping its sign) and returned.

class GcVector

The bit vector value of type GcVector is converted to a Golay code word and returned. Up to 3 erroneous bits in that vector are corrected.

class SubOctad

The octad part of the SubOctad value is converted to a Golay code word and returned.

str

Create random element depending on the string
'r': Create arbitrary Golay code word

Standard operations

Addition of Golay code words and scalar multiplication (with scalars of type int or Parity) are done as usual.

The bitwise and operator & means bitwise and of two code words of type GCode. The result of such an operation on two Golay code words is a Golay cocode word of type Cocode.

The bitwise & operator of a Golay code word and a Golay cocode word of type Cocode is not well defined as a bit vector, but it has a well-defined parity. So in this case the result of the & operator is a parity object of type Parity.

For the bitwise & operator bit vectors of type GcVector, see class GcVector.

The ~ operator means bitwise complement as usual; it returns the complemented code word, which is also of type GCode.

Standard functions

len(g) returns the bit weight of the Golay code word g, i.e. the number of bits set in the word g.

Special functions

Let g1, g2, and g3 be Golay code vectors of type GCode.

The expression g1/4 is a shorthand for Parity(len(g1)/4). It returns len(g1)/4 modulo 2 as a parity object of type Parity.

GcVector(g1 & g2) returns the bitwise intersection of g1 and g2 as a bit vector of type GcVector.

(g1 & g2)/2 is a shorthand for Parity(len(GcVector(g1 & g2))/2). It returns the halved bit weight of g1 & g2 modulo 2 as a parity object of type Parity. This value is also called the commutator of g1 and g2.

g1 & g2 & g3 returns the parity of the bitwise intersection of g1, g2, and g3 as a parity object of type Parity. This value is also called the associator of g1, g2, and g3.

abs(g1) is a shorthand for abs(PLoop(g1)), see class PLoop for details.

property bit_list

Return the ordered list of positions of bits being set

property bits

Return the Golay code word as a 24-bit vector.

The function returns a list with 24 entries equal to 0 or 1.

property gcode

Return the number of the Golay code word.

Same as property ord.

Return number of octad of the Golay code word as an octad.

Complements of octads are also accepted as octads. We have 0 <= o < 759 for the returned number o.

Raise
• ValueError if the Golay code word is not an octad.

property ord

Return the number of the Golay code word.

We have 0 <= i < 0x1000 for the returned number i.

split()

Split the Golay code word g.

Returns

A triple (0, eo, v) with g  =  Omega * eo + v.

Here Omega is the Golay code word containing one bits only, eo is 0 or 1, and v is a Golay code word of type GCode with 0 <= v1.ord < 0x800.

This method is for compatibility with the corresponding method in class PLoop.

Split an octad from the Golay code word g.

Returns

A triple (0, eo, o) with g  =  Omega * eo + o.

Here Omega is the Golay code word containing one bits only, eo is 0 or 1, and v is a Golay code word of type GCode which is either the zero code word or an octad, i.e. a code word of weight 8.

This method is for compatibility with the corresponding method in class PLoop.

Raise
• ValueError if this is not possible.

theta(g2=None)

Return cocycle of Golay code words.

The cocycle theta maps a pair of Golay code words to an integer modulo 2. It is linear in its second argument, so it may also be considered as a mapping from the Golay code to the cocode of the Golay code.

Parameters

g2None (default) or another Golay code word of type GCode.

Returns

• If g2 is a code word of type GCode, we return the value g1.theta(g2) = theta(g1, g2) as a Parity object.

• If g2 is None (default), we return the value g1.theta() = theta(g1) as a Cocode object. Note that g1.theta(g2) == g1.theta() & g2 .

The importance of the theta function comes from the fact that the multiplication of elements of the Parker loop is based on the cocycle. We embed the set of Golay code words into the set of positive Parker loop elements, which are instances of class PLoop.

Let g1 and g2 be Golay code words of type GCode. Then PLoop(g1) and PLoop(g2) are the corresponding positive Parker loop elements, and g1.theta(g2) is an integer modulo 2 of type Parity. We have:

PLoop(g1) * PLoop(g2) == (-1)**g1.theta(g2) * PLoop(g1 + g2) .

property vector

Return bit vector corresponding to the Golay code word as an int.

We have 0 <= v < 0x1000000 for the returned number v. Bit i of the number v is the i-th coordinate of the corresponding bit vector.

class mmgroup.GcVector(value)

Models a 24-bit vector in the underlying space of the Golay code.

The $$2^{24}$$ bit vectors are numbered from 0 to 0xffffff. Bit i in that number refers to the coefficient of the i-th basis vector of the vector space, which may be $$0$$ or $$1$$.

Parameters

value (see table below for legal types) – This is the value of the bit vector to be returned.

Returns

A bit vector of 24 bit length.

Return type

an instance of class GcVector

Raise
• TypeError if type(value) is not in the table given above.

• ValueError if value cannot be converted to an instance of class GcVector.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class GcVector

type

Evaluates to

int

Here the bit vector with number value is returned. 0 <= value < 0x1000000 must hold.

list of int

A list of integers 0 <= i < 24 is interpreted as a list of bit positions to be set in a bit vector. That bit vector is returned.

class GCode

The bit vector corresponding to the Golay code word value is returned.

class PLoop

The Parker loop element value is converted to a Golay code word (by dropping its sign) and then to a bit vector. That bit vector is returned.

class GcVector

A deep copy of parameter value is returned.

str

Create random element depending on the string
'r': Create arbitrary bit vector

Standard operations

Addition of bit vectors and scalar multiplication (with scalars of type int or Parity) are done as usual. The sum of a bit vector and a Golay code word (of type GCode) is a bit vector. The sum of a bit vector and a cocode word (of type Cocode) is a cocode word of type Cocode.

The bitwise and operators &, |, and ~ operate on two bit vectors as expected. If the other operand is a Golay code vector (of type GCode) then it is converted to a bit vector.

Standard functions

len(v) returns the bit weight of the bit vector v, i.e. the number of bits set in the vector v.

property bit_list

Return the ordered list of positions of bits being set

property bits

Return the Golay code word as a 24-bit vector.

Returns a list with 24 entries equal to 0 or 1.

property cocode

Return number of the cocode word corresponding to the vector.

property gcode

Return number of Golay code word corresponding to the bit vector

Raise
• ValueError if the bit vector is not an Golay code word.

If the bit vector is an octad, return the number of that octad

Raise
• ValueError if the bit vector is not an octad.

property ord

Return the number of the bit vector.

We have 0 <= i < 0x1000000 for the returned number i.

syndrome(i=None)

Return syndrome of cocode element as a bit vector.

Parameters

iNone (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns

Syndrome of a Golay cocode element as a bit vector of type GcVector.

Raise
• ValueError if argument i is None and the syndrome is not unique.

v.syndrome(i) is equivalent to Cocode(v).syndrome(i).

syndrome_list(i=None)

Return syndrome of cocode element as list of bit positions.

Parameters

iNone (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns

Syndrome of a Golay cocode element as a list of at most four bit positions.

Raise
• ValueError if argument i is None and the syndrome is not unique.

The syndrome of the Golay cocode element is calculated in the same way as in method syndrome. But here the result is returned as an ordered list of bit positions corresponding to the bits which are set in the syndrome.

v.syndrome_list(i) is equivalent to Cocode(v).syndrome_list(i).

property vector

Return the number of the bit vector.

We have 0 <= i < 0x1000000 for the returned number i.

Same as property ord.

class mmgroup.Cocode(value)

This class models an element of the cocode of the Golay code.

The Golay code is a binary [24, 12, 8] code. So its cocode has $$2^{12}$$ elements, each of it is a $$24$$ bit long word (modulo the Golay code).

The $$2^{12}$$ Golay cocode elements are numbered from 0 to 0xfff. Bit i in that number refers to the coefficient of the i-th basis vector of the Golay cocode, which may be $$0$$ or $$1$$. The chosen basis of the cocode is the reciprocal basis of the chosen basis of the Golay code.

Parameters

value (see table below for legal types) – This is the value of the Golay cocode word to be returned.

Returns

A Golay cocode element

Return type

an instance of class Cocode

Raise
• TypeError if type(value) is not in the table given below.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class Cocode

type

Evaluates to

int

Here the cocode element with number value is returned. 0 <= value <= 0x1000 must hold.

list of int

A list of integers 0 <= i < 24 is interpreted as a list of bit positions to be set in a bit vector. The cocode word corresponding to that bit vector is returned.

class Cocode

A deep copy of parameter value is returned.

class SubOctad

The cocode part of the SubOctad value is converted to a cocode element and returned.

str

Create random element depending on the string
'r': Create arbitrary cocode element
'e': Create an even cocode element
'o': Create an odd cocode element

Standard operations

Addition of cocode elements and scalar multiplication (with scalars of type int or Parity) are done as usual.

g & c and c & g are legal operations for a Golay code element g of type GCode and a cocode element c of type Cocode. The result of this operation is not well defined as a bit vector, but it has a well-defined parity. Thus g & c returns a parity object of type Parity.

Standard functions

Let c be a cocode element of type Cocode. len(c) returns the bit weight of a shortest representative of the Golay code element c.

Special functions

The expression c % 2 is a shorthand for Parity(len(c)). It returns the parity of c as a parity object of type Parity.

property cocode

Return the number of the cocode element.

We have 0 <= i < 0x1000 for the returned number i.

Same as property ord.

property ord

Return the number of the cocode element.

We have 0 <= i < 0x1000 for the returned number i.

property parity

Return parity of the cocode element as a Parity object.

syndrome(i=None)

Return syndrome of cocode element as a bit vector.

Parameters

iNone (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns

Syndrome of a Golay cocode element as a bit vector of type GcVector.

Raise
• ValueError if argument i is None and the syndrome is not unique.

Any Golay cocode element has either a unique shortest representative of bit weight <= 3 or precisely six shortest representatives of bit weight 4 which form a partition of the underlying set of the code. Such a partition is called a tetrad.

In coding theory, a shortest representative of a cocode element is called a syndrome.

If the syndrome is unique, the function returns that syndrome. Otherwise it returns the syndrome containing bit at position i.

syndrome_list(i=None)

Return syndrome of cocode element as list of bit positions.

Parameters

iNone (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns

Syndrome of a Golay cocode element as a list of at most four bit positions.

Raise
• ValueError if argument i is None and the syndrome is not unique.

The syndrome of the Golay cocode element is calculated in the same way as in method syndrome. But here the result is returned as an ordered list of bit positions corresponding to the bits which are set in the syndrome.

class mmgroup.Parity(value)

This class models the parity of a bit vector.

As one might expect, the parity of a bit vector may be odd or even, and it is an element of the field GF(2) of two elements.

This means that arithmetic operations +, -, and * work as expected on instances of class Parity, or on instances of this class combined with integers.

The values 1**p and (-1)**p are defined as usual for an object p of class Parity. Similarly, g**p is defined if g is an element of a group defined in this package and has order 1 or 2. More precisely, g must be an instance of class AbstractGroupWord here.

Bitwise operations &, |, and ^ are illegal on instances of class Parity.

Parity(x) is defined if x an integer, an instance of class Parity, or an instance of any class defined is this package which has a natural parity, e.g. an instance of class GcVector or Cocode.

int(p) evaluates to 0 or 1 for an instance of class Parity.

Implementation remarks

If an object x has an attribute or a property parity then Parity(x) means Parity(x.parity) and x + p means Parity(x) + p for any instance p of class Parity.

If an object x has an attribute or a property parity_class then x * p and p * x mean Parity(parity_class(x) * int(p)). If that attribute or a property has value True then x * p and p * x mean Parity(x * int(P)).

property ord

Return 1 if the parity is odd and 0 if it is even

The Parker loop¶

We deal with the Parker loop, which is a non-associative Moufang loop.

The Parker loop is written multiplicatively its elements can be represented as pairs in the set $$\mathcal{P} = \mathcal{C} \times \mathbb{F}_2$$, see e.g. [Asc86], [Con85]. We also write 1 for the neutral element $$(0,0) \in \mathcal{C} \times \mathbb{F}_2 = \mathcal{P}$$ of the Parker loop and -1 for its negative $$(0,1)$$. Let $$\Omega$$ = $$(0,\tilde{\Omega})$$, where $$\tilde{\Omega}$$ is the Golay code word 1,...,1. Then the center $$Z(\mathcal{P})$$ of $$\mathcal{P}$$ is $$\{1, -1, \Omega, -\Omega\}$$. An element $$(g,s)$$, $$g \in \mathcal{C}$$ is called positive if $$s = 0$$ and negative if $$s = 1$$.

Multiplication of two Parker loop elements $$(g_1,s_1), (g_2,s_2)$$ is given by a cocycle $$\theta: \mathcal{C} \times \mathcal{C} \rightarrow \mathbb{F}_2$$ as follows:

$$(g_1,s_1) \cdot (g_2,s_2) = (g_1 + g_2, s_1 + s_2 + \theta(g_1, g_2))$$.

There are several possibilities for the cocycle $$\theta$$. We choose a cocycle $$\theta$$ satisfying the requirements given by [Sey20], see The basis of the Golay code and of its cocode for details.

We represent elements of $$\mathcal{P}$$ as instances of class PLoop. For Golay code word g given as an instance of class GCode, the value PLoop(g) is the positive element (g,0) of the Parker loop, and -PLoop(g) is the corresponsing negative element (g,1). The constant PLoopOne is equal to the neutral element (0,0) and the constant PLoopOmega is equal to the central element ~PLoopOne. Here the ~ means bitwise complement of the corresponding Golay code element without changing the sign of a Parker loop element. Thus PLoopOmega is the positive Parker loop element corresponding to the Golay code word containing 24 one bits. So the center $$Z(\mathcal{P})$$ of $$\mathcal{P}$$ is:

[PLoopOne, -PLoopOne, PLoopOmega, -PLoopOmega] .

Let g1, g2 be instances of class GCode. For positive elements of the Parker loop the multiplication formula given above can be coded as follows:

PLoop(g1) * PLoop(g2) == (-1)**g1.theta(g2) * PLoop(g1 + g2) .

The elements of the Parker loop are numbered from 0 to 0x1fff. Here the numbers of the posivtive Parker loop elements correspond to the numbers of the Golay code words. The numbering system for the Parker loop is also used for indexing certain elements of the monster group $$\mathbb{M}$$.

A transversal of $$Z(\mathcal{P})$$ in $$\mathcal{P}$$ is used for indexing certain basis vectors of the representation $$\rho$$ of $$\mathbb{M}$$. Property ord of an instance a of class PLoop returns the number of that element of the Parker loop. For indexing vectors in $$\rho$$ it is important to know that (-a).ord =  a.ord ^ 0x1000 and (~a).ord = a.ord ^ 0x800. Thus the Parker loop elements a with 0 <= a.ord < 0x800 are a transversal of $$Z(\mathcal{P})$$ in $$\mathcal{P}$$.

class mmgroup.PLoop(value=0)

This class models an element of the Parker Loop.

The Parker loop is a non-associative loop with $$2^{1+12}$$ elements. Each element can be interpreted as a signed Golay code word, see class GCode. Accordingly, class PLoop is a subclass of class GCode.

The loop operation is written multiplicatively. The neutral element of the loop (corresponding to the positive zero word of the Golay code) is PLoopOne, and its negative is -PLoopOne. PLoopOmega is the (positive) element corresponding to the all-one vector of the Golay code.

The $$2^{1+12}$$ Parker loop elements are numbered from 0 to 0x1fff. Elements 0 to 0xfff are are positive and corresponding to the Golay code words with the same number. The element with number 0x1000 ^ i is the negative of the element with number i.

Parameters

value (see table below for legal types) – This is the value of the Parker loop element to be returned.

Returns

A Parker loop element

Return type

an instance of class PLoop

Raise
• TypeError if type(value) is not in the table given above.

• ValueError if value cannot be converted to an instance of class PLoop.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class PLoop

type

Evaluates to

int

Here the code word with number value is returned. 0 <= value < 0x2000 must hold. We have PLoop(0) == PLoopOne, PLoop(0x1000) == -PLoopOne, and PLoop(0x800) == ~PLoopOne == PLoopOmega.

list of int

Such a list is converted to a Golay code word, see class GCode, and the corresponding (positive) Parker loop element is returned.

class GCode

The corresponding (positive) Parker loop element is returned.

class PLoop

A deep copy of parameter value is returned.

class GcVector

This is converted to a Golay code word, see class GCode, and the corresponding (positive) Parker loop element is returned.

class SubOctad

The octad part of the SubOctad value is returned.

str

Create random element depending on the string
'r': Create arbitrary Parker loop element

Standard operations

Let a be a Parker loop element. The multiplication operator * implements the non-associative loop operation. Division by a Parker loop element means multiplication by its inverse, and exponentiation means repeated multiplication, with a**(-1) the loop inverse of a, as usual.

The ~ operator maps the Parker loop element a to a * PLoopOmega, leaving the sign of a unchanged.

Multiplication with the integer 1 or -1 means the multiplication with the neutral element PLoopOne or with its negative -PLoopOne, respectively.

If any of the oprations +, - or & is applied to a Parker loop element, that element is converted to a Golay code word of type GCode, ignoring the sign. This conversion also takes place if a Parker loop element is multiplied or divided by an integer different from 1 or -1.

Standard functions

len(a) is a shorthand for len(GCode(a)). Here function GCode(a) converts a to a Golay code word of type GCode.

abs(a) returns the element in the set {a, -a} which is positive.

property ord

Return the number of the Parker loop element.

We have 0 <= i < 0x2000 for the returned number i.

parity_class
property sign

Return the sign of the Parker loop element.

This is 1 for a positive and -1 for a negative element.

split()

Split sign and Omega from Parker loop element a.

Returns

a triple (es, eo, v) with a = (-1)**e1 * PLoopOmega**eo * v .

Here v is the unique (positive) element of the Parker loop of type PLoop with 0 <= v.ord < 0x800 satisfying that equation. es and eo are 0 or 1.

Split Parker loop element a into central element and octad

Returns

a triple (es, eo, o) with a = (-1)**e1 * PLoopOmega**eo * o.

Here o is either the neutral Parker loop element PLoopOne or Parker loop element corresponding to a positive octad. es and eo are 0 or 1. An octad is a Golay code word (of type GCode) of weight 8.

Raise
• Raise ValueError if this is not possible.

mmgroup.PLoopZ(e1=0, eo=0)

Return a specific central element of the Parker loop.

Parameters
• e1 (int) – Sign, the sign of the element will be (-1)**e1

• eo (int) – Exponent for PLoopOmega, default is 0

Returns

The central element (-1)**e1  * PLoopOmega**eo of the Parker loop.

Return type

an instance of class PLoop.

Here PLoopOmega is the positive element of the Parker loop corresponding to the Golay code word 1,...,1.

e1 and eo may also be parity objects of type Parity.

An octad is a Golay code word of weight 8. The Golay code has 759 octads. A signed octad is a Parker loop element corresponding to an octad or a complement of an octad. Signed octads are used for indexing some unit vectors of the representation $$\rho$$ of the monster $$\mathbb{M}$$.

Function Octad() returns a signed octad as an instance of class PLoop. Arguments of function Octad() are interpreted in the same way as arguments of the constructor for class PLoop, but the function raises ValueError if the result is not a (possibly complemented) signed octad.

We use some lexical order for numbering the 759 octads, which we do not describe in detail. Due to the well-known properties of the Golay code we can create a random octad and display its number as follows:

from random import sample
# Select 5 random integers between 0 and 23
int_list = sample(range(24), 5)
# Complete these 5 integers to a (unique) octad o
# Display octad o and its number


A suboctad of an octad o is an element of the Golay cocode $$\mathcal{C}^*$$ of even parity which can be represented as a subset of o. Each octad has 64 suboctads. A pair (octad, suboctad) is used for indexing some basis vectors in the representation $$\rho$$. Class SubOctad models such a pair. The constructor of class SubOctad takes two arguments octad and suboctad. The first argument evaluates to a signed octad as in function Octad(). The second argument evaluates to a suboctad, see class SubOctad for details.

The raison d’etre of a suboctad is indexing a basis vector in the representation $$\rho$$. For this purpose we need a pair of integers refering to the octad and the suboctad. For an instance so of class SubOctad that pair is given by (so.octad, so.suboctad).

For an octad o and a suboctad s precisely one of the pairs (o,s) and (~o,s) is actually used as an index for $$\rho$$. The pair (~o,s) is used if the cocode element corresponding to s has minimum weight 2; the pair (o,s) is used if that element has minimum weight 0 or 4. See [Con85] or [Sey20] for background. In this implementation both, (o,s) and (~o,s), refer to the same basis vector of $$\rho$$.

Return a (signed) octad as an element of the Parker loop.

Parameters

octad (see table below for legal types) – the value of the octad to be returned.

Returns

Return type

an instance of class PLoop

Raise
• TypeError if type(octad) is not in the table given above.

• ValueError if octad cannot be converted to a (possibly negated and complemented) octad.

Depending on its type parameter octad is interpreted as follows:

Legal types for parameter octad

type

Evaluates to

int

Here the (positive) octad with number octad is returned. There are 759 octads in the Golay code. So 0 <= octad < 759 must hold.

list of int

Such a list is converted to a Golay code word, see class GCode, and the corresponding (positive) Parker loop element is returned.

class GCode

The corresponding (positive) Parker loop element is returned.

class PLoop

A deep copy of parameter octad is returned.

class GcVector

This is converted to a Golay code word, see class GCode, and the corresponding (positive) Parker loop element is returned.

class SubOctad

The octad part of the SubOctad octad is returned.

class XLeech2

The octad part of the vector octad is returned.

str

Create random element depending on the string
'r': Create arbitrary octad

A complement of an octad is also accepted; then the corresponding Parker loop element is retured. The function raises ValueError if parameter octad does not evaluate to an octad or a complement of an octad.

Parameters
• octad (same as in function Octad) – The first component of the pair (octad, suboctad) to be created.

• suboctad (see table below for legal types) – The second component of the pair (octad, suboctad) to be created.

Returns

Return type

an instance of class SubOctad

Raise
• TypeError if argument octad or suboctad is not of correct type.

A suboctad is an even cocode element that can be represented as a subset of the octad given by the argument octad.

The raison d’etre of class SubOctad is that pairs (octad, suboctad) are used for indexing vectors in the representation of the monster group. Here we want to number the octads from 0 to 758 and the suboctads form 0 to 63, depending on the octad. Note that every octad has 64 suboctads.

Depending on its type parameter suboctad is interpreted as follows:

Legal types for parameter suboctad

type

Evaluates to

int

Here the suboctad with the number given in the argument is taken. That numbering depends on the octad given in the argument octad. 0 <= suboctad < 64 must hold.

list of int

Such a list is converted to a bit vector as in class GcVector, and the cocode element corresponding to that bit vector is taken.

class GCode

The intersection of the octad given as the first argument and the Golay code word given as the second argument is taken.

class GcVector

This is converted to a cocode element, see class Cocode, and that cocode element is taken.

class Cocode

That cocode element is taken as the suboctad.

class SubOctad

The suboctad part of the SubOctad value is taken.

str

Create random element depending on the string
'r': Create arbitrary suboctad

Remark

For an object so of type SubOctad use Octad(so) to obtain its octad as a Parker loop element and Cocode(so) obtain its suboctad as a cocode element. You may obtain more information from the properties of the object so.

If parameter octad is of type SubOctad or XLeech2 the this parameter already describes a pair (octad, suboctad).

as_tuple()

Return data as a tuple

The function returns a tuple (sign, 'T', octad, suboctad) where sign, octad, and suboctad are the integers given by the corresponding properties in class SubOctad.

Such a tuple is used for indexing vectors in the representation of the monster group.

property cocode

Return number of cocode word corresponding to the suboctad.

We have 0 <= c < 0x1000 for the returned number c.

property gcode

Return number of Golay code word corresponding to the octad.

We have 0 <= g < 0x1000 for the returned number g.

We have 0 <= o < 759 for the returned number o.

property sign

Return the sign of the octad.

This is 1 for a positive and -1 for a negative octad.

Return the number of the suboctad.

We have 0 <= s < 64 for the returned number s.

Let [b0, b1,..., b7] be the bits set in the octad of an instance of this class in natural order. The following table shows the suboctad numbers for some suboctads given as cocode elements. More suboctad numbers can be obtained by combining suboctads and their corresponding numbers with XOR.

 [b0,b1] [b0,b2] [b0,b3] [b0,b4] [b0,b5] [b0,b6] s  = 1 s  = 2 s  = 4 s  = 8 s = 16 s = 32

E.g. [b0, b5, b6, b7] is equivalent to [b1, b2, b3, b4] modulo the Golay code and has number s = 1 ^ 2 ^ 4 ^ 8 = 15.

Automorphisms of the Parker loop¶

We deal with a certain group of automorphisms of the Parker loop.

A standard automorphism is an automorphism of the Parker loop $$\mathcal{P}$$ which maps to an automorphism of the Golay code $$\mathcal{C}$$ when factoring out the elements $$\{1,-1\}$$ of $$\mathcal{P}$$. Let $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ be the group of standard automorphisms of $$\mathcal{P}$$. We embed $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ into $${\mathbb{M}}$$ as in [Con85]. In ATLAS notation, see [CCN+85], that group has structure

${{\rm Aut}_{{\rm St}} \mathcal{P}} = 2^{12} . M_{24}\, .$

This means that $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ has an elementary Abelian normal subgroup of order $$2^{12}$$ with factor group $$M_{24}$$. That group extension does not split. Here the group $$2^{12}$$ is isomorphic to the Golay cocode $$\mathcal{C}^*$$ and $$M_{24}$$ is the Mathieu group acting on $$\mathbb{F}_2^{24}$$ by permuting the basis vectors. $$M_{24}$$ is the automorphism group of the Golay code $$\mathcal{C}$$ .

The automorphisms in the subgroup $$\mathcal{C}^*$$ of $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ are called diagonal automorphisms. A diagonal automorphism $$d \in \mathcal{C}^*$$ maps an element $$a$$ of $$\mathcal{P}$$ to $$(-1)^s \cdot a$$ with $$s = |a \, \& \, d|$$. Here $$\&$$ means the bitwise and operation of bit vectors and $$|.|$$ means the bit weight of a bit vector.

Since the extension $$2^{12} . M_{24}$$ does not split, there is no canonical embedding of $$M_{24}$$ into $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$. For practical purposes we need such an embedding. We choose a basis $$b_1,\ldots,b_{11}$$ of the Golay code $$\mathcal{C}$$, see section The basis of the Golay code and of its cocode. Let $$a_i$$ be the positive element of the Parker loop $$\mathcal{P}$$ corresponding to $$b_i$$. For any $$\tilde{g} \in M_{24}$$ we let $$g$$ be the unique element of $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ with $$g \mathcal{C}^* = \tilde{g}$$ that maps all elements $$a_1,\ldots,a_{11}$$ of $$\mathcal{P}$$ to positive elements of $$\mathcal{P}$$. We call $$g$$ the standard representative of $$\tilde{g}$$ in $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$.

Elements of $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ are modelled as instances of class AutPL. If d is an instance of class Cocode representing an element of $$\mathcal{C}^*$$ then AutPL(d) is the corresponding diagonal automorphism.

A permutation $$p \in M_{24}$$ can be represented as a list l_p = [p(0),...,p(23)]. If l_p is such a list then AutPL(l_p) is the standard representative of p in $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$. Here an error occurs if the mapping from i to p(i) is not in $$M_{24}$$. A permutation in $$M_{24}$$ can also be given as a mapping from a subset of $$\{0,\ldots,23\}$$ to $$\{0,\ldots,23\}$$, provided that this mapping extends to a unique element of $$M_{24}$$. For details, see class AutPL.

The group $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ operates naturally on $$\mathcal{P}$$ by right multiplication. It also operates on $$\mathbb{F}_2^{24}$$, $$\mathcal{C}$$, and $$\mathcal{C}^*$$ by right multiplication. Here the basis vectors of $$\mathbb{F}_2^{24}$$ are permuted by $$M_{24}$$; so the kernel of that operation is the subgroup $$\mathcal{C}^*$$ of $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$.

We order the elements $$p$$ of $$M_{24}$$ in lexicographic order based on the lists l_p = [p(0),...,p(23)]. We number the 244823040 elements of $$M_{24}$$ in that order from 0 to 244823039. Thus the number 0 is assigned to the neutral element of $$M_{24}$$, and the number 244823039 is assigned to the permutation p with l_p =

$$\small [ 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 0, 1, 2, 3, 4, 5, 6, 7 ]$$

These numbers are used for addressing the corresponding standard representatives in the subgroup $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ of the monster $$\mathbb{M}$$.

The easiest way to create an element of $$M_{24}$$ is to map an umbral heptad to another umbral heptad. Here an umbral heptad is a set of 7 elements of $$\{0,\ldots,23\}$$ such that precisely 6 of these elements are contained in an octad, see [CS99], Chapter 10. Then the 6 elements in one octad must map to the 6 elements in the other octad.

The set [0,1,2,3,4,5,8] is an umbral heptad with 8 not contained in the octad. We may create the standard representative (in $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$) of a random element of $$M_{24}$$ as follows:

from random import sample
# Select 6 random elements from that octad
# Select one random element not in that octad
extra = sample((~o).bit_list, 1)
# Create umbral heptad from these random elements
# Create a mapping from [0,1,2,3,4,5,8] to that heptad
# Create a permutation in the Mathieu group from that mapping
aut = AutPL(0, hmap)
# 'aut' is the standard representative of the permutation
# Show 'aut' as a permutation in form of a list
print(aut.perm)
# Show the automorphism 'aut' with its permutation number
print(aut)


Remark

Class AutPL is a subclass of class mmgroup.structures.AbstractGroupWord which implements elements of an abstract group and the operations on such elements. For an instance g of AutPL, the object g.group is an instance of a subclass of mmgroup.structures.AbstractGroup. That subclass models the group $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$.

class mmgroup.AutPL(d=0, p=0, unique=1)

This class models a standard automorphism of the Parker loop.

Parameters
• d – This parameter describes an element of the Golay cocode. If d is an instance of class AutPL then this describes an automporphism of the Parker loop; in that case parameter p must be set to its default value. Legal types of parameter d see below. The parameter defaults to zero word of the cocode.

• p – This parameter describes a permutation in the Mathieu group M_24 or, more precisely, the standard representative of that permutation in the automporphism group of the Parker loop. Legal types of that parameter see below. The parameter defaults to neutral element of Mat24.

• unique – If this is True (default) and parameter p is not r then parameter p must describe a unique permutation in the Mathieu group M_24. Otherwise we take the least possible permutation (in lexicographic order) that agrees with parameter p.

Returns

A standard Parker loop automorphism

Return type

an instance of class AutPL

Raise
• TypeError if type(value) is not in the table given below.

• ValueError if the set of arguments cannot be converted to an instance of class AutPL.

Legal types for parameter d in constructor of class AutPL

type

Evaluates to

int

The number of an element of the Golay cocode.

class Cocode

This represents an element of the Golay cocode.

str

Create random element depending on str
'r': Create an arbitrary cocode element
'e': Create an even cocode element
'o': Create an odd cocode element

Any other string is illegal.

class AutPL

A deep copy of the given automorphism in AutPL is returned. Then parmeter p must be set to its default value.

Legal types for parameter p in constructor of class AutPL

type

Evaluates to

int

Here the integer is the number of a permutation in the Mathieu group M_24.

list of int

A list l_p of 24 of disjoint integers 0 <= i < 24 is interpreted as a permutation in M_24 that maps i to l_p[i].

dict

A dictionary specifies a mapping from a subset of the integers 0 <= i < 24 to integers 0 <= dict[i] < 24. This mapping must extend to a permutation in M_24. If parameter unique is True (default) then that permutation must be unique.

zip object

zip(x,y) is equivalent to dict(zip(x,y)).

str

Create random element depending on str
'r': Create an random element of M_24

Any other string is illegal.

Let a be an instance of class GcVector, GCode, Cocode, or PLoop, and let g1 , g2 be instances of class AutPL. Then a * g1 is the result of the natural operation of g1 on a, which belongs to the same class as a.

g1 * g2 means group multiplication, and g1 ** n means exponentiation of g1 with the integer n. g1 ** (-1) is the inverse of g. g1 / g2 means g1 * g2 ** (-1).

g1 ** g2 means g2**(-1) * g1 * g2.

as_tuples()

Convert group element to a list of tuples

For a group element g the following should hold:

g.group.word(*g.as_tuples()) == g .

So passing the tuples in the list returned by this method as arguments to g.group or to g.group.word reconstructs the element g.

This shows how to convert a group element to a list of tuples and vice versa.

check()

Check automorphism for consistency via ‘assert’ statements

a.check() returns a.

property cocode

Return number of cocode element in the automorphism.

For an instance g of AutPL we have

g == AutPL(Cocode(g.cocode)) * AutPL(g.perm).

property parity

Return parity of an automorphism

This is s if PLoopOmega maps to (-1)**s * PLoopOmega for s == 0 or s == 1.

property perm

Return permutation of automorphism as a list p_l.

Then the permutation maps i to p_l[i] for i = 0,...,23.

property perm_num

Return the number of the permutation of the automorphism

The Mathieu group M_24 has 244823040 elements numbered from 0 to 244823039 in lexicographic order. Thus the neutral element has number 0.

The Leech lattice modulo 2 and its preimage $$Q_{x0}$$¶

We deal with an extraspecial group that maps to the Leech lattice modulo 2

Let $$Q_{x0}$$ be the group generated by elements $$x_d, x_\delta$$ with $$d \in \mathcal{P}, \delta \in \mathcal{C}^*$$. Here $$\mathcal{P}$$ is the Parker loop and $$\mathcal{C}^*$$ is the Golay cocode as in [Con85]. We take the following relations in $$Q_x$$ from [Sey20]:

$x_d x_e = x_{d \cdot e} x_{A(d,e)}, \, x_\delta x_\epsilon = x_{\delta \epsilon}, \, [x_d x_\delta] = x_{-1}^{\langle d, \delta \rangle}; \; d, e \in \mathcal{P}; \; \delta , \epsilon \in \mathcal{C}^* \, .$

Here $$A(d,e)$$ is the associator between $$d$$ and $$e$$, i.e. the element of $$\mathcal{C}^*$$ corresponding to the vector $$d \cap e$$; and $$[.,.]$$ is the commutator in $$Q_{x0}$$. Then $$Q_{x0}$$ is an extraspecal group of structure $$2_+^{1+24}$$.

An element of the group $$Q_x$$ is modelled as an instance of class XLeech2.

In that class we encode the element $$x_d \cdot x_\delta$$ of $$Q_{x0}$$ as an integer $$x$$ as follows:

$x = 2^{12} \cdot d \oplus (\delta \oplus \theta(d)) \, .$

Here elements of the Parker loop and elements of the cocode are encoded as integers as in section The Parker loop and The Golay code and its cocode. $$\theta$$ is the cocycle given in section The basis of the Golay code and of its cocode, and ‘$$\oplus$$’ means bitwise addition modulo 2. Note that a Parker loop element is 13 bits long (with the most significant bit denoting the sign) and that a cocode element is 12 bits long.

There is a natural homomorphism from $$Q_{x0}$$ to the Leech lattice $$\Lambda$$ modulo 2 with kernel $$\{x_1, x_{-1}\}$$, as described in [Con85]. This homomorphism maps the group operation in $$Q_{x0}$$ to vector addition in $$\Lambda / 2\Lambda$$. With our numbering in $$Q_{x0}$$ that homomorphism can be realized by simply dropping the sign bit 25; then vector addition in $$\Lambda / 2\Lambda$$ corresponds to the $$\oplus$$ operation on such numbers. The natural quadratic form on the vector in $$\Lambda / 2\Lambda$$ with the number $$2^{12} \cdot d + \delta$$, $$0 \leq d, \delta < 2^{12}$$ is the parity of the bit vector $$d \oplus \delta$$.

class mmgroup.XLeech2(ploop=0, cocode=0, *args)

This class models an element of the group $$Q_{x0}$$.

The group $$Q_{x0}$$ is an extraspecial 2 group of structure $$2^{1+24}$$.

The group operation is written multiplicatively.

The $$2^{1+24}$$ group elements are numbered from 0 to 0x1ffffff. Elements 0 to 0xffffff are considered positive. The element with number 0x1000000 ^ i is the negative of the element with number i.

An element is constructed as a product $$x_d x_\delta$$, where $$d$$ is in the Parker loop and $$\delta$$ is in the Golay cocode.

Parameters
• value – This parameter describes the value of an element of the group $$Q_{x0}$$ as indicated in the table below.

• cocode – This parameter describes an element $$x_\delta$$ (with $$\delta$$ in the Golay cocode) to be right multiplied to the element of $$Q_{x0}$$ obtained from the first parameter.

Returns

An element of the group $$Q_{x0}$$.

Return type

an instance of class XLeech2

Raise
• ValueError if the input cannot converted to an element of the group $$Q_{x0}$$.

• TypeError the ype of an input is illegal.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class XLeech2

type of value

Evaluates to

int

Here the code word with number value is returned. 0 <= value < 0x2000000 must hold.

class XLeech2

A deep copy of the object value is created.

class GCode

The corresponding Golay code element is converted to a (positive) element of $$Q_{x0}$$.

class PLoop

The corresponding Parker loop element is converted to an element of $$Q_{x0}$$.

class SubOctad

The SubOctad is converted to an element of $$Q_{x0}$$.

class MM

Then value in an element of the monster group. If that element is in the subgroup $$Q_{x0}$$ of the monster, then it is converted to the coresponding instance of Create random element depending on the string class XLeech2.

str

see explanation below.

If value is of one of the type listed above then the following parameter is coneted to an element of the Golay cocode (as in the constructor of class Cocode multiplied to the converted parmeter value from the right.

Alternatively, parameter value may be a single letter. If value is one of the capital letters BCTXE then that letter and the following arguments are passed to the constructor of class MMVector in order to generate a (possible negated) basis vector of the representation $$\rho_p$$ of the monster. (Here the characteristic $$p$$ is ignored.) If that basis vector corresponds to an element of $$Q_{x0}$$ then we construct that element of $$Q_{x0}$$; otherwise an error occurs.

If parameter value is the letter 'r' then we generate a random element of $$Q_{x0}$$. If an integer i is given as a second parameter 'r' then we generate a random element of $$Q_{x0}$$ of type i. Here the type of a vector $$v \in \Lambda / 2 \Lambda$$ is the halved norm of the shortest vector in the set $$v + 2 \Lambda$$. If i is specified then it must be equal to 0, 2, 3 or 4.

Standard operations

Let q be an instance of this class. The multiplication operator * implements the group operation. Division by an element means multiplication by its inverse, and exponentiation means repeated multiplication, with q**(-1) the inverse of q, as usual.

Multiplication with the integer 1 or -1 means the multiplication with the neutral element or with the central involution $$x_{-1}$$.

The opration & denotes the scalar product of the vectors in the Leech lattice modulo 2 obtained from an instance of this class, ignoring the sign.

Standard functions

abs(a) returns the element in the set {a, -a} which is positive.

Caution

Although the group $$Q_{x0}$$ has a natural embedding into the subgroup $$G_{x0}$$ of the monster group, we do not consider an instance $$q$$ of class XLeech2 as an element of $$G_{x0}$$. We consider $$q$$ as a (possibly negated) basis vector of a space on which $$G_{x0}$$ acts monomially by right multiplication.

If an instance $$q$$ of class XLeech2 maps to a vector of type 2 in the Leech lattice modulo 2 then $$q$$ is also a unit vector in the 196884-dimensional representation $$\rho$$ of the monster group.

One may use $$q$$ in the constructor of class MM (representing the monster group) for creating the corresponding element of the subgroup $$Q_{x0}$$ of the monster group.

property mmdata

Return internal representation of corresponding monster element.

That internal representation is returned as a numpy array of 32-bit integers.

property ord

Return the number of the element of $$Q_{x0}$$ .

We have 0 <= i < 0x2000000 for the returned number i.

property sign

Return the sign of the element $$Q_{x0}$$.

This is 1 for a positive and -1 for a negative element.

split()

Split element into a product $$x_d \cdot x_\delta$$

The method returns a pair $$(d, \delta)$$ such that $$x_d \cdot x_\delta$$ is equal to the given element of $$Q_{x0}$$.

The element $$d$$ of the Parker loop is an instance of class PLoop. The element $$\delta$$ of the Golay cocode is an instance of class Cocode.

str()

Represent group element as a string

property subtype

Return pair (type, subtype) of the element of $$Q_{x0}$$

Here type is as in property type, and subtype is a one-digit decimal integer describing the subtype of a vector in the Leech lattice modulo 2, as explained in the guide in section Computations in the Leech lattice modulo 2.

property type

Return the type of the element of $$Q_{x0}$$.

This is equal to the type of the corresponding vector $$v$$ in the Leech lattice $$\Lambda$$ modulo 2. The type of a vector $$v \in \Lambda / 2 \Lambda$$ is the halved norm of the shortest vector in the set $$v + 2 \Lambda$$. That type is equal to 0, 2, 3 or 4.

property xsubtype

Return subtype of the element of $$Q_{x0}$$

The function returns the integer 16 * type + subtype, where the pair (type, subtype) is as in property subtype. See section Computations in the Leech lattice modulo 2 in the guide for background.

The basis of the Golay code and of its cocode¶

We chose a basis b_0,…, b_11 of the Golay code $$\mathcal{C}$$ such that the resulting Golay code is compatible to [CS99], Chapter 11.

As usual in the Python or C language we number the indices of the basis vectors of the space $$\mathbb{F}_2^{24}$$ from 0 to 23. Similarly, we number the basis vectors of the Golay code from 0 to 11.

In [CS99] the Golay code is described in terms of the MOG (Miracle Octad Generator), which can be considered as a $$4 \times 6$$ matrix for arranging the basis vectors of $$\mathbb{F}_2^{24}$$. Our numbering of these basis vectors corresponds to the MOG as follows:

 0 4 8 12 16 20 1 5 9 13 17 21 2 6 10 14 18 22 3 7 11 15 19 23

For the cocode $$\mathcal{C}^*$$ we use the reciprocal basis c_0,…, c_11 of the basis b_0,…, b_11 of $$\mathcal{C}$$. Then the scalar product b_i & c_j of b_i and c_j is equal to 1 if i == j and to 0 otherwise.

The basis vectors b_0,…, b_11 of the Golay code are given in the following table. The table also shows the cocyles of the basis vectors as explained below:

       Basis vectors of the Golay code             Cocycle theta
binary: bit 0,...,23            hex         bit 0,...,11
b_0:  0000 1111 0000 1111 1111 1111,  0xfff0f0;   0111 0000 0000
b_1:  0000 1111 1111 0000 1111 1111,  0xff0ff0;   1011 0000 0000
b_2:  0000 1111 1111 1111 0000 1111,  0xf0fff0;   1101 0000 0000
b_3:  0000 1111 1111 1111 1111 0000,  0x0ffff0;   1110 0000 0000
b_4:  0000 0000 0011 0011 0011 0011,  0xcccc00;   1111 0000 0000
b_5:  0000 0000 0101 0101 0101 0101,  0xaaaa00;   1111 0000 0000
b_6:  0000 0011 0000 0011 0101 0110,  0x6ac0c0;   0111 0000 0000
b_7:  0000 0101 0000 0101 0110 0011,  0xc6a0a0;   0111 0000 0000
b_8:  0011 0000 0000 0011 0110 0101,  0xa6c00c;   1000 0000 0010
b_9:  0101 0000 0000 0101 0011 0110,  0x6ca00a;   1000 0000 0010
b_10:  0111 1000 1000 1000 1000 1000,  0x11111e;   0000 0000 0000
b_11:  1111 1111 1111 1111 1111 1111,  0xffffff;   0000 0000 0000


Representatives of the basis vectors c_0,…, c_11 of the Golay cocode are given in the following table:

       Basis vectors of the cocode
binary: bit 0,...,23            hex
c_0:  0000 1000 1000 0000 0000 0000,  0x000110
c_1:  0000 1000 0000 1000 0000 0000,  0x001010
c_2:  0000 1000 0000 0000 1000 0000,  0x010010
c_3:  0000 1000 0000 0000 0000 1000,  0x100010
c_4:  0000 0000 0101 0000 0000 0000,  0x000a00
c_5:  0000 0000 0011 0000 0000 0000,  0x000c00
c_6:  0000 0101 0000 0000 0000 0000,  0x0000a0
c_7:  0000 0011 0000 0000 0000 0000,  0x0000c0
c_8:  0101 0000 0000 0000 0000 0000,  0x00000a
c_9:  0011 0000 0000 0000 0000 0000,  0x00000c
c_10:  1000 1000 1000 1000 1000 1000,  0x111111
c_11:  1000 0000 0000 0000 0000 0000,  0x000001


The cocycle $$\theta: \mathcal{C} \times \mathcal{C} \rightarrow \mathbb{F}_2$$ is used for the multiplication of two elements of the Parker loop, see section The Parker loop. For basis vectors $$b_i$$, $$b_j$$ of $$\mathcal{C}$$ the column theta in the table above contains the value $$\theta(b_i, b_j)$$ in bit $$j$$ of row $$i$$. From these values other values of the cocycle $$\theta$$ can be computed by using

$\begin{split}\theta(g_1 + g_2, g_3) = \theta(g_1, g_3) + \theta(g_2, g_3) + |g_1 \& g_2 \& g_3|, \\ \theta(g_1, g_2 + g_3) = \theta(g_1, g_2) + \theta(g_1, g_3), \quad g_1, g_2, g_3 \in \mathcal{C} \; .\end{split}$

Here $$\&$$ means the bitwise and operation of bit vectors and $$|.|$$ means the bit weight of a bit vector.

The cocycle $$\theta$$ has been chosen in accordance with the requirements in [Sey20]. In that context the grey subspace of $$\mathcal{C}$$ is spanned by $$b_0,\ldots,b_3,b_{10}, b_{11}$$ and the coloured subspace of $$\mathcal{C}$$ is spanned by $$b_4,\ldots,b_9$$. Similarly, the grey subspace of $$\mathcal{C}^*$$ is spanned by $$c_0,\ldots,c_3,c_{10}, c_{11}$$ and the coloured subspace of $$\mathcal{C}^*$$ is spanned by $$c_4,\ldots,c_9$$.

These specific properties of our chosen basis and cocycle are vital for obtaining an effective implementation of a complete generating set of the monster $$\mathbb{M}$$.

The monster group¶

We deal with the representation of elements of the monster group.

Generators of the monster group $$\mathbb{M}$$¶

Conway [Con85] has constructed a 196884-dimensional rational representation $$\rho$$ of the monster $$\mathbb{M}$$ based on representations of two subgroups $$G_{x0} = 2_+^{1+24}.\mbox{Co}_1$$ and $$N_0 = 2^{2+11+22}.( M_{24} \times S_3)$$ of $$\mathbb{M}$$ which generate $$\mathbb{M}$$. Here $$G_{x0}$$ has a normal extraspecial 2-subgroup $$2_+^{1+24}$$ with factor group $$\mbox{Co}_1$$, where $$\mbox{Co}_1$$ is the automorphism group of the Leech lattice modulo 2. The group $$N_0$$ has a normal subgroup $$2^{2+11+22}$$, which is a certain 2 group and the factor group is a direct product of the Mathieu group $$M_{24}$$ and the symmetric permutation group $$S_3$$ of 3 elements.

The group $$N_{x0} = N_0 \cap G_{x0}$$ has index 3 in $$N_{0}$$ and structure $$2^{1+24} . 2^{11} . M_{24}$$. It is generated by elements $$x_\delta$$, $$x_\pi$$, $$x_e$$, $$y_e$$, $$z_e$$, for all $$x_\delta \in \mathcal{C}^*$$, $$\pi \in {{\rm Aut}_{{\rm St}} \mathcal{P}}$$ and $$e \in \mathcal{P}$$.

Here $$\mathcal{C}^*$$ is the Golay cocode defined in section The Golay code and its cocode, $$\mathcal{P}$$ is the Parker loop defined in section The Parker loop, and $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ is the automorphism group of $$\mathcal{P}$$ defined in section Automorphisms of the Parker loop. The group $$N_{0}$$ has a subgroup isomorphic to $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$ generated by the generators $$x_\delta, \delta \in \mathcal{C}^*$$ and $$x_\pi, \pi \in {{\rm Aut}_{{\rm St}} \mathcal{P}}$$. The generators $$x_\delta$$ generate the subgroup of diagonal automorphisms of $${{\rm Aut}_{{\rm St}} \mathcal{P}}$$.

The group $$N_{0}$$ is generated by $$N_{x0}$$ and by another element $$\tau$$ of $$N_{0}$$ or order 3. The group $$G_{x0}$$ is generated by $$N_{x0}$$ and by another element $$\xi$$ of $$G_{x0}$$ or order 3. The elements $$x_\delta$$, $$x_\pi$$, $$x_e$$, $$y_e$$, $$z_e$$, $$\tau$$ and $$\xi$$ generate the monster group $$\mathbb{M}$$. In this package we use the definitions of the generators in [Sey20], which incorporate a modification of [Con85] made in [Iva09]. This leads to simpler relations in $$N_{0}$$. The generators $$x_e$$, $$y_e$$, and $$z_e$$ in [Sey20] correspond to the generators $$x_e \cdot z_{-1}^{|e/4|}$$, $$y_e \cdot x_{-1}^{|e/4|}$$, and $$z_e \cdot y_{-1}^{|e/4|}$$ in [Con85].

Representing elements of the monster group¶

An element of the monster group $$\mathbb{M}$$ is represented as an instance of class MM in module mmgroup.

Elements of the monster group are created by the constructor of class MM. Usually, the constructor of class MM takes two arguments tag and i, where tag is a single small letter describing the type of the generator of $$\mathbb{M}$$, and i is an integer describing the value of that generator. Alternatively, i may be an instance of the appropriate algebraic structure used for indexing a generator of a given type as indicated in the table below.

Implementation of the generators of the monster group¶

Math papers may use (at least) Latin or Greek letters for labelling objects, but most programming languages are restricted to ASCII characters. The following table shows how to create generating of the monster group using the constructor of class MM:

Construction of generating elements of the monster

Element

Construction as an instance of class MM,

$$x_\delta$$

MM('d', delta), delta an instance of class Cocode;

MM('d', delta) returns MM('d', Cocode(delta)) for 0 <= delta < 0x1000.

$$x_\pi$$

MM(pi), pi an instance of class AutPL;

MM('d', delta) * MM('p', n) is equivalent to MM(AutPL(delta, n)) for 0 <= delta < 0x1000, 0 <= n < 244823040 .

$$x_e$$

MM('x', e), x an instance of class PLoop;

MM(('x', e)) returns MM('x', PLoop(e)) for 0 <= e < 0x2000.

$$y_e$$

MM('y', e), e as in case $$x_e$$.

$$z_e$$

MM('z', e), e as in case $$x_e$$.

$$\tau^e$$

MM('t', e), exponent e is an integer which is taken modulo 3.

$$\xi^e$$

MM('l', e), exponent e is an integer which is taken modulo 3.

More possibilities for constructing elements of an instance of class MM are given in the description of that class. Multiplication and exponentiation of group elements works a usual.

Multiplication of elements of the monster group¶

Internally, an element of $$\mathbb{M}$$ is represented as a word in the generators given above. The user should be aware of the fact that multiplication with the * operator is a concatenation of such words, followed by (rather incomplete) reduction step. This means that multplying words may still lead to an exponential growth of the word length.

On can apply the method simplify to an element of the monster group. This method shortens a word representing an element of $$\mathbb{M}$$ to a reasonable length with a very high probability. However, applying this method usually takes a long time. On the author’s computer it may take several minutes to shorten the product of two (previously shortened) random words. This is yet considerably faster than the run time reported in [Wil13].

In such a word we always reduce substrings of generators of the subgroup $$N_0$$ of $$\mathbb{M}$$ to a standard form, which is easy. We apply no relations to the remaining generator $$\xi$$, except for $$\xi^3=1$$. Method simplify uses the techique described in [Wil03] for shortening a word in the monster group.

Future development¶

Future versions of this package may implement improved reduction strategies for words of generators of $$\mathbb{M}$$ :

• Long words of generators of $$\mathbb{M}$$ can be shortened with high probability by method mmgroup.MM.simplify. This method uses the algorithm in [Wil03]. This may take a long time. Here improvements in future versions are desirable.

Python classes implementing the monster group¶

class mmgroup.MM(tag=None, i=None, *args, **kwds)

Models an element of the monster group $$\mathbb{M}$$

Let g1 and g2 be instances of class MM representing elements of the monster group. Then g1 * g2 means group multiplication, and g1 ** n means exponentiation of g1 with the integer n. g1 ** (-1) is the inverse of g. g1 / g2 means g1 * g2 ** (-1). We have 1 * g1 == g1 * 1 == g1 and 1 / g1 == g1 ** (-1).

g1 ** g2 means g2**(-1) * g1 * g2.

Let V be a vector space that is a representation of MM, see class MMVector for details. An instance g1 of class MM operates on the vector space V by right multiplication.

Variables
• tag – In the simplest case, parameter tag is a string of length 1 that determines the type of the atomic group element. There are also some special cases for parameter tag  as indicated below. If tag is not given or equal to 1 then the neutral element of the monster group is constructed.

• i

Parameter i is number of the atomic element of a given tag. Depending on the tag, i may be the number of an element of one of the structures PLoop, Cocode, or the number of an element of the Mathieu group M_24, as explained in class AutPL. An element $$\pi$$ of the group AutPL is mapped to the element $$x_\pi$$ of the Monster group.

The number i may also be an instance of the appropriate class PLoop, Cocode, or AutPL, as indicated in the table below.

Returns

An element of the monster group

Return type

an instance of class MM

Standard tags

The tags listed in the following tables are standard tags that can be used for creating generators (or some short words of generators) of the monster group.

Atomic elements of the Monster group

Tag

Number i

Type of element

'p'

0-244823039

The automorphism AutPL(0, i) of the Parker loop, see below.

'd'

0-0xfff

The diagonal automorphism Cocode(i) in AutPL.

'x'

0-0x1fff

The element $$x_e$$, with e = PLoop(i).

'y'

0-0x1fff

The element $$y_e$$, e = PLoop(i); similar to tag 'x'.

'z'

0-0x1fff

The element $$z_e$$, e = PLoop(i); similar to tag 'x'. We have $$x_e y_e z_e = y_e x_e z_e = 1$$.

't'

0-2

The element $$\tau^i$$,

'l'

0-2

The element $$\xi^i$$,

'q'

0-0x1ffffff

Describes an element of the subgroup $$Q_{x0}$$. See remark below.

'c'

0-0xffffff

A representative of a right coset of $$N_{x0}$$ in $$G_{x0}$$. See remark below.

Apart from the standard tags there are also some tags for special purposes discussed in the following sections.

Remarks

If i is the string 'r' then a random element with the given tag is generated. If i is the string 'n' then a random element with the given tag is generated, which is different from the neutral element with a very high probability.

If tag == 'd' then i = 'o' generates a random odd and i = 'e' generates a random even diagonal automorphism. In this case i may also be an instance of class Cocode, representing the diagonal automorphism correspnding to the given element of the Golay cocode.

If tag == 'p' then i may also be an instance of class AutPL. Then the returned atom is the Parker loop automorphism given by that instance. If i is an integer then the Parker loop automorphism AutPL(0, i) is returned. This automorphism is the standard rpresentative of the i-th element of the Mathieu group M_24 in the automorphism group of the Parker loop.

If tag is 'x', 'y' or 'z' then i may also be an instance of class PLoop, representing an element of the Parker loop.

The exponent i for a tag 't' or 'l' is reduced modulo 3.

The tag 'q' is useful for encoding an element of the subgroup $$Q_{x0}$$ of the monster. An atom with tag 'q' and index i encodes the element $$x_d \cdot x_{\delta} \cdot x_{\theta(d)}$$, with $$d$$ = PLoop(i >> 12) $$\in \mathcal{P}$$, $$\delta$$ = Cocode(i & 0xfff) $$\in \mathcal{C}^*$$, and $$\theta: \mathcal{P} \rightarrow \mathcal{C}^*$$ the cocycle of the Parker loop.

The tag 'c' with index i encodes a representative of the right coset $$N_{x0} g, g \in G_{x0}$$ of $$N_{x0}$$ in $$G_{x0}$$ that maps the standard frame $$\Omega$$ in the Leech lattice modulo 2 to a type-4 vector given by the index i. Here i encodes a vector in the Leech lattice modulo 2 as in the description for tag 'q'. That vector must be of type 4. The sign bit of that vector is ignored.

Generating a random element of the subgroup of the monster

If parameter tag is equal to the string 'r' then parameter 'i' should be a string describing a subgroup of the monster group. Then a uniform distributed element from that subgroup is generated. The follwing subgroups are recognized:

 Parameter i Subgroup 'M' The monster group itself 'G_x0' Subroup 'G_x0' generated by $$x_d, x_\delta, y_d, x_\pi, \xi$$ 'N_0' Subroup 'N_0' generated by $$x_d, x_\delta, y_d, x_\pi, \tau$$ 'N_x0' Subroup 'N_x0' generated by $$x_d, x_\delta, y_d, x_\pi$$ 'N_0_e' Subroup of 'N_0' of index 2 generated by $$x_d, x_\delta, y_d, x_\pi, \tau$$, $$\delta$$ even 'N_x0_e' Subroup of 'N_x0' of index 2 generated by $$x_d, x_\delta, y_d, x_\pi$$, $$\delta$$ even

Subgroup 'G_x0' has structure $$2^{1+24}.\mbox{Co}_1$$, and subgroup 'N_0' has structure $$2^{2+11+22}.\mbox{M}_{24}$$. 'N_x0' is a subgroup of 'N_0' of index 3.

If Parameter i is an positive integer then an element of the monster of shape $$g_0 t_1 g_1 t_2 g_2 ... t_i g_i$$ is created, where $$g_j$$ is a random element of 'G_x0', and $$t_j$$ is $$\tau^{\pm 1}$$.

Generating an element of monster from its internal representation

If parameter tag is equal to the string 'a' then parameter 'i' should be an array-like object containing the internal representation of an element of the monster group.

Internally, an element of the monster group is represented as an array of unsigned 32-bit integers, where each entry of the array describes a generator. See section Header file mmgroup_generators.h for details.

Special types accepted as tags

In the simplest case the argument tag in the constructor is a string of length 1. There are a few other types which are also accepted as tags. For such a special tag, the following parameter i in the constructor is ignored.

Especially, we may encode a word of standard generators as a list of tuples as indicated in the table below.

Legal types as tags in the constructor of class MM

Object of type

Evaluates to

type list

A list represents the product of its entries in the given order. An entry MM(tag, i) can be abbreviated to the tuple (tag, i).

class PLoop

The Parker loop element $$d$$ given by that object is mapped to $$x_d \in \mathbb{M}$$.

class AutPL

The Parker loop automorphism $$\pi$$ given by that object is mapped to $$x_\pi \in \mathbb{M}$$.

class Cocode

The Golay cocode element $$\delta$$ given by that object is mapped to $$x_\delta \in \mathbb{M}$$.

class XLeech2

The element corresponding to that element of $$Q_{x0}$$ is created.

class MM

A deep copy of the given element of $$\mathbb{M}$$ is made.

str of length greater than 1

For an instance g of class MM we have MM(str(g)) == g.

So we can reread printed elements of MM.

as_tuples()

Convert group element to a list of tuples

For a group element g the following should hold:

self.__class__(self.as_tuples()) == self .

This shows how to convert a group element to a list of tuples and vice versa.

chi_G_x0()

Compute characters of element of subgroup $$G_{x0}$$

If the element is in the subgroup $$G_{x0}$$ then the function returns a tuple $$(\chi_M, \chi_{299}, \chi_{24}, \chi_{4096})$$ of integers. Otherwise it raises ValueError.

Here $$\chi_M$$ is the character of the element in the 196833-dimensional rep $$198883_x$$ of the monster.

By Conway’s construction of the monster we have:

$$198883_x = 299_x \oplus 24_x \otimes 4096_x \oplus 98280_x$$,

for suitable irreducible representations $$299_x, 24_x, 4096_x, 98280_x$$ of the group $$G_{x0}$$. The corresponding characters of the element of $$G_{x0}$$ are returned in the tuple given above.

While the product $$\chi_{24} \cdot \chi_{4096}$$ is well defined, the factors $$\chi_{24}$$ and $$\chi_{4096}$$ are defined up to sign only. We normalize these factors such that the first nonzero value of the pair $$(\chi_{24}, \chi_{4096})$$ is positive.

copy()

Return a deep copy of the group element

half_order(max_order=119)

Return the (halved) order of the element of the monster group

The function returns a pair (o, h), where o is the order of the element.

If o is even then the function returns the pair (o, h), where h is the element raised to to the (o/2)-th power. Otherwise the function returns the pair (o, None).

Parameter max_order is as in function check_mm_order.

If h is in the subgroup $$G_{x0}$$ then h is returned as a word in the generators of that subgroup.

in_G_x0()

Check if the element is in the subgroup $$G_{x0}$$

The function returns True if this is the case. If this is the case then the element is converted to a word in the generators of $$G_{x0}$$.

This method uses geometric information about the Leech lattice taken from [Iva99].

in_N_x0()

Check if the element is in the subgroup $$N_{x0}$$

The function returns True if this is the case. If this is the case then the element is converted to a word in the generators of $$N_{x0}$$.

in_Q_x0()

Check if the element is in the subgroup $$Q_{x0}$$

The function returns True if this is the case. If this is the case then the element is converted to a word in the generators of $$Q_{x0}$$.

is_reduced()

Return True if the element of the monster group is reduced

An element g of the monster group represented by an instance of this class may be reduced by calling g.reduce().

property mmdata

Return the internal representation of the group element

Internally, an element of the monster group is represented as an array of unsigned 32-bit integers, where each entry of the array describes a generator. See section Header file mmgroup_generators.h for details.

order(max_order=119)

Return the order of the element of the monster group

We use the method in [LPWW98], section 7, for computing the order of an element of the monster.

If the argument max_order is present then the order of the element is checked up to (and including) max_order only. Then the function returns 0 if the order is greater than max_order. By default, the function returns the exact order of the element.

reduce(copy=False)

Reduce a group element

If group elements are implemented as words, some functions may produce unreduced words. This function reduces the group element in place.

Note that all operators return reduced words. Functions return reduced words unless stated otherwise. However, reducing all words representing the same group element to the same word may be beyond the capabilties of a program.

If copy is set then a reduced copy of the element is returned, in case that the input element is not already reduced.

simplify(ntrials=None, verbose=0)

Try to simplify an element of the monster group

This function tries to simplify an element of the monster group. It may take a long time, but this is the only way to prevent the explosion of the word lengths of elements of the monster group.

The current version uses the word shortening algorithm in [Wil03]. Parameter ntrials specifies the number of trials. Here the default value for ntrials should be used, since the parameter may be dropped in future versions.

The word shortening algorithm and the implementation of this method is experimental and may change in future versions!

The representation of the monster group¶

We deal with the 196884-dimensional representation of the monster.

One purpose of the mmgroup package is to give the user the capability to compute in the 196884-dimensional representation $$\rho_p$$ of the monster group $$\mathbb{M}$$. Here $$\rho$$ is the rational representation 196884_x of the monster constructed in in [Con85], and $$\rho_p$$ is obtained from $$\rho$$ by taking all matrix coefficients modulo a small odd number p. This package supports the cases p = 3, 7, 15, 31, 127, 255.

We are a bit sloppy, calling $$\rho_p$$ a vector space also in cases p = 15, 255. The user may select these values for obtaining representations modulo 5 and 17, respectively.

For calculating in $$\rho_p$$ the user may create an instance of class MM that models an element g of the group $$\mathbb{M}$$ as described in section The monster group. Then the user may create an instance v of class MMVector that models a vector in $$\rho_p$$, with p as above. Vector v acts on the element g of $$\mathbb{M}$$ by right multiplication.

Creating basis vectors of the representation space $$\rho_p$$¶

By construction of $$\rho_p$$ it is natural to label a basis vector of $$\rho_p$$ by a tuple (tag, i0, i1) with integers i0, i1, as described in the next section. Here tag is a single capital letter and indices i0, i1 are unsigned integers; these three quantities describe a basis vector of the space V.

To create a basis vector of $$\rho_p$$ corresponding to the tuple (tag, i0, i1) the user may call the constructor MMVector(p, tag, i0, i1).

For a fixed characteristic p function MMV(p) returns an object correponding to the vector space $$\rho_p$$. Thus the sequence

>>> from mmgroup import MMV
>>> V = MMV(p)
>>> v = V(tag, i0, i1)


creates the same basis vector v as the statement v = MMVector(p, tag, i0, i1).

Description of the basis vectors of the representation space¶

The following table shows the tags available for describing basis vectors. The column Vector in that table shows the basis vector in the notation of [Sey20]. The column Tuple shows the basis vector as a tuple (tag, i0, i1).

Basis vectors of the representation of the monster

Vector

Tuple

Remarks

$$(ij)_1$$

('A',i,j)

0 <= i,j < 24; we have $$(ij)_1 = (ji)_1$$.

$$X_{ij}$$

('B',i,j)

0 <= i,j < 24, i != j; we have $$X_{ij} = X_{ji}$$.

$$X^+_{ij}$$

('C',i,j)

0 <= i,j < 24, i != j; we have $$X^+_{ij} = X^+_{ji}$$.

$$X^+_{d \cdot \delta}$$

('T',o,s)

o = x.octad, s = x.suboctad, x = SubOctad(d, delta),

$$d \in \mathcal{P}$$, $$\delta \in \mathcal{C^*}$$, $$d$$ an octad, $$\delta \subset d$$, $$\delta$$ even. See class SubOctad.

We have 0 <= o < 759, 0 <= s < 64.

$$X^+_{d \cdot i}$$

('X',d,i)

0 <= d < 2048, 0 <= i < 24,

d represents the element PLoop(d) of the Parker loop $$\mathcal{P}$$

$$d^+ \otimes_1 i$$

('Z',d,i)

d and i as in case ('X',d,i)

$$d^- \otimes_1 i$$

('Y',d,i)

d and i as in case ('X',d,i)

Remarks

• The space $$\rho_p$$ is an orthogonal space. Two basis vectors are orthogonal except when equal or opposite. The basis vectors $$(ij)_1$$ have norm 2 in case $$i \neq j$$. All other basis vectors have norm 1.

• In the tuple ('T',o,s) the integers o and s describe the instance SubOctad(o, s) of class SubOctad. Here o and s may be anything that is accepted as input for SubOctad(o, s)

• In the tuples ('X',d,i), ('Y',d,i), ('Z',d,i), the input d may be an instance of class PLoop or anything such that PLoop(d) is an instance of class PLoop. For an instance d of class PLoop we have:

• ('X',d,i) == -('X',-d,i) ==  ('X',~d,i) ,

• ('Y',d,i) == -('Y',-d,i) == -('Y',~d,i) ,

• ('Z',d,i) == -('Z',-d,i) ==  ('Z',~d,i) .

The value of ('X',~d,i) has been set by convention; the other equations are forced.

• The basis vector $$d^+ \otimes_1 i$$ in [Sey20] is equal to the basis vector $$(-1)^{|d/4|} \cdot d^+ \otimes_1 i$$ in [Con85]. This modification simplifies the formulas for the operation of the element $$\xi$$ of $$\mathbb{M}$$ on $$\rho_p$$.

• A first or second index following a tag may be 'r', indicating a random integral index. Any omitted index after a given index 'r' is interpreted as 'r'. For tags 'A', 'B', 'C', 'T' the second index should be 'r' or omitted if the first index is 'r', since in these cases the two indices are not sufficiently independent.

Representing a vector as a list of tuples¶

For creating an arbitrary (but yet sparse) vector in $$\rho_p$$ the user may call MMVector(p, data_list), where data_list is a list of tuples (factor, tag, i0, i1). Here (tag, i0, i1) describes a unit vector and the (optional) integer factor is a scalar factor for that unit vector. Then the constructor returns the linear combination of the unit vectors given in the list.

In order to generate a random multiple of a basis vector, inside a list of tuples, the (optional) component factor of a tuple can be set to one of the following values:

• 'u': equivalent to 1

• 's': a factor 1 or -1 selected at random

• 'n': a random nonzerodivisor modulo p

• 'r': a random integer modulo p

Operations on vector in the representation $$\rho_p$$¶

Vector addition, subtraction and scalar multiplication can be done with operators +, - and * as usual. Elements of the monster group operate on vectors by right multiplication. Only vectors modulo the same characteristic p can be added.

The following code example generates an element g of the monster group and a vector v in the vector space $$\rho_3$$ and displays the result g * v of the operation of g on v. Note that a basis vector (tag, i0, i1) is displayed in the form tag_i0_i1. For a displayed index i0 or i1 the suffix h means hexadecimal notation.

>>> # An instance of class MM represents an element of the monster
>>> from mmgroup import MM
>>> # Function MMV is used to create a representation space
>>> from mmgroup import MMV
>>> # Create representation space V for the monster (modulo 3)
>>> V = MMV(3)
>>> # Create an element g of the monster group
>>> g = MM([('d', 0x123), ('p', 217821225)])
>>> # Create a vector v in the representation space V
>>> v = V([('T', 712, 13), (2, 'X', 0x345, 13)])
>>> # Let g operate on v by right multiplication
>>> print(v * g)
MV<3;-T_444_0fh+X_244h_11>


Special tags for creating vectors in the representation $$\rho_p$$¶

Apart from the standard tags A, B, C, T, X, Y, and Z, the constructor of class MMVector acceps a variety of special tags. Details are given in the following list:

Special tags for constructing a vector

tag, i0, i1

Evaluates to

('D', i0)

Shorthand for ('A', i0, i0)

('I', i0, i1)

Shorthand for the sum of the basis vectors

('A', i0, i0) + ('A', i1, i1) - ('A', i0, i1) - 2 ('B', i0, i1),

see remark below.

('E', i)

This is the basis vector with linear index i.

See the following subsection for details.

('S', data)

Here data is an array-like object (as defined in the numpy package) that encodes a vector in sparse representation as an array of unsigned 32-bit integers.

This is for internal use. For details see the following subsection:

Sparse representation of vectors in $$\rho_p$$.

('V', data)

Here data is an array like object (as defined in the numpy package) that encodes a one-dimensional array of integers of length 196884. The order of the entries is as in the next section.

('R')

Tag 'R' (without any further parameters) stands for the generation of a uniform distributed random vector.

(i, v), i integer

Here i is an integer and v is a vector, i.e.an instance of class MMVector. Then the vector i * v is generated. This is useful for extending the modulus p of a vector, see remark below.

Remarks

The centralizer of a vector labelled by ('I', i0, i1) in the monster has structure $$2 \cdot B$$, where $$B$$ is the Baby Monster, see [Asc86], [Con85], [Iva09] for background. According to our selected basis and cocycle of the Golay Code, it is probably easiest to compute in the centralizer of ('I', 3, 2).

The modulus of a vector can be extended as follows. Assume that v is a vector in $$\rho_3$$, given as an instance of class MMVector. Then w = 5 * v is a well-defined vector in $$\rho_{15}$$. Vector w can be constructed as follows: V15 = MMV(15); w = V15(5, v). Note that the construction w = V15(5*v) leads to an error, since 5*v is defined modulo 3, but not modulo 15.

Linear order of the basis vectors¶

By construction of the representation $$\rho_p$$, it is most natural to use a tuple (tag, i0, i1) for indexing a basis vector of $$\rho_p$$. There is also a linear order of these entries. Such a linear order is required e.g. for expressing a vector in $$\rho_p$$ as an array of integers modulo $$p$$. Therefore an index given by a tuple (tag, i0, i1) is mapped to linear index 0 <= i < 196884. Legal standard tuples are listed in the following table:

Conditions for indices i0, i1

Tag

Condition for i0

Condition for i1

'A'

0 <= i0 < 24

0 <= i1 < 24

'B', 'C'

0 <= i0 < 24

0 <= i1 < 24, i1 != i0

'T'

0 <= i0 < 759

0 <= i1 < 64

'X', 'Y', 'Z'

0 <= i0 < 2048

0 <= i1 < 24

For tag = 'A', 'B', 'C', we also have (tag, i0, i1) == (tag, i1, i0).

The linear order of the tuples (tag, i0, i1) is as follows:

offset 0:

(A,0,0), (A,1,1),  ..., (A,23,23)

offset 24:

(A,1,0),
(A,2,0),  (A,2,1)
(A,23,0),  (A,23,1), ...,  (A,23,22)

offset 300:

Tuples (B,i0,i1), same order as tuples (A,i0,i1) for i0 > i1

offset 576:

Tuples (C,i0,i1), same order as tuples (A,i0,i1) for i0 > i1

offset 852:

(T,  0,0),  (T,  0,1), ...,  (T,  0,63)
(T,  1,0),  (T,  1,1), ...,  (T,  1,63)
(T,758,0),  (T,758,1), ...,  (T,758,63)

offset 49428:

(X,   0,0),  (X,   0,1), ...,  (X,   0,23)
(X,   1,0),  (X,   1,1), ...,  (X,   1,23)
(X,2047,0),  (X,2047,1), ...,  (X,2047,23)

offset 98580:

Tuples (Z,i0,i1), same order as corresponding tuples (X,i0,i1)

offset 147732:

Tuples (Y,i0,i1), same order as corresponding tuples (X,i0,i1)

Sparse representation of vectors in $$\rho_p$$¶

Internally, a vector $$\rho_p$$ is sometimes given in sparse representation. This is useful for sparse vector containing many zero entries. In sparse representation the vector is given as an array of unsigned 32-bit integers. Here each entry of the array encodes a multiple of the basis vector. Such an entry it interpreted as follows:

 Component tag i0 i1 factor Bits 27 - 25 24 - 14 13 - 8 7 - 0

This corresponds to the tuple (factor, tag, i0, i1) which denotes a multiple of a basis vector as described in subsection Representing a vector as a list of tuples.

Tags are mapped to integers as follows:

 'A' 'B' 'C' 'T' 'X' 'Z' 'Y' 1 2 3 4 5 6 7

Other data types accepted as tags for vectors in $$\rho_p$$¶

Some data types are accepted as tags and interprted as described in the following table. In this case parameters i0, i1 after a tag must not be set.

Legal types for constructing a vector

type

Evaluates to

List of tuples

This evaluates to a vector as described in subsection Representing a vector as a list of tuples.

An entry of such a list may also be an instance of class MMVector or a string.

class MMVector

A deep copy of the given vector is returned.

class XLeech2

If tag is of type XLeech2 then the (possibly negative) basis vector corresponding to that tag in $$Q_{x0}$$ is created.

str

For an vector v in V we have V(str(v)) == v.

Python classes implementing the representation of the monster group¶

class mmgroup.MMVector(p, tag=0, i0=None, i1=None)

Models a vector in a representation of the monster group.

The construction of vectors in the representations $$\rho_p$$ of the monster group (using e.g. the constructor of this class) is documented at the beginning of section The representation of the monster group. There a basis vector of that representation is dscribed as a tuple (tag, i0, i1), where tag is a single capital letter and i0, i1 are integers. So we may invoke the constructor of this class as follows:

Parameters
• p – Modulus p of the representation $$\rho_p$$.

• tag – Tag of the unit vector to be constructed. In the standard case this is a single capital letter describing the type of the basis vector.

• i0 – First index in the tuple describing the basis vector.

• i2 – Second index in the tuple describing the basis vector.

Linear operations can be used for for creating linear combination of unit vectors. This is just the simplest cast of the construction of a vector in $$\rho_p$$. Section The representation of the monster group contains a large number of further possibilities for creating such vectors.

Addition and subtraction of vectors in the same space work as usual. This is also the case for scalar multiplication with integers. An element g of the monster group (given as an instance of class MM) operates on a vector v (given as an instance of this class) by right multiplication.

An entry of a vector v (given as an instance of this class) may be adressed as v[tag, i0, i1], where tag is a single letter in the string ABCTXYZD and i0 and i1 are integers, such that the tuple (tag, i0, i1) describes a basis vector. Getting and setting entries of a vector is as in the numpy package. Here i0 and i1 may also be slices of integers in the same way as in numpy arrays. Depending on the tag, the value i0 or i1 may also be a single instance of the appropriate class, as described in the remarks after table Basis vectors of the representation of the monster .

The entries of vector v also have a linear order as described at the beginnning of section The representation of the monster group. Here v['E', i] is the i-th entry in that order. Index i may also be a slice of integers in the same way as in a one-dimensional numpy array.

The internal representation of a vector v in this class is not part of the public interface. Use v['E'] to convert v to an one-dimensional array of 8-bit integers of length 196884.

as_sparse()

Return vector in sparse representation

The sparse representation of a vector is returned as a one-dimensional numpy array of 32-bit integers. Here each entry of that array represents a nonzero component of the vector. Such an entry it interpreted as described in method from_sparse of class MMSpace.

Entries with value zero are dropped.

as_tuples()

Return vector in tuple representation

The function returns a list of tuples (factor, tag, i0, i1). Here (tag, i0, i1) describes a basis vector and value is the coordinate of that vector.

Entries with coordinate zero are dropped.

mul_exp(g, e=1, break_g=False)

Multiply the vector with g ** e inplace

Here g is an element of the moster group represented as an instance of class MM and e is an integer. The vector is updated and the updated vector is returned.

Afterwards, the vector contains an attribute last_timing containing the run time of this operation in seconds. This is useful for benchmarking.

By default, we try to simplify the expression g ** e before multiplying it with the vector. If break_g is set, we always do abs(e) muliplications with g or with its inverse.

projection(*args)

Return projection of the vector v onto a subspace.

Each argument describes a subspace of this space V. The projection of the vector to the space W spanned by all these subspaces is returned.

In the current version each argument must be a tuple (tag, i0, i1) that describes a subspace generated by a basis vector. A legal tag is letter in the string ABCTXYZD, as explained in table Basis vectors of the representation of the monster and class MMSpace.

class mmgroup.MMSpace(*args, **kwds)

Models a 196884-dimensional representation of the monster group

This class contains a collection of functions for manipulating vectors in the rpresentation $$\rho_p$$ of the monster group. Such vectors are instances of class MMVector. Most of these function are used implicitly in the operators applied to these vectors.

Some of these function may be helpful for the user; so we document them in the mmgroup API reference.

static index_to_short(tag, i0=- 1, i1=- 1)

Convert index to a short Leech lattice vector

If tag is an integer, this is interpreted a linear index for a basis vector in the representation $$\rho_p$$ as in method tuple_to_index. Otherwise the tuple (tag, i0, i1) is interpreted a standard index for such a basis vector. If tag is an instance of class MMVector, which is a nonzero multiple of a basis vector, then that basis vector is taken.

Some but not all of these basis vectors correspond to short vector in the Leech lattice up to sign. If this is the case then the function returns a short vector of the Leech lattice as a numpy array of signed 32-bit integers of length 24. The norm of the returned vector is 32.

The function raises ValueError if the basis vector in $$\rho_p$$ does not correspond to a short vector.

The sign of the short vector is undefined, but two calls referring to the same basis vector return the same short vector.

classmethod index_to_tuple(index)

Convert linear index to tuple (tag, i0, i1)

This method reverses the effect of method tuple_to_index. Given a linear index 0 <= i < 196884 for a basis vector, the function returns that index as a tuple (tag, i0, i1) with tags one letter of the string "ABCTXYZ" and integers i0, i1.

See method tuple_to_index for details.

If index is an instance of class MMVector, which is a nonzero multiple of a basis vector, then the index of that basis vector is taken.

classmethod tuple_to_index(tag, i0=- 1, i1=- 1)

Convert tuple (tag, i0, i1) to a linear index

Remarks:

The tuple ('D', i0) is accepted as a shorthand for ('A', i0,i0).

A tuple ('E', i0) means a linear index i0, i.e. this method returns i0 on input ('E', i0), for 0 <= i0 < 196884.

If tag is an instance of class MMVector, which is a nonzero multiple of a basis vector, then the linear index corresponding to that basis vector is returned.

Auxiliary functions for the representation of the monster group¶

mmgroup.characteristics()

Return list of all characteristics p supported

mmgroup.MMV(p)

Return an object correponding to the space $$\rho_p$$

Here characteristic p is as in the constructor of class MM. Thus the sequence

>>> V = MMV(p)
>>> v = V(tag, i0, i1)


returns the same vector in $$\rho_p$$ as the statement MMVector(p, tag, i0, i1).

Function characteristics in module mmgroup returns the list of legal values for the characteristic p.

Technically, MMV(p) is the partial application of the constructor of class MMVector to the number p.

The subgroup $$2^{1+24}.Co_1$$ of the monster and the Clifford group¶

The section describes the fast computation in a certain subgroup $$G_{x0}$$ of the monster $$\mathbb{M}$$ in detail. A person who simply wants do do calculations in the monster group need not read this section.

Introduction¶

In Conway’s construction [Con85] the monster $$\mathbb{M}$$ has a subgroup $$G_{x0}$$ of structure $$2^{1+24}_+.\mbox{Co}_1$$. There $$G_{x0}$$ is constructed as a diagonal product of the two groups $$\mbox{Co}_0$$ of structure $$2.\mbox{Co}_1$$ and $$G(4096_x)$$. $$G(4096_x)$$ is also of structure $$2^{1+24}_+.\mbox{Co}_1$$ but not isomorphic to $$G_{x0}$$. Here $$2^{1+24}_+$$ means an extraspecial group of plus type. $$\mbox{Co}_0$$, and $$\mbox{Co}_1$$ are the automorphism groups of the $$24$$-dimensional Leech lattice and of the Leech lattice modulo $$2$$, see e.g. [CCN+85] or [CS99] for background.

Computation in $$\mbox{Co}_0$$ is easy since that group has a $$24$$-dimensional rational representation. The smallest real representation of the group $$G(4096_x)$$ has dimension $$4096$$, so naive computation in that representation is rather inefficient.

The group $$G(4096_x)$$ is a subgroup of the real Clifford group $$\mathcal{C}_{12}$$. The real Clifford group $$\mathcal{C}_{n}$$ of structure $$2^{1+2n}_+.\mbox{GO}^+_{2n}(2)$$ is defined e.g. in [NRS01]. $$\mathcal{C}_{12}$$ is a subgroup of the complex Clifford group $$\mathcal{X}_{n}$$ of structure $$\frac{1}{2} ( 2^{1+2n}_+ \times Z_8 ). \mbox{Sp}_{2n}(2)$$, which is also defined in [NRS01]. Here a factor $$\frac{1}{2}$$ means identification of central subgroups of order $$2$$ of the factors of a direct product. $$\mbox{GO}^+_{2n}(2)$$ and $$\mbox{Sp}_{2n}(2)$$ are the orthogonal subgroup (of $$+$$-type) and the symplectic subgroup of the group $$GL_{2n}(2)$$ of invertible $$2n \times 2n$$-matrices with entries in $$\mathbb{F}_2$$, as defined in [CCN+85].

Effective computation in the group $$\mathcal{X}_{n}$$ has received a lot of attention from the theory of quantum computation, see e.g. [AG04]. In the next section we present efficient algorithms for computing in $$\mathcal{X}_{n}$$ and in its $$2^{n}$$ dimensional complex representation.

Computation in the Clifford group¶

In this section we present effective algorithms for computing in the complex Clifford group of structure $$\frac{1}{2} ( 2^{1+2n}_+ \times Z_8 ). \mbox{Sp}_{2n}(2)$$ defined in [NRS01]. Here a factor $$\frac{1}{2}$$ means identification of central subgroups of order $$2$$ of the factors of a direct product as in [CCN+85].

The complex Clifford group $$\mathcal{X}_{n}$$ has a unitary complex representation of dimension $$2^n$$ which has been studied in the theory of quantum computation, see e.g. [AG04]. For calculations in the monster group it would be sufficient to deal with the subgroup $$\mathcal{C}_{n}$$ of $$\mathcal{X}_{n}$$ consisting of the real matrices of that representation. However, the extra effort for extending the real to the complex case is marginal, and using our algorithms for the complex Clifford group might be useful in the theory of quantum computation.

Usually, in quantum physics it suffices to calculate in a unitary group up to a scalar multiple of the unit matrix. Therefore we cannot simply cut an paste existing algorithms for calculating in $$\mathcal{X}_{n}$$ used in quantum physics. We keep the following exposition independent of the theory of quantum computation, but we do not hide the fact that the main ideas are strongly influenced by that theory.

We present an algorithm that performs matrix multiplication in $$\mathcal{X}_{n}$$ in $$O(n)^3$$ bit operation. Therefore we store an element of $$\mathcal{X}_{n}$$ in $$O(n)^2$$ bits. In case $$n=12$$ this is considerably more efficient than dealing with complex $$4096 \times 4096$$ matrices.

We will introduce certain complex-valued functions defined on a Boolean vector space $$\mathbb{F}_2^n$$ which we will call quadratic mappings. Such a function has a natural interpretation as a vector in $$\mathbb{C}^{2^n}$$. It will turn out that quadratic mappings are closed under tensor products and under tensor contraction. Since matrix multiplication is just a special case of tensor contraction, we may consider quadratic mappings on $$\mathbb{F}_2^n \times \mathbb{F}_2^n$$ as a monoid of $$2^n \times 2^n$$ matrices closed under matrix multiplication. It turns out that the unitary matrices in this monoid are just a representation of the Clifford group $$\mathcal{X}_{n}$$.

Let $$V = \mathbb{F}_2^n$$ be a Boolean vector space and $$\mathbb{T}$$ be the unit circle in the set $$\mathbb{C}$$ of the complex numbers. Then $$\mathbb{F}_2^n$$ is an additive and $$\mathbb{T}$$ is a multiplicative Abelian group. For any mapping $$f: V \rightarrow \mathbb{T}$$ define the mapping $$\Delta f: V \times V \rightarrow \mathbb{T}$$ by

$\Delta f(x,y) = f(x+y) \cdot f(x)^{-1} \cdot f(y)^{-1} \cdot f(0) .$

A mapping $$g: V \rightarrow \mathbb{T}$$ is bilinear if

$\begin{split}g(x_1 + x_2, x_3) = g(x_1, x_3) \cdot g(x_2, x_3) , \\ g(x_1, x_2 + x_3) = g(x_1, x_3) \cdot g(x_1, x_3) .\end{split}$

Then we obviously have $$g(x_1,x_2) = \pm 1$$ and $$g(0,x_2) = g(x_1,0) = 1$$. Thus there is a unique symmetric bilinear form $$\beta(g): V \times V \rightarrow \mathbb{F}_2$$ with $$g(x_1, x_2) = (-1)^{\beta(g)(x_1, x_2)}$$. A function $$q: V \rightarrow \mathbb{T}$$ is called quadratic if $$q(0) = 1$$ and $$\Delta q$$ is bilinear. For a quadratic function $$q$$ all functional values of $$q$$ are fourth roots of unity. We write $$\beta(q)$$ for $$\beta(\Delta q)$$. Put

$R_8 = \{ 2^{e/2} \cdot w \mid e \in \mathbb{Z}, w \in \mathbb{C}, w^8 = 1\} \cup \{0\} \; .$

Let $$e \in R_8$$, let $$q: \mathbb{F}_2^m \rightarrow \mathbb{T}$$ be a quadratic function, and let $$a: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n$$ be an affine mapping. Then we define a function $$f = f(e, a, q): \mathbb{F}_2^n \rightarrow \mathbb{C}$$ by

(1)$f(e,a,q)(x) = e \cdot \sum_{\{y \in \mathbb{F}_2^m \mid a(y) = x\}} q(y) .$

We call a function $$f(e,a,q)$$ satisfying (1) a quadratic mapping. We call the triple $$(e, a, q)$$ a representation of the quadratic mapping $$f(e, a, q)$$. Occasionally we also consider quadratic mappings $$f(e, a, q)$$ where $$q$$ is a scalar multiple of a quadratic function with $$q(0) \in R_8$$. We sometimes abbreviate $$f(e, a, q)(x)$$ to $$f(x)$$ if the meaning of $$e, a, q$$ is clear from the context.

The following lemma is a direct consequence of the definition of a quadratic mapping.

Lemma 1:

Let $$g, g_1: V = \mathbb{F}_2^n \rightarrow \mathbb{C}$$ be quadratic mappings. Then

• For any affine mapping $$a : \mathbb{F}_2^{n'} \rightarrow \mathbb{F}_2^{n}$$ the composition $$g \circ a$$ given by $$x \mapsto g(a(x))$$ is a quadratic mapping on $$\mathbb{F}_2^{n'}$$.

Hence the definition of a quadratic mapping on the affine space $$V$$ is invariant to translations and to basis transformations of $$V$$.

• The product $$g \cdot g_1$$ of the functions $$g$$ and $$g_1$$ is a quadratic mapping on $$V$$.

• For any any affine subspace $$W$$ of $$V$$ restriction of $$g$$ to $$W$$, and also characteristic function $$\chi_W : V \rightarrow V$$ of the subspace $$W$$ is a quadratic mapping.

• For any linear subspace $$W$$ of $$V$$ the function $$g^{(W)} : V/W \rightarrow \mathbb{C}$$ given by $$x \mapsto \sum_{y \in W} g(x+y)$$ is a quadratic mapping.

A function $$f: \mathbb{F}_2 \rightarrow \mathbb{C}$$ has a natural interpretation as a vector in $$\mathbb{C}^2$$. Similarly, a function $$g: \mathbb{F}_2^n \rightarrow \mathbb{C}$$ has a natural interpretation as a tensor in the tensor product $$(\mathbb{C}^2)^{\otimes n}$$. If $$\mathbb{C}^2$$ has basis $$(b_0, b_1)$$ then the tensor corresponding to $$g$$ has coordinate $$g(i_1,\ldots,i_n)$$ at the basis vector $$b_{i_1} \otimes \ldots \otimes b_{i_n}$$ of $$(\mathbb{C}^2)^{\otimes n}$$. We call $$g$$ the coordinate function of the tensor. If $$g$$ is a function $$\mathbb{F}_2^n \rightarrow \mathbb{C}$$ and $$x_j \in \mathbb{F}_2^{n_j}$$ holds with $$\sum_{j=1}^k n_j = n$$ then we put $$g(x_1,\ldots,x_k)$$ = $$g(x)$$, where $$x$$ is the concatenation of the bit vectors $$x_1, \ldots, x_k$$.

A vector (or a tensor) in a space over $$\mathbb{F}_2^n$$ is called a quadratic state vector (or a quadratic state tensor) if its coordinate function is a quadratic mapping. Using Lemma 1 we can easily show that tensor products and tensor contractions of quadratic state vectors are quadratic state vectors. As we shall see later, they can easily be computed in practice. A matrix is a special kind of a tensor, and matrix multiplication is a special case of the contraction of a tensor product. Thus the matrix product of two quadratic state matrices is also a quadratic state matrix.

For any affine mapping $$a: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n$$ there is a unique linear mapping $$l(a)$$ that differs from $$a$$ by the constant $$a(0)$$. We write $$\ker a$$ for $$\ker l(a)$$. We call a representation $$(e, a, q)$$ of a quadratic mapping injective if $$\ker a = 0$$. We have:

Lemma 2:

Every quadratic mapping has an injective representation.

Proof

Let $$e \in R_8, a : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n$$, and $$q$$ a quadratic function on $$\mathbb{F}_2^m$$ such that $$g = f(e, a, q)$$ and $$m$$ is minimal. Assume $$\ker a \neq 0$$. Then we construct a tuple $$(e', a', q'$$) with $$g = f(e', a', q')$$, such that the domain of $$a'$$ and of $$q'$$ is a proper affine subspace of the domain of $$a$$.

Let $$v \in \ker A \setminus \{0\}$$ and $$W$$ be a subspace of $$\mathbb{F}_2^m$$ with $$\left<v \right> \oplus W = \mathbb{F}_2^m$$. Then for $$w \in W$$ we have $$q(w+v) = q(v) \cdot (-1)^{h(w)} \cdot r$$, with $$h$$ a linear form on $$W$$ given by $$h(w) = \beta(q)(v, w)$$ and $$r = q(v)/q(0)$$ a fourth root of unity. Since $$v \in \ker A$$, we have

$f(e,a,q)(x) = e \cdot \sum_{\{y \in W \mid a(y) = x\}} q(y) + q(y + v) = e \cdot \sum_{\{y \in W \mid a(y) = x\}} q(y) t(h(y)) \; ,$

where $$t(z) = 1 + r \cdot (-1)^z$$ for $$z \in \mathbb{F}_2$$. Let $$W'$$ be the support of $$t \circ h$$, i.e. $$W' = \{y \in W \mid t(h(y)) \neq 0\}$$. In case $$W' = \emptyset$$ we have $$f(e,a,q) = 0$$. Otherwise it suffices to show that $$W'$$ is an affine subspace of $$W$$, and that the restriction of $$t \circ h$$ to $$W'$$ is a quadratic function up to a scalar multiple in $$R_8$$.

Since $$r$$ is a fourth root ot unity, $$t(0)$$ and $$t(1)$$ are in $$R_8$$. If $$h$$ is zero then $$t \circ h$$ is a constant function on $$W$$.

If $$r$$ is an imaginary fourth root of unity then $$t(0) \neq 0$$ and $$t(1)/t(0) = \pm \sqrt{-1}$$. Thus $$t$$ is a quadratic function on $$\mathbb{F}_2$$ up to the factor $$t(0)$$. Since $$h$$ is linear, $$t \circ h$$ is also a quadratic function on $$W$$.

If $$r = \pm 1, h \neq 0$$, then the function $$t \circ h$$ is constant on $$W'$$, and we have $$W' = \ker h$$ if $$r = 1$$ and $$W' = W \setminus \ker h$$ if $$r = -1$$.

q.e.d.

The complex Clifford group $$\mathcal{X}_n$$ is a group which is defined in [AG04] and [NRS01]. It has a unitary representation in $$(\mathbb{C}^2)^{\otimes n}$$.

Lemma 3

The unitary complex quadratic state matrices representing endomorphisms of the space $$\mathbb{C}^{2^n}$$ make up a representation of the complex Clifford group $$\mathcal{X}_n$$ .

Sketch Proof

It is easy to see that all generators of $$\mathcal{X}_n$$ in [NRS01] are unitary complex quadratic state matrices. The group $$\mathcal{X}'_n$$ of such matrices is closed under multiplication. It is obviously closed under computing the inverse, which is the conjugate transpose for a unitary matrix. Thus $$\mathcal{X}_n$$ is a subgroup of $$\mathcal{X}'_n$$ . By Lemma 3 the group $$\mathcal{X}'_n$$ is finite. By Theorem 6.5 in [NRS01] all finite supergroups of $$\mathcal{X}_n$$ in the unitary group are generated by $$\mathcal{X}_n$$ and a scalar multiple of the unit matrix by a root of unity. Comparing the scalar multiples of the unit matrix in $$\mathcal{X}_n$$ and $$\mathcal{X}'_n$$ yields $$\mathcal{X}_n$$ = $$\mathcal{X}'_n$$.

q.e.d.

Background from the theory of quantum computing¶

In the theory of quantum computation a state vector representing the state of $$n$$ qubits can be written as a vector in $$(\mathbb{C}^2)^{\otimes n}$$, where the $$2^n$$ basis vectors of that space are labelled by the elements of $$\mathbb{F}_2^n$$. Here the $$n$$ qubits correspond to the $$n$$ factors $$\mathbb{F}_2$$ of $$\mathbb{F}_2^n$$. In [AG04] the unit vectors which are also quadratic state vectors are called stabilizer states. By Lemma 2 the product of a stabilizer state with a unitary quadratic state matrix is a stabilizer state. Thus Lemma 3 implies that the Clifford group $$\mathcal{X}_n$$ stabilizes the stabilizer state vectors. In the theory of quantum computation this fact is known as the Gottesman-Knill theorem.

In [AG04] there is a fast algorithm for calculating in the Clifford group $$\mathcal{X}_n$$. As usual in quantum theory, this algorithm ignores scalar factors in the matrix representation of $$\mathcal{X}_n$$. This means that we have to create our own algorithm for computing in $$\mathcal{X}_n$$.

Let $$g = f(e, a, q): \mathbb{F}_2^n \rightarrow \mathbb{C}$$ with $$e \in R_8$$, $$a : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n$$ an affine mapping, and $$q: \mathbb{F}_2^m \rightarrow \mathbb{T}$$. We implement the quadratic mapping $$g$$ as a triple $$(e, A, Q)$$.

Here $$A$$ is an $$(m + 1) \times n$$ bit matrix representing $$a$$, and $$Q$$ is a symmetric $$(m + 1) \times (m + 1)$$ bit matrix representing $$q$$. All vector and matrix indices start with $$0$$ as usual in the C language. For $$x = (x_1,\ldots, x_m) \in \mathbb{F}_2^m$$, $$x_0 = 1$$ and bit matrices $$A, Q$$ as above we put:

$a(x) =(x_0,\ldots, x_m) \cdot A \quad , \quad q(x) = \exp \left(\pi \sqrt{-1} /2 \cdot \ \sum_{j,k = 0}^m Q_{j,k} x_j x_k \right) \; .$

We write $$\sqrt{-1}$$ for the imaginary unit, and we use the letters $$i, j, \ldots$$ as indices.

The user may consider a quadratic mapping $$g : \mathbb{F}_2^n \rightarrow \mathbb{C}$$ as a $$2^n$$-dimensional complex vector, regardless of its representation. In C or python its is convenient to write g[i] for the i-th component of such vector g, and to assume that the index $$i = \sum_{j=0}^{n-1} 2^j \cdot i_j$$, $$i_j \in \{0,1\}$$ denotes the bit vector $$(i_{n-1},...i_0)$$ in $$\mathbb{F}_2^n$$. In accordance with that convention we label the entries of the $$m+1 \times n$$ bit matrix $$A$$ as follows:

$\begin{split}A = \left( \begin{array}{lcl} A_{n-1,0} & \ldots & A_{0,0} \\ \vdots & & \vdots \\ A_{n-1,m} & \ldots & A_{0,m} \end{array} \right) \; .\end{split}$

Any affine mapping $$a : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n$$ can be written as $$(x_1,\ldots, x_m) \mapsto (1, x_1,\ldots, x_m) \cdot A$$ for a suitable $$(m + 1) \times n$$ bit matrix $$A$$ as above.

Wie label the entries of the symmetric $$m+1 \times m+1$$ bit matrix $$Q$$ as usual. We stress that all bits $$Q_{j,k}, x_j, x_k$$ in sum in the expression for $$q(x)$$ must be interpreted as integers equal to $$0$$ or $$1$$ (modulo $$4$$). But since $$Q$$ is a symmetric matrix, it suffices to know the off-diagonal entries of $$Q$$ modulo $$2$$ if we assume $$Q_{j,k} = Q_{k,j}$$. Due to the condition $$q(0) = 1$$ we only consider matrices $$Q$$ with $$Q_{0,0} = 0$$. It is easy to check that we can encode any quadratic function $$q: \mathbb{F}_2^m \rightarrow \mathbb{T}$$ as a symmetric $$(m + 1) \times (m + 1)$$ bit matrix $$Q$$ (with $$Q_{0,0} = 0$$) uniquely as above.

Given $$e$$ and matrices $$A, Q$$ as above, we define $$f(e,A,Q) = f(e,a,q)$$, where $$a$$ and $$q$$ are as in the last equation.

We encode a number $$e \in R_8 \setminus \{0\}$$ as an integer $$e'$$ such that $$e = \exp(e' \pi \sqrt{-1} / 4) \cdot 2^{\lfloor e'/16 \rfloor / 2}$$, with $$\lfloor x \rfloor$$ the greatest integer $$\leq x$$. We encode the constant quadratic mapping $$0$$ as a matrix $$A$$ with zero rows.

Changing the representation of a quadratic mapping¶

The representation $$f(e,A,Q)$$ of a quadratic mapping $$q$$ is not unique. In this section we define some elementary operations $$T_{i,j}, X_{i, j}$$ on a triple $$(e, a, Q)$$ that to not change the quadratic mapping $$f(e,A,Q)$$. In the next section we will use these operations to reduce the representation $$f(e,A,Q)$$ to a standard form.

Let $$(b_1, \ldots, b_m)$$ be the standard basis of $$\mathbb{F}_2^m$$. For $$1 \leq i, j \leq m, i \neq j$$, define the linear transformation $$T_{i,j} : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^m$$ by:

$T_{i,j}(b_j) = b_j + b_i \, , \, T_{i,j}(b_k) = b_k \quad \mbox{for} \quad k \neq j \; .$

We also define the (affine) translation $$T_{0,j} : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^m$$ by $$T_{0,j}(x) = x + b_j$$ for all $$x \in \mathbb{F}_2^m$$.

Let $$q'$$ be the quadratic function $$q \circ T_{i,j}$$ given by $$x \mapsto q(T_{i,j}(x))$$. Let $$Q'$$ be the symmetric bit matrix representing $$q'$$. Then for $$i, j > 0, i \neq j$$ we have

$\begin{split}\begin{array}{rcll} Q'_{i,0} = Q'_{0,i} & = & Q_{i,0} + Q_{j,0} + Q_{i,j} + Q_{i,i} \cdot Q_{j,j} \, , \\ Q'_{i,i} & = & Q'_{i,i} + Q_{j,j} \, , \\ Q'_{i,k} = Q'_{k,i} & = & Q_{i,k} + Q_{j,k} & \mbox{for} \quad k > 0, k\neq i \, , \\ Q'_{k,l} & = & Q_{k,l} & \mbox{for all other pairs} \quad (k, l) \; . \end{array}\end{split}$

The quadratic function $$q \circ T_{0,j}, \; j > 0$$ is equal to $$e \cdot q'$$ with $$e = \exp(\pi \sqrt{-1} \cdot(Q_{0,i} + Q_{i,i}/2))$$. Here $$q'$$ is the quadratic function represented by the bit matrix $$Q'$$ with

$\begin{split}\begin{array}{rcll} Q'_{0,0} & = & 0 \, , \\ Q'_{0,k} = Q'_{k,0} & = & Q_{0,k} + Q_{j,k} & \mbox{for} \quad k > 0 \, , \\ Q'_{k,l} & = & Q_{k,l} & \mbox{for all other pairs} \quad (k, l) \; . \end{array}\end{split}$

For an affine mapping $$a: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n$$ the mapping $$a' = a \circ T_{i,j}$$ with $$i \geq 0, j > 0, j \neq i$$ is represented by the matrix $$A'$$ given by:

$\begin{split}\begin{array}{rcll} A'(i, l) & = & A(i, l) + A(j, l) \, , \\ A'(k, l) & = & A(k, l) & \mbox{for} \quad k \neq j \; . \end{array}\end{split}$

This means that adding row and column $$j >0$$ to row and and column $$i \geq 0$$ of a matrix $$Q$$ representing a quadratic function changes that matrix to a matrix $$Q'$$ representing $$Q \circ T_{i,j}$$, up to a scalar factor (which is a fourth root of unity) and some corrections required for the entries $$Q'_{0,j}, Q'_{j,0}$$ and $$Q'_{0,0}$$ of $$Q'$$. Similarly, adding row $$j$$ to row $$i$$ of a matrix $$A$$ representing an affine mapping from $$\mathbb{F}_2^m$$ to $$\mathbb{F}_2^n$$ changes matrix $$A$$ to a matrix representing the affine mapping $$A \circ T_{i,j}$$.

We obviously have $$f(e, A, Q) = f(e, A \circ T_{i,j}, Q \circ T_{i,j})$$. So we may perform a row operation on matrix $$A$$, and also a row and a column operation on matrix Q without changing f(e, A, Q), (up to a few corrections in line and column $$0$$ of $$Q$$).

If $$f(e, A, Q)$$ is in echelon form, (as defined in the following section), then it remains in echelon form after applying an operation $$T_{i,j}, i < j$$.

For $$i, j > 0$$ let $$X_{i,j}$$ be the operation on the triple $$(e, A, Q)$$ that exchanges rows $$i$$ with row $$j$$ of $$A$$ and $$Q$$, and also column $$i$$ with column $$j$$ of $$Q$$. The operation $$X_{i,j}$$ does not change $$f(e, A, Q)$$.

Reducing the representation of a quadratic mapping¶

We call a representation $$(e, A, Q)$$ of a quadratic mapping reduced if the following conditions hold:

• $$A$$ has no nonzero rows.

• Let $$A_1$$ be the matrix obtained from $$A$$ by prepending the column vector $$(1,0,\ldots,0)^\top$$. Then the leading coefficient of a row of $$A_1$$ is always strictly to the right of the leading coefficient of the row above it.

• Each column containing a leading coefficient of a row has zeros in all its other entries.

Here the leading coefficient of a row of matrix $$A$$ is the first nonzero entry in that row. We call the representation $$(e, A, Q)$$ echelonized if only the first two of the three conditions above are satisfied.

Obviously, a reduced or echelonized representation $$(e, A, Q)$$ also injective. It is easy to see that any quadratic mapping has a unique reduced representation.

In this section we present an algorithm for converting a representation of a quadratic function to a reduced representation. Function qstate12_reduce in module qstate12.c implements this algorithm.

A matrix is in row echelon form if

• All rows consisting of only zeros are at the bottom.

• The leading coefficient of a nonzero row is always strictly to the right of the leading coefficient of the row above it.

A matrix $$A$$ is in reduced row echelon form if it is in echelon form, and each column containing a leading coefficient of a row has zeros in all its other entries. See e.g. https://en.wikipedia.org/wiki/Row_echelon_form .

Let $$T_{i,j}, X_{i,j}$$ be as in the last section. In order to reduce a representation $$(e, A, Q)$$ of a quadratic mapping $$f(e, A, Q)$$ we apply several operations $$T_{i,j}, X_{i,j}$$ on the components $$e, A, Q$$. Neither of these two operations changes $$f(e, A, Q)$$.

Given $$A$$, let $$A_1 = A_1(A)$$ be obtained from $$A$$ as above. By applying a sequence of operations $$T_{i,j}$$, $$X_{i,j}$$ we may convert $$A_1$$ to reduced echelon form. If $$A_1$$ is in reduced echelon form and contains no zero rows at the bottom then the representation $$(e, A, Q)$$ is reduced. Otherwise we use the following algorithm repeatedly to remove the zero rows from the bottom of $$A$$.

Let $$i$$ be the index of the last row of $$A$$ and assume $$A_{i,j}=0$$ for all $$j$$.

Let $$i'$$ be the highest index with $$Q_{i,i'}=1$$. If such an $$i'$$ exists then we add row $$i'$$ of $$A$$ to all rows $$k$$ where $$Q_{k,i}=1$$ holds and we adjust $$Q$$. Afterwards we have $$Q_{i',i}=1$$ for at most one index $$i'$$.

Case 1: $$Q_{i',i}=0$$ for all $$i'$$

The we may delete the last row of $$A$$ , adjust $$Q$$, and double $$e$$ without changing $$f(e, A, Q)$$.

Case 2: $$Q_{0,i}=1$$

Then $$f(e, A, Q)$$ is the constant function $$0$$.

Case 3. $$Q_{i',i}=1, 0 < i' < i$$

Then we add row $$i$$ of $$A$$ to all rows $$k \notin \{i,i'\}$$ where $$Q_{k,i'}=1$$ holds and we adjust $$Q$$. Afterwards we have $$Q_{k,i'} = Q_{i',k} = Q_{k,i} = Q_{i,k} = 0$$ for all $$k \notin \{i,i'\}$$, $$Q_{i,i} = 0$$ , and $$Q_{i,i'} = Q_{i',i} = 1$$. So we may delete rows $$i$$ and $$i'$$ of $$A$$, adjust $$Q$$, and double $$e$$ without changing $$f(e, A, Q)$$.

Case 4: $$Q_{i,i}=1$$

Then $$f(e, A, Q)$$ is not changed if we delete the last row $$i$$ of $$A$$, adjust $$Q$$, and multiply $$e$$ by $$1 + \sqrt{-1}$$.

Remark

The algorithm sketched in this subsection yields an alternative proof of Lemma 2.

Let $$g: \mathbb{F}_2^{n} \rightarrow \mathbb{C}$$ be a quadratic mapping with $$g = f(e,A,Q)$$, where $$A$$ is an $$(m+1) \times n$$ and $$Q$$ is an $$(m+1) \times (m+1)$$ bit matrix. Define $$g^{(j)}: \mathbb{F}_2^{n+1}\rightarrow \mathbb{C}$$ by

$g^{(j)}(x_{n},\ldots, x_j, x_{j-1}, \ldots, x_0) = g(x_{n},\ldots, x_{j+1}, x_{j-1}, \ldots, x_0) \; .$

So $$g^{(j)}$$ does not depend on bit $$j$$ of $$x$$.

Then we have $$g^{(j)} = f(e,A',Q')$$ for matrices $$A',Q'$$ defined as follows. $$A'$$ is obtained from $$A'$$ by first appending a zero row at the bottom, and then inserting a zero column to the right of bit position $$j$$. Finally, we change the entry at the bottom of the inserted column from $$0$$ to $$1$$. $$Q'$$ is obtained from $$Q'$$ by appending a zero row at the bottom and a zero column at the right. Then we have

$f(e,A',Q')(x_{n},\ldots, x_j, x_{j-1}, \ldots, x_0) = f(e,A,Q)(x_{n},\ldots, x_{j+1}, x_{j-1}, \ldots, x_0) \; ,$

as required. Function qstate12_extend in module qstate12.c implements the extension of a quadratic mapping.

Products and tensor products of quadratic mappings¶

Let $$g^{(\lambda)}, \lambda = 1, 2$$, be arbitrary complex-valued functions on $$\mathbb{F}_2^{n_\lambda}$$. Let $$V_\lambda$$ be the complex vector space $$(\mathbb{C}^2)^{\otimes {n_\lambda}}$$ of dimension $$2^{n_\lambda}$$. Then $$g^{(\lambda)}$$ has a natural interpretation as a vector in $$V_\lambda$$. Here the basis vectors of $$V_\lambda$$ are labelled by the elements of $$\mathbb{F}_2^{n_\lambda}$$. Any function $$h:\mathbb{F}_2^{n_1 + n_2} \rightarrow \mathbb{C}$$ can be considered as tensor in the space $$V_1 \otimes V_2$$. Then the coordinate of that tensor with respect to the basis vector labeled by $$b_1 \otimes b_2$$ , $$b_\lambda \in \mathbb{F}_2^{n_\lambda}$$, is equal to $$h(b_1, b_2)$$.

For $$\lambda = 1, 2$$ let $$g^{(\lambda)} : \mathbb{F}_2^{n_\lambda} \rightarrow \mathbb{C}$$ be as above. For $$c \leq j \leq \min(n_1, n_2)$$ we define a mapping $$(g^{(1)} \odot g^{(2)})_{j,c} : \mathbb{F}_2^{n_1+n_2-j-c} \rightarrow \mathbb{C}$$ by

$\left(g^{(1)} \odot g^{(2)}\right)_{j,c} \;(x', x_1, x_2) = \sum_{x \in \mathbb{F}_2^c} g^{(1)}(x, x', x_1) \cdot g^{(2)}(x, x', x_2) \; ,$

where $$x' \in \mathbb{F}_2^{j-c}, \; x_\lambda \in \mathbb{F}_2^{n_\lambda-j}$$. We abbreviate $$(g^{(1)} \odot g^{(2)})_{j,0}$$ to $$(g^{(1)} \odot g^{(2)})_{0}$$.

If $$g^{(1)}$$ and $$g^{(2)}$$ are quadratic mappings then $$(g^{(1)} \odot g^{(2)})_n$$ is a quadratic mapping by Lemma 1. Condsidering the corresponding quadratic state vectors we see that $$(g^{(1)} \odot g^{(2)})_0$$ is just the tensor product $$g^{(1)} \otimes g^{(2)}$$ of $$g^{(1)}$$ and $$g^{(2)}$$.

The functions $$g^{(\lambda)}, \lambda = 1, 2$$ defined above may also be considered as tensors in the spaces $$V_0 \otimes V_\lambda$$ with $$V_0 = (\mathbb{C}^2)^{ \otimes j}$$, $$V_\lambda = (\mathbb{C}^2)^{ \otimes n_\lambda - j}$$. Then $$g^{(1)} \otimes g^{(2)} \in V_0 \otimes V_1 \otimes V_0 \otimes V_2$$. We assume that $$V_0$$ is equal to it dual space via the standard Euclidean scalar product. Then we obtain the contraction of $$g^{(1)} \otimes g^{(2)}$$ over the two copies of $$V_0$$ as $$(g^{(1)} \otimes g^{(2)})_{j,j}$$. The result has to be interpreted as a tensor in the space $$V_1 \otimes V_2$$.

The tensors $$g^{(\lambda)}$$ in the space $$V_0 \otimes V^\lambda$$ given above can also be considered as $$2^{j} \times 2^{k_\lambda}$$ matrices $$M_\lambda$$, with $$k_\lambda = n_\lambda - j$$. Then the contraction $$(g^{(1)} \otimes g^{(2)})_{j,j}$$ given above corresponds to the matrix product $$M_1^\top \cdot M_2$$, which is a $$k_1 \times k_2$$ matrix.

In the next two sections we present an algorithm for computing $$(g^{(1)} \odot g^{(2)})_{j,c}$$ for quadratic mappings $$g^{(1)}, g^{(2)}$$. This yields an algorithm for tensor contraction and also for matrix multiplication of quadratic state matrices. Note that the transposition of a quadratic state matrix $$M$$ is a rather simple operation that can be achieved by exchanging columns in the $$A$$ part of a representation $$(e, A, Q)$$ of $$M$$. The functions qstate12_product and qstate12_matmul in module qmatrix12.c implement the operation $$(. \odot .)_{j,c}$$ and the matrix multiplication.

The operator $$(. \odot .)_{j,c}$$ can be implemented in python with the numpy package. Let c1 and c2 be one-dimensional complex numpy arrays of length $$2^{n_1}$$ and $$2^{n_2}$$ corresponding to the vectors $$g^{(1)}$$ and $$g^{(2)}$$, respectively. Then a numpy array c3 corresponding to the vector $$(g^{(1)} \otimes g^{(2)})_{j,c}$$ can be computed as follows:

import numpy as np
c1a = c1.reshape((2**c, 2**(j-c), -1))
c2a = c2.reshape((2**c, 2**(j-c), -1))
c3 = np.einsum("cjk,cjl->jkl", c1a, c2a)
c3 = c3.reshape((-1,))


Without going into details, we remark that in the graphical ZX-calculus (which is used for describing linear maps between qubits) is an appropriate setup for ‘explaining’ the operation $$(. \odot .)_{j,c}$$, see e.g. https://en.wikipedia.org/wiki/ZX-calculus .

An algorithm for multiplying quadratic mappings¶

In this section we present an effective algorithm for computing the product $$g^{(1)} \cdot g^{(2)}$$ of two quadratic mappings $$g^{(1)}, g^{(2)}: \mathbb{F}_2^n \rightarrow \mathbb{C}$$. Such an algorithm is a key ingredient for implementing the operator $$(.\odot.)_{j,c}$$. For $$\lambda = 1,2$$ let $$(e^{(\lambda)}, A^{(\lambda)}, Q^{(\lambda)})$$ be a reduced representation of $$g^{(\lambda)}$$.

We will show that for any $$j \leq n$$ there are quadratic mappings $$g^{(\lambda,j)} = f\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)} \big)$$ with $$g^{(1,j)} \cdot g^{(2,j)}$$ = $$g^{(1)} \cdot g^{(2)}$$, where the first $$j$$ columns of $$A^{(1,j)}$$ and $$A^{(2,j)}$$ are equal, and both, $$A^{(1,j)}$$ and $$A^{(2,j)}$$, are in reduced echelon form. We put $$(e^{(\lambda,0 )}, A^{(\lambda, 0)}, Q^{(\lambda, 0)})$$ = $$(e^{(\lambda)}, A^{(\lambda)}, Q^{(\lambda)})$$.

Assume that $$e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}$$ satisfy the conditions given above. Then we can compute $$\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big)$$ from $$\big(e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\big)$$ as follows:

Case 1: Both, $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$, have a row with leading coefficient in column $$j$$.

Since $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$ are in reduced echelon form and the first $$j-1$$ columns of these two matrices are equal, we conclude that the first $$j$$ columns of $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$ are equal.

So we may put $$\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big) = \big( e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\big)$$ for $$\lambda = 1,2$$.

Case 2: Only $$A^{(1,j-1)}$$ has a row with leading coefficient in column $$j$$.

Assume that this row of $$A^{(1,j-1)}$$ has index $$i$$. We add row $$i$$ to all rows $$k$$ of $$A^{(1,j-1)}$$ where $$A^{(1,j-1)}_{k,j} \neq A^{(2,j-1)}_{k,j}$$. Therefore we apply the operation $$T_{i,k}$$ defined in section Changing the representation of a quadratic mapping. So we obtain a representation $$f\big(e^{(1,j-1)'}, A^{(1,j-1)'}, Q^{(1,j-1)'}\big)$$ of $$g^{(1,j-1)}$$, where the first $$j$$ columns of $$A^{(1,j-1)'}$$ and $$A^{(2,j-1)}$$ are equal, except for the coefficient in row $$i$$, column $$j$$.

We obtain $$A^{(1,j)}$$ from $$A^{(1,j-1)'}$$ by deleting row $$i$$ of $$A^{(1,j-1)'}$$, and $$Q^{(1,j)}$$ from $$Q^{(1,j-1)'}$$ by deleting row and column $$i$$. We put $$e^{(1,j)} = e^{(1,j-1)'}$$. We put $$\left(e^{(2,j)},A^{(2,j)},Q^{(2,j)}\right)$$ = $$\left(e^{(2,j-1)},A^{(2,j-1)},Q^{(2,j-1)}\right)$$.

By construction, matrix $$A^{(1,j)}$$ is in reduced echelon from and the first $$j$$ columns of $$A^{(1,j)}$$ and $$A^{(2,j)}$$ are equal.

It remains to show that deleting row $$i$$ of matrix $$A^{(1,j-1)'}$$ does not change $$g^{(1)} \cdot g^{(2)}$$.

Let $$D^{(\lambda)}$$ be the submatrix of $$A^{(\lambda,j-1)'}$$ that consists of the first $$j$$ columns of $$A^{(1,j-1)'}$$. For computing $$g^{(1)} \cdot g^{(2)}$$ we only have to consider rows of matrix $$D^{(1)}$$ that are linear combinations of rows of matrix $$D^{(2)}$$, excluding row $$0$$ of both matrices. By construction, $$D^{(1)}$$ and $$D^{(2)}$$ are in reduced echelon form, row $$i$$ of $$D^{(1)}$$ has its leading coefficient in column $$j$$, and in $$D^{(2)}$$ there is no row with leading coefficient in column $$j$$. Thus row $$i$$ of $$D^{(1)}$$ is not a linear combination of the rows of $$D^{(2)}$$, ignoring row $$0$$ of $$D^{(2)}$$.

Case 3: Only $$A^{(2,j-1)}$$ has a row with leading coefficient in column $$j$$.

This case is symmetric to case 2, exchanging the role of $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$.

Case 4: Neither $$A^{(1,j-1)}$$ nor $$A^{(2,j-1)}$$ has a row with leading coefficient in column $$j$$.

Case 4.1: Columns $$j$$ of $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$ are equal.

Then we may proceed as in case 1.

Case 4.2: Column $$j$$ of $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$ are equal except in row $$0$$.

Assume that $$x^{(1)}$$ is in the support of $$g^{(1,j-1)}$$, $$x^{(2)}$$ is in the support of $$g^{(2,j-1)}$$, and that the leftmost $$j-1$$ bits of $$x^{(1)}$$ and $$x^{(2)}$$ are equal. Then from the properties of $$A^{(1,j-1)}$$ and $$A^{(2,j-1)}$$ we conclude that $$x^{(1)}$$ and $$x^{(2)}$$ must differ in the bit at position $$j$$. Thus $$g^{(1,j-1)} \cdot g^{(2,j-1)}$$ is the constant function $$0$$, and we may put $$e^{(1,j)} = e^{(2,j)} = 0$$.

Case 4.3: There is an $$i>0$$ with $$A^{(1,j-1)}_{i,j} \neq A^{(2,j-1)}_{i,j}$$.

Let $$i$$ be the highest row index such that $$A^{(1,j-1)}_{i,j} \neq A^{(2,j-1)}_{i,j}$$ holds.

For $$\lambda = 1,2$$ we add row $$i$$ to all rows $$k$$ of $$A^{(\lambda,j-1)}$$ where $$A^{(1,j-1)}_{k,j} \neq A^{(2,j-1)}_{k,j}$$ by applying operations $$T_{i,k}$$.

So we obtain a representation $$f\big(e^{(1,j-1)'}, A^{(1,j-1)'}, Q^{(1,j-1)'}\big)$$ of $$g^{(1,j-1)}$$, where the first $$j$$ columns of $$A^{(1,j-1)'}$$ and $$A^{(2,j-1)}$$ are equal, except for the coefficient in row $$i$$, column $$j$$.

For $$j = 1, 2$$ we obtain $$A^{(\lambda,j)}$$ from $$A^{(\lambda,j-1)'}$$ by deleting row $$i$$ of $$A^{(\lambda,j-1)'}$$. We obtain $$Q^{(\lambda,j)}$$ from $$Q^{(\lambda,j-1)'}$$ by deleting row and column $$i$$. We put $$e^{(\lambda,j)} = e^{(\lambda,j-1)'}$$.

A similar argument as in case 2 shows that matrices $$A^{(1,j)}$$ and $$A^{(2,j)}$$ are as required and that deleting row $$i$$ from $$A^{(1,j-1')}$$ and $$A^{(2,j-1')}$$ does not change $$g^{(1)} \cdot g^{(2)}$$.

Now we may compute the product of $$g^{(1)}$$ and $$g^{(2)}$$ as follows:

$g^{(1)} \cdot g^{(2)} = g^{(1,n)} \cdot g^{(2,n)} = f\big( e^{(1,n)} \cdot e^{(2,n)}, A^{(1,n)}, Q^{(1,n)} \odot Q^{(2,n)} \big) \; .$

If the symmetric $$(m+1) \times (m+1)$$ bit matrices $$Q^{(\lambda)}, \lambda = 1,2$$, represent the quadratic functions $$q^{(\lambda)} : \mathbb{F}_2^m \rightarrow\mathbb{T}$$, then we define $$Q^{(1)} \odot Q^{(2)}$$ as the symmtric $$(m+1) \times (m+1)$$ bit matrix representing the quadratic function $$q^{(1)} \cdot q^{(2)}$$. The entries $$Q^{(1 \odot 2)}_{i,j}$$ of $$Q^{(1)} \odot Q^{(2)}$$ can be computed as follows:

$\begin{split}\begin{array}{ll} Q^{(1 \odot 2)}_{i,j} = Q^{(1)}_{i,j} + Q^{(2)}_{i,j} & \quad \mbox{for} \quad i, j > 0 \; , \\ Q^{(1 \odot 2)}_{i,0} = Q^{(1 \odot 2)}_{0,i} = Q^{(1)}_{0,i} + Q^{(2)}_{0,i} + Q^{(1)}_{i,i} \cdot Q^{(2)}_{i,i} & \quad \mbox{for} \quad i > 0 \; , \\ Q^{(1 \odot 2)}_{0,0} = 0 \; , \end{array}\end{split}$

The corrections in row and column $$0$$ of $$Q^{(1 \odot 2)}$$ are necessary, since the diagonal entries of $$Q^{(1)}$$ are to be interpreted modulo $$4$$.

So our algorithm allows us to multiply guadratic mappings effectively.

Remark

In certain cases we have to compute $$\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big)$$ from $$\big(e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\big)$$; and we have the additional information that e.g. the factor $$g_1$$ of the product $$g_1 \cdot g_2$$ is a quadratic mapping that does not depend on qubit $$i$$. Then the part $$A^{(1,j-1)}$$ of the representation of $$g^{(1,j-1)}$$ always has a row $$i$$ such that $$A^{(1,j-1)}_{i,j}$$ is the only nonzero entry in row $$i$$ and in column $$j$$ of $$A^{(1,j-1)}$$. Furthermore, row $$i$$ and column $$j$$ of $$Q^{(1,j-1)}$$ are zero in that case. Thus only cases 1 and 2 can occur in the above computation, and adding row $$i$$ of $$A^{(1,j-1)}$$ to any other row in that matrix affects column $$j$$ of $$A^{(1,j-1)}$$ only, and does not affect $$Q^{(1,j-1)}$$. In our implmentation we make use of this simplification wherever appropriate.

Computing tensor and matrix products¶

In this section we explain how to compute the operator $$(. \odot ,)_{j,c}$$. For $$\lambda = 1,2$$ let $$g^{(\lambda)} : \mathbb{F}_2^{n_\lambda}$$ be quadratic mappings and $$0 \leq c \leq j \leq \min(n_1, n_2)$$. We first show how to compute a representation of $$(g^{(1)} \odot g^{(2)})_{j}$$ from the representations of $$g^{(1)}$$ and $$g^{(2)}$$.

For actually computing $$(g^{(1)} \odot g^{(2)})_j$$ we may extend the mapping $$g^{(1)}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1-j} \rightarrow \mathbb{C}$$ to a mapping $$g^{(1')}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1-j} \times \mathbb{F}_2^{n_2-j} \rightarrow \mathbb{C}$$, with $$g^{(1')}$$ not depending on the last factor $$\mathbb{F}_2^{n_2-j}$$, as described in one of the last sections. Similarly, we may extend $$g^{(2)}$$ to a mapping $$g^{(2')}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1-j} \times \mathbb{F}_2^{n_2-j} \rightarrow \mathbb{C}$$, with $$g^{(2')}$$ not depending on the factor $$\mathbb{F}_2^{n_2-j}$$ in the middle. Then we simply have $$(g^{(1)} \odot g^{(2)})_j = g^{(1')} \cdot g^{(2')}$$.

Using the techniqes discussed in section Extending a quadratic mapping and in the last section we can compute a representation of $$(g^{(1)} \odot g^{(2)})_j$$ from representations of $$g^{(1)}$$ and $$g^{(2)}$$.

It remains to compute $$(g^{(1)} \odot g^{(2)})_{j,c}$$ from $$(g^{(1)} \odot g^{(2)})_{j}$$. We have

$\big(g^{(1)} \odot g^{(2)}\big)_{j,c}(x) = \sum_{y \in \mathbb{F}_2^c} \big(g^{(1)} \odot g^{(2)}\big)_{j}(y, x) \quad \mbox{for} \quad x \in \mathbb{F}_2^{n_1+n_2-j-c} \; .$

Let $$h : \mathbb{F}_2^n \rightarrow \mathbb{C}$$ be a quadratic mapping with representation $$(e, A, Q)$$, and define $$h_c : \mathbb{F}_2^{n-c} \rightarrow \mathbb{C}$$ by $$x \mapsto \sum_{y \in \mathbb{F}_2^{c}} h(y,x)$$. Then $$h_c$$ is a quadratic mapping with representation $$(e, A_c, Q)$$, where $$A_c$$ is obtained from $$A$$ by deleting the leftmost $$c$$ columns of $$A$$.

So we may easily compute $$(g^{(1)} \odot g^{(2)})_{j,c}$$ from $$(g^{(1)} \odot g^{(2)})_{j}$$.

For any function $$g: \mathbb{F}_2^{n} \rightarrow \mathbb{C}$$ define $$\hat{g}^{(j)}: \mathbb{F}_2^{n}\rightarrow \mathbb{C}$$ by

$\begin{split}\hat{g}^{(j)}(x_{n-1},\ldots, x_j, \ldots, x_0) = \left\{ \begin{array}{ll} g(x_{n-1},\ldots, x_j, \ldots, x_0) & \quad \mbox{if} \quad x_j = 0 \\ 0 & \quad \mbox{if} \quad \mbox x_j = 1 \end{array} \right.\end{split}$

Then $$\hat{g}^{(j)} = g \cdot \hat{\chi}^{(j)}$$, where $$\hat{\chi}^{(j)} : \mathbb{F}_2^{n} \rightarrow \mathbb{C}$$ is a projection function given by $$(x_{n-1},\ldots, x_j, \ldots, x_0) \mapsto 1 - x_j$$. It is easy to find a representation of the quadratic mapping $$\hat{\chi}^{(j)}$$ so that we can compute a representation of $$\hat{g}^{(j)}$$ from a representation of a quadratic mapping $$g$$. This computation is implemented in function qstate12_restrict_zero in module qstate12.c.

Function $$\hat{g}^{(j)}$$ corresponds to a certain kind of a restriction of the function $$g$$. Let $$g$$ be a quadratic mapping and $$(e, A, Q)$$ be a representation of $$\hat{g}^{(j)}$$. Let $$V = \mathbb{F}_2^{n-1-j} \times \{0\} \times \mathbb{F}_2^{j}$$. Let $$g\mid_V$$ be the restriction of $$g$$ to $$V$$. Then $$(e, A_j, Q)$$ is a representation of the restriction $$g\mid_V$$, where $$A_j$$ is the matrix obtained from matrix $$A$$ by deleting column $$j$$. Function qstate12_restrict in module qstate12.c computes a representation of $$g\mid_V$$ from a representation of $$g$$.

The restriction of a quadratic mapping discussed in this section can be used for describing a measurement of a stabilizer state on a quantum computer, see e.g. [AG04].

A quadratic state matrix $$S$$ of shape $$(n_0, n_1)$$ is an element of the tensor product $$V_0 \otimes V_1$$ with the basis vectors of $$V_k$$ being indexed by $$\mathbb{F}_2^{n_k}, k = 0, 1$$, such that the coordinate function of $$S$$ is a quadratic mapping. That coordinate function is a function $$\mathbb{F}_2^{n_0} \times \mathbb{F}_2^{n_1} \rightarrow \mathbb{C}$$.

Thus $$S$$ corresponds to a complex $$2^{n_0} \times 2^{n_1}$$ matrix. We may implement $$S$$ as a quadratic state vector of $$n_0 + n_1$$ qubits, augmented by an information about its shape $$(n_0, n_1)$$ . We let the $$n_0$$ qubits with high indices correspond to the rows of $$S$$; and we let the $$n_1$$ qubits with low indices correspond to the columns of $$S$$.

In python we implement a quadratic state matrix as a instance of class QStateMatrix in module mmgroup.structures.qs_matrix. A matrix of shape $$(0,n)$$ corresponds to a row vector of dimension $$2^{n}$$ and a matrix of shape $$(n,0)$$ corresponds to a column vector of dimension $$2^{n}$$. We have seen above that the unitary quadratic state matrices of shape $$(n,n)$$ form the Clifford group $$\mathcal{X}_{n}$$. We have also discussed fast algorithms for multiplication and inversion of such matrices. So class QStateMatrix supports fast computation in Clifford group $$\mathcal{X}_{n}$$ for $$n \leq 12$$, which is sufficient for computing in the subgroup $$2^{1+24}.\mbox{Co}_1$$ of the monster group.

On the C level, a quadratic state matrix is implemented as a structure of type qstate12_type as defined in file clifford12.h. E.g. function qstate12_matmul in file qmatrix12.c multiplies two such quadratic state matrices.

For practical calculations with quadratic state matrices it is vital to keep the following correspondences in mind.

Let $$S$$ be a $$2^{n_0} \times 2^{n_1}$$ quadratic state matrix. We put $$n = {n_0}+ {n_1}$$. We implement Let $$S$$ as a quadratic state vector $$V = f(e, A, Q)$$, where $$A$$ is a $$m \times n$$ bit matrix and $$Q$$ is a symmetric $$m \times m$$ bit matrix $$Q$$. So entry $$S[i_0, i_1]$$ corresponds to entry $$i_0 \cdot 2^{n_1} + i_1$$ of that quadratic state vector $$V$$ for $$0 \leq i_0 < 2^{n_0}$$ and $$0 \leq i_1 < 2^{n_1}$$. Also, entry $$i$$ of the quadratic state vector $$V$$ corresponds to a row vector of $$n$$ bits containg the binary representation of $$i$$.

We concatenate matrices $$A$$ and $$Q$$ to a $$m \times (n + m)$$ bit matrix $$M$$ with $$M[i,j] = A[i,j]$$ and $$M[i,j+n] = Q[i,j]$$. In C and in python we implement the bit matrix as an array of unsigned 64-bit integers, so that bit $$M[i,j]$$ corresponds to bit $$j$$ (of valence $$2^j$$) of entry $$i$$ of that array.

Displaying quadratic state vectors and matrices¶

We use the bra-ket formalism to display quadratic state vectors. We display a column unit vector as a ket. E.g. |1011> means the column unit vector labelled by the bit vector $$(1,0,1,1)$$ in $$(\mathbb{C}^2)^{\otimes 4}$$. This corresponds to a state where the qubits with indices $$3,2,1,0$$ have values $$1,0,1,1$$ , respectively. Similarly, we display a row vector as a bra. So e.g. <110| means the row unit vector labelled by $$(1,1,0)$$. A $$2^4 \times 2^3$$ matrix with an entry one in the row labelled by $$(1,0,1,1)$$ and the column labelled by $$(1,1,0)$$, and zeros elsewhere, is displayed as |1011><110|.

We also want to display certain linear combinations of such unit vectors or matrices. As we have seen earlier, the coordinate function of such a state vector in $$(\mathbb{C}^2)^{\otimes n}$$ is a function $$\mathbb{F}_2^n \rightarrow \mathbb{C}$$. We only consider state vectors where the support of the coordinate function is an affine subspace of $$\mathbb{F}_2^n$$, and where the nonzero coordinates are in the set $$\{\pm 1, \pm \sqrt{-1}\}$$, up to a global scalar factor. Furthermore, the nonzero coordinates must be given by a certain quadratic form $$Q$$ that we will specify below.

The support of the coordinate function is an affine subspace $$a_0 + V$$, where $$a_0 \in \mathbb{F}_2^n$$ and $$V$$ is a linear subpace of $$\mathbb{F}_2^n$$ with a basis, say, $$(a_1,\ldots a_m)$$. In order to specify the support of the coordinate function, we write $$a_0$$ in bra-ket notation as above, and we write coordinates $$a_1,\ldots,a_m$$ underneath the coordinate $$a_0$$ without any bras or kets. We may give the basis $$(a_1,\ldots, a_m)$$ in echelon form, omitting leading zeros. We write $$A$$ for the with row vectors $$(a_0,\ldots,a_m)^\top$$.

We write a lower triangular matrix $$Q$$ with diagonal entries '.' or 'j' and off-diagonal entries entries '+' or '-' to the left of the coordinate matrix $$A$$. Here an entry '-' means $$-1$$, 'j' means $$\sqrt{-1}$$, and anything else means $$1$$. We write $$q_{i,j}$$ for the entries of the matrix matrix $$Q$$. Then we put:

$f(A, Q) = \sum_{x = (x_0,\ldots,x_m) \in \{0,1\}^{m+1}, x_0 = 1} \! \! \! Q(x) \cdot \left| \oplus_{k=0}^m x_k \cdot a_k \right> \, , \quad Q(x) = \prod_{i, j = 0}^m q_{i,j}^{x_i \cdot x_j} \, .$

We use the same notation if the values $$a_i$$ are kets or matrices witten in the form |ket><bra|. For example:

.   |10><01|
-.    1  10
-+j       1


means $$1 \cdot \left|10\right> \left<01\right| - 1 \cdot \left|11\right> \left<11\right| - \sqrt{-1} \cdot \left|10\right> \left<00\right| + \sqrt{-1} \cdot \left|11\right>\left<10\right|$$.

E.g. the coefficient in the third term of that sum is computed as:

$\begin{split}Q(1,0,1) = \textstyle{ (1, 0, 1) \left( \begin{array}{ccc} . & & \\ - & . & \\ - & + & j \end{array} \right) \left( \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \right) = (-1) \cdot \sqrt{-1} = -\sqrt{-1}} \; .\end{split}$

It turns out that up to a scalar factor all elements of the complex Clifford group $$\mathcal{X}_{n}$$ and all stabilizer states can be displayed in that way. So we can display any element of $$\mathcal{X}_{n}$$ and any stabilizer state of $$2n$$ qubits on one page for $$n$$ up to about $$25$$.

We define a special reduced matrix representation $$(e, A, Q)$$ of a quadratic state matrix $$S$$ of shape $$(n_0, n_1)$$ that differs slightly from the reduced representation of a quadratic state vector. That representation satisfies the following conditions:

1. We require that the representation $$(e, A, Q)$$ is echelonized (but not necessarly reduced), as described in section Reducing the representation of a quadratic mapping.

2. Let $$A'$$ be the bit matrix obtained from $$A$$ by removing the leftmost $$n_0$$ columns from $$A$$. We require that a permutation of the rows of matrix $$A'$$, excluding row $$0$$, is in (not necessarily reduced) echelon form.

Note that the first $$n_0$$ columns of the bit matrix $$A$$ correspond to the $$2^{n_0}$$ rows of the complex matrix $$S$$; and that the remaining $$n_1$$ columns of $$A$$ correspond to the $$2^{n_1}$$ columns of $$S$$.

3. Let $$K_0$$ be the set of the rows of the bit matrix $$A$$ such that all bits in the leftmost $$n_0$$ columns of that row are zero. Let $$K_1$$ be the set of the rows of $$A$$ such that all bits in rightmost $$n_1$$ columns of that row are zero. We exclude row $$0$$ from $$K_0$$ and from $$K_1$$.

If the bit matrix $$A$$ has $$m'$$ rows then the bit matrix $$Q$$ is a symmetric $$m' \times m'$$ bit matrix. Let $$Q'$$ be the submatrix of $$Q$$ that consists of all rows with index in $$K_1$$ and of all columns with index in $$K_0$$ .

We require that submatrix $$Q'$$ of $$Q$$ has at most one nonzero entry in each row and in each column.

Note that $$K_0 \cap K_1 = \emptyset$$, since the representation $$(e, A, Q)$$ is echelonized.

We may obtain a reduced matrix representation $$(e, A, Q)$$ of a quadratic state matrix $$S$$ of shape $$(n_0, n_1)$$ as follows:

• Starting from a reduced representation $$(e_0, A_0, Q_0)$$ of a quadratic state vector $$S$$ we may obtain a representation $$(e_1, A_1, Q_1)$$ of the matrix $$S$$ satifying condition (2.) by applying a seqence of transformations $$T_{i,j}, i < j$$. Then $$A_1$$ is also in echelon form. $$T_{i,j}$$ is defined in section Implementation of quadratic mappings.

• We apply a sequence of transformations $$T_{i,j}, i < j$$, with $$i, j \in K_0$$ or $$i, j \in K_1$$ to $$(e_1, A_1, Q_1)$$. These transformations preserve the echelon form of $$A_1$$ and also property (2.). Since $$K_0 \cap K_1 = \emptyset$$, these transformations act as row and column operations on the submatrix $$Q'$$ of $$Q$$. So we may achieve property (3.) by a sequence of such transformations, thus obtaining a suitable representation $$(e, A, Q)$$ of $$S$$.

Using a reduced matrix representation $$(e, A, Q)$$ of a quadratic state matrix $$S$$ has a variety of advantages.

• We can easily compute the rank of $$S$$ as follows:

For $$(e, A, Q)$$ let $$K_0, K_1, Q'$$ be defined as above. Let $$K_2$$ be the subset $$K_1$$ containing all rows of $$A$$ such that the corrsponding row of bit matrix $$Q'$$ is zero. Then the binary logarithm of the rank of $$S$$ is equal to the number of rows of matrix $$A$$ with are neither in $$K_0$$ nor in $$K_2$$. Here we have to exclude row $$0$$ of $$A$$.

We omit the proof of this fact since we do not need it for our purposes.

• That representation can be used for decomposing $$S$$ into a product $$M_1 \cdot H \cdot M_2$$ of quadratic state matrices, where $$M_1, M_2$$ are monomial and $$H$$ is a Hadamard-like matrix. By a Hadamard-like matrix we mean a tensor product of $$2 \times 2$$ unit matrices and matrices $$\left( \begin{smallmatrix}1 & 1 \\ 1 & -1 \end{smallmatrix} \right)$$.

If $$S$$ has shape $$(n,n)$$ then such a decomposition reduces the complexity of multiplying $$S$$ with an arbitrary complex vector form $$O(4^n)$$ to $$O(n \cdot 2^n)$$.

Essentially, we have used such a decomposition for multiplying the non-monimial part of generator $$\xi$$ of the monster $$\mathbb{M}$$ with a vector of our representation of $$\mathbb{M}$$. Since this special case is discussed elsewhere, we do not go into details here.

• In the next section we will introduce the Pauli group $$\mathcal{P}_{n}$$, which is an important normal subgroup of $$\mathcal{X}_{n}$$. Using the reduced matrix representation of an element $$S$$ of $$\mathcal{X}_{n}$$ we can conugate any element of $$\mathcal{P}_{n}$$ with $$S$$ in $$O(n^2)$$ bit operations.

With quadratic state matrices, a general matrix multiplication in the Clifford group $$\mathcal{X}_{n}$$ costs $$O(n^3)$$ bit operations.

Function qstate12_reduce_matrix in file qmatrix12.c converts any representation of a quadratic state matrix to a reduced matrix representation. For the sake of effiency, we relax condition 3 on matrix $$Q'$$ as follows. A permutation of the rows of $$Q'$$ is in echelon form when the columns of $$Q'$$ are reversed.

The Pauli group¶

The Pauli group $$\mathcal{P}_{n}$$ of $$n$$ qubits is the normal subgroup of the Clifford group $$\mathcal{X}_{n}$$ generated by the not gates, the phase $$\pi$$ gates in $$\mathcal{X}_{n}$$, and by the scalar multiples of the unit matrix by a fourth root of unity. It has structure $$\frac{1}{2}(2_+^{1+2n} \times Z_4)$$, exponent $$4$$ and order $$2^{2n+2}$$.

We represent an element of $$\mathcal{P}_{n}$$ as a product of $$2n+2$$ generators. Each generator may have exponent $$0$$ or $$1$$. The sequence of these exponents are stored as a bit vector as follows:

• Bit $$2n+1$$ corresponds to multiplication with the scalar $$\sqrt{-1}$$.

• Bit $$2n$$ corresponds to multiplication with the scalar $$-1$$.

• Bit $$n+i$$ with $$0 \leq i < n$$ corresponds to a not gate applied to qubit $$i$$.

• Bit $$i$$ with $$0 \leq i < n$$ corresponds to a phase $$\pi$$ gate applied to qubit $$i$$.

Factors are ordered by bit positions, with the most significant bit position occuring first. In the C language we represent bit vectors a integers as usual.

All generators commute and have order $$2$$ except for the following cases:

• A phase $$\pi$$ gate anticommutes with a not gate applied to the same qubit, i.e their commutator is the scalar $$-1$$.

• Of course, the scalar $$\sqrt{-1}$$ squares to the scalar $$-1$$.

Functions qstate12_pauli_vector_mul and qstate12_pauli_vector_exp in module qs_matrix.c perform multiplication and exponentiation in the Pauli group $$\mathcal{P}_{n}$$.

Given an element $$p$$ of the Pauli group and a reduced matrix representation $$(e, A, Q)$$ of a unitary quadratic state matrix $$S$$, we can quickly compute the conjugate $$S \cdot p \cdot S^{-1}$$ as follows:

• Right multiply $$S$$ with $$p$$ by applying the appropriate gates to $$S$$. This affects row $$0$$ of the bit matrix $$A$$ and row and column $$0$$ of the symmetic bit matrix $$Q$$ only.

• Restore the original values $$A[0,j]$$ for all $$j < n$$ and the original values $$Q[0,k] = Q[k,0]$$ for all $$k > n$$ by applying appropriate transformations $$T_{0,j}$$ to the modified representation $$(e, A, Q)$$. This does not change the value $$S \cdot p$$ of the complex matrix computed in the previous step. $$T_{0,j}$$ is defined in section Implementation of quadratic mappings.

• We may restore the the remaining original values of row and column $$0$$ of $$Q$$ by applying phase $$\pi$$ gates to $$S$$. These gate operations correspond to a left multiplication with a element $$p_1$$ of the Pauli group.

• We may restore the the remaining original values of row $$0$$ of $$A$$ by applying not gates to $$S$$. These gate operations correspond to a left multiplication with a element $$p_2$$ of the Pauli group.

• Up to a known scalar factor we have obtained an equation $$S = p_2 \cdot p_1 \cdot S \cdot p$$, with $$p_1, p_2$$ in the Pauli group. With this equation the requested conjugation is an easy computation in the Pauli group.

Function qstate12_pauli_conjugate in module qs_matrix.c performs this conjugation.

Applying a gate to a quadratic mapping¶

In the theory of quantum computing we may apply so-called gates to a quadratic state vector in $$(\mathbb{C}^2)^{\otimes n}$$. For our puposes a gate is a linear operation on $$(\mathbb{C}^2)^{\otimes n} = (\mathbb{C}^2)^{\otimes k} \otimes (\mathbb{C}^2)^{\otimes n-k}$$ which may be written as a tensor product of a unitary $$2^k \times 2^k$$ matrix G and a $$2^{n-k} \times 2^{n-k}$$ identitiy matrix for a small number $$1 \leq k \leq 2$$. Here we may permute the factors $$\mathbb{C}^2$$ of $$(\mathbb{C}^2)^{\otimes n}$$ arbitrarily before the decompostion into a tensor product as above.

We state without proofs how to apply a certain gates to a quadratic mapping. The gates listed below generate the Clifford group. Here a quadratic mapping represents a quadratic state vector as before. A quadratic state matrix of shape $$(n_0, n_1)$$ is considered as a quadratic mapping $$\mathbb{F}_2^{n_0} \times \mathbb{F}_2^{n_1} \rightarrow \mathbb{C}$$.

The not gate

A not gate operating in qubit $$j$$ maps a state $$g$$ to a state $$g'$$ with $$g'(x) = g(x + e_j)$$, where $$e_j = (0,\ldots,0,1,0,\ldots,0)$$ and the component $$1$$ is at position j. A not gate operating in qubit $$j$$ is implemented for $$g = f(e,A,Q)$$ by flipping the bit $$A_{0,j}$$. The C function state12_gate_not implements a not gate.

The controlled not gate

A controlled not gate is a gate that negates a target qubit $$j \neq j'$$ controlled by a qubit $$j'$$. Such a gate maps a state $$g$$ to a state $$g'$$ with $$g'(x) = g(x + \langle e_{j'},x \rangle \cdot e_j)$$, where $$\langle .,. \rangle$$ is the scalar product of bit vectors. Such a gate is implemented for $$g = f(e,A,Q)$$ by adding column $$j'$$ of $$A$$ to column $$j$$ of $$A$$. The C function state12_gate_ctrl_not implements a controlled not gate.

The phase $$\phi$$ gate

Applying a phase $$\phi$$ gate to qubit $$j$$ of a state $$g= f(e,A,Q)$$ changes the state $$g$$ to a state $$g'$$ with

$g'(x_{n-1},\ldots,x_j,\ldots,x_{0}) = \exp(\phi x_j \sqrt{-1}) \cdot g(x_{n-1},\ldots,x_j,\ldots,x_{0}) \; .$

We consider only phases $$\phi$$ which are multiples of $$\pi/2$$. For an $$(m+1) \times n$$ matrix $$A$$ let $$A_j$$ be the $$j$$-th column of matrix $$A$$. Let $$A_{-1}$$ be the column vector $$(1,0,\ldots,0)^\top$$ with $$m+1$$ entries. Then a phase $$\pi$$ gate on qubit $$j$$ maps $$f(e,A,Q)$$ to

$f\left( (-1)^{A_{0,j}} \cdot e, A, Q \odot A_{-1} A_j ^\top \odot A_j A_{-1}^\top \right) \; .$

A phase $$\pi/2$$ gate on qubit $$j$$ maps $$f(e,A,Q)$$ to

$f\left( \sqrt{-1}^{A_{0,j}} \cdot e, A, Q \odot A_j A_j ^\top \right) \; .$

Here we consider $$A_j, A_{-1}$$ as a $$(m+1) \times 1$$ matrices, so that the matrix product $$A_j A_{-1}^\top$$ is an $$(m+1) \times (m+1)$$ matrix. Operator $$\odot$$ is as in section Multiplication of quadratic mappings.

The C function qstate12_gate_phi implements phase gate.

The controlled phase $$\pi$$ gate

Applying a controlled phase $$\pi$$ gate to qubits $$j$$ and $$j'$$ of a state $$g= f(e,A,Q)$$ changes the state $$g$$ to a state $$g'$$ with

$g'(\ldots,x_j,\ldots,x_{j'},\ldots ) = (-1)^{x_j x_{j'}} \cdot g(\ldots,x_j,\ldots,x_{j'},\ldots) \; .$

A controlled phase $$\pi$$ gate on qubit $$j$$ and $$j'$$ maps $$f(e,A,Q)$$ to

$f\left( (-1)^{A_{0,j} \cdot A_{0,j'}} \cdot e, A, Q \odot A_j A_{j'}^\top \odot A_{j'} A_j^\top \right) \; .$

The C function qstate12_gate_ctrl_phi implements controlled phase gate.

A Hadamard gate at qubit $$j$$ is a a mapping that changes a quadratic mapping $$g$$ to another quadratic mapping $$1/\sqrt{2} \cdot g'$$ with

$\begin{split}g'(\ldots,x_{j+1},x_j,x_{j+1},\ldots) = \\ g(\ldots,x_{j+1},0,x_{j-1},\ldots) + (-1)^{x_j} \cdot g(\ldots,x_{j+1},1,x_{j-1},\ldots) \; .\end{split}$

We implement the application of a Hadamard gate on qubit $$j$$ to a quadatic mapping $$g$$ represented as $$(e, A, Q)$$ as follows.

We append a zero row at $$A$$ and also a zero row and a zero column at $$Q$$. Let $$i$$ be the index of the appended row and column. Then we change $$Q_{i,k}$$ and $$Q_{k,i}$$ to $$A_{k,j}$$, $$A_{k,j}$$ to $$0$$ for all $$k \neq i$$, and $$A_{i,j}$$ to $$1$$. Let $$A', Q'$$ be the modified matrices $$A', Q'$$. Then we have $$g' = f(e, A', Q')$$.

The C function state12_gate_h implements a Hadamard gate.

Correctness of the implementation of the Hadamard gate

The correctness of that imlpementation can be seen as follows. W.l.o.g we assume that $$j$$ is the last index $$0$$. Let $$x = (x_{n-1},\ldots, x_0) \in \mathbb{F}_2^n$$, $$y = (y_0,\ldots, y_m) \in \mathbb{F}_2^{m+1}$$ with $$y_0 = 1$$, and assume $$y \cdot A = x$$ for the matrix product $$y \cdot A$$. Then

$(y, b) \cdot A' = (x_{n-1},\ldots,x_1,b) \quad \mbox{for} \quad b \in \mathbb{F}_2 \; .$

Let $$q, q'$$ be the quadratic mappings given by $$Q, Q'$$. Then

$q'(y, b) = (-1)^{b \cdot \langle y, A_0 \rangle} \cdot q(y) = (-1)^{b \cdot x_0} \cdot q(y) \; ,$

where $$A_0$$ is the last column of $$A$$. Thus

$f(e, A',Q')(x_{n-1},\ldots, x_0) = g(x_{n-1},\ldots, x_1, 0) + (-1)^{x_0} \cdot g(x_{n-1},\ldots, x_1, 1) \; .$
Computing the trace of a quadratic state matrix¶

We briefly explain the computation of the trace of a quadratic state matrix $$S$$ of shape $$(n, n)$$. Such a matrix is considered as a mapping $$\mathbb{F}_2^{n} \times \mathbb{F}_2^{n} \rightarrow \mathbb{C}$$. So there are $$n$$ qubits corresponding to the rows and $$n$$ qubits corresponding the columns of the matrix.

For $$i = 0, \ldots, n-1$$ we apply a control not gate to the $$i$$-th row qubit, controlled by the $$i$$-th column qubit. This moves the diagonal entries of the matrix $$S$$ to row $$0$$.

Using the techniques described above we may restrict the modified matrix to row 0, and sum up all entries of that row. This leads to a scalar that has the value of the trace of $$S$$.

Class QStateMatrix modelling a quadratic state matrix¶

class mmgroup.structures.qs_matrix.QStateMatrix(*args: Any, **kwargs: Any)

This class models a quadratic state matrix

Quadratic state matrices are described in the API reference in section Computation in the Clifford group.

Parameters
• rows (int or and instance of class QStateMatrix) –

• Binary logarithm of the number of rows of the matrix

• or an instance of class QStateMatrix. Then a deep copy of that instance is created.

• cols (A nonnegative int, if parameter rows is an int) – Binary logarithm of the number of columns of the matrix

• data – The data of the matrix as described below

• mode – Evaluated according as described below

Raise
• TypeError if type(data) is not as expected.

• ValueError if data cannot be converted to an instance of class QStateMatrix.

In terms of the theory of quantum computing, rows, cols = 0, n creates a column vector or a -ket |v> corresponding to a state of of n qubits, and rows, cols = n, 0 creates a row vector or a -bra <v| corresponding to a linear function on a state of n qubits.

If rows == cols == n and the created 2**n times 2**n matrix is invertible, then the matrix is (a scalar multiple of) an element of the complex Clifford $$\mathcal{X}_{12}$$ of n qubits described in [NRS01].

If rows is an instance of this class then a copy of that instance is created.

If rows and cols are integers then data may be:

• None (default). Then the zero matrix is created.

• A list of integers. Then that list of integers must encode a valid pair (A, Q) of bit matrices that make up a state, as described in The subgroup 2^{1+24}.Co_1 of the monster and the Clifford group, subsection Quadratic state matrices. In this case parameter mode is evaluated as follows:

• 1: create matrix Q from lower triangular part

• 2: create matrix Q from upper triangular part

• Anything else: matrix Q must be symmetric.

• An integer v. Then one of the values rows and cols must be zero and the unit (row or column) vector with index v is created. Here a row vector is an 1 times 2**cols and a column vector is a 2**rows times 1 matrix.

As in numpy, matrix multiplication of quadratic state matrices is done with the @ operator and elementwise multiplication of such matrices is done with the * operator. A quadratic state matrix may also be multiplied by a scalar. Here the scalar must be zero or of the form:

$2^{e/2} \cdot w \, , \quad e \in \mathbb{Z}, \; w \in \mathbb{C}, \, w^8 = 1 \; .$

Divison by such a scalar is legal.

A matrix of type QStateMatrix may be indexed with square brackets as in numpy in order to obtain entries, rows, columns or submatrices. Then a complex numpy array (or a complex number) is returned as in numpy. It is not possible to change the matrix via item assignment. So the easiest way to obtain a complex version of an instance qs of type QStateMatrix is to write qs[:,:].

A row or column index has a natural interpretation as a bit vector. In the theory of quantum computation a bit of such a bit vector corresponds to a qubit. Let qs be a quadratic state matrix of shape (m, n) and

$x = \sum_{k=0}^{m-1} 2^k x_k, \; y = \sum_{k=0}^{n-1} 2^k y_k, \, x_k, y_k \in \{0, 1 \}.$

Then qs[x,y] is the entry of matrix qs with row index corresponding to the bit vector $$(x_{m-1},\ldots,x_0)$$ and column index corresponding to the bit vector $$(y_{n-1},\ldots,y_0)$$.

Officially, we support matrices with rows, cols <= 12 only. Methods of this class might work for slightly larger matrices. Any attempt to constuct a too large matrix raises ValueError.

property H

Return conjugate transposed matrix as in numpy

property T

Return transposed matrix as in numpy

conjugate()

Compute complex conjugate of the matrix

Returns

instance of class QStateMatrix.

copy()

Return a deep copy of the matrix

extend(j, nqb, copy=True)

Insert nqb qubits at position j. .

Let qs be the state of shape (n0+n1), and let n = n0 + n1. We change qs to the following state qs' depending on n + nqb qubits:

qs'(x[n-1],...,x[j],y[nqb-1],...,y[0],x[j-1]...,x[0]) = qs(x[n-1],...,x[j],x[j-1]...,x[0]) .

The function returns ket, i.e. a column vector of shape (n + nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

extend_zero(j, nqb, copy=True)

Insert nqb zero qubits at position j.

Let qs be the state of shape (n0+n1), and let n = n0 + n1. We change qs to the following state qs' depending on n + nqb qubits:

qs'(x[n-1],...,x[j],y[nqb-1],...,y[0],x[j-1]...,x[0]) is equal to qs(x[n-1],...,x[j],x[j-1]...,x[0]) if y[0] = ... = y[nqb-1] = 0 and equal to zero otherwise.

The function returns ket, i.e. a column vector of shape (n + nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

gate_ctrl_not(vc, v)

Apply controlled not gates to a state

Change the state qs to a state qs' with qs'(x) = qs(x (+) <vc,x> * v) where '(+)' is the bitwise xor operation, and <.,.> is the scalar product of bit vectors. The result is not reduced. The scalar product of the bit vectors j and jc must be zero. Otherwise the ctrl not operation is not unitary.

Computing qs.gate_ctrl_not(1 << jc, 1 << j), for jc != j, corresponds to applying a controlled not gate to qubit j contolled by qubit jc. This operation is unitary if and only if the scalar product of j and jc is zero.

gate_ctrl_phi(v1, v2)

Apply controlled phase gates to a state

Change the state qs to a state qs' with qs'(x) = qs(x) * (-1)**(<v1,x>*<v2,x>), where <.,.> is the scalar product of bit vectors and '**' denotes exponentiation. The result is reduced if the input is reduced. Computing qs.gate_ctrl_phi(1 << j1, 1 << j2) corresponds to applying a phase pi gate to qubit j2 controlled by qubit j1.

gate_h(v)

Apply Hadamard gates to a state

Apply a Hadamard gate to all qubits j of the state qs (referred by self) with v & (1 << j) == 1. Aplying a Hadamard gate to gate j changes a state qs to a state 1/sqrt(2) * qs', where qs'(..,x[j+1],x_j,x[j-1],..) = qs(..,x[j+1],0,x[j-1],..) + (-1)**(x_j) * qs(..,x[j+1],1,x[j-1],..) . The result is not reduced.

gate_not(v)

Apply not gates to a state

Change the state qs to a state qs' with qs'(x) = qs(x (+) v), where '(+)' is the bitwise xor operation. The result is reduced if the input is reduced. Computing qs.gate_not(1 << j) corresponds to negating qubit j.

gate_phi(v, phi)

Apply phase gate to a state

Change the state qs to a state qs' with qs'(x) = qs(x) * sqrt(-1)**(phi * <v,x>), where <.,.> is the scalar product of bit vectors and '**' denotes exponentiation. The result is reduced if the input is reduced. Computing qs.gate_phi(1 << j, phi) corresponds to applying a phase (phi * pi/2) gate to qubit j.

inv()

Return inverse matrix

Returns an instance of class QStateMatrix. Raise ValueError if matrix is not invertible.

lb_norm2()

Return binary logarithm of squared operator norm.

The operator norm is the largest absolute singular value of the matrix. For a quadratic state matrix this is a power of $$\sqrt{2}$$ or zero.

The function returns -1 if the matrix is zero.

lb_rank()

Return binary logarithm of the rank of the matrix

The rank of a nonzero quadratic state matrix is a power of two. The function returns -1 if the matrix is zero.

order(max_order)

Try to find the order of a matrix

If the matrix m has order e for e <= max_order, i.e. m.power(e) is the unit matrix, then e is returned. Otherwise ValueError is raised.

The function might also succeed if e is slighty larger than max_order. It has run time O(max_order**0.5).

pauli_conjugate(v, arg=True)

Conjugate Pauli group elements by the matrix

The method conjugates an element of the Pauli group or a list of such elements with the quadratic matrix and returns the congugated Pauli group element (or the list of conjugated elements). All Pauli group elements are encoded as in method pauli_vector.

If $$M$$ is mapped to $$M v M^{-1}$$.

Matrix $$M$$ must be in a Clifford group. The function raises ValueError if this is not the case.

In case arg = False the (complex) arguments of the returned Pauli group elements are not computed.

pauli_vector()

Return matrix as a Pauli vector if it is in the Pauli group

We represent an element of the Pauli group $$\mathcal{P}_{n}$$ as a product of $$2n+2$$ generators. Each generator may have exponent $$0$$ or $$1$$. The sequence of these exponents are stored as a bit vector as follows:

• Bit $$2n+1$$ corresponds to multiplication with the scalar $$\sqrt{-1}$$.

• Bit $$2n$$ corresponds to multiplication with the scalar $$-1$$.

• Bit $$n+i$$ with $$0 \leq i < n$$ corresponds to a not gate applied to qubit $$i$$.

• Bit $$i$$ with $$0 \leq i < n$$ corresponds to a phase $$\pi$$ gate applied to qubit $$i$$.

Factors are ordered by bit positions, with the most significant bit position occuring first.

The function returns the bit vector corresponding to this object as an integer. It raises ValueError if the matrix iy not in the Pauli group.

power(e)

Return the e-th power of the matrix

For a matrix m the power with exponent e = 2 is m @ m, and the power with e = -1 is the inverse matrix of m.

reshape(new_shape, copy=True)

Reshape matrix to given shape

Parameters
• new_shape (tuple of two integers) – This shape of the reshaped matrix. It must be a pair of integers. A pair (n0, n1) correponds to a complex 2**n0 times 2**n1 matrix.

• copy (bool) – A deep copy of the reshaped matrix is returned if copy is True (default). Otherwise the matrix is reshaped in place.

new_shape[0] + new_shape[1] = self.shape[0] + self.shape[0] must hold.

If one of the values new_shape[0], new_shape[1] is -1 then the other value is calculated from the sum self.shape[0] + self.shape[1].

restrict(j, nqb, copy=True)

This is method restrict_zero with deletion.

Let qs be the state of shape (n0+n1), and let n = n0 + n1. We change qs to the following state qs' depending on n - nqv qubits:

qs'(x[n'-1],...,x[0]) is equal to qs(x[n'-1],...,x[j],0,...,0,x[-1],...,x[0]).

The function returns ket, i.e. a column vector of shape (n - nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

restrict_zero(j, nqb, copy=True)

Restrict nqb qubits starting at postion j to 0.

Let qs be the state of shape (n0+n1), and let n = n0 + n1. We change qs to the following state qs' depending on n qubits:

qs'(x[n-1],...,x[0]) is equal to qs(x[n-1],...,x[0]) if x[j] = ... = x[j+nqb-1] = 0 and equal to zero otherwise. We do not change the shape of qs.

The output is reduced if the input is reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

rot_bits(rot, nrot, start=0)

Rotate qubit indices of the state matrix qs in place

If the state matrix qs has shape (0,n) or (n,0) we rotate the qubits of qs in place as follows:

For n0 <= i < n0 + nrot we map qubit i to qubit n0 + (i + rot) % nrot. E.g. nrot = 3, rot = 1, n0 = 0 means qubits are mapped as 0->1, 1->2, 2->0.

Here the entries of the state matrix are labelled by bit vectors of length n. Let qs(x[0],...,x[n-1]) be the entry of the state matrix corresponding to the bit vector (x[n-1],...,x[0]).

Then the function changes qs to qs' with qs'(...,x[start+nrot],y[nrot-1],...,y[0],x[start-1],...) = qs(...,x[start+nrot],z[nrot-1],...,z[0],x[start-1],...), where z[j] = y[j - rot (mod 3)].

If the state matrix qs has shape (n0, n1) then we label the entries of state matrix by bit vectors of length n0 + n1, with the n1 highest bits corresponding to the rows of the matrix, and the n0 lowest bits corresponding to the columns of the matrix.

property shape

Get shape of the complex matrix represented by the state

The function returns a pair (rows, cols) meaning that the state corresponds to a complex 2**nrows times 2**ncols matrix.

show(reduced=True)

Return a state as a string.

If reduced is True (default) then the reduced representation of the state is displayed. Otherwise the state is displayed ‘as is’.

The standard conversion of a state to a string, i.e. method __str__(), is equivalent to method show().

sumup(j, nqb, copy=True)

Sum up nqb qubits starting at position j.

Let qs be the state of shape (n0+n1), and let n = n0 + n1. We change qs to the following state qs' depending on n - nqb qubits:

qs'(x[n-1],...,x[j+nqb],x[j-1],...,x[0]) = sum_{x[j+nqb-1],...,x[j]}  qs1(x[nn1-1],...,x[0]) .

The function returns ket, i.e. a column vector of shape (n - nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

trace()

Return the trace of a square matrix.

The trace is returned as an integer, a floating point number, or a complex number.

Exchange qubit arguments the state qs in place

We label the entries of the state matrix qs by bit vectors and define qs(x[n-1],...,x[0]), with n = n0 + n1, (n0, n1) = qs.shape as in method rot_bits.

We exchange qubit j with argument qubit j + sh of the state, if bit j of mask is set. If bit j of mask is set then bit j + sh of mask must not be set. No mask bit at position >= n - sh may be set.

E.g. qs.qstate12_xch_bits(1, 0x11) changes the state matrix qs to a state matrix qs' with qs'(...,x6,x5,x4,x3,x2,x1,x0.) = qs(...,x6,x4,x5,x3,x2,x0,x1).

mmgroup.structures.qs_matrix.qs_unit_matrix(nqb)

Return unit matrix as an instance of class QStateMatrix

The returned unit matrix has shape (nqb, nqb). So it represents a 2**nqb times 2**nqb` unit matrix.

References

AG04(1,2,3,4,5,6)

S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. CoRR, 2004. URL: http://arxiv.org/abs/quant-ph/0406196.

Asc86(1,2,3,4)

M. Aschbacher. Sporadic Groups. Cambridge University Press, New York, 1986.

Con85(1,2,3,4,5,6,7,8,9,10,11,12,13,14)

J. H. Conway. A simple construction of the Fischer-Griess monster group. Inventiones Mathematicae, 1985.

CCN+85(1,2,3,4)

J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson. Atlas of Finite Groups. Clarendon Press, Oxford, 1985.

CS99(1,2,3,4)

J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, New York, 3rd edition, 1999. ISBN 0-387-98585-9.

Iva99

A. A. Ivanov. Geometry of Sporadic Groups I, Petersen and Tilde Geometries. Cambridge University Press, June 1999. ISBN 0521413621.

Iva09(1,2)

A. A. Ivanov. The Monster Group and Majorana Involutions. Cambridge University Press, April 2009. ISBN 0521889944.

LPWW98

S. Linton, R. Parker, P. Walsh, and R. Wilson. Computer construction of the Monster. J. Group Theory, 1:307–337, 1998.

NRS01(1,2,3,4,5,6,7)

G. Nebe, E. M. Rains, and N. J. A. Sloane. The invariants of the clifford groups. IJDCC: Designs, Codes and Cryptography, 2001.

Sey20(1,2,3,4,5,6,7,8,9,10)

M. Seysen. A computer-friendly construction of the monster. arXiv e-prints, pages arXiv:2002.10921, February 2020. arXiv:2002.10921.

Wil03(1,2,3)

R. Wilson. Computing in the monster. In Group, Combinatorics & Geometry, Durham 2001, 327–337. World Scientific Publishing, 2003.

Wil13

R. A. Wilson. The Monster and black-box groups. arXiv e-prints, pages arXiv:1310.5016, October 2013. arXiv:1310.5016.