QUBO

[maliheha]

Why this Nup? Because of the quantum hype, there are so many solvers which solve QUBOs heuristically where the input is just a Q matrix. We can consider having this nup with a similar interface.

Does it fall under an existing category?

• Other (General)

What will the API be?

qubo = nupstup.qubo(coeff_matrix=Q)

Where Q is a scipy sparse graph structure. The output is an array of 0/1s.

Additional context Downside: This can encourage comparison of Gurobi with quantum or quantum-inspired solvers for problems where we know QUBO is not necessarily the right form.

[simonbowly]

It would be great to have a specific implementation of a QUBO, but the general case does not really give a lot to discuss on a documentation page. In the same vein, we'd avoid having a nup for MILP where the user passes in matrices and gets back a vector; this can already be done succinctly in gurobipy and doesn't serve as an entry point from outside mathematical programming.

Some alternatives that might be more suitable are:

1. Do we have any domain-specific examples where Gurobi already does well on a QUBO formulation for the problem?
2. Is there a specific real-world problem where practitioners commonly think "I must translate my constraints to a QUBO and and wait for a quantum computer" but where we could show a MIP formulation already makes the problem tractable?

Option (2) could be a really useful entry point for people who have realised that they need optimization but don't yet realise they can already tackle their problem with classical methods :)

[maliheha]

I do not agree that we need a specific application for QUBO. The motivation for proposing this nup was the following:

• There are so many companies who are looking into quantum computing. The interest around quantum and its application is significantly greater than the interest around classical optimization (this is definitely my opinion given my experience being in this field and I might be wrong).
• For the majority of people in the quantum world, optimization means solving QUBOs because this is the only tool that they know and care about. The software wrappers around D-Wave, Microsoft quantum-inspired solvers, Fujitsu Digital Annealer, NTT quantum optic solver only requires a Q matrix. Some of these devices are available through Amazon Braket and Microsoft Azure.
• A company who has already invested a lot of time to get a Q matrix to be able to solve its problem with all of these different quantum (or quantum-inspired) devices would like to use the same matrix to see how Gurobi performs. They are not necessarily interested in learning gurobipy.

I understand your concern about the documentation and yes I agree that adding a QUBO nup can indirectly imply that we are promoting solving QUBOs instead of MIPs. Something that we probably want to avoid.

Anyways, I think we can delete this nup. Sorry, I should have thought more before adding this nup.

[simonbowly]

A company who has already invested a lot of time to get a Q matrix to be able to solve its problem with all of these different quantum (or quantum-inspired) devices would like to use the same matrix to see how Gurobi performs. They are not necessarily interested in learning gurobipy.

I hadn't thought of it that way, and it's a really good point. A little more googling and I came across qubovert, qbsolv, PyQUBO. All these packages have additional complexity related either to sampling of annealer results or converting between formulations. It would be nice to show by contrast an API that "just works".

Let's keep this open for discussion.

[rluce]

While I share the general concerns of "too little away from just using gurobipy on the BQP", I think I have some sympathies for having a QUBO nup. Foremost because I think some people riding the quantum wave simply may not be aware that MILP provides a technology to solve problems today. And if people can just do

from nupstup import qubo

G = <load my graph>
x = qubo(G)

it may well be that the right people get attracted by it.

[simonbowly]

Just had someone at OR22 essentially ask for a QUBO nup ... so @maliheha you're on the money here :)

[simonbowly]

Done with #46