RepLAB: A Computational/Numerical Approach to Representation Theory
645
The block-diagonalization of an invariant SDP rests on the following.
Problem 1 Given a description of a compact group G and its representation ρ,
return the change of basis matrix U , the dimensions {D i }, and the multiplicities
{M i } such that (4) and (5) are satisfied.
RepLAB solves this problem as follows. The compact group G is given as an
oracle that samples from the Haar measure on G; for finite groups, a permutation
representation can be provided for faster computations. The representation ρ
is provided as an image function. Our algorithm then returns a floating-point
approximation of the change of basis matrix U along with {D i }, {M i }. Additional
structure is discovered and returned for real representations (see next section).
1 A Tour of RepLAB Features
Let us consider a small toy problem, resulting from a symmetrized moment-based
relaxation [28]. We compute the quantum upper bound on the CHSH expression
I =
ψ
xy (−1) xy A x B y
ψ
, where |ψ is a bipartite quantum state and {A x },
{B y } are ±1-valued Hermitian operators acting on the first and second subsystem,
respectively, for x, y ∈ {0, 1}.
The SDP program corresponds to
MAX4y
s.t. X = C + Ay 0
,
C =
1
1
1
1
1
,
A=
0
1 1
1 −1
1 1
1 −1
,
(6)
where y ∈ R, X is Hermitian and the constraint X 0 means that X is SDP. This
SDP is invariant under the signed permutation matrices ρ g 1 and ρ g 2 :
ρ g 1 =
1
0 1
1 0
1 −1
,
ρ g 2 =
⎛
⎝
1
−1 0
0 −1
−1 0
0 −1
⎞
⎠ ,
(7)
corresponding to the action of the signed permutations [29] g 1 = [1, 3, 2, 4, −5]
and g 2 = [1, −4, −5, −2, 3] where we write a signed permutation using the image
on its domain g = [g(1), g(2), g(3), g(4), g(5)]. The domain is i ∈ {1, . . . , 5}; by
repeated composition, following the convention (g ˙
h)(i) = g(h(i)), these generate
the group G = g 1 , g 2 . We now show how to block diagonalize ρ using RepLAB
and eigenvalue computations usually dominate, in O((n 1 ) 3 + . . . (n I ) 3 ). For memory: the problem
data scales in O(mn 2 ) in the worst-case, but often less due to sparsity. The Schur complement
matrix requires O(m 2 ) storage, and the matrices X and χ require storage in O((n 1 ) 2 +. . .+(n I ) 2 ).
When using our technique, the block-diagonalization of a SDP of size n × n produces a SDP with
blocks of size n
i = M i .
645
The block-diagonalization of an invariant SDP rests on the following.
Problem 1 Given a description of a compact group G and its representation ρ,
return the change of basis matrix U , the dimensions {D i }, and the multiplicities
{M i } such that (4) and (5) are satisfied.
RepLAB solves this problem as follows. The compact group G is given as an
oracle that samples from the Haar measure on G; for finite groups, a permutation
representation can be provided for faster computations. The representation ρ
is provided as an image function. Our algorithm then returns a floating-point
approximation of the change of basis matrix U along with {D i }, {M i }. Additional
structure is discovered and returned for real representations (see next section).
1 A Tour of RepLAB Features
Let us consider a small toy problem, resulting from a symmetrized moment-based
relaxation [28]. We compute the quantum upper bound on the CHSH expression
I =
ψ
xy (−1) xy A x B y
ψ
, where |ψ is a bipartite quantum state and {A x },
{B y } are ±1-valued Hermitian operators acting on the first and second subsystem,
respectively, for x, y ∈ {0, 1}.
The SDP program corresponds to
MAX4y
s.t. X = C + Ay 0
,
C =
1
1
1
1
1
,
A=
0
1 1
1 −1
1 1
1 −1
,
(6)
where y ∈ R, X is Hermitian and the constraint X 0 means that X is SDP. This
SDP is invariant under the signed permutation matrices ρ g 1 and ρ g 2 :
ρ g 1 =
1
0 1
1 0
1 −1
,
ρ g 2 =
⎛
⎝
1
−1 0
0 −1
−1 0
0 −1
⎞
⎠ ,
(7)
corresponding to the action of the signed permutations [29] g 1 = [1, 3, 2, 4, −5]
and g 2 = [1, −4, −5, −2, 3] where we write a signed permutation using the image
on its domain g = [g(1), g(2), g(3), g(4), g(5)]. The domain is i ∈ {1, . . . , 5}; by
repeated composition, following the convention (g ˙
h)(i) = g(h(i)), these generate
the group G = g 1 , g 2 . We now show how to block diagonalize ρ using RepLAB
and eigenvalue computations usually dominate, in O((n 1 ) 3 + . . . (n I ) 3 ). For memory: the problem
data scales in O(mn 2 ) in the worst-case, but often less due to sparsity. The Schur complement
matrix requires O(m 2 ) storage, and the matrices X and χ require storage in O((n 1 ) 2 +. . .+(n I ) 2 ).
When using our technique, the block-diagonalization of a SDP of size n × n produces a SDP with
blocks of size n
i = M i .