Skip to main content

qubovert

master branch

Travis-CI Documentation Status Code Coverage Code Quality

dev branch

Travis-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/jiosue/qubovert.git
cd qubovert
pip install -e .

Then you can use it in Python versions 3.6 and above with

import qubovert

# get info
help(qubovert)

# see the main functionality
print(qubovert.__all__)

# see the utilities defined
help(qubovert.utils)
print(qubovert.utils.__all__)

# see the satisfiability library
help(qubovert.sat)
print(qubovert.sat.__all__)

# see all the probles defined
print(qubovert.problems.__all__)

# to see specifically the np problems:
help(qubovert.problems.np)
print(qubovert.problems.np.__all__)

# etc ...

Example of the typical workflow

Create the binary objective function to minimize.

from qubovert import boolean_var
from qubovert.sat import NOT

N = 10

x = {i: boolean_var('x(%d)' % i) for i in range(N)}

model = sum(NOT(x[i-1]) * x[i] for i in range(N-1))

# enforce that x_1 equals the XOR of x_3 and x_5 with a penalty factor of 3
model.add_constraint_eq_XOR(x[1], x[3], x[5], lam=3)

# enforce that the sum of all variables is less than 4 with a penalty factor of 5.
model.add_constraint_lt_zero(sum(x.values()) - 4, lam=5)

Then, if you have a QUBO solver (or just use qubovert.utils.solve_qubo_bruteforce):

from anywhere import qubo_solver

qubo = model.to_qubo()
qubo_energy, qubo_solution = qubo_solver(qubo)
model_solution = model.convert_solution(qubo_solution)
print(model_solution)

Otherwise, if you have a QUSO solver (or just use qubovert.utils.solve_quso_bruteforce):

from anywhere import quso_solver

quso = model.to_quso()
quso_energy, quso_solution = quso_solver(quso)
model_solution = model.convert_solution(quso_solution)
print(model_solution)

Each model_solution should be the same! You can test that it is the correct solution by comparing it to model.solve_bruteforce(). You can also check if all of the constraints are satisfied by running model.is_solution_valid(model_solution).

For the second example, let’s create a spin model. The Hamiltonian is H.

from qubovert import spin_var

z = [spin_var(i) for i in range(4)]
H = z[0] * z[1] * z[2] - 2 * z[1] * z[3] + sum(z) ** 2

# enforce that spin 0 and spin 2 are aligned with penalty factor 2
H.add_constraint_eq_zero(z[0] * z[2] - 1, lam=2)

Now we can do the same that we did with the binary objective function above. If you have a QUBO solver (or just use qubovert.utils.solve_qubo_bruteforce):

from anywhere import qubo_solver

qubo = H.to_qubo()
qubo_energy, qubo_solution = qubo_solver(qubo)
H_groundstate = H.convert_solution(qubo_solution)
print(H_groundstate)

Otherwise, if you have a QUSO solver (or just use qubovert.utils.solve_quso_bruteforce):

from anywhere import quso_solver

quso = H.to_quso()
quso_energy, quso_solution = quso_solver(quso)
H_groundstate = H.convert_solution(quso_solution)
print(H_groundstate)

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

See qubovert.__all__.

  • QUBO: Quadratic Unconstrained Boolean Optimization

  • QUSO: Quadratic Unconstrained Spin Optimization

  • PUBO: Polynomial Unconstrained Boolean Optimization

  • PUSO: Polynomial Unconstrained Spin Optimization

  • PCBO: Polynomial Constrained Boolean Optimization

  • PCSO: Polynomial Constrained Spin Optimization

Boolean variables are in {0, 1}, and spin variables are in {1, -1}. See the docstrings for qubovert.PCBO, qubovert.PCSO, qubovert.QUBO, qubovert.QUSO, qubovert.PUBO, and qubovert.PUSO. There are many utilities in the utils library that can be helpful; see qubovert.utils.__all__. We implement various utility functions, including

  • solve_pubo_bruteforce,

  • solve_puso_bruteforce,

  • pubo_value,

  • puso_value,

  • pubo_to_puso,

  • puso_to_pubo,

  • subgraph,

  • normalize,

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

We also have a sat library for boolean expressions; see qubovert.sat.__all__. Consider the following 3-SAT example. We have variables x0, x1, x2, x3, which we’ll just label with 0, 1, 2, 3.

from qubovert.sat import AND, NOT, OR
from anywhere import qubo_solver

C = AND(OR(0, 1, 2), OR(NOT(0), 2, NOT(3)), OR(NOT(1), NOT(2), 3))

# C is 1 for a satisfying assignment, else 0
# So minimizing P will solve it.
P = -C

