Polynomial Constrained Boolean Optimization (PCBO)

Accessed with qubovert.PCBO. Note that it is important to use the PCBO.convert_solution function to convert solutions of the PUBO, QUBO, PUSO or QUSO formulations of the PCBO back to a solution to the PCBO formulation.

We also discuss the qubovert.boolean_var and qubovert.integer_var functions here, which just create PCBO objects.

qubovert.boolean_var(name)

boolean_var.

Create a PCBO (see qubovert.PCBO) from a single boolean variable.

Parameters: name (any hashable object.) – Name of the boolean variable.
Returns: pcbo – The model representing the boolean variable.
Return type: qubovert.PCBO object.

Examples

>>> from qubovert import boolean_var, PCBO
>>>
>>> x0 = boolean_var("x0")
>>> print(x0)
{('x0',): 1}
>>> print(isinstance(x0, PCBO))
True
>>> print(x0.name)
x0

>>> x = [boolean_var('x{}'.format(i)) for i in range(5)]
>>> pcbo = sum(x)
>>> print(pcbo)
{('x0',): 1, ('x1',): 1, ('x2',): 1, ('x3',): 1, ('x4',): 1}
>>> pcbo **= 2
>>> print(pcbo)
{('x0',): 1, ('x0', 'x1'): 2, ('x2', 'x0'): 2, ('x3', 'x0'): 2,
 ('x4', 'x0'): 2, ('x1',): 1, ('x2', 'x1'): 2, ('x3', 'x1'): 2,
 ('x4', 'x1'): 2, ('x2',): 1, ('x2', 'x3'): 2, ('x2', 'x4'): 2, ('x3',): 1,
 ('x4', 'x3'): 2, ('x4',): 1}
>>> pcbo *= -1
>>> print(pcbo.solve_bruteforce())
{'x0': 1, 'x1': 1, 'x2': 1, 'x3': 1, 'x4': 1}
>>> pcbo.add_constraint_eq_zero(x[0] + x[1])
>>> print(pcbo.solve_bruteforce())
{'x0': 0, 'x1': 0, 'x2': 1, 'x3': 1, 'x4': 1}

Notes

qubovert.boolean_var(name) is equivalent to qubovert.PCBO.create_var(name).

qubovert.integer_var(prefix, num_bits, log_trick=True)

integer_var.

Return a PCBO object representing an integer variable with num_bits bits.

Parameters

prefix (str.) – The prefix for the boolean variable names.
num_bits (int.) – Number of bits to represent the integer variable with.
log_trick (bool (optional, defaults to True)) – Whether or not to use a log encoding for the integer.

Returns

i

Return type

qubovert.PCBO object.

Example

>>> from qubovert import integer_var
>>> var = integer_var('a', 4)
>>> print(var)
{('a0',): 1, ('a1',): 2, ('a2',): 4, ('a3',): 8}
>>> print(var.name)
a

>>> from qubovert import integer_var
>>> var = integer_var('a', 4, log_trick=False)
>>> print(var)
{('a0',): 1, ('a1',): 1, ('a2',): 1, ('a3',): 1}

class qubovert.PCBO(*args, **kwargs)

PCBO.

This class deals with Polynomial Constrained Boolean Optimization problems. PCBO inherits some methods and attributes from the PUBO class. See help(qubovert.PUBO).

PCBO has all the same methods as PUBO, but adds some constraint methods; namely

add_constraint_eq_zero(P, lam=1, ...) enforces that P == 0 by penalizing with lam,
add_constraint_ne_zero(P, lam=1, ...) enforces that P != 0 by penalizing with lam,
add_constraint_lt_zero(P, lam=1, ...) enforces that P < 0 by penalizing with lam,
add_constraint_le_zero(P, lam=1, ...) enforces that P <= 0 by penalizing with lam,
add_constraint_gt_zero(P, lam=1, ...) enforces that P > 0 by penalizing with lam, and
add_constraint_ge_zero(P, lam=1, ...) enforces that P >= 0 by penalizing with lam.

Each of these takes in a PUBO P and a lagrange multiplier lam that defaults to 1. See each of their docstrings for important details on their implementation.

We then implement logical operations:

