  Many problems in information theory can be reduced to optimizations over
matrices, where the rank of the matrices is constrained. We establish a link
between rank-constrained optimization and the theory of quantum entanglement.
More precisely, we prove that a large class of rank-constrained semidefinite
programs can be written as a convex optimization over separable quantum states
and, consequently, we construct a complete hierarchy of semidefinite programs
for solving the original problem. This hierarchy not only provides a sequence
of certified bounds for the rank-constrained optimization problem, but also
gives pretty good and often exact values in practice when the lowest level of
the hierarchy is considered. We demonstrate that our approach can be used for
relevant problems in quantum information processing, such as the optimization
over pure states, the characterization of mixed unitary channels and faithful
entanglement, and quantum contextuality, as well as in classical information
theory including the maximum cut problem, pseudo-Boolean optimization, and the
orthonormal representation of graphs. Finally, we show that our ideas can be
extended to rank-constrained quadratic and higher-order programming.
