# Quadratic Unconstrained Boolean Optimization (QUBO)

Accessed with `qubovert.QUBO`

class qubovert.QUBO(*args, **kwargs)

QUBO.

Class to manage converting general QUBO problems to and from their QUBO and QUSO formluations.

This class deals with QUBOs that have boolean labels that do not range from 0 to n-1. If your labels are nonnegative integers, consider using `qubovert.utils.QUBOMatrix`. Note that it is generally more efficient to initialize an empty QUBO object and then build the QUBO, rather than initialize a QUBO object with an already built dict.

QUBO inherits some methods and attributes the `QUBOMatrix` class. See `help(qubovert.utils.QUBOMatrix)`.

QUBO inherits some methods and attributes the `BO` class. See `help(qubovert.utils.BO)`.

Example

```>>> qubo = QUBO()
>>> qubo[('a',)] += 5
>>> qubo[(0, 'a')] -= 2
>>> qubo -= 1.5
>>> qubo
{('a',): 5, ('a', 0): -2, (): -1.5}
```
```>>> qubo = QUBO({('a',): 5, (0, 'a'): -2, (): -1.5})
>>> qubo
{('a',): 5, ('a', 0): -2, (): -1.5}
>>> Q = qubo.to_qubo()
>>> Q
{(0,): 5, (0, 1): -2, (): -1.5}
>>> qubo.convert_solution({0: 1, 1: 0})
{'a': 1, 0: 0}
```

Note

For efficiency, many internal variables including mappings are computed as the problemis being built. This can cause these values to be wrong for some specific situations. Calling `refresh` will rebuild the dictionary, resetting all of the values. See `help(QUBO.refresh)`

Examples

```>>> from qubovert import QUBO
>>> Q = PUSO()
>>> Q[('a',)] += 1
>>> Q, Q.mapping, Q.reverse_mapping
{('a',): 1}, {'a': 0}, {0: 'a'}
>>> Q[('a',)] -= 1
>>> Q, Q.mapping, Q.reverse_mapping
{}, {'a': 0}, {0: 'a'}
>>> Q.refresh()
>>> Q, Q.mapping, Q.reverse_mapping
{}, {}, {}
```

__init__.

This class deals with QUBOs that have boolean labels that do not range from 0 to n-1. If your labels are nonnegative integers, consider using `qubovert.utils.QUBOMatrix`. Note that it is generally more efficient to initialize an empty QUBO object and then build the QUBO, rather than initialize a QUBO 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.

Examples

```>>> qubo = QUBO()
>>> qubo[('a',)] += 5
>>> qubo[(0, 'a')] -= 2
>>> qubo -= 1.5
>>> qubo
{('a',): 5, ('a', 0): -2, (): -1.5}
```
```>>> qubo = QUBO({('a',): 5, (0, 'a'): -2, (): -1.5})
>>> qubo
{('a',): 5, ('a', 0): -2, (): -1.5}
```
property Q

Return a plain dictionary representing the QUBO. Each key is a tuple of two integers, ie (1, 1) corresponds to (1,). Note that the offset in the QUBOMatrix is ignored (ie the value corresponding to the key ()). See the `offset` property to access it.

Returns

Q – Plain dictionary representing the QUBO in standard form.

Return type

dict.

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.

convert_solution(solution, spin=False)

convert_solution.

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

Parameters
• solution (iterable or dict.) – The QUBO or QUSO solution output. The QUBO 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 QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.

• 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 QUBO solutions values {0, 1}.

Return type

dict.

Example

```>>> qubo = QUBO({('a',): 1, ('a', 'b'): -2, ('c',): 1})
>>> Q = qubo.to_qubo()
>>> Q
{(0,): 1, (0, 1): -2, (2,): 1}
>>> solution = solve_qubo(Q)  # any solver you want
>>> solution
[1, 1, 0]  # or {0: 1, 1: 1, 2: 0}
>>> sol = qubo.convert_solution(solution)
>>> sol
{'a': 1, 'b': 1, 'c': 0}
```
```>>> qubo = QUBO({('a',): 1, ('a', 'b'): -2, ('c',): 1})
>>> L = qubo.to_quso()
>>> solution = solve_quso(L)  # any solver you want
>>> solution
[-1, -1, 1]  # or {0: -1, 1: -1, 2: 1}
>>> sol = qubo.convert_solution(solution)
>>> sol
{'a': 1, 'b': 1, 'c': 0}
```
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'
```
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.

Included for consistency with other problem classes. Always returns True since this is an unconstrainted problem.

Parameters

solution (iterable or dict.) –

Returns

valid – Always returns True.

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_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
{}, {}, {}
```
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

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

self, all_solutions, self.is_solution_valid)``.

Parameters

all_solutions (bool.) – See the description of the `all_solutions` parameter in `qubovert.utils.solve_qubo_bruteforce`.

Returns

res`qubovert.utils.solve_qubo_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

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

to_pubo.

Since the model is already a QUBO, `self.to_pubo` will simply return `qubovert.utils.PUBOMatrix(self.to_qubo())`.

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.

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

to_qubo.

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

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 dictionary but following all the conventions of this class.

Parameters

arguments (defines a dictionary, 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 the QUBO. Calling `self.value(x)` is the same as calling `qubovert.utils.qubo_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 QUBO 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.