add_constraint_AND, add_constraint_NAND,
add_constraint_eq_AND, add_constraint_eq_NAND,
add_constraint_OR, add_constraint_NOR`,
add_constraint_eq_OR, add_constraint_eq_NOR,
add_constraint_XOR, add_constraint_XNOR,
add_constraint_eq_XOR, add_constraint_eq_XNOR,
add_constraint_BUFFER, add_constraint_NOT,
add_constraint_eq_BUFFER, add_constraint_eq_NOT.

See each of their docstrings for important details on their implementation.

Notes

Variables names that begin with "__a" should not be used since they are used internally to deal with some ancilla variables to enforce constraints.
The self.solve_bruteforce method will solve the PCBO ensuring that all the inputted constraints are satisfied. Whereas qubovert.utils.solve_pubo_bruteforce(self) or qubovert.utils.solve_pubo_bruteforce(self.to_pubo()) will solve the PUBO created from the PCBO. If the inputted constraints are not enforced strong enough (ie too small lagrange multipliers) then these may not give the correct result, whereas self.solve_bruteforce() will always give the correct result (ie one that satisfies all the constraints).

Examples

See qubovert.PUBO for more examples of using PCBO without constraints.

>>> H = PCBO()
>>> H.add_constraint_eq_zero({('a', 1): 2, (1, 2): -1, (): -1})
>>> H
{('a', 1, 2): -4, (1, 2): 3, (): 1}
>>> H -= 1
>>> H
{('a', 1, 2): -4, (1, 2): 3}

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

Enforce that c == a b

>>> H = PCBO().add_constraint_eq_AND('c', 'a', 'b')
>>> H
{('c',): 3, ('b', 'a'): 1, ('c', 'a'): -2, ('c', 'b'): -2}

>>> from any_module import qubo_solver
>>> # or from qubovert.utils import solve_qubo_bruteforce as qubo_solver
>>> 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)
>>> H.add_constraint_OR(['a', 'b'], ['c', 'd'])
>>>
>>> H
{('b', 'a'): -2, (): 4, ('b',): -1, ('c',): -1,
 ('c', 'd'): -1, ('c', 'd', 'b', 'a'): 1}
>>> Q = H.to_qubo()
>>> Q
{(): 4, (0,): -1, (2,): -1, (2, 3): 1, (4,): 6, (0, 4): -4,
 (1, 4): -4, (5,): 6, (2, 5): -4, (3, 5): -4, (4, 5): 1}
>>> obj_value, sol = qubo_solver(Q)
>>> sol
{0: 1, 1: 1, 2: 1, 3: 0, 4: 1, 5: 0}
>>> solution = H.convert_solution(sol)
>>> solution
{'b': 1, 'a': 1, 'c': 1, 'd': 0}

__init__.

This class deals with polynomial constrained boolean optimization. Note that it is generally more efficient to initialize an empty PCBO object and then build the PCBO, rather than initialize a PCBO object with an already built dict.

Parameters: arguments (define a dictionary with dict(*args, **kwargs).) – The dictionary will be initialized to follow all the convensions of the class. Alternatively, args[0] can be a PCBO object.

Examples

>>> pcbo = PCBO()
>>> pcbo[('a',)] += 5
>>> pcbo[(0, 'a')] -= 2
>>> pcbo -= 1.5
>>> pcbo
{('a',): 5, ('a', 0): -2, (): -1.5}
>>> pcbo.add_constraint_eq_zero({('a',): 1}, lam=5)
>>> pcbo
{('a',): 10, ('a', 0): -2, (): -1.5}

>>> pcbo = PCBO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> pcbo
{('a',): 5, ('a', 0, 1): -2, (): -1.5}

add_constraint_AND(*variables, lam=1)

add_constraint_AND.

Add a penalty to the PCBO that is only zero when \(a \land b \land c \land ...\) is True, with a penalty factor lam, where a = variables[0], b = variables[1], etc.

Parameters

*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_AND('a', 'b')  # enforce a AND b
>>> H
{('b', 'a'): -1, (): 1}

>>> H = PCBO()
>>> H.add_constraint_AND('a', 'b', 'c', 'd')
>>> # enforce a AND b AND c AND d

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> # enforce a AND b
>>> H = PCBO().add_constraint_AND(a, b)

add_constraint_BUFFER(a, lam=1)

add_constraint_BUFFER.

Add a penalty to the PCBO that is only nonzero when \(a == 1\) is True, with a penalty factor lam.

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_BUFFER('a')  # enforce a

>>> from qubovert import boolean_var, PCBO
>>> a = boolean_var('a')
>>> # enforce a
>>> H = PCBO().add_constraint_BUFFER(a)

add_constraint_NAND(*variables, lam=1)

add_constraint_NAND.

Add a penalty to the PCBO that is only zero when \(\lnot (a \land b \land c \land ...)\) is True, with a penalty factor lam, where a = variables[0], b = variables[1], etc.

Parameters

*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_NAND('a', 'b')  # enforce a NAND b

>>> H = PCBO()
>>> H.add_constraint_NAND('a', 'b', 'c', 'd')
>>> # enforce a NAND b NAND c NAND d

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> # enforce a NAND b
>>> H = PCBO().add_constraint_NAND(a, b)

add_constraint_NOR(*variables, lam=1)

add_constraint_NOR.

Add a penalty to the PCBO that is only nonzero when \(\lnot(a \lor b \lor c \lor d \lor ...)\) is True, with a penalty factor lam, where a = variables[0], b = variables[1], etc.

Parameters

*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_NOR('a', 'b')  # enforce a NOR b

>>> H = PCBO()
>>> H.add_constraint_NOR('a', 'b', 'c', 'd')
>>> # enforce a NOR b NOR c NOR d

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> # enforce a NOR b
>>> H = PCBO().add_constraint_NOR(a, b)

add_constraint_NOT(a, lam=1)

add_constraint_NOT.

Add a penalty to the PCBO that is only nonzero when \(\lnot a\) is True, with a penalty factor lam.

Parameters

a (any hashable object or a dict.) – The label for boolean variables a, or its PUBO representation.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_NOT('a')  # enforce not a
>>> H
{('a',): 1}

>>> from qubovert import boolean_var, PCBO
>>> a = boolean_var('a')
>>> # enforce not a
>>> H = PCBO().add_constraint_NOT(a)

add_constraint_OR(*variables, lam=1)

add_constraint_OR.

Add a penalty to the PCBO that is only nonzero when \(a \lor b \lor c \lor d \lor ...\) is True, with a penalty factor lam, where a = variables[0], b = variables[1], etc.

Parameters

*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_OR('a', 'b')  # enforce a OR b
>>> H
{('a',): -1, ('b',): -1, ('b', 'a'): 1, (): 1}

>>> H = PCBO()
>>> H.add_constraint_OR('a', 'b', 'c', 'd')  # enforce a OR b OR c OR d

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> # enforce a OR b
>>> H = PCBO().add_constraint_OR(a, b)

add_constraint_XNOR(*variables, lam=1)

add_constraint_XNOR.

Add a penalty to the PCBO that is only nonzero when \(\lnot(v_0 \oplus v_1 \oplus ... \oplus v_n)\) is True, with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …, v_n = variables[-1]. See qubovert.sat.XNOR for the XNOR convention that qubovert uses for more than two inputs.

Parameters

*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_XNOR('a', 'b')  # enforce a XNOR b

>>> H = PCBO()
>>> H.add_constraint_XNOR('a', 'b', 'c')  # enforce a XNOR b XNOR c

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> # enforce a XNOR b
>>> H = PCBO().add_constraint_XNOR(a, b)

add_constraint_XOR(*variables, lam=1)

add_constraint_XOR.

Add a penalty to the PCBO that is only nonzero when \(v_0 \oplus v_1 \oplus ... \oplus v_n\) is True, with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …, v_n = variables[-1]. See qubovert.sat.XOR for the XOR convention that qubovert uses for more than two inputs.

Parameters

*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_XOR('a', 'b')  # enforce a XOR b

>>> H = PCBO()
>>> H.add_constraint_XOR('a', 'b', 'c')  # enforce a XOR b XOR c

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> # enforce a XOR b
>>> H = PCBO().add_constraint_XOR(a, b)

add_constraint_eq_AND(a, *variables, lam=1)

add_constraint_eq_AND.

Add a penalty to the PCBO that enforces that \(a = v_0 \land v_1 \land v_2 \land ...\), with a penalty factor lam, where v_1 = variables[0], v_2 = variables[1], …

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_AND('a', 'b', 'c')  # enforce a == b AND c

>>> H = PCBO()
>>> # enforce (a AND b AND c AND d) == 'e'
>>> H.add_constraint_eq_AND('e', 'a', 'b', 'c', 'd')

>>> from qubovert import boolean_var, PCBO
>>> a, b, c = boolean_var('a'), boolean_var('b'), boolean_var('c')
>>> H = PCBO()
>>> # enforce that a == b AND c
>>> H.add_constraint_eq_AND(a, b, c)

References

https://arxiv.org/pdf/1307.8041.pdf equation 6.

add_constraint_eq_BUFFER(a, b, lam=1)

add_constraint_eq_BUFFER.

Add a penalty to the PCBO that enforces that \(a == b\) with a penalty factor lam.

Parameters

a (any hashable object or a dict.) – The label for boolean variables a, or its PUBO representation.
b (any hashable object or a dict.) – The label for boolean variables b, or its PUBO representation.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_BUFFER('a', 'b')  # enforce a == b

>>> from qubovert import PCBO, boolean_var
>>> a, b = boolean_var('a'), boolean_var('b')
>>> H = PCBO()
>>> H.add_constraint_eq_BUFFER(a, b)  # enforce a == b

add_constraint_eq_NAND(a, *variables, lam=1)

add_constraint_eq_NAND.

Add a penalty to the PCBO that enforces that \(\lnot (v_0 \land v_1 \land v_2 \land ...) == a\), with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …

Parameters

a (any hashable object or a dict.) – The label for boolean variables a, or its PUBO representation.
*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_NAND('a', 'b', 'c')  # enforce a == b NAND c

>>> H = PCBO()
>>> # enforce a == b NAND c NAND d
>>> H.add_constraint_eq_NAND('a', 'b', 'c', 'd')

>>> from qubovert import boolean_var, PCBO
>>> a, b, c = boolean_var('a'), boolean_var('b'), boolean_var('c')
>>> # enforce a == b NAND c
>>> H = PCBO().add_constraint_eq_NAND(a, b, c)

add_constraint_eq_NOR(a, *variables, lam=1)

add_constraint_eq_NOR.

Add a penalty to the PCBO that enforces that \(\lnot(v_0 \lor v_1 \lor v_2 \lor ...) == a\), with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_NOR('a', 'b', 'c')  # enforce a == b NOR c

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

>>> from qubovert import boolean_var, PCBO
>>> # enforce a == b NOR c
>>> a, b, c = boolean_var('a'), boolean_var('b'), boolean_var('c')
>>> H.add_constraint_eq_NOR(a, b, c)

add_constraint_eq_NOT(a, b, lam=1)

NOT.

Add a penalty to the PCBO that enforces that \(\lnot a == b\) with a penalty factor lam.

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
b (any hashable object or a dict.) – The label for boolean variable b, or its PUBO representation.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_NOT('a', 'b')  # enforce NOT(a) == b

>>> from qubovert import boolean_var, PCBO
>>> a, b = boolean_var('a'), boolean_var('b')
>>> H.add_constraint_eq_NOT(a, b)  # enforce NOT(a) == b

add_constraint_eq_OR(a, *variables, lam=1)

add_constraint_eq_OR.

Add a penalty to the PCBO that enforces that \(v_0 \lor v_1 \lor v_2 \lor ... == a\), with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_OR('a', 'b', 'c')  # enforce a == b OR c

>>> H = PCBO()
>>> # enforce a == b OR c OR d
>>> H.add_constraint_eq_OR('a', 'b', 'c', 'd')

add_constraint_eq_XNOR(a, *variables, lam=1)

add_constraint_eq_XNOR.

Add a penalty to the PCBO that enforces that :math:lnot(v_0 oplus v_1 oplus …) == a with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_XNOR('a', 'b', 'c')  # enforce a == b XNOR c

>>> H = PCBO()
>>> # enforce a == b XNOR c XNOR d
>>> H.add_constraint_eq_XNOR('a', 'b', 'c', 'd')

>>> from qubovert import boolean_var, PCBO
>>> a, b, c = boolean_var('a'), boolean_var('b'), boolean_var('c')
>>> # enforce a == b XNOR c
>>> H = PCBO().add_constraint_eq_XNOR(a, b, c)

add_constraint_eq_XOR(a, *variables, lam=1)

add_constraint_eq_XOR.

Add a penalty to the PCBO that enforces that \(v_0 \oplus v_1 \oplus ... == a\) with a penalty factor lam, where v_0 = variables[0], v_1 = variables[1], …

Parameters

a (any hashable object or a dict.) – The label for boolean variable a, or its PUBO representation.
*variables (arguments.) – Each element of variables is a hashable object or a dict (its PUBO representation). They are the label of the boolean variables.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the clause.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

>>> H = PCBO()
>>> H.add_constraint_eq_XOR('a', 'b', 'c')  # enforce a == b XOR c

>>> H = PCBO()
>>> # enforce a == b XOR c XOR d
>>> H.add_constraint_eq_XOR('a', 'b', 'c', 'd')

add_constraint_eq_zero(P, lam=1, bounds=None, suppress_warnings=False)

add_constraint_eq_zero.

Enforce that P == 0 by penalizing invalid solutions with lam.

Parameters

P (dict representing a PUBO.) – The PUBO constraint such that P == 0. Note that P will be converted to a qubovert.PUBO object if it is not already, thus it must follow the conventions, see help(qubovert.PUBO). Please note that if P contains any symbols, then bounds must be supplied, since they cannot be determined when symbols are present.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the constraint.
bounds (two element tuple (optional, defaults to None)) – A tuple (min, max), the minimum and maximum values that the PUBO P can take. If bounds is None, then they may be calculated (approximately).
suppress_warnings (bool (optional, defaults to False)) – Whether or not to surpress warnings.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Examples

The following enforces that \(\prod_{i=0}^{3} x_i == 0\).

>>> H = PCBO()
>>> H.add_constraint_eq_zero({(0, 1, 2, 3): 1})
>>> H
{(0, 1, 2, 3): 1}

The following enforces that \(\sum_{i=1}^{3} i x_i x_{i+1} == 0\).

>>> H = PCBO()
>>> H.add_constraint_eq_zero({(1, 2): 1, (2, 3): 2, (3, 4): 3})
>>> H
{(1, 2): 1, (1, 2, 3): 4, (1, 2, 3, 4): 6,
 (2, 3): 4, (2, 3, 4): 12, (3, 4): 9}

Here we show how operations can be strung together.

>>> H = PCBO()
>>> H.add_constraint_eq_zero(
        {(0, 1): 1}
    ).add_constraint_eq_zero(
        {(1, 2): 1, (): -1}
    )
>>> H
{(0, 1): 1, (1, 2): -1, (): 1}

add_constraint_ge_zero(P, lam=1, log_trick=True, bounds=None, suppress_warnings=False)

add_constraint_ge_zero.

Enforce that P >= 0 by penalizing invalid solutions with lam.

Parameters

P (dict representing a PUBO.) – The PUBO constraint such that P >= 0. Note that P will be converted to a qubovert.PUBO object if it is not already, thus it must follow the conventions, see help(qubovert.PUBO). Please note that if P contains any symbols, then bounds must be supplied, since they cannot be determined when symbols are present.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the constraint.
log_trick (bool (optional, defaults to True)) – Whether or not to use the log trick to enforce the inequality constraint. See Notes below for more details.
bounds (two element tuple (optional, defaults to None)) – A tuple (min, max), the minimum and maximum values that the PUBO P can take. If bounds is None, then they will be calculated (approximately), or if either of the elements of bounds is None, then that element will be calculated (approximately), or if either of the elements of bounds is None, then that element will be calculated (approximately).
suppress_warnings (bool (optional, defaults to False)) – Whether or not to surpress warnings.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Notes

There is no general way to enforce non integer inequality constraints. Thus this function is only guarenteed to work for integer inequality constraints (ie constraints of the form \(x_0 + 2x_1 + ... \geq 0\)). However, it can be used for non integer inequality constraints, but it is recommended that the value of lam be set small, since valid solutions may still recieve a penalty to the objective function. For example,
```
>>> H = PCBO()
>>> H.add_constraint_ge_zero({(0,): -1, (1,): -2, (2,):1.5, (): -.4})
>>> H
{(0,): 1.7999999999999998, (0, 1): 4, (0, 2): -3.0, (0, '__a0'): 2,
 (1,): 5.6, (1, 2): -6.0, (1, '__a0'): 4, (2,): 1.0499999999999998,
 (2, '__a0'): -3.0, (): 0.16000000000000003, ('__a0',): 1.8}
