Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I am trying to formulate a problem as QUBO problem and am not able to transform the inequality constraint.
$$ \sum_i^N x_i \geq 1 $$ into a suitable penalty function. For N = 2, the penalty term can be written as $$ P(1-x_1-x_2+x_1x_2)$$ as mentioned in A Tutorial on Formulating and Using QUBO Models. Can someone help me in generalising the above constraint to equivalent penalty.
It would help if you used slack variables and squared penalties. One way of doing it is by defining the following penalty $$P\left(\sum_{i=1}^{N}x_i - 1 - Z \right)^2,$$ where $Z$ is an integer variable such that $0 \leq Z \leq N-1$.
If you use the D-Wave API, I believe you can easily define an integer (discrete) variable $Z$. If you use something else, you may need to express $Z$ as an expansion of auxiliary binary variables: $$ Z = \sum_{k=0}^{M-1} 2^ky_k + ry_M, $$ where $M = \lfloor \log_2 Z \rfloor$ and $r$ is the remainder so that $Z \leq N-1$. The remainder can be written as $r = N + 1 - 2^M$. For more details on this, see Section 2.4.
Intuitively, whenever $\sum_i x_i \geq 1$, the values of $Z$ make the entire penalty term disappear. However, when $\sum_i x_i =0$, no matter what $Z$ is, we get the penalty $P(1 + Z)^2$.
