Polynomial Constrained Spin Optimization (PCSO)
Accessed with qubovert.PCSO
. Note that it is important to use the PCSO.convert_solution
function to convert solutions of the PUBO, QUBO, PUSO, or QUSO formulations of the PCSO back to a solution to the PCSO formulation.
We also discuss the qubovert.spin_var
function here, which is just returns a PCSO
.
- qubovert.spin_var(name)
spin_var.
Create a PCSO (see
qubovert.PCSO
) from a single spin variable.- Parameters
name (any hashable object.) – Name of the spin variable.
- Returns
pcso – The model representing the spin variable.
- Return type
qubovert.PCSO object.
Examples
>>> from qubovert import spin_var, PCSO >>> >>> z0 = spin_var("z0") >>> print(z0) {('z0',): 1} >>> print(isinstance(z0, PCSO)) True >>> print(z0.name) z0
>>> z = [spin_var('z{}'.format(i)) for i in range(5)] >>> pcso = sum(z) >>> print(pcso) {('z0',): 1, ('z1',): 1, ('z2',): 1, ('z3',): 1, ('z4',): 1} >>> pcso **= 2 >>> print(pcso) {(): 5, ('z0', 'z1'): 2, ('z2', 'z0'): 2, ('z3', 'z0'): 2, ('z0', 'z4'): 2, ('z2', 'z1'): 2, ('z3', 'z1'): 2, ('z4', 'z1'): 2, ('z3', 'z2'): 2, ('z2', 'z4'): 2, ('z3', 'z4'): 2} >>> pcso *= -1 >>> print(pcso.solve_bruteforce(all_solutions=True)) [{'z0': -1, 'z1': -1, 'z2': -1, 'z3': -1, 'z4': -1}, {'z0': 1, 'z1': 1, 'z2': 1, 'z3': 1, 'z4': 1}] >>> pcso.add_constraint_eq_zero(z[0] + z[1]) >>> print(pcso.solve_bruteforce(all_solutions=True)) [{'z0': -1, 'z1': 1, 'z2': -1, 'z3': -1, 'z4': -1}, {'z0': -1, 'z1': 1, 'z2': 1, 'z3': 1, 'z4': 1}, {'z0': 1, 'z1': -1, 'z2': -1, 'z3': -1, 'z4': -1}, {'z0': 1, 'z1': -1, 'z2': 1, 'z3': 1, 'z4': 1}]
Notes
qubovert.spin_var(name)
is equivalent toqubovert.PCSO.create_var(name)
.
- class qubovert.PCSO(*args, **kwargs)
PCBO.
This class deals with Polynomial Constrained Spin Optimization. PCSO inherits some methods and attributes from the
PUSO
class. Seehelp(qubovert.PUSO)
.PCSO
has all the same methods asPUSO
, but adds some constraint methods; namelyadd_constraint_eq_zero(H, lam=1, ...)
enforces thatH == 0
by penalizing withlam
,add_constraint_ne_zero(H, lam=1, ...)
enforces thatH != 0
by penalizing withlam
,add_constraint_lt_zero(H, lam=1, ...)
enforces thatH < 0
by penalizing withlam
,add_constraint_le_zero(H, lam=1, ...)
enforces thatH <= 0
by penalizing withlam
,add_constraint_gt_zero(H, lam=1, ...)
enforces thatH > 0
by penalizing withlam
, andadd_constraint_ge_zero(H, lam=1, ...)
enforces thatH >= 0
by penalizing withlam
.
Each of these takes in a PUSO
H
and a lagrange multiplierlam
that defaults to 1. 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 PCSO ensuring that all the inputted constraints are satisfied. Whereasqubovert.utils.solve_puso_bruteforce(self)
orqubovert.utils.solve_puso_bruteforce(self.to_pubo())
will solve the PUSO created from the PCSO. If the inputted constraints are not enforced strong enough (ie too small lagrange multipliers) then these may not give the correct result, whereasself.solve_bruteforce()
will always give the correct result (ie one that satisfies all the constraints).
Examples
See
qubovert.PUSO
for more examples of using PCSO without constraints. Seequbovert.PCBO
for many constraint examples in PUBO form.PCSO
is the same but converting to PUSO.>>> H = PCSO() >>> H.add_constraint_eq_zero({('a', 1): 2, (1, 2): -1, (): -1}) >>> H {(): 6, ('a', 2): -4, ('a', 1): -4, (1, 2): 2}
>>> H = PCSO() >>> H.add_constraint_eq_zero( {(0, 1): 1} ).add_constraint_lt_zero( {(1, 2): 1, (): -1} )
__init__.
This class deals with polynomial constrained spin optimization. Note that it is generally more efficient to initialize an empty PCSO object and then build the PCSO, rather than initialize a PCSO 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 PCSO.
Examples
>>> pcso = PCSO() >>> pcso[('a',)] += 5 >>> pcso[(0, 'a')] -= 2 >>> pcso -= 1.5 >>> pcso {('a',): 5, ('a', 0): -2, (): -1.5} >>> pcso.add_constraint_eq_zero({('a',): 1, ('b',): 1}, lam=5) >>> pcso {('a',): 5, ('a', 0): -2, (): 8.5, ('a', 'b'): 10}
>>> pcso = PCSO({('a',): 5, (0, 'a', 1): -2, (): -1.5}) >>> pcso {('a',): 5, ('a', 0, 1): -2, (): -1.5}
- add_constraint_eq_zero(H, lam=1, bounds=None, suppress_warnings=False)
add_constraint_eq_zero.
Enforce that
H == 0
by penalizing invalid solutions withlam
.- Parameters
H (dict representing a PUSO.) – The PUSO constraint such that H == 0. Note that
H
will be converted to aqubovert.PUSO
object if it is not already, thus it must follow the conventions, seehelp(qubovert.PUSO)
. Please note that ifH
contains any symbols, thenbounds
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 PUSOH
can take. Ifbounds
is None, then they may be calculated (approximately), or if either of the elements ofbounds
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 PCSO in place, but returns
self
so that operations can be strung together.- Return type
PCSO.
Examples
The following enforces that \(\sum_{i=1}^{3} i z_i z_{i+1} == 0\).
>>> H = PCSO() >>> H.add_constraint_eq_zero({(1, 2): 1, (2, 3): 2, (3, 4): 3})
Here we show how operations can be strung together.
>>> H = PCSO() >>> H.add_constraint_lt_zero( {(0, 1): 1} ).add_constraint_eq_zero( {(1, 2): 1, (): -1} )
- add_constraint_ge_zero(H, lam=1, log_trick=True, bounds=None, suppress_warnings=False)
add_constraint_ge_zero.
Enforce that
H >= 0
by penalizing invalid solutions withlam
.- Parameters
H (dict representing a PUSO.) – The PUSO constraint such that H >= 0. Note that
H
will be converted to aqubovert.PUSO
object if it is not already, thus it must follow the conventions, seehelp(qubovert.PUSO)
. Please note that ifH
contains any symbols, thenbounds
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 PUSOH
can take. Ifbounds
is None, then they will be calculated (approximately), or if either of the elements ofbounds
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 PCSO in place, but returns
self
so that operations can be strung together.- Return type
PCSO.
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 \(z_0 + 2z_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 = PCSO() >>> H.add_constraint_ge_zero( {(0,): -0.5, (): -1.15, (1,): -1.0, (2,): 0.75}) >>> H {(0,): 1.65, (): 4.785, (0, 1): 1.0, (1,): 3.3, (0, 2): -0.75, (2,): -2.4749999999999996, ('__a0', 0): 0.5, ('__a0',): 1.65, (1, 2): -1.5, ('__a0', 1): 1.0, ('__a0', 2): -0.75} >>> H.is_solution_valid(test_sol) True >>> H.value(test_sol) 0.01
{0: -1, 1: -1, 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
isTrue
, then approximately \(\log_2 |\max_z \text{H.value(z)}|\) ancilla bits will be used. Iflog_trick
isFalse
, then approximately \(|\max_z \text{H.value(z)}|\) ancilla bits will be used.
- add_constraint_gt_zero(H, lam=1, log_trick=True, bounds=None, suppress_warnings=False)
add_constraint_gt_zero.
Enforce that
H > 0
by penalizing invalid solutions withlam
.- Parameters
H (dict representing a PUSO.) – The PUSO constraint such that H > 0. Note that
H
will be converted to aqubovert.PUSO
object if it is not already, thus it must follow the conventions, seehelp(qubovert.PUSO)
. Please note that ifH
contains any symbols, thenbounds
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 PUSOH
can take. Ifbounds
is None, then they will be calculated (approximately), or if either of the elements ofbounds
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 PCSO in place, but returns
self
so that operations can be strung together.- Return type
PCSO.
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 \(z_0 + 2z_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 = PCSO() >>> H.add_constraint_gt_zero( {(0,): -0.5, (): -1.65, (1,): -1.0, (2,): 0.25}) >>> test_sol = {0: -1, 1: -1, 2: 1} >>> H.is_solution_valid(test_sol) True >>> H.value(sol) 0.01
{0: -1, 1: -1, 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
isTrue
, then approximately \(\log_2 |\max_z \text{H.value(z)}|\) ancilla bits will be used. Iflog_trick
isFalse
, then approximately \(|\max_z \text{H.value(z)}|\) ancilla bits will be used.
- add_constraint_le_zero(H, lam=1, log_trick=True, bounds=None, suppress_warnings=False)
add_constraint_le_zero.
Enforce that
H <= 0
by penalizing invalid solutions withlam
.- Parameters
H (dict representing a PUSO.) – The PUSO constraint such that H <= 0. Note that
H
will be converted to aqubovert.PUSO
object if it is not already, thus it must follow the conventions, seehelp(qubovert.PUSO)
. Please note that ifH
contains any symbols, thenbounds
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 PUSOH
can take. Ifbounds
is None, then they will be calculated (approximately), or if either of the elements ofbounds
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 PCSO in place, but returns
self
so that operations can be strung together.- Return type
PCSO.
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 \(z_0 + 2z_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 = PCSO() >>> H.add_constraint_le_zero( {(0,): 0.5, (): 1.15, (1,): 1.0, (2,): -0.75}) >> H {(0,): 1.65, (): 4.785, (0, 1): 1.0, (1,): 3.3, (0, 2): -0.75, (2,): -2.4749999999999996, ('__a0', 0): 0.5, ('__a0',): 1.65, (1, 2): -1.5, ('__a0', 1): 1.0, ('__a0', 2): -0.75} >>> test_sol = {0: -1, 1: -1, 2: 1, '__a0': 1} >>> H.is_solution_valid(test_sol) True >>> H.value(test_sol) 0.01
{0: -1, 1: -1, 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
isTrue
, then approximately \(\log_2 |\min_z \text{H.value(z)}|\) ancilla bits will be used. Iflog_trick
isFalse
, then approximately \(|\min_z \text{H.value(z)}|\) ancilla bits will be used.
- add_constraint_lt_zero(H, lam=1, log_trick=True, bounds=None, suppress_warnings=False)
add_constraint_lt_zero.
Enforce that
H < 0
by penalizing invalid solutions withlam
. See Notes below for more details.- Parameters
H (dict representing a PUSO.) – The PUSO constraint such that H < 0. Note that
H
will be converted to aqubovert.PUSO
object if it is not already, thus it must follow the conventions, seehelp(qubovert.PUSO)
. Please note that ifH
contains any symbols, thenbounds
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 PUSOH
can take. Ifbounds
is None, then they will be calculated (approximately), or if either of the elements ofbounds
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 PCSO in place, but returns
self
so that operations can be strung together.- Return type
PCSO.
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 \(z_0 + 2z_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 = PCSO() >>> H.add_constraint_lt_zero( >>> {(0,): 0.5, (): 1.65, (1,): 1.0, (2,): -0.25}) >>> test_sol = {0: -1, 1: -1, 2: 1} >>> H.is_solution_valid(test_sol) True >>> H.value(test_sol) 0.01
{0: -1, 1: -1, 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
isTrue
, then approximately \(\log_2 |\min_z \text{H.value(z)}|\) ancilla bits will be used. Iflog_trick
isFalse
, then approximately \(|\min_z \text{H.value(z)}|\) ancilla bits will be used.
- add_constraint_ne_zero(H, lam=1, log_trick=True, bounds=None, suppress_warnings=False)
add_constraint_ne_zero.
Enforce that
H != 0
by penalizing invalid solutions withlam
. See Notes below for more details.- Parameters
H (dict representing a PUSO.) – The PUSO constraint such that H != 0. Note that
H
will be converted to aqubovert.PUSO
object if it is not already, thus it must follow the conventions, seehelp(qubovert.PUSO)
. Please note that ifH
contains any symbols, thenbounds
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 PUSOH
can take. Ifbounds
is None, then they will be calculated (approximately), or if either of the elements ofbounds
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 PCSO in place, but returns
self
so that operations can be strung together.- Return type
PCSO.
Notes
There is no general way to enforce non integer inequality constraints. Thus this function is only guarenteed to work for integer inequality constraints. 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
isTrue
, then approximately \(\log_2 |\min_x \text{P.value(x)}|\) ancilla bits will be used. Iflog_trick
isFalse
, then approximately \(|\min_x \text{P.value(x)}|\) ancilla bits will be used.
- 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 asqubovert.PUBO
, properties such asmapping
andreverse_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 fromself
and resets the cached values.
- property constraints
constraints.
Return the constraints of the PCSO.
- Returns
res – The keys of
res
are'eq'
,'ne'
,'lt'
,'le'
,'gt'
, and'ge'
. The values are lists ofqubovert.PUSO
objects. For a given key, value pairk, v
, thev[i]
element represents the PUSOv[i]
being == 0 ifk == 'eq'
, != 0 ifk == 'ne'
, < 0 ifk == 'lt'
, <= 0 ifk == 'le'
, > 0 ifk == 'gt'
, >= 0 ifk == 'ge'
.- Return type
dict.
- 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 ifsolution
contains all 1’s. In this case, it is unclear whethersolution
came from a spin or boolean formulation of the problem, and we will figure it out based on thespin
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 theto_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
wherex
andy
are variables of the PUSO, thensolution
must have values forx
,y
, andz
. If the QUSO solver found thatx = 1
,y = -1
, andz = 1
, then the constraint thatz = xy
is not satisfied (one possible cause for this is if thelam
argument into_quso
is too small).convert_solution
will return thatx = 1
andy = -1
and ignore the value ofz
.
- 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.
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 theself.to_pubo
,self.to_qubo
,self.to_puso
, orself.to_quso
formulations, then you should first callself.convert_solution
. Seehelp(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 PCSO in order to enforce the inputted constraints.
- Returns
num – Number of ancillas in the PCSO.
- 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='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 asqubovert.PUBO
, properties such asmapping
andreverse_mapping
). This can cause these values to be wrong for some specific situations. Callingrefresh
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 PCSO 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 theself.to_pubo
,self.to_qubo
,self.to_puso
, orself.to_quso
formulations, then you should first callself.convert_solution
. Seehelp(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, theconvert_solution
method keeps track of the mapping and can/should always be used. But if you want a consistent mapping, thenset_mapping
can be used.Consider the following examples (we use the
qubovert.QUBO
class for the examples, which is a subclass ofBO
).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. Seehelp(self.mapping)
Notes
Using
set_mapping
to set the mapping will also automatically set thereverse_mapping
, so there is no need to call bothset_mapping
andset_reverse_mapping
.
- set_reverse_mapping(*args, **kwargs)
set_reverse_mapping.
Same as
set_mapping
but reversed. Seehelp(self.reverse_mapping)
andhelp(self.set_mapping)
.- Parameters
arguments (defines a dictionary with
d = dict(*args, **kwargs)
.) –d
will become the reverse mapping. Seehelp(self.reverse_mapping)
.
Notes
Using
set_reverse_mapping
to set the mapping will also automatically set themapping
, so there is no need to call bothset_mapping
andset_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_puso_bruteforce(
self, all_solutions, self.is_solution_valid)[1]``.
- Parameters
all_solutions (bool.) – See the description of the
all_solutions
parameter inqubovert.utils.solve_puso_bruteforce
.- Returns
res –
qubovert.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 innodes
, and external nodes are given the values inconnections
.- Parameters
nodes (set.) – Nodes of
self
to include in the subgraph.connections (dict (optional, defaults to {})) – For each node in
self
that is not innodes
, we assign a value given byconnections.get(node, 0)
.
- Returns
D – The subgraph of
self
with nodes innodes
and the values of the nodes not included given byconnections
.- 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 outputD
.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 seehelp(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
a PCSO object.
- subvalue(values)
subvalue.
Replace each element in
self
with a value invalues
if it exists.- Parameters
values (dict.) – For each node
v
inself
that is invalues
, we replace the node withvalues[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 toself.to_qubo()
.If
self
is a QUSO,self.to_enumerated()
is equivalent toself.to_quso()
.If
self
is a PUBO or PCBO,self.to_enumerated()
is equivalent toself.to_pubo()
.If
self
is a PUSO or PCSO,self.to_enumerated()
is equivalent toself.to_puso()
.- Returns
res – If
self
is a QUBO type, then this method returns the corresponding QUBOMatrix type. Ifself
is a QUSO type, then this method returns the corresponding QUSOMatrix type. Ifself
is a PUBO or PCBO type, then this method returns the corresponding PUBOMatrix type. Ifself
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 ofself
, ie seeself.degree
.lam (function (optional, defaults to None)) – Note that if
deg
is None ordeg >= self.degree
, thenlam
is unneccessary and will not be used. Iflam
is None, the functionPUBO.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 bylam(v)
, wherev
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 that3
should be the product of1
and2
will be enforced with a penalty weightlam(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. Ifpairs
is None, then it will be the empty setset()
. 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
ifz == xy
,3*lam(v)
ifx == y == 0 and z == 1
, andlam(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 ofself
, ie seeself.degree
.lam (function (optional, defaults to None)) – Note that if
deg
is None ordeg >= self.degree
, thenlam
is unneccessary and will not be used. Iflam
is None, the functionPUBO.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 bylam(v)
, wherev
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 that3
should be the product of1
and2
will be enforced with a penalty weightlam(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. Ifpairs
is None, then it will be the empty setset()
. 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 andlam
.
- 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 functionPUBO.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 bylam(v)
, wherev
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 that3
should be the product of1
and2
will be enforced with a penalty weightlam(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. Ifpairs
is None, then it will be the empty setset()
. 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 functionPUBO.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 bylam(v)
, wherev
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 that3
should be the product of1
and2
will be enforced with a penalty weightlam(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. Ifpairs
is None, then it will be the empty setset()
. 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 PCSO but following all the conventions of this class.
- Parameters
*args/**kwargs (defines a dictionary or PCSO.) – 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 callingqubovert.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.