648
D. Rosset et al.
2.1 Sampling from the Commutant Algebra
We first obtain a generic element of the commutant algebra. Compared to other
approaches [34–36], we sample first a generic matrix X from the Gaussian Unitary
Ensemble [37]. This ensures that the distribution is invariant under unitary changes
of basis, and provides guarantees on eigenvalue separation. We then project X on
the commutant subspace. We compute X =
G ρ g Xρ −1
g dμ(g), where μ is the Haar
measure of G. This simplifies to X =
1
|G|
g∈G ρ g Xρ −1
g for finite groups. We thus
reduced the problem of sampling from C ρ to the problem of projecting on C ρ .
To average X over a compact group, we work with an oracle that samples elements from the Haar measure μ. Given an integer ν, we sample sets T 1 , . . . , T ν from
μ, typically with |T i | = 3. We then define X ν = Σ ρ,T ν [Σ ρ,T ν−1 [. . . Σ ρ,T 1 [X]]],
and observe that X ν → X when ν → ∞. We monitor convergence by the
Frobenius norm Δ i =
|X i+1 − X i
| FRO , and fit Δ i ≈ ν +α exp(−βi) (exponential
convergence on top of numerical noise floor ν). We thus reduced the subtask of
sampling from C ρ to the task of sampling from G itself.
For finite groups, we use a trick from [38] where fixed sets {T i } are computed
such that X ν = X exactly for finite ν. Of course, one can always set ν = 1 and
T 1 = G, but in practice much better decompositions are obtained. 4
2.2 Computing the Eigendecomposition of a Hermitian Matrix
We decompose numerically X
= X + X
† into ˆ
X = U X
U † , getting a change
of basis matrix U such that ˆ
X is diagonal. After eigenvalue reordering, ˆ
X has the
form (5) with fully diagonal blocks Ξ i . Due to genericity, no eigenvalue repeats
inside each Ξ i and across them. We thus group equal eigenvalues and denote the
basis of the corresponding eigenspaces by the matrices U 1 , . . . , U M . Then
σ
i
: g → σ
i
g = U
i ρ g (U
i )
†
(9)
are irreducible subrepresentations of ρ. The computational cost of this step is O(n 3 )
if n is the dimension of ρ.
4 For example, every element of the symmetric group S D can be written uniquely as a product
of powers of the cycles (1, 2), (1, 2, 3), . . . , (1, . . . , D), reducing the computational effort from
O(|G|) = O(D!) to O(D 2 ) image computations.
D. Rosset et al.
2.1 Sampling from the Commutant Algebra
We first obtain a generic element of the commutant algebra. Compared to other
approaches [34–36], we sample first a generic matrix X from the Gaussian Unitary
Ensemble [37]. This ensures that the distribution is invariant under unitary changes
of basis, and provides guarantees on eigenvalue separation. We then project X on
the commutant subspace. We compute X =
G ρ g Xρ −1
g dμ(g), where μ is the Haar
measure of G. This simplifies to X =
1
|G|
g∈G ρ g Xρ −1
g for finite groups. We thus
reduced the problem of sampling from C ρ to the problem of projecting on C ρ .
To average X over a compact group, we work with an oracle that samples elements from the Haar measure μ. Given an integer ν, we sample sets T 1 , . . . , T ν from
μ, typically with |T i | = 3. We then define X ν = Σ ρ,T ν [Σ ρ,T ν−1 [. . . Σ ρ,T 1 [X]]],
and observe that X ν → X when ν → ∞. We monitor convergence by the
Frobenius norm Δ i =
|X i+1 − X i
| FRO , and fit Δ i ≈ ν +α exp(−βi) (exponential
convergence on top of numerical noise floor ν). We thus reduced the subtask of
sampling from C ρ to the task of sampling from G itself.
For finite groups, we use a trick from [38] where fixed sets {T i } are computed
such that X ν = X exactly for finite ν. Of course, one can always set ν = 1 and
T 1 = G, but in practice much better decompositions are obtained. 4
2.2 Computing the Eigendecomposition of a Hermitian Matrix
We decompose numerically X
= X + X
† into ˆ
X = U X
U † , getting a change
of basis matrix U such that ˆ
X is diagonal. After eigenvalue reordering, ˆ
X has the
form (5) with fully diagonal blocks Ξ i . Due to genericity, no eigenvalue repeats
inside each Ξ i and across them. We thus group equal eigenvalues and denote the
basis of the corresponding eigenspaces by the matrices U 1 , . . . , U M . Then
σ
i
: g → σ
i
g = U
i ρ g (U
i )
†
(9)
are irreducible subrepresentations of ρ. The computational cost of this step is O(n 3 )
if n is the dimension of ρ.
4 For example, every element of the symmetric group S D can be written uniquely as a product
of powers of the cycles (1, 2), (1, 2, 3), . . . , (1, . . . , D), reducing the computational effort from
O(|G|) = O(D!) to O(D 2 ) image computations.