In quantum information theory, semidefinite programs are often useful, as one is often interested in the behaviour of linear maps over convex sets. For example, they have very recently been used to compute the completely bounded norm of a linear map [1], prove that QIP = PSPACE [2], and bound a new family of norms of operators [3]. However, if you were to look at the standard form of a semidefinite program provided on the Wikipedia page linked above, you would likely only see some very superficial connections with the standard form of quantum semidefinite programs in references [1-3] — this post aims to bridge that gap and show that the two forms are indeed equivalent (or at the very least outline the key steps in proving they are equivalent).

The “Quantum” Form

Let M_n denote the space of n×n complex matrices. Assume that we are given Hermitian matrices A = A^* ∈ M_n and B = B^* ∈ M_m, as well as a Hermicity-preserving linear map Φ : M_n → M_m (i.e., a map such that Φ(X) is Hermitian whenever X is Hermitian). Then we can define a “quantum” semidefinite program to be the following pair of optimization problems:

In the dual problem, Φ^† refers to the dual map of Phi — that is, the adjoint map in the sense of the Hilbert-Schmidt inner product. It is not surprising that many problems in quantum information theory can be formulated as an optimization problem of this type — completely positive maps (a special class of Hermicity-preserving maps) model quantum channels, positive semidefinite matrices represent quantum states, and the trace of a product of two positive semidefinite matrices represents an expectation value.

The Standard Form

In the more conventional set up of semidefinite programming, we are given matrices D and {G_i} ∈ M_r and a complex vector c ∈ C^s. The associated semidefinite program is given by the following pair of optimization problems:

The interested reader should read on Wikipedia about how semidefinite programs generalize linear programs and how their theory of duality works. It is also important to note that semidefinite programs can be solved efficiently to any desired accuracy by a variety of different solvers, using a number of different algorithms. Thus, once we show that quantum semidefinite programs can be put into this standard form, we will be able to efficiently solve quantum semidefinite programs.

Converting the Quantum Form to the Standard Form

Define a linear map Ψ : M_n → (M_m ⊕ M_n) by

Then the requirement that Ψ(P) ≤ B and P ≥ 0 is equivalent to

The dual map Ψ^† is given by

By putting these last few steps together, we see that our original quantum semidefinite program is of the following form:

The inequality in the dual problem was able to be replaced by equality because of the flexibility that was introduced by the arbitrary positive operator R. Now let {E_a} and {F_a} be families of left and right generalized Choi-Kraus operators for Ψ. Denote the (k,l)-entry of P by p_kl and the (i,j)-entry of E_a or F_a by e_aij or f_aij, respectively. Then

where

Finally, defining x := vec(P) and c := vec(A) (where vec refers to the vectorization of a matrix, which stacks each of its columns on top of each other into a column vector) shows that the quantum primal problem is in the form of the standard primal problem. Some simple linear algebra can be used to show that the quantum dual form reduces to the standard dual form as well.

Downloads:

• QuantumSDP.pdf — PDF version of this blog post

References:

1. J. Watrous, Semidefinite programs for completely bounded norms. Preprint (2009). arXiv:0901.4709 [quant-ph]
2. R. Jain, Z. Ji, S. Upadhyay, J. Watrous, QIP = PSPACE. Preprint (2009). arXiv:0907.4737 [quant-ph]
3. N. Johnston and D. W. Kribs, A family of norms with applications in quantum information theory. Journal of Mathematical Physics 51, 082202 (2010). arXiv:0909.3907 [quant-ph]