Polynomial Reduction by Substitution for Ising Model

Hello,

I'm trying to reduce a problem with the formula found in section 3.5.2 of the problem solving handbook;

P(s1,s2;sz ) = 3 + s1s2 − 2(s1 + s2)sz −s1 − s2 + 2sz

For this penalty term P(-1,-1,1) = 12 and P(-1,-1,-1) = 0 (full results below). The penalty term for binary variables works correctly (table 3.4). I think this is because 0*0=0 but -1*-1=1. Am I correct in thinking the current penalty term for spins is wrong? And would a simple workaround be to convert my Ising problem to QUBO, reduce, then solve? 

Thanks,

Charles

def P(s1,s2,sz):
return 3+s1*s2-2*(s1+s2)*sz-s1-s2+2*sz

print(P(-1,-1,-1))
print(P(-1,-1,1))
print(P(-1,1,-1))
print(P(-1,1,1))
print(P(1,-1,-1))
print(P(1,-1,1))
print(P(1,1,-1))
print(P(1,1,1))
0

Comments

1 comment
  • Hi Charles,

    Apologies for the delayed response!

    Although P(s1,s2;sz ) = 3 + s1s2 − 2(s1 + s2)sz −s1 − s2 + 2sz is the Ising penalty function for a boolean AND operation, you are right we need a different model to perform the higher order polynomial reduction in case of Ising problem.

    Instead of converting your non-quadratic Ising problem to qubo, you can use make_quadratic() function included in the Ocean SDK. This function performs the reduction for you while implicitly adding any auxiliary variables, if needed.

    Here's an example:

    import dimod

    J = {('s1','s2','s3'): 1} 

    bqm = dimod.make_quadratic(J, strength= 1, vartype= dimod.SPIN)

     

    this returns binary quadratic model that utilizes following Ising penalty function P to reduce the triplet interaction into pair-wise, while strength parameter acts as penalty weight (for more details please check here).

    P = -0.5sz-0.5(s2+s3)-aux+0.5(s1+s3)sz+(s1+s3)aux+0.5s1*s3+sz*aux

    here, sz = s1*s3 and aux is the additional auxiliary variable.

     

    I hope this helps! Please let me know if you have any other questions.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post