# P is a PUBO
Q = P.to_qubo()
solution = qubo_solver(Q)

print(solution)  # {0: 0, 1: 0, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0}
converted_sol = P.convert_solution(solution)
print(converted_sol) # {0: 0, 3: 0, 1: 0, 2: 1}

print(C.value(converted_sol))  # will print 1 because it satisfies C

Finally, let’s look at some general examples. See the following PCBO examples (much of the same functionality can be used with PCSO problems).

from qubovert import PCBO

H = PCBO()
H.add_constraint_eq_zero({('a', 1): 2, (1, 2): -1, (): -1})
print(H)
# {('a', 1, 2): -4, (1, 2): 3, (): 1}
H -= 1
print(H)
# {('a', 1, 2): -4, (1, 2): 3}
from qubovert import boolean_var

x0, x1, x2 = boolean_var("x0"), boolean_var("x1"), boolean_var("x2")
H = x0 + 2 * x1 * x2 - 3 + x2
print(H)
# {('x0',): 1, ('x1', 'x2'): 2, (): -3, ('x2',): 1}

Note that for very large problems, it is slower to use the boolean_var functionality. For example, consider the following where creating H0 is much faster than creating H1!

from qubovert import boolean_var, PCBO

H0 = PCBO()
for i in range(1000):
    H0[(i,)] += 1

xs = [boolean_var(i) for i in range(1000)]
H1 = sum(xs)

Here we show how to solve problems with the bruteforce solver, and how to convert problems to QUBO and QUSO form. You can use any QUBO/QUSO solver you’d like to solve!

H = PCBO()

# minimize -x_0 - x_1 - x_2
for i in (0, 1, 2):
    H[(i,)] -= 1

# subject to constraints
H.add_constraint_eq_zero(  # enforce that x_0 x_1 - x_2 == 0
    {(0, 1): 1, (2,): -1}
).add_constraint_lt_zero(  # enforce that x_1 x_2 + x_0 < 1
    {(1, 2): 1, (0,): 1, (): -1}
)
print(H)
# {(1,): -2, (2,): -1, (0, 1): 2, (1, 2): 2, (0, 1, 2): 2}

print(H.solve_bruteforce(all_solutions=True))
# [{0: 0, 1: 1, 2: 0}]

Q = H.to_qubo()
solutions = [H.convert_solution(sol)
             for sol in Q.solve_bruteforce(all_solutions=True)]
print(solutions)
# [{0: 0, 1: 1, 2: 0}]  # matches the PCBO solution!

L = H.to_quso()
solutions = [H.convert_solution(sol)
             for sol in L.solve_bruteforce(all_solutions=True)]
print(solutions)
# [{0: 0, 1: 1, 2: 0}]  # matches the PCBO solution!

Here we show how to add various boolean constraints to models.

H = PCBO()
# make it favorable to AND variables a and b, and variables b and c
H.add_constraint_AND('a', 'b').add_constraint_AND('b', 'c')

# make it favorable to OR variables b and c
H.add_constraint_OR('b', 'c')

# make it favorable to (a AND b) OR (c AND d) OR e
H.add_constraint_OR(['a', 'b'], ['c', 'd'], 'e')

# enforce that 'b' = NOR('a', 'c', 'd')
H.add_constraint_eq_NOR('b', 'a', 'c', 'd')

print(H)
# {(): 5, ('c',): -2, ('c', 'a', 'b', 'd'): 1, ('a', 'e', 'b'): 1,
#  ('c', 'e', 'd'): 1, ('e',): -1, ('a',): -1, ('c', 'a'): 1,
#  ('a', 'd'): 1, ('c', 'b'): 2, ('d',): -1, ('b', 'd'): 2}
Q = H.to_qubo()
print(Q)
# {(): 5, (2,): -2, (5,): 12, (0, 1): 4, (0, 5): -8, (1, 5): -8,
#  (6,): 12, (2, 3): 4, (2, 6): -8, (3, 6): -8, (5, 6): 1, (4, 5): 1,
#  (4, 6): 1, (4,): -1, (0,): -1, (0, 2): 1, (0, 3): 1, (1, 2): 2,
#  (3,): -1, (1, 3): 2}
obj_value, sol = qubo_solver(Q)
print(sol)
# {0: 0, 1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 0}
solution = H.convert_solution(sol)
print(solution)
# {'a': 0, 'b': 0, 'c': 1, 'd': 0, 'e': 1}

See the following PUBO example.

from qubovert import PUBO
from any_module import qubo_solver
# or you can use my bruteforce solver...
# from qubovert.utils import solve_qubo_bruteforce as qubo_solver