>>> test_sol = {0: 0, 1: 0, 2: 1, '__a0': 1}
>>> H.is_solution_valid(test_sol)
True
>>> H.value(test_sol)
0.01
```
{0: 0, 1: 0, 2: 1} is a valid solution to H, but it will still cause a nonzero penalty to be added to the objective function.
To enforce the inequality constraint, ancilla bits will be introduced (labels with _a). If log_trick is True, then approximately \(\log_2 |\max_x \text{P.value(x)}|\) ancilla bits will be used. If log_trick is False, then approximately \(|\max_x \text{P.value(x)}|\) ancilla bits will be used.

Examples

Enforce that \(x_a x_b x_c - x_a + 4x_a x_b - 3x_c \geq -2\).

>>> H = PCBO().add_constraint_ge_zero(
        {('a', 'b', 'c'): 1, ('a',): -1,
         ('a', 'b'): 4, ('c',): -3, (): 2}
    )
>>> H
{('b', 'c', 'a'): -19, ('b', 'c', 'a', '__a0'): -2,
 ('__a1', 'b', 'c', 'a'): -4, ('__a2', 'b', 'c', 'a'): -8, ('a',): -3,
 ('b', 'a'): 24, ('c', 'a'): 6, ('a', '__a0'): 2, ('__a1', 'a'): 4,
 ('__a2', 'a'): 8, ('b', 'a', '__a0'): -8, ('__a1', 'b', 'a'): -16,
 ('__a2', 'b', 'a'): -32, ('c',): -3, ('c', '__a0'): 6,
 ('__a1', 'c'): 12, ('__a2', 'c'): 24, (): 4, ('__a0',): -3,
 ('__a1',): -4, ('__a1', '__a0'): 4, ('__a2', '__a0'): 8,
 ('__a2', '__a1'): 16}
>>> H.is_solution_valid({'b': 0, 'c': 0, 'a': 1})
True
>>> H.is_solution_valid({'b': 0, 'c': 1, 'a': 1})
False

add_constraint_gt_zero(P, lam=1, log_trick=True, bounds=None, suppress_warnings=False)

add_constraint_gt_zero.

Enforce that P > 0 by penalizing invalid solutions with lam.

Parameters

P (dict representing a PUBO.) – The PUBO constraint such that P > 0. Note that P will be converted to a qubovert.PUBO object if it is not already, thus it must follow the conventions, see help(qubovert.PUBO). Please note that if P contains any symbols, then bounds must be supplied, since they cannot be determined when symbols are present.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the constraint.
log_trick (bool (optional, defaults to True)) – Whether or not to use the log trick to enforce the inequality constraint. See Notes below for more details.
bounds (two element tuple (optional, defaults to None)) – A tuple (min, max), the minimum and maximum values that the PUBO P can take. If bounds is None, then they will be calculated (approximately), or if either of the elements of bounds is None, then that element will be calculated (approximately).
suppress_warnings (bool (optional, defaults to False)) – Whether or not to surpress warnings.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Notes

There is no general way to enforce non integer inequality constraints. Thus this function is only guarenteed to work for integer inequality constraints (ie constraints of the form \(x_0 + 2x_1 + ... > 0\)). However, it can be used for non integer inequality constraints, but it is recommended that the value of lam be set small, since valid solutions may still recieve a penalty to the objective function. For example,
```
>>> H = PCBO()
>>> H.add_constraint_gt_zero({(0,): -1, (1,): -2, (2,): .5, (): -.4})
>>> test_sol = {0: 0, 1: 0, 2: 1}
>>> H.is_solution_valid(test_sol)
True
>>> H.value(test_sol)
0.01
```
{0: 0, 1: 0, 2: 1} is a valid solution to H, but it will still cause a nonzero penalty to be added to the objective function.
To enforce the inequality constraint, ancilla bits will be introduced (labels with _a). If log_trick is True, then approximately \(\log_2 |\max_x \text{P.value(x)}|\) ancilla bits will be used. If log_trick is False, then approximately \(|\max_x \text{P.value(x)}|\) ancilla bits will be used.

Examples

Enforce that \(x_a x_b x_c - x_a + 4x_a x_b - 3x_c > -2\).

>>> H = PCBO().add_constraint_gt_zero(
        {('a', 'b', 'c'): 1, ('a',): -1,
         ('a', 'b'): 4, ('c',): -3, (): 2}
    )
>>> H
{('b', 'c', 'a'): -19, ('b', '__a0', 'c', 'a'): -2,
 ('b', 'c', 'a', '__a1'): -4, ('a',): -3, ('b', 'a'): 24,
 ('c', 'a'): 6, ('__a0', 'a'): 2, ('a', '__a1'): 4,
 ('b', '__a0', 'a'): -8, ('b', 'a', '__a1'): -16, ('c',): -3,
 ('__a0', 'c'): 6, ('c', '__a1'): 12, (): 4, ('__a0',): -3,
 ('__a1',): -4, ('__a0', '__a1'): 4}
>>> H.is_solution_valid({'b': 0, 'c': 0, 'a': 1})
True
>>> H.is_solution_valid({'b': 0, 'c': 1, 'a': 1})
False

add_constraint_le_zero(P, lam=1, log_trick=True, bounds=None, suppress_warnings=False)

add_constraint_le_zero.

Enforce that P <= 0 by penalizing invalid solutions with lam.

Parameters

P (dict representing a PUBO.) – The PUBO constraint such that P <= 0. Note that P will be converted to a qubovert.PUBO object if it is not already, thus it must follow the conventions, see help(qubovert.PUBO). Please note that if P contains any symbols, then bounds must be supplied, since they cannot be determined when symbols are present.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the constraint.
log_trick (bool (optional, defaults to True)) – Whether or not to use the log trick to enforce the inequality constraint. See Notes below for more details.
bounds (two element tuple (optional, defaults to None)) – A tuple (min, max), the minimum and maximum values that the PUBO P can take. If bounds is None, then they will be calculated (approximately), or if either of the elements of bounds is None, then that element will be calculated (approximately).
suppress_warnings (bool (optional, defaults to False)) – Whether or not to surpress warnings.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Notes

There is no general way to enforce non integer inequality constraints. Thus this function is only guarenteed to work for integer inequality constraints (ie constraints of the form \(x_0 + 2x_1 + ... \leq 0\)). However, it can be used for non integer inequality constraints, but it is recommended that the value of lam be set small, since valid solutions may still recieve a penalty to the objective function. For example,
```
>>> H = PCBO()
>>> H.add_constraint_le_zero({(0,): 1, (1,): 2, (2,): -1.5, (): .4})
>>> H
{(0,): 1.7999999999999998, (0, 1): 4, (0, 2): -3.0, (0, '__a0'): 2,
 (1,): 5.6, (1, 2): -6.0, (1, '__a0'): 4, (2,): 1.0499999999999998,
 (2, '__a0'): -3.0, (): 0.16000000000000003, ('__a0',): 1.8}
