Quadratization

[AndradeTiago]

Currently, the reduce_degree is done inside each toqubo_constraint! call.

If it was done after every constraint is known, it could leverage in the knowledge of how many times each product appears in the model.

[pedromxavier]

reduce_degree is now called quadratize to match the literature we're relying on. Currently we store the objective's PBF and also a vector of PBFs, one for each constraint. Do you suggest quadratizing after assembling the total energy function or before computing the penalization coefficients?

[AndradeTiago]

Good question. I think we should take advantage of things: 1) If we know all terms with degree greater than two, we can quadratize more efficiently since we know how many times each product appears; 2) Some terms may appear in different constraints with opposing sings (e.g.; +x1x2x3 in one constraint and -x1x2x3 in another).

With that in mind, I would recommend quadratizing after assembling the total energy function.

[AndradeTiago]

Another interesting feature would be to choose penalization coefficients in order to cancel out the opposing terms since we can always replace a penalization coefficients by a greater one. However, I think that it is more complex and I prefer to not be done right now since it might result in bigger penalization coefficients and to have an heuristic to choose which terms to cancel.

[pedromxavier]

Item 1) seems very neat. 2) & 3) give me a gut feeling that if there is anything efficient out there, it has to do with disjoint sets and other graph-like peculiar data structures. Somehow looks like what Tries do. By now, I think we should stick to the material @bernalde pointed out and maybe implement a few more of those tricks. Some inference system on chosing which strategy based on degree / density of the polynomial would be a huge step!

[bernalde]

I agree with @pedromxavier in the sense that a more sophisticated way of coming up with quadratization is (a) an area of reasearch by itself and (b) most likely already developed. In the Dattani's book, many approaches are included, in order that the author recommends. I would go ahead and check this answer of the authors (https://or.stackexchange.com/questions/7506/breakthroughs-in-operations-research-since-2010?noredirect=1&lq=1) and implement a couple of them starting with the trivial ones and following the ones that he recommends.
If we then see a better way of quadratizing the constraints, then we have another paper!

[AndradeTiago]

Sure, I agree that we should keep it simple by now and think more about if there's an efficient way to do the complicated parts before implementing them.

[pedromxavier]

I readed @bernalde's pointers again and found the results about aux-less quadratizations very impressive! Many groups found new approaches recently and that makes not so afraid to spend a little time thinking about that later 😄.

[bernalde]

This trick of aux-less quadratization methods is mapping the energy function to something that has the same minima of lower degree (not a trivial task). I think that the first approach in https://arxiv.org/abs/1508.04816 should be the easiest one to follow and implement
Moreover, this repo https://github.com/HPQC-LABS/QuadratizationCode has already a myriad of code (somewhat disorganized) for the quadratizations.
On a slightly related note, I was really surprised when I saw you had already implemented the domain wall approach! It seems to work like a charm in practice https://arxiv.org/abs/2108.12004

[AndradeTiago]

Very interesting. I was worried that it could introduce new inputs with the minimum value, this could lead to false negatives in the constraints violation. However, this is not the case as the papers state this:
"Any input that minimizes the original objective function also minimizes the new one, and no new inputs can minimize the objective function"

I'll read more carefully to understand the method.