9
$\begingroup$

Inequalities cannot be directly converted into a QUBO form. By inequality, I mean something like this:

0⩽ Expression ⩽ N.

We can introduce a slack variable and convert it to an equality problem:

⟹ Expression + s = N where: s ∈ Z, s ∈ [0,N]

Since the slack variables, being encoded on a quantum computer, can hold only discrete values(0, 1, 2...N) the expression also must be of a discrete nature and be of the same values(0, 1, 2...N) to satisfy the constraint.

How to encode inequality constraints when the expression is discrete but the values of the expression have sporadic (and maybe unknown) intervals(0, 1.2, 1.5, 3.8....N).

$\endgroup$
1
  • $\begingroup$ What do you mean by this sentence: "expression is discrete but the values of the expression have sporadic(and maybe unknown) intervals"? Do you mean that, "Expression" either equal 0 or 1.2 or, ... up to N? $\endgroup$ Commented May 20, 2021 at 16:00

1 Answer 1

1
$\begingroup$

First of all, since you mention D-Wave in the title, I want to mention that the slack variables need to be constrained even further than you showed in your question. Specifically, your $N$ has to be equal to at most 1, meaning that $s \in \{0,1\}$.

So how do you deal with a discrete variable that takes values like: $d \in \{0, 1.2, 1.5, 3.8,....,15\}$? You have to first convert it to binary.

This is done for ternary variables like $t\in \{ -1,0,+1\}$ on page 70 of this PDF, and you can do it for more complicated variables in a similar way!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.