Abstract
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 tensors and polynomials. 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 and 1310.0017.