Analytic solutions in Semi-Definite Programming

Question

From my experience in the application of Semi-definite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example, there are SDPs whose solution is the fidelity of two operators or the trace norm of an operator. Does anyone know of more examples? Or more importantly, is there a general theory behind this notion of analytic solutions?

Answer 1

There are many examples in quantum information and computation where quantities of interest are expressible as optimal values of semidefinite programs. Here are a few beyond those mentioned in the question:

• The optimal probability to correctly distinguish states chosen from a known ensemble is expressible as an SDP. (See arXiv:quant-ph/0205178 .)

• The general adversary bound, which characterizes the number of queries needed to compute a function by a quantum algorithm in the query model, is represented by a semidefinite program for each possible input length of the problem being considered. (See arXiv:1011.3020 for further details and references.)

• There exists a hierarchy of semidefinite programs that characterizes the set of separable density operators. (See arXiv:quant-ph/0308032 .)

• Quantum interactive proof systems and the study of quantum coin-flipping protocols are closely tied to semidefinite programming. Suppose you have an interaction between two parties, say Alice and Bob, who exchange quantum information. If you fix one of the two parties, say Alice, and you ask what the optimal probability is for Bob to force Alice to output a particular result, then you can phrase this optimal probability as a semidefinite program. (There are many references here, including http://dl.acm.org/citation.cfm?id=335387, arXiv:quant-ph/0403193, arXiv:0907.4737, arXiv:quant-ph/0611234, arXiv:1003.0038, arXiv:0711.4114, arXiv:1104.1140 .)

• The optimal probability for cooperating players Alice and Bob to win an XOR game can, through the use of a well-known theorem of Tsirelson, be phrased as a semidefinite program. This leads to a perfect parallel repetition theorem for quantum provers in XOR proof systems. (See arXiv:quant-ph/0608146 .)

• The completely bounded trace norm (or diamond norm) of a mapping from matrices to matrices can be expressed as an SDP. This norm is useful for defining a physically motivated measure of distance between quantum channels. (See arXiv:0901.4709 for the SDP.)

These SDPs do not all necessarily have analytic solutions, but they have the same flavor as the examples mentioned in the original question in that they represent interesting and arguably fundamental quantities in quantum information and computation. There are other examples as well -- these just happen to be ones I'm familiar with.

The original question asks if there is a general theory behind the existence of analytic solutions to SDPs. I am not aware of such a theory, and cannot see much hope for one to exist. If you write down a random SDP, there will probably not be a nice closed form for the solution.

The reality, at least as I view it, is that things work in the other direction. The SDPs for the fidelity and trace norm mentioned in the original question were specifically designed to represent those quantities: it is not an accident that the optimal solutions were given by such nice and important functions. If you have another quantity in mind, you might be able to express it as an SDP in a simple way by using some thought to come up with the SDP... but going in the other direction, from an SDP to an analytic solution, seems certain to be hard in general.