QUBOgen

• QUBO matrix generator on major combinatorial optimization problems written in Python

Installation

$ pip install qubogen

Examples

Number Partitioning

How to partition a given multiset of numbers into two subsets S1, S2 such that |sum(S1) - sum(S2)| is as small as possible?

import qubogen

sample multiset

s = np.array([3,1,1,2,2,1])

create qubo matrix with qubogen.qubo_number_partition

qubogen.qubo_number_partition(s)

array([[-21,   3,   3,   6,   6,   3],
       [  3,  -9,   1,   2,   2,   1],
       [  3,   1,  -9,   2,   2,   1],
       [  6,   2,   2, -16,   4,   2],
       [  6,   2,   2,   4, -16,   2],
       [  3,   1,   1,   2,   2,  -9]])

Graph Coloring

• For a given graph, how to color the vertices such that no two adjacent vertices are of same color?

sample graph: builtin data structure qubogen.Graph

edges = [[0,1],[0,4],[1,2],[1,3],[1,4],[2,3],[3,4]]
n_nodes
g = qubogen.Graph(edges=edges, n_nodes=n_nodes)

create qubo matrix with qubogen.qubo_graph_coloring

q=qubogen.qubo_graph_coloring(g, n_color=3)

Other combinatorial optimization problems

qubogen is also available for the below problems:

Refs

• A Tutorial on Formulating and Using QUBO Models