2
$\begingroup$

I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the values of the SDPs. The CVX package seems to be very straightforward to get up and running, but I'm a bit unsure in how to convert the SDPs in this scenario and how to interpret the results. For completeness and to try to be a bit helpful, the primal and dual problems for the maximization constraint are replicated from the paper below.

Primal Problem:

maximize: $\langle Q_a, X \rangle$

subject to: $Tr_{\mathcal{Y}}(X) = \mathcal{I}_{\mathcal{X}},$

$\qquad \qquad X \in Pos(\mathcal{Y} \otimes \mathcal{X})$

Dual Problem:

minimize: $Tr(Y)$

subject to: $\mathcal{I}_{\mathcal{Y}} \otimes Y \geq Q_a,$

$\qquad \qquad Y \in Herm(\mathcal{X})$

In this case, these are the SDPs which correspond to Bob's maximum probability for winning some quantum protocol between two parties (more information is in the paper, but if you're going to take the time to help me, by all means ask if I can clarify something in a bit more detail). The variables $Q_a$ and $X$ correspond to the Choi-Jamiolkowski representation of the channel for Alice and Bob respectively. My attempt at putting this into MATLAB is as follows:

n = 3;
cvx_begin sdp
    variable Y(n,n) hermitian;
    dual variable X;
    maximize ( trace ( Y ) );
    subject to
       X : kron(eye(n), Y) >= 0;
cvx_end

Since I don't have a partial trace operation, I'm essentially flipping the roles of the primal and dual functions by swapping the maximization and minimization constraints. This may not be the right way to go about it though, so any feedback would certainly be helpful. Basically my understanding is that if you provide the primal problem, CVX is smart enough to solve the corresponding dual (Section 3.7 of the CVX manual).

Running the above works, but yields a status failed result, leading me to think that there is something I'm most likely missing here:

Status: Failed
Optimal value (cvx_optval): NaN
$\endgroup$
  • 1
    $\begingroup$ I have pinged Abel Molina. Hopefully he will have the time to respond. $\endgroup$ – Artem Kaznatcheev Oct 15 '12 at 0:39
  • $\begingroup$ Thank you very much Artem, I sincerely appreciate the effort. $\endgroup$ – Vincent Russo Oct 15 '12 at 1:25
  • 1
    $\begingroup$ It seems to me that this question is asking for how to use a software (MathLab) which I think makes it off-topic for cstheory. $\endgroup$ – Kaveh Oct 15 '12 at 1:36
  • 1
    $\begingroup$ @Kaveh I completely disagree, this is asking how to use a very specialized package of matlab which is heavily used by theorists in quantum info. For instance, see the comments on Abel's answer to Scott's quantum money Q, where he includes code from this package to solve a theory question. That answer is one of the most notable contributions to TP.SE (and now cstheory) that I am aware of. $\endgroup$ – Artem Kaznatcheev Oct 15 '12 at 1:42
  • $\begingroup$ I also disagree. I think this question is better suited here compared to one where the focus is on programming languages. I say this because the question is directly related to a research question in cs theory. Users here are also more likely to know how cvx relates to other aspects of operator theory / quantum information etc. In addition, I'm also inquiring on aspects on the problem directly related to the theory, and not anything related to the code. $\endgroup$ – Vincent Russo Oct 15 '12 at 1:46
5
$\begingroup$

The new SDP that you obtain by replacing minimize by maximize is not necessarily closely related to the first one. Right now the value is infinity, and if you replaced 0 by $Q_a$ on the right side of the constraint, the value is always going to be 0 or infinity (if it's not 0, you can just multiply any solution with positive value by an arbitrary constant, and increase the value).

The way I went about this general issue when solving these SDPs was just implementing the partial trace, and then coding the dual and primal problem separately. The implementation of the partial trace is at https://cs.uwaterloo.ca/~amolinap/prtrace.m, hope it is useful!

$\endgroup$
  • $\begingroup$ Thanks very much for the swift reply, Abel! That clears up my question very well. Thanks again! $\endgroup$ – Vincent Russo Oct 15 '12 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.