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.