Skip to main content

A package for formulating, simulating, and solving problems in boolean and spin form

Project description

The one-stop package for formulating, simulating, and solving problems in boolean and spin form.

master branch

GitHub Actions CI Documentation Status Code Coverage Code Quality

dev branch

GitHub Actions CI Documentation Status Code Coverage

pypi distribution

pypi dist pypi dist downloads

Please see the Repository and Docs. For examples/tutorials, see the notebooks.

Installation

For the stable release (same version as the master branch):

pip install qubovert

Or 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 qv

Note that to install from source on Windows you will need Microsoft Visual C++ Build Tools 14 installed.

Example of the typical workflow

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.

Create the boolean objective function to minimize

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.

Solving the model with bruteforce

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))

Solving the model with qubovert’s simulated annealing

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))

Solving the model with D-Wave’s simulated annealer

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))

Managing QUBO, QUSO, PUBO, PUSO, PCBO, and PCSO formulations

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()

Basic examples of common functionality

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.sample

Now 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))

Convert common problems to quadratic form (the problems library)

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 True

To 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 True

To see problem specifics, run

help(qubovert.problems.SetCover)
help(qubovert.problems.VertexCover)
# etc

https://raw.githubusercontent.com/jtiosue/qubovert/master/assets/qvfire.png

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

qubovert-1.2.5.tar.gz (97.7 kB view details)

Uploaded Source

Built Distributions

qubovert-1.2.5-cp39-cp39-win_amd64.whl (167.9 kB view details)

Uploaded CPython 3.9 Windows x86-64

qubovert-1.2.5-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (187.3 kB view details)

Uploaded CPython 3.9 manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

qubovert-1.2.5-cp39-cp39-macosx_10_15_x86_64.whl (165.0 kB view details)

Uploaded CPython 3.9 macOS 10.15+ x86-64

qubovert-1.2.5-cp38-cp38-win_amd64.whl (167.9 kB view details)

Uploaded CPython 3.8 Windows x86-64

qubovert-1.2.5-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (187.5 kB view details)

Uploaded CPython 3.8 manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

qubovert-1.2.5-cp38-cp38-macosx_10_15_x86_64.whl (165.0 kB view details)

Uploaded CPython 3.8 macOS 10.15+ x86-64

qubovert-1.2.5-cp37-cp37m-win_amd64.whl (167.9 kB view details)

Uploaded CPython 3.7m Windows x86-64

qubovert-1.2.5-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (188.6 kB view details)

Uploaded CPython 3.7m manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

qubovert-1.2.5-cp37-cp37m-macosx_10_15_x86_64.whl (165.0 kB view details)

Uploaded CPython 3.7m macOS 10.15+ x86-64

File details

Details for the file qubovert-1.2.5.tar.gz.

File metadata

  • Download URL: qubovert-1.2.5.tar.gz
  • Upload date:
  • Size: 97.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.8.13

File hashes

Hashes for qubovert-1.2.5.tar.gz
Algorithm Hash digest
SHA256 fae18be6be59df70cb04c985f0c9491804e6fa5ef3798e0dbffd2d6357af2e58
MD5 783e254fe93d1a8ed855e54db4c100db
BLAKE2b-256 4e99c65c7e2a1ea5ee8e8df9669df62bf0b7fe48437d2591e5012308655cb774

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp39-cp39-win_amd64.whl.

File metadata

  • Download URL: qubovert-1.2.5-cp39-cp39-win_amd64.whl
  • Upload date:
  • Size: 167.9 kB
  • Tags: CPython 3.9, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.9.13

File hashes

Hashes for qubovert-1.2.5-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 f3969c0d7c0f5a4793205c77154d32aa0896fc85ff117a75290055d561e94826
MD5 57a8f448e942d61c4ce5d5bb81d62bfa
BLAKE2b-256 213158f00c3cf8aafd13f29c357bce8748c3ae3cbc8fd65cdbb6ce75d9b98dd8

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for qubovert-1.2.5-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 340fedf785bb4934947ecff2e81dce9f6800125a6b338894b1ae09dc50a76260
MD5 5c4aaff930f79d37ccf99f4cc0e3ed0e
BLAKE2b-256 a9a84fa4fd285b49cc01ace88a6786ba6629cd2211f00ced61e3649f8d5ace43

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp39-cp39-macosx_10_15_x86_64.whl.