>>> test_sol = {0: 0, 1: 0, 2: 1, '__a0': 1}
>>> H.is_solution_valid(test_sol)
True
>>> H.value(test_sol)
0.01
```
{0: 0, 1: 0, 2: 1} is a valid solution to H, but it will still cause a nonzero penalty to be added to the objective function.
To enforce the inequality constraint, ancilla bits will be introduced (labels with _a). If log_trick is True, then approximately \(\log_2 |\min_x \text{P.value(x)}|\) ancilla bits will be used. If log_trick is False, then approximately \(|\min_x \text{P.value(x)}|\) ancilla bits will be used.

Examples

Enforce that \(-x_a x_b x_c + x_a -4x_a x_b + 3x_c \leq 2\).

>>> H = PCBO().add_constraint_le_zero(
        {('a', 'b', 'c'): -1, ('a',): 1,
         ('a', 'b'): -4, ('c',): 3, (): -2}
    )
>>> H
{('b', 'c', 'a'): -19, ('b', 'c', 'a', '__a0'): -2,
 ('__a1', 'b', 'c', 'a'): -4, ('__a2', 'b', 'c', 'a'): -8, ('a',): -3,
 ('b', 'a'): 24, ('c', 'a'): 6, ('a', '__a0'): 2, ('__a1', 'a'): 4,
 ('__a2', 'a'): 8, ('b', 'a', '__a0'): -8, ('__a1', 'b', 'a'): -16,
 ('__a2', 'b', 'a'): -32, ('c',): -3, ('c', '__a0'): 6,
 ('__a1', 'c'): 12, ('__a2', 'c'): 24, (): 4, ('__a0',): -3,
 ('__a1',): -4, ('__a1', '__a0'): 4, ('__a2', '__a0'): 8,
 ('__a2', '__a1'): 16}
>>> H.is_solution_valid({'b': 0, 'c': 0, 'a': 1})
True
>>> H.is_solution_valid({'b': 0, 'c': 1, 'a': 1})
False

add_constraint_lt_zero(P, lam=1, log_trick=True, bounds=None, suppress_warnings=False)

add_constraint_lt_zero.

Enforce that P < 0 by penalizing invalid solutions with lam. See Notes below for more details.

Parameters

P (dict representing a PUBO.) – The PUBO constraint such that P < 0. Note that P will be converted to a qubovert.PUBO object if it is not already, thus it must follow the conventions, see help(qubovert.PUBO). Please note that if P contains any symbols, then bounds must be supplied, since they cannot be determined when symbols are present.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the constraint.
log_trick (bool (optional, defaults to True)) – Whether or not to use the log trick to enforce the inequality constraint. See Notes below for more details.
bounds (two element tuple (optional, defaults to None)) – A tuple (min, max), the minimum and maximum values that the PUBO P can take. If bounds is None, then they will be calculated (approximately), or if either of the elements of bounds is None, then that element will be calculated (approximately).
suppress_warnings (bool (optional, defaults to False)) – Whether or not to surpress warnings.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Notes

There is no general way to enforce non integer inequality constraints. Thus this function is only guarenteed to work for integer inequality constraints (ie constraints of the form \(x_0 + 2x_1 + ... < 0\)). However, it can be used for non integer inequality constraints, but it is recommended that the value of lam be set small, since valid solutions may still recieve a penalty to the objective function. For example,
```
>>> H = PCBO()
>>> H.add_constraint_lt_zero({(0,): 1, (1,): 2, (2,): -.5, (): .4})
>>> test_sol = {0: 0, 1: 0, 2: 1}
>>> H.is_solution_valid(test_sol)
True
>>> H.value(test_sol)
0.01
```
{0: 0, 1: 0, 2: 1} is a valid solution to H, but it will still cause a nonzero penalty to be added to the objective function.
To enforce the inequality constraint, ancilla bits will be introduced (labels with _a). If log_trick is True, then approximately \(\log_2 |\min_x \text{P.value(x)}|\) ancilla bits will be used. If log_trick is False, then approximately \(|\min_x \text{P.value(x)}|\) ancilla bits will be used.

Examples

Enforce that \(-x_a x_b x_c + x_a -4x_a x_b + 3x_c < 2\).

>>> H = PCBO().add_constraint_lt_zero(
        {('a', 'b', 'c'): -1, ('a',): 1,
         ('a', 'b'): -4, ('c',): 3, (): -2}
    )
>>> H
{('b', 'c', 'a'): -19, ('b', '__a0', 'c', 'a'): -2,
 ('b', 'c', 'a', '__a1'): -4, ('a',): -3, ('b', 'a'): 24,
 ('c', 'a'): 6, ('__a0', 'a'): 2, ('a', '__a1'): 4,
 ('b', '__a0', 'a'): -8, ('b', 'a', '__a1'): -16, ('c',): -3,
 ('__a0', 'c'): 6, ('c', '__a1'): 12, (): 4, ('__a0',): -3,
 ('__a1',): -4, ('__a0', '__a1'): 4}
>>> H.is_solution_valid({'b': 0, 'c': 0, 'a': 1})
True
>>> H.is_solution_valid({'b': 0, 'c': 1, 'a': 1})
False

add_constraint_ne_zero(P, lam=1, log_trick=True, bounds=None, suppress_warnings=False)

add_constraint_ne_zero.

Enforce that P != 0 by penalizing invalid solutions with lam. See Notes below for more details.

Parameters

P (dict representing a PUBO.) – The PUBO constraint such that P != 0. Note that P will be converted to a qubovert.PUBO object if it is not already, thus it must follow the conventions, see help(qubovert.PUBO). Please note that if P contains any symbols, then bounds must be supplied, since they cannot be determined when symbols are present.
lam (float > 0 or sympy.Symbol (optional, defaults to 1)) – Langrange multiplier to penalize violations of the constraint.
log_trick (bool (optional, defaults to True)) – Whether or not to use the log trick to enforce the inequality constraint. See Notes below for more details.
bounds (two element tuple (optional, defaults to None)) – A tuple (min, max), the minimum and maximum values that the PUBO P can take. If bounds is None, then they will be calculated (approximately), or if either of the elements of bounds is None, then that element will be calculated (approximately).
suppress_warnings (bool (optional, defaults to False)) – Whether or not to surpress warnings.

Returns

self – Updates the PCBO in place, but returns self so that operations can be strung together.

Return type

PCBO.

Notes

There is no general way to enforce non integer inequality constraints. Thus this function is only guarenteed to work for integer inequality constraints (ie constraints of the form \(x_0 + 2x_1 + ... != 0\)). However, it can be used for non integer inequality constraints, but it is recommended that the value of lam be set small, since valid solutions may still recieve a penalty to the objective function.
To enforce the inequality constraint, ancilla bits will be introduced (labels with _a). If log_trick is True, then approximately \(\log_2 |\min_x \text{P.value(x)}|\) ancilla bits will be used. If log_trick is False, then approximately \(|\min_x \text{P.value(x)}|\) ancilla bits will be used.

Examples

Enforce that \(-x_a x_b x_c + x_a -4x_a x_b + 3x_c != 2\).

>>> H = PCBO().add_constraint_ne_zero(
        {('a', 'b', 'c'): -1, ('a',): 2,
        ('a', 'b'): -4, ('c',): 3, (): -2}
    )
>>> print(H)
{('c', 'a', 'b'): -19, ('__a0', 'c', 'a', 'b'): -4,
 ('__a0', 'c', '__a1', 'a', 'b'): -4, ('c', '__a1', 'a', 'b'): 2,
 ('__a0', 'c', '__a2', 'a', 'b'): -8, ('c', '__a2', 'a', 'b'): 4,
 ('__a0', '__a3', 'c', 'a', 'b'): -16, ('__a3', 'c', 'a', 'b'): 8,
 ('__a0', 'c', '__a4', 'a', 'b'): -32, ('c', '__a4', 'a', 'b'): 16,
 ('a',): -8, ('c', 'a'): 12, ('__a0', 'a'): 8,
 ('__a0', '__a1', 'a'): 8, ('__a1', 'a'): -4,
 ('__a0', '__a2', 'a'): 16, ('__a2', 'a'): -8,
 ('__a0', '__a3', 'a'): 32, ('__a3', 'a'): -16,
 ('__a0', '__a4', 'a'): 64, ('__a4', 'a'): -32, ('a', 'b'): 24,
 ('__a0', 'a', 'b'): -16, ('__a0', '__a1', 'a', 'b'): -16,
 ('__a1', 'a', 'b'): 8, ('__a0', '__a2', 'a', 'b'): -32,
 ('__a2', 'a', 'b'): 16, ('__a0', '__a3', 'a', 'b'): -64,
 ('__a3', 'a', 'b'): 32, ('__a0', '__a4', 'a', 'b'): -128,
 ('__a4', 'a', 'b'): 64, ('__a0', 'c'): 12, ('__a0', 'c', '__a1'): 12,
 ('c', '__a1'): -6, ('__a0', 'c', '__a2'): 24, ('c', '__a2'): -12,
 ('__a0', '__a3', 'c'): 48, ('__a3', 'c'): -24,
 ('__a0', 'c', '__a4'): 96, ('c', '__a4'): -48, ('c',): -9, (): 9,
 ('__a0',): -8, ('__a0', '__a1'): -8, ('__a1',): 7,
 ('__a0', '__a2'): -16, ('__a2',): 16, ('__a3',): 40,
 ('__a0', '__a4'): -64, ('__a4',): 112, ('__a2', '__a1'): 4,
 ('__a3', '__a1'): 8, ('__a4', '__a1'): 16, ('__a3', '__a2'): 16,
 ('__a4', '__a2'): 32, ('__a0', '__a3'): -32, ('__a3', '__a4'): 64}
>>> print(H.is_solution_valid({'b': 0, 'c': 0, 'a': 1}))
False
>>> print(H.is_solution_valid({'b': 0, 'c': 1, 'a': 1}))
True

clear()

clear.

For efficiency, the internal variables for degree, num_binary_variables, max_index are computed as the dictionary is being built (and in subclasses such as qubovert.PUBO, properties such as mapping and reverse_mapping). This can cause these values to be wrong for some specific situations. Thus, when we clear, we also need to reset all of these cached values. This function remove all the elments from self and resets the cached values.

property constraints

constraints.

Return the constraints of the PCBO.

Returns: res – The keys of res are some or all of 'eq', 'ne', 'lt', 'le', 'gt', and 'ge'. The values are lists of qubovert.PUBO objects. For a given key, value pair k, v, the v[i] element represents the PUBO v[i] being == 0 if k == 'eq', != 0 if k == 'ne', < 0 if k == 'lt', <= 0 if k == 'le', > 0 if k == 'gt', >= 0 if k == 'ge'.
Return type: dict.

convert_solution(solution, spin=False)

convert_solution.

Convert the solution to the integer labeled PUBO to the solution to the originally labeled PUBO.

Parameters

solution (iterable or dict.) – The PUBO, PUSO, QUBO, or QUSO solution output. The PUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for PUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value. The QUBO/QUSO solution output includes the assignment for the ancilla variables used to reduce the degree of the PUBO.
spin (bool (optional, defaults to False)) – spin indicates whether solution is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin parameter.

Returns

res – Maps boolean variable labels to their PUBO solutions values {0, 1}.

Return type

dict.

Example

>>> pubo = PUBO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> pubo
{('a',): 5, ('a', 0, 1): -2, (): -1.5}
>>> P = pubo.to_pubo()
>>> P
{(0,): 5, (0, 1): -2, (): -1.5}
>>> pubo.convert_solution({0: 1, 1: 0, 2: 1})
{'a': 1, 0: 0, 1: 1}

In the next example, notice that we introduce ancilla variables to represent that `(0, 1) term. See the to_qubo method for more info.

