Detecting a rank loop in the NPA hierarchy
Posted on 09 February 2015The NPA hierarchy of semidefinite relaxations often converges at a low level. If this happens, there will be a rank loop in the solution matrix: a part of the solution corresponding to a moment matrix of lower order will have the same rank as the complete matrix. With the upcoming release 1.7 of Ncpol2sdpa, it is possible to calculate the ranks of increasing submatrices of the solution matrix, corresponding to increasing orders of the relaxation. Since the generated SDP is solved by numerical methods, the small inaccuracies often block the detection of a rank loop. Here we detail how we can overcome this problem, using the CHSH inequality in the probability picture as an example.
First, import everything from Ncpol2sdpa:
from ncpol2sdpa import *
Next, we set up the CHSH problem:
A_configuration = [2, 2]
B_configuration = [2, 2]
I = [[ 0, -1, 0 ],
[-1, 1, 1 ],
[ 0, 1, -1 ]]
A = generate_measurements(A_configuration, 'A')
B = generate_measurements(B_configuration, 'B')
substitutions = projective_measurement_constraints(A, B)
objective = define_objective_with_I(I, A, B)
To detect a rank loop, we will need a relatively high level relaxation. We obtain a level-5 relaxation:
level = 5
sdpRelaxation = SdpRelaxation(flatten([A, B]))
sdpRelaxation.get_relaxation(level, objective=objective,
substitutions=substitutions)
Assuming that SDPA is in the path, we solve this relaxation and try to find a rank loop:
sdpRelaxation.solve()
print(sdpRelaxation.find_solution_ranks())
This is not looking good. This list contains the ranks of the increasing submatrices of the solution matrix. Not all is lost, though. The arbitrary-precision flavour of SDPA, SDPA-GMP can overcome the numerical errors, given sufficient amount of time. If the executable is in the path, we can pass the name of the solver to the solve_sdp function:
sdpRelaxation.solve(solver='sdpa',
solverparameters={"executable":"sdpa_gmp", "paramsfile"="params.gmp.sdpa"})
print(sdpRelaxation.find_solution_ranks())
Evidently, the rank loop is there between levels 4 and 5.
