The one-stop package for formulating, simulating, and solving problems in boolean and spin form.
master branch
dev branch
pypi distribution
Please see the Repository and Docs. For examples/tutorials, see the notebooks.
For the stable release (same version as the master branch):
pip install qubovertOr to install from source:
git clone https://github.com/jtiosue/qubovert.git
cd qubovert
pip install -e .Then you can use it in Python versions 3.6 and above with
import qubovert as qvNote that to install from source on Windows you will need Microsoft Visual C++ Build Tools 14 installed.
Here we show an example of formulating a pseudo-boolean objective function. We can also make spin objective functions (Hamiltonians) in a very similar manner. See the notebooks for examples.
from qubovert import boolean_var
N = 10
# create the variables
x = {i: boolean_var('x(%d)' % i) for i in range(N)}
# minimize \sum_{i=0}^{N-2} (1-2x_{i}) x_{i+1}
model = 0
for i in range(N-1):
model += (1 - 2 * x[i]) * x[i+1]
# subject to the constraint that x_1 equals the XOR of x_3 and x_5
# enforce with a penalty factor of 3
model.add_constraint_eq_XOR(x[1], x[3], x[5], lam=3)
# subject to the constraints that the sum of all variables is less than 4
# enforce with a penalty factor of 5
model.add_constraint_lt_zero(sum(x.values()) - 4, lam=5)Next we will show multiple ways to solve the model.
Before using the bruteforce solver, always check that model.num_binary_variables is relatively small!
model_solution = model.solve_bruteforce()
print("Variable assignment:", model_solution)
print("Model value:", model.value(model_solution))
print("Constraints satisfied?", model.is_solution_valid(model_solution))Please see the definition of PUBO in the next section. We will anneal the PUBO.
from qubovert.sim import anneal_pubo
res = anneal_pubo(model, num_anneals=10)
model_solution = res.best.state
print("Variable assignment:", model_solution)
print("Model value:", res.best.value)
print("Constraints satisfied?", model.is_solution_valid(model_solution))D-Wave's simulated annealer cannot anneal PUBOs as we did above. Instead the model must be reduced to a QUBO. See the next section for definitions of QUBO and PUBO.
from neal import SimulatedAnnealingSampler
# Get the QUBO form of the model
qubo = model.to_qubo()
# D-Wave accept QUBOs in a different format than qubovert's format
# to get the qubo in this form, use the .Q property
dwave_qubo = qubo.Q
# solve with D-Wave
res = SimulatedAnnealingSampler().sample_qubo(dwave_qubo, num_reads=10)
qubo_solution = res.first.sample
# convert the qubo solution back to the solution to the model
model_solution = model.convert_solution(qubo_solution)
print("Variable assignment:", model_solution)
print("Model value:", model.value(model_solution))
print("Constraints satisfied?", model.is_solution_valid(model_solution))qubovert defines, among many others, the following objects.
- QUBO: Quadratic Unconstrained Boolean Optimization (
qubovert.QUBO) - QUSO: Quadratic Unconstrained Spin Optimization (
qubovert.QUSO) - PUBO: Polynomial Unconstrained Boolean Optimization (
qubovert.PUBO) - PUSO: Polynomial Unconstrained Spin Optimization (
qubovert.PUSO) - PCBO: Polynomial Constrained Boolean Optimization (
qubovert.PCBO) - PCSO: Polynomial Constrained Spin Optimization (
qubovert.PCSO)
Each of the objects has many methods and arbitary arithmetic defined; see the docstrings of each object and the notebooks for more info. A boolean optimization model is one whose variables can be assigned to be either 0 or 1, while a spin optimization model is one whose variables can be assigned to be either 1 or -1. The qubovert.boolean_var(name) function will create a PCBO representing the boolean variable with name name. Similarly, the qubovert.spin_var(name) function will create a PCSO representing the spin variable with name name.
There are many utilities in the utils library that can be helpful. Some examples of utility functions are listed here.
qubovert.utils.solve_pubo_bruteforce, solve a PUBO by iterating through all possible solutions.qubovert.utils.solve_puso_bruteforce, solve a PUSO by iterating through all possible solutions.qubovert.utils.pubo_to_puso, convert a PUBO to a PUSO.qubovert.utils.puso_to_pubo, convert a PUSO to a PUBO.qubovert.utils.pubo_value, determine the value that a PUBO takes with a particular solution mapping.qubovert.utils.puso_value, determine the value that a PUSO takes with a particular solution mapping.qubovert.utils.approximate_pubo_extrema, approximate the minimum and maximum values that a PUBO can take; the true extrema will lie within these bounds.qubovert.utils.approximate_puso_extrema, approximate the minimum and maximum values that a PUSO can take; the true extrema will lie within these bounds.qubovert.utils.subgraph, create the subgraph of a model that only contains certain given variables.qubovert.utils.subvalue, create the submodel of a model with certain values of the model replaced with values.qubovert.utils.normalize, normalize a model such that its coefficients have a maximum absolute magnitude.
See qubovert.utils.__all__ for more. Please note that all conversions between boolean and spin map {0, 1} to/from {1, -1} in that order! This is the convention that qubovert uses everywhere.
The PCBO and PCSO objects have constraint methods; for example, the .add_constraint_le_zero method will enforce that an expression is less than or equal to zero by adding a penalty to the model whenever it does not. The PCBO object also has constraint methods for satisfiability expressions; for example, the .add_constraint_OR will enforce that the OR of the given boolean expression evaluates to True by adding a penalty to the model whenever it does not. See the docstrings and notebooks for more info.
For more utilities on satisfiability expressions, qubovert also has a sat library; see qubovert.sat.__all__. Consider the following 3-SAT example. We have variables x0, x1, x2, x3, labeled by 0, 1, 2, 3. We can create an expression C that evaluates to 1 whenever the 3-SAT conditions are satisfied.
from qubovert.sat import AND, NOT, OR
C = AND(OR(0, 1, 2), OR(NOT(0), 2, NOT(3)), OR(NOT(1), NOT(2), 3))
# C = 1 for a satisfying assignment, C = 0 otherwise
# So minimizing -C will solve it.
P = -C
solution = P.solve_bruteforce()See the notebooks for many fully worked out examples. Here we will just show some basic and brief examples.
The basic building block of a binary optimization model is a Python dictionary. The keys of the dictionary are tuples of variable names, and the values are their corresponding coefficients. For example, in the below code block, model1, model2, and model3 are equivalent.
from qubovert import boolean_var, PUBO
x0, x1, x2 = boolean_var('x0'), boolean_var('x1'), boolean_var('x2')
model1 = -1 + x0 + 2 * x0 * x1 - 3 * x0 * x2 + x0 * x1 * x2
model2 = {(): -1, ('x0',): 1, ('x0', 'x1'): 2, ('x0', 'x2'): -3, ('x0', 'x1', 'x2'): 1}
model3 = PUBO(model2)Similarly, in the below code block, model1, model2, and model3 are equivalent.
from qubovert import spin_var, PUSO
z0, z1, z2 = spin_var('z0'), spin_var('z1'), spin_var('z2')
model1 = -1 + z0 + 2 * z0 * z1 - 3 * z0 * z2 + z0 * z1 * z2
model2 = {(): -1, ('z0',): 1, ('z0', 'z1'): 2, ('z0', 'z2'): -3, ('z0', 'z1', 'z2'): 1}
model3 = PUSO(model2)Let's take the same model from above (ie define model = model1.copy()). Suppose we want to find the ground state of the model subject to the constraints that the sum of the variables is negative and that the product of z0 and z1 is 1. We have to enforce these constraints with a penalty called lam. For now, let's set it as a Symbol that we can adjust later.
from sympy import Symbol
lam = Symbol('lam')
model.add_constraint_lt_zero(z0 + z1 + z2, lam=lam)
model.add_constraint_eq_zero(z0 * z1 - 1, lam=lam)Note that constraint methods can also be strung together if you want. So we could have written this as
model.add_constraint_lt_zero(
z0 + z1 + z2, lam=lam
).add_constraint_eq_zero(
z0 * z1 - 1, lam=lam
)The first thing you notice if you print(model.variables) is that there are now new variables in the model called '__a0' and '__a1'. These are auxillary or ancilla variables that are needed to enforce the constraints. The next thing to notice if you print(model.degree) is that the model is a polynomial of degree 3. Many solvers (for example D-Wave's solvers) only solve degree 2 models. To get a QUBO or QUSO (which are degree two modes) from model, simply call the .to_qubo or .to_quso methods, which will reduce the degree to 2 by introducing more variables.
qubo = model.to_qubo()
quso = model.to_quso()Next let's solve the QUBO and/or QUSO formulations. First we have to substitute a value in for our placeholder symbol lam that is used to enforce the constraints. We'll just use lam=3 for now.
qubo = qubo.subs({lam: 3})
quso = quso.subs({lam: 3})Here we will use D-Wave's simulated annealer.
from neal import SimulatedAnnealingSampler
# D-Wave represents QUBOs a little differently than qubovert does.
# to get D-Wave's form, use the .Q property
dwave_qubo = qubo.Q
# D-Wave represents QUSOs a little differently than qubovert does.
# to get D-Wave's form, use the .h property the linear terms and the
# .J property for the quadratic terms
dwave_linear, dwave_quadratic = quso.h, quso.J
# call dwave
qubo_res = SimulatedAnnealingSampler().sample_qubo(dwave_qubo)
quso_res = SimulatedAnnealingSampler().sample_ising(dwave_linear, dwave_quadratic)
qubo_solution = qubo_res.first.sample
quso_solution = quso_res.first.sampleNow we have to convert the solution in terms of the QUBO/QUSO variables back to a solution in terms of the original variables. We can then check if the proposed solution satisfies all of the constraints!
converted_qubo_solution = model.convert_solution(qubo_solution)
print(model.is_solution_valid(converted_qubo_solution))
converted_quso_solution = model.convert_solution(quso_solution)
print(model.is_solution_valid(converted_quso_solution))One of the goals of qubovert is to become a large collection of problems mapped to QUBO and QUSO forms in order to aid the recent increase in study of these problems due to quantum optimization algorithms. Use Python's help function! I have very descriptive doc strings on all the functions and classes. Please see the notebooks for a few more examples as well.
See the following Set Cover example.
from qubovert.problems import SetCover
from any_module import qubo_solver
# or you can use my bruteforce solver...
# from qubovert.utils import solve_qubo_bruteforce as qubo_solver
U = {"a", "b", "c", "d"}
V = [{"a", "b"}, {"a", "c"}, {"c", "d"}]
problem = SetCover(U, V)
Q = problem.to_qubo()
obj, sol = qubo_solver(Q)
solution = problem.convert_solution(sol)
print(solution)
# {0, 2}
print(problem.is_solution_valid(solution))
# will print True, since V[0] + V[2] covers all of U
print(obj == len(solution))
# will print TrueTo use the QUSO formulation instead:
from qubovert.problems import SetCover
from any_module import quso_solver
# or you can use my bruteforce solver...
# from qubovert.utils import solve_quso_bruteforce as quso_solver
U = {"a", "b", "c", "d"}
V = [{"a", "b"}, {"a", "c"}, {"c", "d"}]
problem = SetCover(U, V)
L = problem.to_quso()
obj, sol = quso_solver(L)
solution = problem.convert_solution(sol)
print(solution)
# {0, 2}
print(problem.is_solution_valid(solution))
# will print True, since V[0] + V[2] covers all of U
print(obj == len(solution))
# will print TrueTo see problem specifics, run
help(qubovert.problems.SetCover)
help(qubovert.problems.VertexCover)
# etc