>>> pubo = PUBO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> pubo.mapping
{'a': 0, 0: 1, 1: 2}
>>> Q = pubo.to_qubo(3)
>>> Q
{(0,): 5, (0, 3):-2, ():-1.5, (1, 2): 3, (3,): 3, (1, 3): 3, (2, 3): 3}
>>> pubo.convert_solution({0: 1, 1: 0, 2: 1, 2: 0})
{'a': 1, 0: 0, 1: 1}

Notes

We take ignore the ancilla variable assignments when we convert the solution. For example if the conversion from PUBO to QUBO introduced an ancilla varable z = xy where x and y are variables of the PUBO, then solution must have values for x, y, and z. If the QUBO solver found that x = 1, y = 0, and z = 1, then the constraint that z = xy is not satisfied (one possible cause for this is if the lam argument in to_qubo is too small). convert_solution will return that x = 1 and y = 0 and ignore the value of z.

copy()

copy.

Same as dict.copy, but we adjust the method so that it returns a DictArithmetic object, or whatever object is the subclass.

Returns: d – Same as self.__class__.
Return type: DictArithmetic object, or subclass of.

classmethod create_var(name)

create_var.

Create the variable with name name.

Parameters: name (hashable object allowed as a key.) – Name of the variable.
Returns: res – The model representing the variable with type cls.
Return type: cls object.