File metadata

File hashes

Hashes for qubovert-1.2.5-cp39-cp39-macosx_10_15_x86_64.whl
Algorithm Hash digest
SHA256 714c5cca2888e0e4f8ea93521895e249b9d8a5a4e3df7b24023072ce31d40243
MD5 3052807af29c2593b06818d5cc92c658
BLAKE2b-256 8998749dd68697f6e378ef036c7c2b9f39ef6b03f1646dcd37d0266bbd066149

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp38-cp38-win_amd64.whl.

File metadata

  • Download URL: qubovert-1.2.5-cp38-cp38-win_amd64.whl
  • Upload date:
  • Size: 167.9 kB
  • Tags: CPython 3.8, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.8.10

File hashes

Hashes for qubovert-1.2.5-cp38-cp38-win_amd64.whl
Algorithm Hash digest
SHA256 3f3e2c982ee58c667470856fc694c6cd2282bef9302224068dce50b8de5ae0e5
MD5 ce73eb2f039570a0bbf6e565e7c623d5
BLAKE2b-256 828298fe380933e510f72ece44c9d5ff575dab501cf959f1b7f76d0acc2b3597

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for qubovert-1.2.5-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 88d5b172d837c302df58e5148542550e01b93b66a29c47bbe590908905cc29c9
MD5 eb48cc8dd420b6ee824c85dd079c6258
BLAKE2b-256 304e94fdbc43b433970950b532d2fd190bdfae8e3393716a6533ea32e123501f

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp38-cp38-macosx_10_15_x86_64.whl.

File metadata

File hashes

Hashes for qubovert-1.2.5-cp38-cp38-macosx_10_15_x86_64.whl
Algorithm Hash digest
SHA256 bb5cf544986f4ea4644b4fb6ca7b9ad291d73b736f9244bde641c5cbb1052588
MD5 827b7e0848a02df868104bf4ddc907da
BLAKE2b-256 f2b4a158e4b405b768825d0ee76395c6d5614160859460eb8ed64db1f03adad5

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp37-cp37m-win_amd64.whl.

File metadata

  • Download URL: qubovert-1.2.5-cp37-cp37m-win_amd64.whl
  • Upload date:
  • Size: 167.9 kB
  • Tags: CPython 3.7m, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.7.9

File hashes

Hashes for qubovert-1.2.5-cp37-cp37m-win_amd64.whl
Algorithm Hash digest
SHA256 a3bc606cfe0c6c3b9e51e344ee1c2843523067d0d1ed1073475aba15da2b4069
MD5 f5dfe55e56ce41a1e6838a9999d4ba3a
BLAKE2b-256 c3ae89afee034b775858283446e6549a37ae96a820637b7cccdbec7818db2313

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for qubovert-1.2.5-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 4d0f07883363a5bfa099ab7c9a83fbcb4a12effc37876ce6e9aa63267695f690
MD5 82e9b75298a19edb41643d5ee9993c29
BLAKE2b-256 aefa6ce63fdccf5fc6bd9d40bc4a39a1fbfe5bb87a496bd254806d1f75a93368

See more details on using hashes here.

File details

Details for the file qubovert-1.2.5-cp37-cp37m-macosx_10_15_x86_64.whl.

File metadata

File hashes

Hashes for qubovert-1.2.5-cp37-cp37m-macosx_10_15_x86_64.whl
Algorithm Hash digest
SHA256 f8cbb7a1748b83103b9c4c6ec1807d2b05157e5250963b5f765b8fa031334a27
MD5 592eecde26737431911b242f4388f32a
BLAKE2b-256 67b71106349ac0943871abc19f78e9bf536152b89310b865cdab0c2a9fe2beb4

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page