644
D. Rosset et al.
software to automate symmetry reduction of SDP optimization problems, with
direct application to quantum information problems. 1
An invariant SDP problem corresponds to a matrix invariant under a group
representation. Following [24], let G be a compact group, with finite dimensional
representation ρ acting on the representation space V = C n :
ρ : G → U (n), g → ρ g ,
(1)
where U (n) is the group of unitary 2 n × n matrices. If a SDP problem is ρ-invariant,
it has a Hermitian matrix X with X = ρ g Xρ
†
g for all g ∈ G, so that X is in the
commutant [25, Sec 1.7] C ρ of the algebra generated by ρ:
C ρ = {X ∈ C
n×n
: [X, ρ g ] = 0, ∀g ∈ G},
[X, ρ g ] = ρ g X − Xρ g .
(2)
The decomposition of ρ into irreducible subrepresentations (irreps) corresponds
to
V = V
1
⊕ . . . ⊕ V
N ,
V
i
= W
i,1
⊕ . . . ⊕ W
i,M i ,
(3)
where the isotypic components V i regroup the subspaces W i,j corresponding to
identical irreps. We write D i = dim W i,j the dimension of the i-th irrep in the
decomposition and M i its multiplicity. There is a unitary U such that ∀g ∈ G:
ˆ
ρ g = Uρ g U
†
=
⎛
⎜
⎝
ˆ
ρ 1
g
. . .
ˆ
ρ I
g
⎞
⎟
⎠ ,
ˆ
ρ
i
g =
⎛
⎜
⎝
ˆ
ρ
i,1
g
. . .
ˆ
ρ
i,M i
g
⎞
⎟
⎠ = M i ⊗ ˆ
ρ
i,1
g ,
(4)
as ˆ
ρ
i,j
g = ˆ
ρ
i,k
g , ∀j, k. By Schur’s lemma [26], the matrix X has the form:
ˆ
X = UXU
†
=
⎛
⎜
⎝
ˆ
X 1
. . .
ˆ
X N
⎞
⎟
⎠ ,
ˆ
X
i
= Ξ
i
⊗ D i ,
(5)
where Ξ i is a M i × M i Hermitian matrix, so X 0 is equivalent to {Ξ i 0} i . 3
1 Noting that a similar approach is currently pursued for conformal bootstrap [22, 23].
2 RepLAB works with nonunitary representations of compact groups too as they can have numerical
advantages. We keep this presentation simple by assuming unitarity.
3 This saves on memory and CPU time requirements. Consider a SDP problem min X tr[CX] such
that X is SDP and tr[A i X] = b i for i = 1, . . . , m. Assume X has dimension n × n with blocks of
size n i so that n = n 1 + . . . + n I . The complexity of standard interior point primal-dual methods
is as follows. For CPU time [27]: when m n, the factoring of the Schur complement matrix
dominates in O(m 3 ). When mλn (which we observe is the common case), Cholesky factorizations
D. Rosset et al.
software to automate symmetry reduction of SDP optimization problems, with
direct application to quantum information problems. 1
An invariant SDP problem corresponds to a matrix invariant under a group
representation. Following [24], let G be a compact group, with finite dimensional
representation ρ acting on the representation space V = C n :
ρ : G → U (n), g → ρ g ,
(1)
where U (n) is the group of unitary 2 n × n matrices. If a SDP problem is ρ-invariant,
it has a Hermitian matrix X with X = ρ g Xρ
†
g for all g ∈ G, so that X is in the
commutant [25, Sec 1.7] C ρ of the algebra generated by ρ:
C ρ = {X ∈ C
n×n
: [X, ρ g ] = 0, ∀g ∈ G},
[X, ρ g ] = ρ g X − Xρ g .
(2)
The decomposition of ρ into irreducible subrepresentations (irreps) corresponds
to
V = V
1
⊕ . . . ⊕ V
N ,
V
i
= W
i,1
⊕ . . . ⊕ W
i,M i ,
(3)
where the isotypic components V i regroup the subspaces W i,j corresponding to
identical irreps. We write D i = dim W i,j the dimension of the i-th irrep in the
decomposition and M i its multiplicity. There is a unitary U such that ∀g ∈ G:
ˆ
ρ g = Uρ g U
†
=
⎛
⎜
⎝
ˆ
ρ 1
g
. . .
ˆ
ρ I
g
⎞
⎟
⎠ ,
ˆ
ρ
i
g =
⎛
⎜
⎝
ˆ
ρ
i,1
g
. . .
ˆ
ρ
i,M i
g
⎞
⎟
⎠ = M i ⊗ ˆ
ρ
i,1
g ,
(4)
as ˆ
ρ
i,j
g = ˆ
ρ
i,k
g , ∀j, k. By Schur’s lemma [26], the matrix X has the form:
ˆ
X = UXU
†
=
⎛
⎜
⎝
ˆ
X 1
. . .
ˆ
X N
⎞
⎟
⎠ ,
ˆ
X
i
= Ξ
i
⊗ D i ,
(5)
where Ξ i is a M i × M i Hermitian matrix, so X 0 is equivalent to {Ξ i 0} i . 3
1 Noting that a similar approach is currently pursued for conformal bootstrap [22, 23].
2 RepLAB works with nonunitary representations of compact groups too as they can have numerical
advantages. We keep this presentation simple by assuming unitarity.
3 This saves on memory and CPU time requirements. Consider a SDP problem min X tr[CX] such
that X is SDP and tr[A i X] = b i for i = 1, . . . , m. Assume X has dimension n × n with blocks of
size n i so that n = n 1 + . . . + n I . The complexity of standard interior point primal-dual methods
is as follows. For CPU time [27]: when m n, the factoring of the Schur complement matrix
dominates in O(m 3 ). When mλn (which we observe is the common case), Cholesky factorizations