It is not so surprising that quantum mechanics presents hard new problems for optimization. For example, finding the lowest energy configuration of a physical system or simulating its dynamics both become more computationally difficult when we consider quantum systems. Less obvious is that the mathematics of quantum information can yield new methods of analyzing classical hard problems in optimization. In both directions, the link involves optimization problems related to norms of tensors and maximizing polynomials over many variables. I will survey connections in both directions and discuss some promising open problems.
The talk will not assume a background in quantum information theory. It is partly based on arXiv preprints 1205.4484, 1210.6367, 1310.0017 and 1509.05065.