pubo = PUBO()
pubo[('a', 'b', 'c', 'd')] -= 3
pubo[('a', 'b', 'c')] += 1
pubo[('c', 'd')] -= 2
pubo[('a',)] += 1
pubo -= 3  # equivalent to pubo[()] -= 3
pubo **= 4
pubo *= 2

Q = pubo.to_qubo()
obj, sol = qubo_solver(Q)
solution = pubo.convert_solution(sol)
print((obj, solution))
# (2, {'a': 1, 'b': 1, 'c': 1, 'd': 0})

Symbols can also be used, for example:

from qubovert import PCSO
from sympy import Symbol

a, b = Symbol('a'), Symbol('b')

# enforce that z_0 + z_1 == 0 with penalty a
H = PCSO().add_constraint_eq_zero({(0,): 1, (1,): 1}, lam=a)
print(H)
# {(): 2*a, (0, 1): 2*a}
H[(0, 1)] += b
print(H)
# {(): 2*a, (0, 1): 2*a + b}
H_subs = H.subs({a: 2})
print(H_subs)
# {(): 4, (0, 1): 4 + b}

H_subs = H.subs({a: 2, b: 3})
print(H_subs)
# {(): 4, (0, 1): 7}

Please note that H.mapping is not necessarily equal to H.subs(...).mapping. Thus, when using the PCBO.convert_solution function, make sure that you use the correct PCBO instance!

The convension used is that () elements of every dictionary corresponds to offsets. Note that some QUBO solvers accept QUBOs where each key is a two element tuple (since for a QUBO {(0, 0): 1} is the same as {(0,): 1}). To get this standard form from our QUBOMatrix object, just access the property Q. Similar for the QUSOMatrix. For example:

from qubovert.utils import QUBOMatrix
Q = QUBOMatrix()
Q += 3
Q[(0,)] -= 1
Q[(0, 1)] += 2
Q[(1, 1)] -= 3
print(Q)
# {(): 3, (0,): -1, (0, 1): 2, (1,): -3}
print(Q.Q)
# {(0, 0): -1, (0, 1): 2, (1, 1): -3}
print(Q.offset)
# 3
from qubovert.utils import QUSOMatrix
L = QUSOMatrix()
L += 3
L[(0, 1, 1)] -= 1
L[(0, 1)] += 2
L[(1, 1)] -= 3
print(L)
# {(0,): -1, (0, 1): 2}
print(L.h)
# {0: -1}
print(L.J)
# {(0, 1): 2}
print(L.offset)
# 0

Convert common problems to QUBO form (the problems library)

See qubovert.problems.__all__.

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.

See the following Set Cover example. All other problems can be used in a similar way.

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://emoji.slack-edge.com/T24940PQV/qvfire/8fdd5c5b7e9b5f15.png

Metadata

Release files for qubovert 1.0.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for qubovert 1.0.0
File Size Uploaded Provenance Actions
qubovert-1.0.0.tar.gz 71.4 kB Without provenance Details for qubovert-1.0.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for qubovert 1.0.0
File Interpreter ABI Platform Actions
qubovert-1.0.0-py3-none-any.whl Python 3 none any Details for qubovert-1.0.0-py3-none-any.whl

Total release size: 194.1 kB

Release files / qubovert-1.0.0.tar.gz

Download URL qubovert-1.0.0.tar.gz
Size 71.4 kB
Tags Source
SHA-256 checksum
How to use checksums
294b9d8f09d939f2a92e4a8bd2b6c81747052ea5a34b7b1505f7dca23755b936
BLAKE2b-256 checksum
How to use checksums
7dd1773cff5c0ade18cc0bba51f03e7aef544d91cc505fb34f1faa1d8f85adc1
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/1.13.0 pkginfo/1.5.0.1 requests/2.21.0 setuptools/41.0.1 requests-toolbelt/0.9.1 tqdm/4.32.2 CPython/3.7.2

Release files / qubovert-1.0.0-py3-none-any.whl

Download URL qubovert-1.0.0-py3-none-any.whl
Size 122.7 kB
Tags Python 3
SHA-256 checksum
How to use checksums
33a0945067936e83448dba2fba01e745a1e2901d17d31804321a271235964567
BLAKE2b-256 checksum
How to use checksums
60dcfab182a513bc31073de87fad5eb6d5af3516979380e62ede6eb1dee74d92
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/1.13.0 pkginfo/1.5.0.1 requests/2.21.0 setuptools/41.0.1 requests-toolbelt/0.9.1 tqdm/4.32.2 CPython/3.7.2

Security for qubovert 1.0.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page