Examples

>>> from qubovert.utils import DictArithmetic
>>>
>>> x = DictArithmetic.create_var('x')
>>> x == DictArithmetic({('x',): 1})
True
>>> isinstance(x, DictArithmetic)
True
>>> x.name
'x'

>>> from qubovert import QUSO
>>>
>>> z = QUSO.create_var('z')
>>> print(z)
{('z',): 1}
>>> print(isinstance(z, QUSO))
True
>>> print(z.name)
'z'

static default_lam(v)

default_lam.

This is the default function used in to_qubo. It returns 1 + abs(v). It weights the penalties used to enforce the constraint xy = z. See the to_qubo method.

Parameters: v (float.) –
Returns: res – Penalty weight.
Return type: float.

property degree

degree.

Return the degree of the problem.

Returns: deg
Return type: int.

fromkeys(value=None, /): Create a new dictionary with keys from iterable and values set to value.

get(key, default=None, /): Return the value for key if key is in the dictionary, else default.

is_solution_valid(solution)

is_solution_valid.

Finds whether or not the given solution satisfies the constraints.

Parameters: solution (dict.) – Must be the solution in terms of the original variables. Thus if solution is the solution to the self.to_pubo, self.to_qubo, self.to_puso, or self.to_quso formulations, then you should first call self.convert_solution. See help(self.convert_solution).
Returns: valid – Whether or not the given solution satisfies the constraints.
Return type: bool.

items() → a set-like object providing a view on D's items

keys() → a set-like object providing a view on D's keys

property mapping

mapping.

Return a copy of the mapping dictionary that maps the provided labels to integers from 0 to n-1, where n is the number of variables in the problem.

Returns: mapping – Dictionary that maps provided labels to integer labels.
Return type: dict.

property max_index

max_index.

Return the maximum label of the integer labeled version of the problem.

Returns: m
Return type: int.

property name

name.

Return the name of the object.

Returns: name
Return type: object.

Example

>>> d = DictArithmetic()
>>> d.name
None
>>> d.name = 'd'
>>> d.name
'd'

normalize(value=1)

normalize.

Normalize the coefficients to a maximum magnitude.

Parameters: value (float (optional, defaults to 1)) – Every coefficient value will be normalized such that the coefficient with the maximum magnitude will be +/- 1.

Examples

>>> from qubovert.utils import DictArithmetic
>>> d = DictArithmetic({(0, 1): 1, (1, 2, 'x'): 4})
>>> d.normalize()
>>> print(d)
{(0, 1): 0.25, (1, 2, 'x'): 1}

>>> from qubovert.utils import DictArithmetic
>>> d = DictArithmetic({(0, 1): 1, (1, 2, 'x'): -4})
>>> d.normalize()
>>> print(d)
{(0, 1): 0.25, (1, 2, 'x'): -1}

>>> from qubovert import PUBO
>>> d = PUBO({(0, 1): 1, (1, 2, 'x'): 4})
>>> d.normalize()
>>> print(d)
{(0, 1): 0.25, (1, 2, 'x'): 1}

>>> from qubovert.utils import PUBO
>>> d = PUBO({(0, 1): 1, (1, 2, 'x'): -4})
>>> d.normalize()
>>> print(d)
{(0, 1): 0.25, (1, 2, 'x'): -1}

property num_ancillas

num_ancillas.

Return the number of ancilla variables introduced to the PCBO in order to enforce the inputted constraints.

Returns: num – Number of ancillas in the PCBO.
Return type: int.

property num_binary_variables

num_binary_variables.

Return the number of binary variables in the problem.

Returns: n – Number of binary variables in the problem.
Return type: int.

property num_terms

num_terms.

Return the number of terms in the dictionary.

Returns: n – Number of terms in the dictionary.
Return type: int.

property offset

offset.

Get the part that does not depend on any variables. Ie the value corresponding to the () key.

Returns: offset
Return type: float.

pop(k[, d]) → v, remove specified key and return the corresponding value.: If key is not found, d is returned if given, otherwise KeyError is raised

popitem()

Remove and return a (key, value) pair as a 2-tuple.

Pairs are returned in LIFO (last-in, first-out) order. Raises KeyError if the dict is empty.

pretty_str(var_prefix='x')

pretty_str.

