Bug: Bounding the entangled value of an extended nonlocal game

[vprusso]

There appears to be a bug in how the entangled value of an extended nonlocal game is calculated. Here is a specific example:

import numpy as np
from toqito.states import basis
from toqito.nonlocal_games.extended_nonlocal_game import ExtendedNonlocalGame


def moe_mub_3_in_2_out_game():
    e_0, e_1 = basis(2, 0), basis(2, 1)

    e_p = (e_0 + e_1) / np.sqrt(2)
    e_m = (e_0 - e_1) / np.sqrt(2)

    dim = 2

    a_out, b_out = 2, 2
    a_in, b_in = 3, 3

    pred_mat = np.zeros([dim, dim, a_out, b_out, a_in, b_in])

    pred_mat[:, :, 0, 0, 0, 0] = e_0 @ e_0.conj().T
    pred_mat[:, :, 1, 1, 0, 0] = e_1 @ e_1.conj().T

    pred_mat[:, :, 0, 0, 1, 1] = e_p @ e_p.conj().T
    pred_mat[:, :, 1, 1, 1, 1] = e_m @ e_m.conj().T

    pred_mat[:, :, 0, 0, 2, 2] = e_m @ e_m.conj().T
    pred_mat[:, :, 1, 1, 2, 2] = e_p @ e_p.conj().T

    prob_mat = 1/3 * np.identity(3)
    
    return prob_mat, pred_mat

prob_mat, pred_mat = moe_mub_3_in_2_out_game()
moe_mub_game = ExtendedNonlocalGame(prob_mat, pred_mat, reps=1)

unent = moe_mub_game.unentangled_value()
ent_lb = moe_mub_game.quantum_value_lower_bound(iters=4, tol=1e-3)
ent_ub = moe_mub_game.commuting_measurement_value_upper_bound()
ns = moe_mub_game.nonsignaling_value()

print(f"Unentangled: {unent}")
print(f"Entangled (lower bound): {ent_lb}")
print(f"Entangled (upper bound): {ent_ub}")
print(f"Non-signaling: {ns}")

Which yields the following output:

Unentangled: 0.6666666647449602
Entangled (lower bound): 0.8726724977845179
Entangled (upper bound): 0.6666666666102078
Non-signaling: 0.8726779963173201

It holds that for extended nonlocal games that unent <= ent_lb <= ent_ub <= ns, so the fact that ent_ub < ent_lb indicates that there is either a problem in the quantum_value_lower_bound or commuting_measurement_value_upper_bound functions.

[anushkrishnav]

I would be happy to take on this task, let me explore what the problem is, whats the expected output if there is any if not let me go over the logic. Can you assign me the issue ?

[vprusso]

Hi @anushkrishnav

Thank you for your interest in this problem.

The current output in the above code yields:

Unentangled: 0.6666666647449602
Entangled (lower bound): 0.8726724977845179
Entangled (upper bound): 0.6666666666102078
Non-signaling: 0.8726779963173201

While the expected output as described above should be

Unentangled: 0.6666666647449602
Entangled (lower bound): 0.6666666647449602
Entangled (upper bound): 0.6666666666102078
Non-signaling: 0.8726779963173201

That is, it doesn't make sense that the entangled lower bound is higher than the unentangled bound.

Does that make sense?

As for assignment, the way we are approaching things is that once you have successfully completed the issue, we will go ahead and assign the issue. So go ahead and dive in, and feel free to let me know if you have any questions!

[anushkrishnav]

Thank you, yeh, I am working on the code as we speak , The upper bound is lower than the lower bound which doesn't make sense, i am looking to see if the problem is in the way upper bound is calculated, will get back if I have any questions !

[vprusso]

Sounds good! Don't hesitate to ask anything, and thank you again for your interest!

[atomgardner]

@vprusso: Something tangential that came up while trying to understand this. Should the sub matrix blocks in npa_constraints be changed to the following? (where m=referee_dim)

-            sub_mat = r_var[i::dim, j::dim]
+            sub_mat = r_var[i*m:(i+1)*m, j*m:(j+1)*m]

