# Quantum bound on the CHSH inequality using semidefinite relaxations

Posted on 03 June 2014

The Tsirelson bound on the Clauser-Horne-Shimony-Holt inequality defines the maximum value on quantum correlations in a bipartite system where the two sites have two measurements each, with two possible outcomes .

The problem of finding the maximum quantum violation can be cast as a polynomial optimization problem of noncommuting variables, which in turn is approximated by a hierarchy of semidefinite programming (SDP) relaxations . The probabilities are described by projection operators over normalized states -- we label the projectors by $E_i$. They pairwise belong to measurements $M_k$, where $M_1$ and $M_2$ are on one site of the system, and $M_3$ and $M_4$ are on the other site. Hence, for instance, $E_1, E_2\in M_1$, $E_3, E_4\in M_2$, and so on. The optimization problem becomes

$$\max_{E,\phi} \langle \phi, \sum_{ij} c_{ij} E_i E_j\phi \rangle$$

subject to

$$\begin{split} \|\phi\| & = 1,\\ E_i^\dagger & = E_i & \quad \forall i,\\ E_i E_j & = \delta_{ij}E_i & \quad E_i,E_j \in M_k, \forall k,\\ \sum_i E_i & = 1 & \quad \forall M_k,\\ \lbrack E_i,E_j\rbrack & = 0 &\quad \forall E_i \in M_1\cup M_2, E_j\in M_3\cup M_4. \end{split}$$

We use the latest git version of Ncpol2sdpa to translate the polynomial optimization problem to an SDP , and then we solve it with SDPA. To begin with, we import the necessary functions from Ncpol2sdpa:

In :
from ncpol2sdpa import generate_operators, SdpRelaxation, \
projective_measurement_constraints


We cast the problem in the form of expectation values to get the familiar value of the maximum violation, $2\sqrt{2}$. This requires defining a helper function to generate the expectation values given the projectors and the outcomes:

In :
def expectation_values(M, outcomes):
exp_values = []
for k in range(len(M)):
exp_value = 0
for i in range(len(M[k])):
exp_value += outcomes[k][i]*M[k][i]
exp_values.append(exp_value)
return exp_values


The total number of variables is 8 ($2^2 2^2$). We generate the necessary number of Hermitian variables and divide them into the appropriate measurements:

In :
n_vars = 8
E = generate_operators('E', n_vars, hermitian=True)
M, outcomes = [], []
for i in range(n_vars//2):
M.append([E[2*i], E[2*i+1]])
outcomes.append([1, -1])
A = [M, M]
B = [M, M]


Ncpol2sdpa has a built-in function to generate the constraints for projective measurements. With that, we define the constraints of the optimization problem:

In :
inequalities= []
monomial_substitutions = projective_measurement_constraints(A, B)


The objective function uses the expectation values. We have to take the negative of it, as the SDP solver can only minimize a function. The objective for the maximum violation thus becomes:

In :
C = expectation_values(M, outcomes)
objective = -(C*C + C*C + C*C - C*C)


Setting the relaxation level to one, the solution already converges:

In :
level = 1
sdpRelaxation = SdpRelaxation(E, verbose=2)
sdpRelaxation.get_relaxation(level, objective=objective, inequalities=inequalities,
substitutions=monomial_substitutions)
sdpRelaxation.solve()
print(sdpRelaxation.primal, sdpRelaxation.dual)

The problem has 8 noncommuting Hermitian variables
Calculating block structure...
Estimated number of SDP variables: 44
Generating moment matrix...
Reduced number of SDP variables: 32

-2.8284270121271873 -2.8284272225649443


References

 Clauser, J. F.; Horne, M. A.; Shimony, A. & Holt, R. A. Proposed Experiment to Test Local Hidden-Variable Theories. Physical Review Letters, 1969, 23, 880-884.

 Navascués, M.; Pironio, S. & Acín, A. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 2008, 10, 073013.

 Wittek, P. Ncpol2sdpa -- Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables. arXiv:1308.6029, 2013.

Share on:    