Linear programming with unitary-equivariant constraints

Understand

Unitary equivariance is a natural symmetry that occurs in many contexts in physics and mathematics.

• Optimization problems with such symmetry can often be formulated as semidefinite programs for a $d^{p+q}$-dimensional matrix variable that commutes with $U^{\otimes p} \otimes \bar{U}^{\otimes q}$, for all $U \in \mathrm{U}(d)$.
• Solving such problems naively can be prohibitively expensive even if $p+q$ is small but the local dimension $d$ is large.
• We show that, under additional symmetry assumptions, this problem reduces to a linear program that can be solved in time that does not scale in $d$, and we provide a general framework to execute this reduction under different types of symmetries.