PUBO to QUBO: The ancillary parameter

[camillerievan]

If I try to transform a PUBO
x(0) x(1) x(2)

to QUBO, it will give me
6 x(3) + 2 x(0) x(1) - 4 x(0) x(3) - 4 x(1) x(3) + x(2) x(3)

QUESTION 1 = BUT should not the QUBO formula instead be:
-( 6 x(3) + 2 x(0) x(1) - 4 x(0) x(3) - 4 x(1) x(3) ) + x(2) x(3)
and obviously x(3) = x(0) x(1)

QUESTION 2 =
In this case I am assuming that the ancillary*** x(3) was based on
x(3) = x(0) x(1)

the new cost function is this
x(2) x(3)

and the constraint to make QUBO work is
6 x(3) + 2 x(0) x(1) - 4 x(0) x(3) - 4 x(1) x(3)

Is there a way to get the ancillary*** formula?

[jtiosue]

Question 1:

No it should be as is. The point is that if x(0) x(1) != x(3) then there is a positive penalty to the cost function. That way the minimum of the new cost function corresponds to the minimum of the original cost function.

Question 2:

I don't think I fully understand your question. Your interpretation is correct that the new cost function is x(2)x(3) and the rest is added to enforce the ancillary condition that x(3) = x(0) x(1). What do you mean by "get the ancillary formula"?

[camillerievan]

Q1: OK, I agree if you want to minimize. However, is there a way to change the output if I need to maximize? In which case you need to give a negative penalty? So the correct equation to maximize would be -(6 x(3) + 2 x(0) x(1) - 4 x(0) x(3) - 4 x(1) x(3)) + x(2) x(3) .... correct?

Q2: By the 'ancillary formula' I mean that the original cost function has 3 binary values: x_0, x_1, and x_2. Qubovert introduced x_3, for which x_3 = x_0 x_1. I would like to get this formula as well as the penalty functions in 2 separate equations. As parameters of the cost function increase from 3 -> n, the number of these equations I guess increases.

[jtiosue]

1. No, qubovert is set up to always be considering minimization. I do this in much the same spirit as e.g. SciPy optimization. Any maximization problem can always be turned into a minimization problem via a simple minus sign, so to keep things simple SciPy only implements minimization methods. I chose to do the same.
2. At the moment, there is no automatic way to do this in qubovert. But I can explain where the reduction comes from and perhaps that will help. See below. I will think about ways to automatically incorporate this information in qubovert.

The degree reduction is performed in the _reduce_degree method. As you can see here, the constraint that is added is alway the same. Namely, to enforce that z = x*y, we add the penalty function qv.PCBO().add_constraint_eq_AND(z, x, y, lam=func_lam(v)). Unless you provide your own func_lam, it will be set to PUBO.default_lam, which is PUBO.default_lam(v) = 1 + abs(v). Note that here v is the value of the term that x and y are involved in (the reduction is performed term by term). Essentially, one needs the penalty strength lam to be large enough such that the minimum will never violate the constraint z = x*y.

The pairs of variables x, y that are ultimately chosen to be paired (that is, we choose a bunch of variables x1,x2,...,y1,y2,... and then enforce that z1=x1*y1, z2=x2*y2, ...) are stored in the reductions dictionary initialized here.

Alternatively, if you want to yourself choose which variable should be paired, you can supply the pairs keyword to any of the methods (.to_pubo, .to_qubo, etc.). See e.g. here, here, and here.

[camillerievan]

with reference to point 1, yes that's what I usually do, however when I negate the formula I get the following

COST + CONSTRAINT I get a low for example of x_3=0, x_2=1, x_1=0, x_0=0, which is a low of 0 for x_0 x_1 x_2
but negating (COST + CONSTRAINT) the low I get is x_3=1, x_2=1, x_1=0, x_0=0 which is certainly not the maximum of x_0 x_1 x_2

[jtiosue]

@camillerievan The objective function must be negated, not the whole thing. For example, suppose I want to maximize x(0)x(1)x(2). Then I would make a PUBO p as

x = [qv.boolean_var(i) for i in range(3)]
p = - x[0]*x[1]*x[2]

Notice the minus sign. Then to convert it to QUBO, I'd do q = p.to_qubo().

Notice this is very different from doing q = -(x[0]*x[1]*x[2]).to_qubo() which I believe is what you are doing now.

[camillerievan]

Oh! Yes. Thanks a lot. Actually, it makes sense - one need to negate the original cost function!

The binary calculation now looks as follows: