Any ideas on efficient/convenient ways to encode group elements and operations ? In particular, I am interested in reducing strings of elements in a finite group by the group operation. But, I want to use them in other ways, eg get a matrix representation of an element.
For example, Cliffords.jl includes the N-qubit pauli groups, which are the groups generated by {X, Y, Z}^⊗N, where X, Y, Z are Pauli operators. It seems to a be an efficient encoding.
The most performant encoding I have found is an n x n Matrix{Int} (or UInt8 etc.) representing the multiplication table. On the other hand, encoding elements as singleton types increases the time for string reduction by a factor of 10. (Note that these don’t appear to be practical for the N-qubit Pauli groups for arbitrary N. I can’t think of a better encoding than that used in Cliffords.jl.)
Here is an example of these two encodings for the cyclic group of order 3:
# Investigate efficiency of reduction of strings of group elements by the group operation.
# We compare two implementations of the cyclic group of order three:
# 1. group elements are encoded as singleton types. Multiplication table is
# encoded as methods.
# 2. elements are encoded as integers. Multiplication table is
# encoded as a Matrix of integers.
#
# The result: integer encoding is roughly 10x faster.
using BenchmarkTools
using StaticArrays
# Singleton types encoding cyclic group of order 3
struct At end
struct Bt end
struct Idt end
const A = At()
const B = Bt()
const Id = Idt()
const group_elements = (A, B, Id)
get_group_element(i::Integer) = group_elements[i]
groupop(::At, ::At) = B
groupop(::At, ::Bt) = Id
groupop(::Bt, ::Bt) = A
groupop(::Bt, ::At) = Id
groupop(::Idt, ::Idt) = Id
groupop(::Bt, ::Idt) = B
groupop(::Idt, ::Bt) = B
groupop(::At, ::Idt) = A
groupop(::Idt, ::At) = A
# Encode cyclic group of order 3 as integers
# Using UInt8, etc. changes speed by about 10%
const _mult_table = zeros(Int, 3, 3)
const (a, b, id) = (1, 2, 3)
for (x, y, z) in ((a, a, b), (a, b, id), (b, b, a),
(b, a, id), (id, id, id), (b, id, b),
(id, b, b), (a, id, a), (id, a, a))
_mult_table[x, y] = z
end
const mult_table = SMatrix{3,3}(_mult_table)
groupop(x::Integer, y::Integer) = mult_table[x, y]
# Compare reduction of string of elements
function reduction_timing(num_elements::Integer)
a_int = rand(1:3, num_elements)
a_type = get_group_element.(a_int)
res_int = @btime reduce(groupop, $a_int)
res_type = @btime reduce(groupop, $a_type)
get_group_element(res_int) == res_type || error("reductions do not agree.")
return nothing
end
Here is a typical result:
julia> reduction_timing(10)
15.313 ns (0 allocations: 0 bytes)
213.471 ns (0 allocations: 0 bytes)
but I guess the tensor just represent the “canonical form”.