Polynomial Unconstrained Spin Optimization (PUSO)

Accessed with qubovert.PUSO

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

PUSO.

Class to manage converting general PUSO problems to and from their PUSO, PUBO, QUSO, and QUBO formluations. In general, this class deals with unconstrained optimization problems that have arbitrary degree. To convert this to a QUSO (see to_quso) or QUBO (to_qubo) we have to introduce ancilla variables. The convert_solution method deals with converting a solution to the problem with ancilla variables back to the solution to the original problem.

This class deals with PUSOs that have spin labels that do not range from 0 to n-1. Note that it is generally more efficient to initialize an empty PUSO object and then build the PUSO, rather than initialize a PUSO object with an already built dict.

PUSO inherits some methods and attributes the PUSOMatrix class. See help(qubovert.utils.PUSOMatrix).

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

Example

>>> puso = PUSO()
>>> puso[('a',)] += 5
>>> puso[(0, 'a', 1)] -= 2
>>> puso -= 1.5
>>> puso
{('a',): 5, ('a', 0, 1): -2, (): -1.5}

>>> puso = PUSO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> puso
{('a',): 5, ('a', 0, 1): -2, (): -1.5}
>>> H = puso.to_puso()
>>> H
{(0,): 5, (0, 1): -2, (): -1.5}
>>> puso.convert_solution({0: 1, 1: -1, 2: 1})
{'a': 1, 0: -1, 1: 1}


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

>>> puso = PUSO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> puso.mapping
{'a': 0, 0: 1, 1: 2}
>>> L = puso.to_quso()
>>> L
{(0,): 0.75, (): 11.25, (3,): 8.5, (0, 1): 4.25, (1,): -4.25, (0, 3): -8.5,
(1, 3): -8.5, (2, 3): -4.0, (1, 2): 2.0, (0, 2): 2.0, (2,): -2.0}
>>> puso.convert_solution({0: 1, 1: -1, 2: 1, 3: -1})
{'a': 1, 0: -1, 1: 1}


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(PUSO.refresh)

Examples

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


__init__.

This class deals with PUSOs that have spin labels that do not range from 0 to n-1. Note that it is generally more efficient to initialize an empty PUSO object and then build the PUSO, rather than initialize a PUSO 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

>>> puso = PUSO()
>>> puso[('a',)] += 5
>>> puso[(0, 'a')] -= 2
>>> puso -= 1.5
>>> puso
{('a',): 5, ('a', 0): -2, (): -1.5}

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

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

convert_solution.

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

Parameters
• solution (iterable or dict.) – The PUSO, PUSO, QUSO, or QUSO solution output. The PUSO 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 PUSO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value. The QUSO/QUSO solution output includes the assignment for the ancilla variables used to reduce the degree of the PUSO.

• spin (bool (optional, defaults to True)) – 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 spin variable labels to their PUSO solutions values {1, -1}.

Return type

dict.

Example

>>> puso = PUSO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> puso
{('a',): 5, ('a', 0, 1): -2, (): -1.5}
>>> H = puso.to_puso()
>>> H
{(0,): 5, (0, 1): -2, (): -1.5}
>>> puso.convert_solution({0: 1, 1: -1, 2: 1})
{'a': 1, 0: -1, 1: 1}


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

>>> puso = PUSO({('a',): 5, (0, 'a', 1): -2, (): -1.5})
>>> puso.mapping
{'a': 0, 0: 1, 1: 2}
>>> L = puso.to_quso(3)
>>> L
{(0,): 5, (0, 3): -2, (): -2.25,
(1, 2): 3/4, (2, 3): 3/4, (1, 3): 3/4, (1,): 3/2, (2,): 3/2, (3,): 3}
>>> puso.convert_solution({0: 1, 1: -1, 2: 1, 2: -1})
{'a': 1, 0: -1, 1: 1}


Notes

We take ignore the ancilla variable assignments when we convert the solution. For example if the conversion from PUSO to QUSO introduced an ancilla varable z = xy where x and y are variables of the PUSO, then solution must have values for x, y, and z. If the QUSO solver found that x = 1, y = -1, and z = 1, then the constraint that z = xy is not satisfied (one possible cause for this is if the lam argument in to_quso is too small). convert_solution will return that x = 1 and y = -1 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'

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='z')

pretty_str.

Return a pretty string representation of the model.

Parameters

var_prefix (str (optional, defaults to 'z').) – 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_puso_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_puso_bruteforce.

Returns

resqubovert.utils.solve_puso_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 PUSOMatrix / QUSOMatrix. It will get rid of pairs 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.

Example

>>> squash_key((0, 4, 0, 3, 3, 2, 3))
>>> (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(deg=None, lam=None, pairs=None)

to_pubo.

Create and return upper triangular degree deg PUBO representing the PUSO 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 PUSO, 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 PUSO. 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(deg=None, lam=None, pairs=None)

to_puso.

Create and return upper triangular degree deg PUSO 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 PUSO. If deg is None, then the degree of the output PUSO 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 PUSO, 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 PUSO. 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

H – The upper triangular PUSO matrix, a PUSOMatrix object. 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.

Notes

See the to_pubo docstring for more information on the penalties and lam.

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 PUSO to a QUBO. The solution to the PUSO 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 PUSO 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 Hquso may be reduced to a term (0, 3): 3 for the QUSO, 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 PUSO, 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 PUSO. 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, an 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(lam=None, pairs=None)

to_quso.

Create and return upper triangular QUSO 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 PUSO to a QUSO. The solution to the PUSO can be read from the solution to the QUSO 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 PUSO to a QUSO, we add penalties to the QUSO 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 PUSO may be reduced to a term (0, 3): 3 for the QUSO, 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 PUSO, 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 PUSO. 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

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

Return type

qubovert.utils.QUSOMatrix object.

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

value.

Find the value of

$$\sum_{i,...,j} H_{i...j} z_{i} ... z_{j}$$. Calling self.value(z) is the same as calling qubovert.utils.puso_value(z, self).

Parameters

z (dict or iterable.) – Maps variable labels to their values, -1 or 1. Ie z[i] must be the value of variable i.

Returns

value – The value of the PUSO/QUSO with the given assignment z.

Return type

float.

Example

>>> from qubovert.utils import QUSOMatrix, PUSOMatrix
>>> from qubovert import QUSO, PUSO

>>> H = PUSOMatrix({(0, 1): -1, (0,): 1})
>>> z = {0: -1, 1: 1}
>>> H.value(z)
0

>>> H = PUSO({(0, 1): -1, (0,): 1})
>>> z = {0: -1, 1: 1}
>>> H.value(z)
0

>>> L = QUSOMatrix({(0, 1): -1, (0,): 1})
>>> z = {0: -1, 1: 1}
>>> L.value(z)
0

>>> L = QUSO({(0, 1): -1, (0,): 1})
>>> z = {0: -1, 1: 1}
>>> L.value(z)
0

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.