Return a pretty string representation of the model.

Parameters: var_prefix (str (optional, defaults to 'x').) – The prefix for the variables.
Returns: res
Return type: str.

refresh()

refresh.

For efficiency, the internal variables for degree, num_binary_variables, max_index are computed as the dictionary is being built (and in subclasses such as qubovert.PUBO, properties such as mapping and reverse_mapping). This can cause these values to be wrong for some specific situations. Calling refresh will rebuild the dictionary, resetting all of the values.

Examples

>>> from qubovert.utils import PUBOMatrix
>>> P = PUBOMatrix()
>>> P[(0,)] += 1
>>> P, P.degree, P.num_binary_variables
{(0,): 1}, 1, 1
>>> P[(0,)] -= 1
>>> P, P.degree, P.num_binary_variables
{}, 1, 1
>>> P.refresh()
>>> P, P.degree, P.num_binary_variables
{}, 0, 0

>>> from qubovert import PUBO
>>> P = PUBO()
>>> P[('a',)] += 1
>>> P, P.mapping, P.reverse_mapping
{('a',): 1}, {'a': 0}, {0: 'a'}
>>> P[('a',)] -= 1
>>> P, P.mapping, P.reverse_mapping
{}, {'a': 0}, {0: 'a'}
>>> P.refresh()
>>> P, P.mapping, P.reverse_mapping
{}, {}, {}

classmethod remove_ancilla_from_solution(solution)

remove_ancilla_from_solution.

Take a solution to the PCBO and remove all the ancilla variables, ( represented by _a prefixes).

Parameters: solution (dict.) – Must be the solution in terms of the original variables. Thus if solution is the solution to the self.to_pubo, self.to_qubo, self.to_puso, or self.to_quso formulations, then you should first call self.convert_solution. See help(self.convert_solution).
Returns: res – The same as solution but with all the ancilla bits removed.
Return type: dict.

property reverse_mapping

reverse_mapping.

Return a copy of the reverse_mapping dictionary that maps the integer labels to the provided labels. Opposite of mapping.

Returns: reverse_mapping – Dictionary that maps integer labels to provided labels.
Return type: dict.

set_mapping(*args, **kwargs)

set_mapping.

BO sublcasses automatically create a mapping from variable names to integers as they are being built. However, the mapping is based on the order in which elements are entered and therefore may not be as desired. Of course, the convert_solution method keeps track of the mapping and can/should always be used. But if you want a consistent mapping, then set_mapping can be used.

Consider the following examples (we use the qubovert.QUBO class for the examples, which is a subclass of BO).

Example 1:

>>> from qubovert import QUBO
>>> Q = QUBO()
>>> Q[(0,)] += 1
>>> Q[(1,)] += 2
>>> Q.mapping
{0: 0, 1: 1}
>>> Q.to_qubo()
{(0,): 1, (1,): 2}

Example 2:

>>> from qubovert import QUBO
>>> Q = QUBO()
>>> Q[(1,)] += 2
>>> Q[(0,)] += 1
>>> Q.mapping
{0: 1, 1: 0}
>>> Q.to_qubo()
{(0,): 2, (1,): 1}

To ensure consistency in mappings, you can provide your own mapping with set_mapping. See the following modified examples.

Modified example 1:

>>> from qubovert import QUBO
>>> Q = QUBO()
>>> Q[(0,)] += 1
>>> Q[(1,)] += 2
>>> Q.set_mapping({0: 0, 1: 1})
>>> Q.mapping
{0: 0, 1: 1}
>>> Q.to_qubo()
{(0,): 1, (1,): 2}

Modified example 2:

>>> from qubovert import QUBO
>>> Q = QUBO()
>>> Q[(1,)] += 2
>>> Q[(0,)] += 1
>>> Q.set_mapping({0: 0, 1: 1})
>>> Q.mapping
{0: 0, 1: 1}
>>> Q.to_qubo()
{(0,): 1, (1,): 2}

Parameters: arguments (defines a dictionary with d = dict(*args, **kwargs).) – d will become the mapping. See help(self.mapping)

Notes

Using set_mapping to set the mapping will also automatically set the reverse_mapping, so there is no need to call both set_mapping and set_reverse_mapping.

set_reverse_mapping(*args, **kwargs)

set_reverse_mapping.

Same as set_mapping but reversed. See help(self.reverse_mapping) and help(self.set_mapping).

Parameters: arguments (defines a dictionary with d = dict(*args, **kwargs).) – d will become the reverse mapping. See help(self.reverse_mapping).

Notes

Using set_reverse_mapping to set the mapping will also automatically set the mapping, so there is no need to call both set_mapping and set_reverse_mapping.

setdefault(key, default=None, /)

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

simplify()

simplify.

If self has any symbolic expressions, this will go through and simplify them. This will also make everything a float!

Returns
Return type: None. Updates it in place.

solve_bruteforce(all_solutions=False)

solve_bruteforce.

Solve the problem bruteforce. THIS SHOULD NOT BE USED FOR LARGE PROBLEMS! This is the exact same as calling ``qubovert.utils.solve_pubo_bruteforce(

self, all_solutions, self.is_solution_valid)[1]``.

Parameters: all_solutions (bool.) – See the description of the all_solutions parameter in qubovert.utils.solve_pubo_bruteforce.
Returns: res – qubovert.utils.solve_pubo_bruteforce.
Return type: the second element of the two element tuple that is returned from

classmethod squash_key(key)

squash_key.

Will convert the input key into the standard form for PUBOMatrix / QUBOMatrix. It will get rid of duplicates and sort. This method will check to see if the input key is valid.

Parameters: key (tuple of integers.) –
Returns: k – A sorted and squashed version of key.
Return type: tuple of integers.
Raises: KeyError if the key is invalid. –

Example

>>> squash_key((0, 4, 0, 3, 3, 2))
>>> (0, 2, 3, 4)

subgraph(nodes, connections=None)

subgraph.

Create the subgraph of self that only includes vertices in nodes, and external nodes are given the values in connections.

Parameters

nodes (set.) – Nodes of self to include in the subgraph.
connections (dict (optional, defaults to {})) – For each node in self that is not in nodes, we assign a value given by connections.get(node, 0).

Returns

D – The subgraph of self with nodes in nodes and the values of the nodes not included given by connections.

Return type

same as type(self)

Notes

Any offset value included in self (ie {(): 1}) will be ignored, however there may be an offset in the output D.

Examples

>>> G = DictArithmetic(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2}
>>> )
>>> D = G.subgraph({0, 2}, {1: 5})
>>> D
{(0,): -17, (0, 2): -1, (): 10}

>>> G = DictArithmetic(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2}
>>> )
>>> D = G.subgraph({0, 2})
>>> D
{(0, 2): -1, (0,): 3}

>>> G = DictArithmetic(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2}
>>> )
>>> D = G.subgraph({0, 1}, {2: -10})
>>> D
{(0, 1): -4, (0,): 13, (1,): 2}

>>> G = DictArithmetic(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2}
>>> )
>>> D = G.subgraph({0, 1})
>>> D
{(0, 1): -4, (0,): 3, (1,): 2}

subs(*args, **kwargs)

subs.

Replace any sympy symbols that are used in the dict with values. Please see help(sympy.Symbol.subs) for more info.

Parameters: arguments (substitutions.) – Same parameters as are inputted into sympy.Symbol.subs.
Returns: res – Same as self but with all the symbols replaced with values.
Return type: PCBO object.

subvalue(values)

subvalue.

Replace each element in self with a value in values if it exists.

Parameters: values (dict.) – For each node v in self that is in values, we replace the node with values[v].
Returns: D
Return type: same as type(self)

