Semidefinite programming hierarchies for quantum information

The mathematical structure of many quantities of interest in cryptography and information theory can be phrased as multilinear maximization programs. The idea is that the optimization for classical resources is captured by the program with scalar variables, whereas the optimization for quantum resources corresponds to allowing the variables to be matrix-valued. These quantum optimization problems then come in two flavors: one where the dimension is fixed by the problem and one where the underlying dimension is optimized over. In general, strong hardness results are known for either problem, where the latter is not even known to be computable.

In my talk, I will present methods for finding approximate solutions via efficiently computable semidefinite programming lower and upper bounds. By means of a concrete example - the problem of noisy channel coding - I will show how this allows to quantify the difference between classical and quantum information.