These direct NPA constraints (for k=1 at least) don't have any effect on this issue (comment out the whole construction and you'll get the same value.)

[vprusso]

Hey @atomgardner

Thanks for your interest in this issue and for your comment.

Hmm, as you said, this might be a different issue (as changing this doesn't seem to have a difference for k=1).

My pre-coffee answer is that I believe that the indexing as it is would be correct, but to be transparent, another hacker put this together during a UnitaryHack of a prior year, so it's been a little while since I've reviewed the code.

Indeed, the issue mentioned here might be related to this, but I'm not entirely sure. If your observation is correct though, another suspect line would, presumably, be the following:

-             old_sub_mat = r_var[old_i::dim, old_j::dim]
+            old_sub_mat = r_var[i*m:(i+1)*m, j*m:(j+1)*m]

I do appreciate you looking into this as this issue in particular has been a really perplexing one for me, and any help, comments, or anything of the sort would be most appreciated!

[atomgardner]

Interesting. OK. I see now that its pulling the (s,t) entry out of each sub-block—slick.

[diffeo-christopher]

@vprusso Season's greetings! I'm trying to learn some quantum computing and I jumped into the deep end.
I looked at your thesis for the monogamy-of-entanglement code example in MATLAB (Section 6.8, example A.1.6) and am wondering if there is some translation issue between MATLAB and Python/cvxpy that only shows up here for some reason!

I tried some "obvious" things, like the termination condition of the inner loop in quantum_value_lower_bound (I changed it to abs(it_diff) > tol; no avail) and to see how random the random unitary function is, and to see how much the answer depends on the initial random POVMs.

I double-checked the "4 in, 3 out" case from the documentation (success!). I'm currently looking at the lower bounds that __optimize_alice and __optimize_bob generate on each iteration for the current "3 in, 2 out" case. I have an observation and a question:

Observation: many of the generated candidate lower bounds are in fact the expected answer of about 0.66, so the question to me is why it would ever generate anything larger at all. (Of course the correct 0.66 gets maxed with 0.87 which is at least part of the problem).

Question: right now, the two __optimize_* functions have these lines:

               rho, lower_bound = self.__optimize_alice(bob_povms)
                bob_povms, lower_bound = self.__optimize_bob(rho)

The lower_bound returned by __optimize_alice seems to be immediately discarded. Is that intentional? Is there something that could be, or needs to be done with both of those values?

[vprusso]

Seasons greetings, @diffeo-christopher !

Definitely does seem as if you decided to jump into the deep end :)

Let me begin by addressing your question. Yes, it seems awkward that the lower bound of the first optimization is completely ignored. While this is indeed misleading and likely should be refactored for clarity, the purpose of the two optimization problems is to perform an "alternating projection"-type approach where the measurement operators of one party are fixed (initially as random unitaries) and the second party has their measurements as variables in this problem to optimize over. Realistically, we can discard the initial lower bound value as what we care about are the optimized measurements.

You'll notice as well that this same technique is also used. In nonlocal_game.py in similarly named functions. From what I can tell, the test cases in the nonlocal game case pass with that approach. As there are more known nonlocal games than extended nonlocal games, the test cases here are (hopefully) well covered.

So the tl;dr for the question is, yes, the lower bound value is discarded as we are really just after the measurements that are thrown into the second SDP and take the lower bound from that. Likely, we should replace lower_bound with _ in the first call to __optimize_alice for clarity.

Another thing I should mention is that the thesis listing you noted on Discord uses this logic in MATLAB to calculate the lower bound (here). You'll notice that the overall approach and technique are indeed similar.

Presumably, the approach in toqito should mimic that of the one in MATLAB. Indeed the A6 listing (here) invokes that lower bound code and appears to attain the correct answer.

So either there is some subtle difference in the way in which these approaches are being implemented or perhaps something more subtle syntactically between the implementations.

Happy to help out with this one and to field any further questions you may have. Thanks again for your interest, and also happy to provide any specific recommendations to you if you are diving into the world of quantum!