Examples

>>> G = DictArithmetic(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2
>>> }
>>> D = G.subvalue({0: 2})
>>> D
{(1,): -6, (2,): -2, (): 8}

>>> G = DictArtihmetic(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2
>>> }
>>> D = G.subvalue({2: -3})
>>> D
{(0, 1): -4, (0,): 6, (1,): 2, (): 2}

>>> G = PUBO(
>>>     {(0, 1): -4, (0, 2): -1, (0,): 3, (1,): 2, (): 2
>>> }
>>> D = G.subvalue({2: -3})
>>> D
{(0, 1): -4, (0,): 6, (1,): 2, (): 2}

to_enumerated()

to_enumerated.

Return the default enumerated Matrix object.

If self is a QUBO, self.to_enumerated() is equivalent to self.to_qubo().

If self is a QUSO, self.to_enumerated() is equivalent to self.to_quso().

If self is a PUBO or PCBO, self.to_enumerated() is equivalent to self.to_pubo().

If self is a PUSO or PCSO, self.to_enumerated() is equivalent to self.to_puso().

Returns: res – If self is a QUBO type, then this method returns the corresponding QUBOMatrix type. If self is a QUSO type, then this method returns the corresponding QUSOMatrix type. If self is a PUBO or PCBO type, then this method returns the corresponding PUBOMatrix type. If self is a PUSO or PCSO type, then this method returns the corresponding PUSOMatrix type.
Return type: QUBOMatrix, QUSOMatrix, PUBOMatrix, or PUSOMatrix object.

to_pubo(deg=None, lam=None, pairs=None)

to_pubo.

Create and return upper triangular degree deg PUBO representing the problem. The labels will be integers from 0 to n-1.

Parameters

deg (int >= 0 (optional, defaults to None)) – The degree of the final PUBO. If deg is None, then the degree of the output PUBO will be the same as the degree of self, ie see self.degree.
lam (function (optional, defaults to None)) – Note that if deg is None or deg >= self.degree, then lam is unneccessary and will not be used. If lam is None, the function PUBO.default_lam will be used. lam is the penalty factor to introduce in order to enforce the ancilla constraints. When we reduce the degree of the model, we add penalties to the lower order model in order to enforce ancilla variable constraints. These constraints will be multiplied by lam(v), where v is the value associated with the term that it is reducing. For example, a term (0, 1, 2): 3 in the higher order model may be reduced to a term (0, 3): 3 for the lower order model, and then the fact that 3 should be the product of 1 and 2 will be enforced with a penalty weight lam(3).
pairs (set (optional, defaults to None)) – A set of tuples of variable pairs to prioritize pairing together in to degree reduction. If a pair in pairs is found together in the PUBO, it will be chosen as a pair to reduce to a single ancilla. You should supply this parameter if you have a good idea of an efficient way to reduce the degree of the PUBO. If pairs is None, then it will be the empty set set(). In other words, no variable pairs will be prioritized, and instead variable pairs will be chosen to reduce to an ancilla bases solely on frequency of occurrance.

Returns

P – The upper triangular PUBO matrix, a PUBOMatrix object. For most practical purposes, you can use PUBOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.PUBOMatrix).

Return type

qubovert.utils.PUBOMatrix object.

Notes

The penalty that we use to enforce the constraints that the ancilla variable z is equal to the product of the two variables that it is replacing, xy, is:

0 if z == xy, 3*lam(v) if x == y == 0 and z == 1, and lam(v) else.

See https://arxiv.org/pdf/1307.8041.pdf equation 6.

to_puso(*args, **kwargs)

to_puso.

Create and return PUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls to_pubo or to_quso and converts to a PUSO formulation.

Parameters

arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.

Returns

H – For most practical purposes, you can use PUSOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.PUSOMatrix).

Return type

qubovert.utils.PUSOMatrix object.

Raises

RecursionError` if neither to_pubo nor to_puso are define –
in the subclass. –

to_qubo(lam=None, pairs=None)

to_qubo.

Create and return upper triangular QUBO representing the problem. The labels will be integers from 0 to n-1. We introduce ancilla variables in order to reduce the degree of the PUBO to a QUBO. The solution to the PUBO can be read from the solution to the QUBO by using the convert_solution method.

Parameters

lam (function (optional, defaults to None)) – If lam is None, the function PUBO.default_lam will be used. lam is the penalty factor to introduce in order to enforce the ancilla constraints. When we reduce the degree of the PUBO to a QUBO, we add penalties to the QUBO in order to enforce ancilla variable constraints. These constraints will be multiplied by lam(v), where v is the value associated with the term that it is reducing. For example, a term (0, 1, 2): 3 in the PUBO may be reduced to a term (0, 3): 3 for the QUBO, and then the fact that 3 should be the product of 1 and 2 will be enforced with a penalty weight lam(3).
pairs (set (optional, defaults to None)) – A set of tuples of variable pairs to prioritize pairing together in to degree reduction. If a pair in pairs is found together in the PUBO, it will be chosen as a pair to reduce to a single ancilla. You should supply this parameter if you have a good idea of an efficient way to reduce the degree of the PUBO. If pairs is None, then it will be the empty set set(). In other words, no variable pairs will be prioritized, and instead variable pairs will be chosen to reduce to an ancilla bases solely on frequency of occurrance.

Returns

Q – The upper triangular QUBO matrix, a QUBOMatrix object. For most practical purposes, you can use QUBOMatrix in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.QUBOMatrix).

Return type

qubovert.utils.QUBOMatrix object.

to_quso(*args, **kwargs)

to_quso.

Create and return QUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls to_qubo and converts the QUBO formulation to an QUSO formulation.

Parameters

arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.

Returns

L – The upper triangular coupling matrix, where two element tuples represent couplings and one element tuples represent fields. For most practical purposes, you can use IsingCoupling in the same way as an ordinary dictionary. For more information, see help(qubovert.utils.QUSOMatrix).

Return type

qubovert.utils.QUSOMatrix object.

Raises

RecursionError` if neither to_qubo nor to_quso are define –
in the subclass. –

update(*args, **kwargs)

update.

Update the PCBO but following all the conventions of this class.

Parameters: arguments (defines a dictionary or PCBO.) – Ie d = dict(*args, **kwargs). Each element in d will be added in place to this instance following all the required convensions.

value(x)

value.

Find the value of \(\sum_{i,...,j} P_{i...j} x_{i} ... x_{j}\). Calling self.value(x) is the same as calling qubovert.utils.pubo_value(x, self).

Parameters: x (dict or iterable.) – Maps boolean variable indices to their boolean values, 0 or 1. Ie x[i] must be the boolean value of variable i.
Returns: value – The value of the PUBO with the given assignment x. Ie
Return type: float.

Example

>>> from qubovert.utils import QUBOMatrix, PUBOMatrix
>>> from qubovert import QUBO, PUBO

>>> P = PUBOMatrix({(0, 0): 1, (0, 1): -1})
>>> x = {0: 1, 1: 0}
>>> P.value(x)
1

>>> Q = QUBOMatrix({(0, 0): 1, (0, 1): -1})
>>> x = {0: 1, 1: 0}
>>> Q.value(x)
1

>>> P = PUBO({(0, 0): 1, (0, 1): -1})
>>> x = {0: 1, 1: 0}
>>> P.value(x)
1

>>> Q = QUBO({(0, 0): 1, (0, 1): -1})
>>> x = {0: 1, 1: 0}
>>> Q.value(x)
1

values() → an object providing a view on D's values

property variables

variables.

Return a set of all the variables in the dict.

Returns: res
Return type: set.