Improving heuristic computational methods for bounding extended nonlocal game values

[vprusso]

Description

There appears to be a mismatch between what is obtained numerically vs. the literature for a given extended nonlocal game. The premise of this example (and additional details of the game) can be found in Section 6.3 in arXiv:1704.07375.

Example

Let $\zeta = \exp(\frac{2 \pi i}{3})$ and consider the following four mutually unbiased bases:

$$ \begin{equation} \begin{aligned} \mathcal{B}_0 &= { e_0,\ e_1,\ e_2}, \\ \mathcal{B}_1 &= { \frac{e_0 + e_1 + e_2}{\sqrt{3}}, \frac{e_0 + \zeta^2 e_1 + \zeta e_2}{\sqrt{3}}, \frac{e_0 + \zeta e_1 + \zeta^2 e_2}{\sqrt{3}} }, \\ \mathcal{B}_2 &= { \frac{e_0 + e_1 + \zeta e_2}{\sqrt{3}}, \frac{e_0 + \zeta^2 e_1 + \zeta^2 e_2}{\sqrt{3}}, \frac{e_0 + \zeta e_1 + e_2}{\sqrt{3}} }, \\ \mathcal{B}_3 &= { \frac{e_0 + e_1 + \zeta^2 e_2}{\sqrt{3}}, \frac{e_0 + \zeta^2 e_1 + e_2}{\sqrt{3}}, \frac{e_0 + \zeta e_1 + \zeta e_2}{\sqrt{3}} }. \end{aligned} \end{equation} $$

Define an extended nonlocal game $G_{MUB} = (\pi,R)$ so that

$$ \begin{equation} \pi(0) = \pi(1) = \pi(2) = \pi(3) = \frac{1}{4} \end{equation} $$

and $R$ is such that

$$ \begin{equation} { R(0|x), R(1|x), R(2|x) } \end{equation} $$

represents a measurement with respect to the basis $\mathcal{B}x$, for each $x \in {0,1,2,3}$. Taking the description of $G{MUB}$, we can encode this as follows.

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

# Define the monogamy-of-entanglement game defined by MUBs.
 prob_mat = 1 / 4 * np.identity(4)

 dim = 3
 e_0, e_1, e_2 = basis(dim, 0), basis(dim, 1), basis(dim, 2)

 eta = np.exp((2 * np.pi * 1j) / dim)
 mub_0 = [e_0, e_1, e_2]
 mub_1 = [
      (e_0 + e_1 + e_2) / np.sqrt(3),
      (e_0 + eta ** 2 * e_1 + eta * e_2) / np.sqrt(3),
      (e_0 + eta * e_1 + eta ** 2 * e_2) / np.sqrt(3),
 ]
 mub_2 = [
      (e_0 + e_1 + eta * e_2) / np.sqrt(3),
      (e_0 + eta ** 2 * e_1 + eta ** 2 * e_2) / np.sqrt(3),
      (e_0 + eta * e_1 + e_2) / np.sqrt(3),
 ]
 mub_3 = [
      (e_0 + e_1 + eta ** 2 * e_2) / np.sqrt(3),
      (e_0 + eta ** 2 * e_1 + e_2) / np.sqrt(3),
      (e_0 + eta * e_1 + eta * e_2) / np.sqrt(3),
 ]

 # List of measurements defined from mutually unbiased basis.
 mubs = [mub_0, mub_1, mub_2, mub_3]
 
 num_in = 4
 num_out = 3
 pred_mat = np.zeros([dim, dim, num_out, num_out, num_in, num_in], dtype=complex)

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

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

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

 pred_mat[:, :, 0, 0, 3, 3] = mubs[3][0] @ mubs[3][0].conj().T
 pred_mat[:, :, 1, 1, 3, 3] = mubs[3][1] @ mubs[3][1].conj().T
 pred_mat[:, :, 2, 2, 3, 3] = mubs[3][2] @ mubs[3][2].conj().T

Now that we have encoded $G_{MUB}$, we can use heuristic techniques to compute upper and lower bounds on the quantum value, as well as computing the unentangled and non-signaling values. Recall that for any extended nonlocal game that

$$ \begin{equation} \omega(G) \leq \omega^*(G) \leq \omega_c(G) \leq \omega_{ns}(G), \end{equation} $$

where, for some extended nonlocal game $G$:

• $\omega(G)$: The unentangled value
• $\omega^*(G)$: The quantum value
• $\omega_c(G)$: The commuting measurement operator value
• $\omega_{ns}(G)$: The non-signaling value

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}")

The output for this is:

Unentangled: 0.65450912
Entangled (lower bound): 0.65455409
Entangled (upper bound/commuting k=1): 0.65451107
Non-signaling: 0.78867612

That is, we have that

$$ \begin{equation} \omega(G_{MUB}) = \frac{3 + \sqrt{5}}{8} \approx 0.65409. \end{equation} $$

It is uncertain what the optimal standard quantum strategy is for this game, but the value of such a strategy is bounded as follows

$$ 2/3 \geq \omega^*(G) \geq 0.6609. $$

Issue

The issue is that the literature states that $2/3 \geq \omega^*(G) \geq 0.6609$, however the upper bound technique is deriving a value that is actually lower than both 2/3 and $0.6609$. As you compute higher levels in the hierarchy, the value should only decrease. The fact that the first level of the hierarchy yields a lower value implies one of two things:

1. The numerical approach is insufficient or incorrect and is not attaining the correct upper bound value or
2. The literature result is incorrect and the true quantum value is equal to the unentangled value (i.e., there is no quantum advantage in this game).

For additional context and conversations around this topic, refer to the #1233, and more specifically, to this comment thread.

[aman-coder03]

hi, @vprusso is this issue still open and available to work on? i would be happy to take it up!!