# QUBO formulation regarding penalty

During the formulation of a QUBO matrix I have a question regarding penalty formulation. Once I'm done with QUBO formulation such as xi*A*xj where A is the QUBO matrix, xi and xj are binary variables.

However, the variables xi and xj shall satisfy the constraint such as xi+xj1

In this case, I can extend my QUBO formulation to the follows: xi*A*xj+(xi+xj1) where penalty:(xi+xj1)

I would like to know whether my formulation regarding penalty is correct? I suppose yes because once both xi and xj and xj violate the constraint, it will deliver positive energy as penalty, otherwise 0 or negative energy.

On the other hand, based on the documentation regarding problem formulation, the approach to solve inequalities (as penalty) is using slack variable. I think the reason why they do this is they try to solve the problem without building QUBO matrix directly, correct?

• Hi Kai-Chun,

Using `( xi + xj −1 )` as penalty for constraint `xi + xj ≤ 1`, will prefer `xi==0``xj==0` over `xi==1``xj==0` and `xi==0``xj==1`.

I recommend the penalty `( xi * xj )` unless preferring 0,0 over 1,0 and 0,1 was intended.

`QUBO = xi * A * xj + ( xi * xj )Objective = xi * A * xjConstraint = xi + xj ≤ 1where A is the QUBO matrix, and xi and xj are binary variables`

Thank you for your explanation. If I get your idea correctly, i.e. negative energy is always better than zero or positive energy.

However, I still have a question regarding your penalty formulation xi * xj because your penalty value also delivers 0,0 which is the best assignment of both variables. Can you please explain why this penalty term is better?

Thank you for your explanation again!

• Hi Kai-Chun,

Yes, the minimum energy state is preferred.

The following three solutions: (xi==0, xj==0), (xi==0, xj==1) and (xi==1, xj==0) all match the constraint of  xi + xj ≤ 1 . However, since the minimum energy state is preferred, using the penalty (xi + xj - 1) will prefer xi==0, xj==0 over the other two solutions

`penalty (xi + xj - 1)--------------xi==0, xj==0  = -1xi==0, xj==1  = 0xi==1, xj==0  = 0xi==1, xj==1  = 1`

While using the penalty (xi * xj) would weigh all three possible solutions equally

`penalty (xi * xj)--------------xi==0, xj==0  = 0xi==0, xj==1  = 0xi==1, xj==0  = 0xi==1, xj==1  = 1`

• Thank you! Now I understand more.