mqt.problemsolver.qubo_tools.pathfinder.cost_functions

Includes all cost functions supported by the pathfinding QuboGenerator.

Module Contents

GetVariableFunction
SetCallback
class EncodingType[source]

Bases: enum.Enum

The encoding types supported for the QUBO generation.

ONE_HOT = 1
DOMAIN_WALL = 2
BINARY = 3
class A[source]

Bases: sympy.Function

Custom sympy function for the adjacency matrix.

A(v, w) represents the weight of edge (v, w).

class X[source]

Bases: sympy.Function

Custom sympy function for the encoding variables.

x(p, v, i) represents a single binary variable. Its meaning depends on the encoding type.

class Decompose[source]

Bases: sympy.Function

Custom sympy function for the decomposition of an integer into its binary digits.

Example

Decompose(5, 1) represents digit 1 of the binary string 101, i.e., 1.

doit(**_hints: Any) → sympy.Expr[source]

Evaluate objects that are not evaluated by default like limits, integrals, sums and products. All objects of this kind will be evaluated recursively, unless some species were excluded via ‘hints’ or unless the ‘deep’ hint was set to ‘False’.

>>> from sympy import Integral
>>> from sympy.abc import x

>>> 2*Integral(x, x)
2*Integral(x, x)

>>> (2*Integral(x, x)).doit()
x**2

>>> (2*Integral(x, x)).doit(deep=False)
2*Integral(x, x)
class ExpandingSum[source]

Bases: sympy.Sum

Represents a sum that is always expanded into a sum of its elements when calling doit().

args: tuple[sympy.Expr, tuple[sympy.Symbol, sympy.Expr, sympy.Expr]]

Returns a tuple of arguments of ‘self’.

Examples

>>> from sympy import cot
>>> from sympy.abc import x, y

>>> cot(x).args
(x,)

>>> cot(x).args[0]
x

>>> (x*y).args
(x, y)

>>> (x*y).args[1]
y

Notes

Never use self._args, always use self.args. Only use _args in __new__ when creating a new function. Do not override .args() from Basic (so that it is easy to change the interface in the future if needed).

doit(**_hints: Any) → sympy.Expr[source]

Evaluate objects that are not evaluated by default like limits, integrals, sums and products. All objects of this kind will be evaluated recursively, unless some species were excluded via ‘hints’ or unless the ‘deep’ hint was set to ‘False’.

>>> from sympy import Integral
>>> from sympy.abc import x

>>> 2*Integral(x, x)
2*Integral(x, x)

>>> (2*Integral(x, x)).doit()
x**2

>>> (2*Integral(x, x)).doit(deep=False)
2*Integral(x, x)
class SumSet(expr: sympy.Expr, element_expr: sympy.Expr, latex: _StringForSumSet)[source]

Bases: sympy.Expr

A class that can be used to represent a sum over a set.

This is just a symbolic representation for the display of the equation. In the background, it stores the actual expanded sum that is used for calculations.

expr: sympy.Expr
element_expr: sympy.Expr
latex: _StringForSumSet
doit(**hints: Any) → sympy.Expr[source]

Replaces the sum by the actual expression it represents.

Returns:

The expression that is represented by the sum.

__eq__(other: object) → bool[source]

Overrides the default implementation.

__hash__() → int[source]

Overrides the default implementation.

class FormulaHelpers[source]

Provides static methods for the more efficient construction of sympy formulas.

static sum_from_to(expression: sympy.Expr, var: str, from_number: sympy.Expr | float, to_number: sympy.Expr | float) → sympy.Expr[source]

Generates a sum of the form Sum(expression, (var, from_number, to_number).

Parameters:

  • expression (sp.Expr) – The term inside the sum.

  • var (str) – The iteration variable of the sum as a string.

  • from_number (sp.Expr | float) – The lower bound of the sum.

  • to_number (sp.Expr | float) – The upper bound of the sum.

Returns:

The sympy sum term.

Return type:

sp.Expr

static prod_from_to(expression: sympy.Expr, var: str, from_number: sympy.Expr | float, to_number: sympy.Expr | float) → sympy.Expr[source]

Generates a product of the form Product(expression, (var, from_number, to_number).

Parameters:

  • expression – The term inside the sum.

  • var – The iteration variable of the sum as a string.

  • from_number – The lower bound of the sum.

  • to_number – The upper bound of the sum.

Returns:

The sympy sum term.

static sum_set(expression: sympy.Expr, variables: list[str], latex: str, callback: SetCallback) → sympy.Expr[source]

Generates a sum of the form sum_{[variables] in [callback]} [expression].

Parameters:

  • expression – The term inside the sum.

  • variables – A list of iteration variables of the sum as strings.

  • latex – The LaTex representation of the set expression.

  • callback – A callback returning the set over which the sum should iterate.

Returns:

The sympy sum term.

static adjacency(v: int | str | sympy.Expr, w: int | str | sympy.Expr) → sympy.Expr[source]

Returns an access to the adjacency matrix with indices v and w.

v and w may be of type int, str, or sympy expressions.

Parameters:

  • v (int | str | sp.Expr) – The “from” index of the adjacency matrix.

  • w (int | str | sp.Expr) – The “to” index of the adjacency matrix.

Returns:

A call to the adjacency matrix function.

Return type:

sp.Expr

static variable(name: str) → sympy.Symbol[source]

Returns a variable with the given name.

Parameters:

name (str) – The name of the variable.

Returns:

The generated variable.

Return type:

sp.Symbol

static get_encoding_variable_one_hot(path: str | int | sympy.Expr, vertex: str | int | sympy.Expr, position: str | int | sympy.Expr, _num_vertices: int = 0) → sympy.Expr[source]

Returns an access to the binary variable x_{path, vertex, position} that represents the statement “Vertex vertex is located at position position in path path” for One-Hot encoding.

All indices can be integers, strings, or sympy expressions. The _num_vertices parameter is only included for compatibility.

Parameters:

  • path (Any) – The path index.

  • vertex (Any) – The vertex index.

  • position (Any) – The position index.

  • _num_vertices (int, optional) – The number of vertices in the graph. Defaults to 0.

Returns:

An expression representing the statement “Vertex vertex is located at position position in path path” for One-Hot encoding.

Return type:

sp.Expr

static get_encoding_variable_domain_wall(path: str | int | sympy.Expr, vertex: str | int | sympy.Expr, position: str | int | sympy.Expr, _num_vertices: int = 0) → sympy.Expr[source]

Returns an expression representing the statement “Vertex vertex is located at position position in path path” for Domain-Wall encoding.

All indices can be integers, strings, or sympy expressions. The _num_vertices parameter is only included for compatibility.

Parameters:

  • path (Any) – The path index.

  • vertex (Any) – The vertex index.

  • position (Any) – The position index.

  • _num_vertices (int, optional) – The number of vertices in the graph. Defaults to 0.

Returns:

An expression representing the statement “Vertex vertex is located at position position in path path” for Domain-Wall encoding.

Return type:

sp.Function

static get_encoding_variable_binary(path: str | int | sympy.Expr, vertex: str | int | sympy.Expr, position: str | int | sympy.Expr, num_vertices: int = 0) → sympy.Expr[source]

Returns an expression representing the statement “Vertex vertex is located at position position in path path” for Binary encoding.

All indices can be integers, strings, or sympy expressions. The _num_vertices parameter is only included for compatibility.

Parameters:

  • path (Any) – The path index.

  • vertex (Any) – The vertex index.

  • position (Any) – The position index.

  • num_vertices (int, optional) – The number of vertices in the graph. Defaults to 0.

Returns:

An expression representing the statement “Vertex vertex is located at position position in path path” for Binary encoding.

Return type:

sp.Function

static get_for_each_path(expression: sympy.Expr, paths: list[int]) → sympy.Expr[source]

Returns a sum iterating over the given expression for each path in paths.

Parameters:

  • expression (sp.Expr) – The expression to sum up.

  • paths (list[int]) – The paths over which to sum the expression.

Returns:

A sum of the expression for each path.

Return type:

sp.Expr

static get_for_each_position(expression: sympy.Expr, path_size: int) → sympy.Expr[source]

Returns a sum iterating over the given expression for each possible index in the path.

Parameters:

  • expression (sp.Expr) – The expression to sum up.

  • path_size (int) – The maximum length of a path.

Returns:

A sum of the expression for each position.

Return type:

sp.Expr

static get_for_each_vertex(expression: sympy.Expr, vertices: list[int]) → sympy.Expr[source]

Returns a sum iterating over the given expression for each possible vertex in vertices.

Parameters:

  • expression (sp.Expr) – The expression to sum up.

  • vertices (list[int]) – The list of vertices for which the expression should be summed.

Returns:

A sum of the expression for each vertex.

Return type:

sp.Expr

class CostFunction[source]

Bases: abc.ABC

An abstract base class for cost functions.

Represents a cost function that can be translated into a QUBO expression.

get_formula(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Translates the cost function into a QUBO expression.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

abstractmethod get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_one_hot(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for One-Hot encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_domain_wall(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Domain-Wall encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_binary(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Binary encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class CompositeCostFunction(*parts: tuple[CostFunction, int])[source]

Bases: CostFunction

A composite cost function that is the sum of multiple cost functions.

summands

A list of tuples of cost functions and their weights.

Type:

list[tuple[CostFunction, int]]

summands: list[tuple[CostFunction, int]]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

get_formula(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Translates the cost function into a QUBO expression.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathPositionIs(position: int, vertex_ids: list[int], path: int)[source]

Bases: CostFunction

A cost function that penalises paths that do not contain a given vertex at a given position.

vertex_ids

The list of vertices, one of which must be located at the given position.

Type:

list[int]

path

The path index.

Type:

int

position

The position index.

Type:

int

vertex_ids: list[int]
path: int
position: int
get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathStartsAt(vertex_ids: list[int], path: int)[source]

Bases: PathPositionIs

A cost function that penalises paths that do not start at a given vertex.

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathEndsAt(vertex_ids: list[int], path: int)[source]

Bases: CostFunction

A cost function that penalises paths that do not end at a given vertex.

vertex_ids

The list of vertices, one of which must be located at the end of the path.

Type:

list[int]

path

The path index.

Type:

int

vertex_ids: list[int]
path: int
get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathContainsVertices(min_occurrences: int, max_occurrences: int, vertex_ids: list[int], path_ids: list[int])[source]

Bases: CostFunction

A cost function that penalises paths that do not contain a given set of vertices.

vertex_ids

The list of vertices subject to the constraint.

Type:

list[int]

min_occurrences

The minimum number of occurrences of the vertices in the path.

Type:

int

max_occurrences

The maximum number of occurrences of the vertices in the path.

Type:

int

path_ids

The list of paths to which the cost function applies.

Type:

list[int]

vertex_ids: list[int]
min_occurrences: int
max_occurrences: int
path_ids: list[int]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathContainsVerticesExactlyOnce(vertex_ids: list[int], path_ids: list[int])[source]

Bases: PathContainsVertices

A cost function that penalises paths that do not contain a given set of vertices exactly once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsVerticesAtLeastOnce(vertex_ids: list[int], path_ids: list[int])[source]

Bases: PathContainsVertices

A cost function that penalises paths that do not contain a given set of vertices at least once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsVerticesAtMostOnce(vertex_ids: list[int], path_ids: list[int])[source]

Bases: PathContainsVertices

A cost function that penalises paths that do not contain a given set of vertices at most once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsEdges(min_occurrences: int, max_occurrences: int, edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: CostFunction

A cost function that penalises paths that do not contain a given set of edges.

edges

The list of edges subject to the constraint.

Type:

list[tuple[int, int]]

min_occurrences

The minimum number of occurrences of the edges in the path.

Type:

int

max_occurrences

The maximum number of occurrences of the edges in the path.

Type:

int

path_ids

The list of paths to which the cost function applies.

Type:

list[int]

edges: list[tuple[int, int]]
min_occurrences: int
max_occurrences: int
path_ids: list[int]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathContainsEdgesExactlyOnce(edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: PathContainsEdges

A cost function that penalises paths that do not contain a given set of edges exactly once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsEdgesAtLeastOnce(edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: PathContainsEdges

A cost function that penalises paths that do not contain a given set of edges at least once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsEdgesAtMostOnce(edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: PathContainsEdges

A cost function that penalises paths that do not contain a given set of edges at most once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathBound(path_ids: list[int])[source]

Bases: CostFunction

An abstract cost function for penalties limited to an individual path.

path_ids

The list of paths to which the cost function applies.

Type:

list[int]

path_ids: list[int]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PrecedenceConstraint(pre: int, post: int, path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths that do not satisfy a given precedence constraint.

pre

The vertex that must precede post.

Type:

int

post

The vertex that must follow pre.

Type:

int

pre: int
post: int
get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathComparison(path_one: int, path_two: int)[source]

Bases: CostFunction

An abstract cost function for penalties that compare two paths.

path_one

The first path.

Type:

int

path_two (int): The second path.

path_one: int
path_two: int
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathsShareNoVertices(path_one: int, path_two: int)[source]

Bases: PathComparison

A cost function that penalises paths that share vertices.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathsShareNoEdges(path_one: int, path_two: int)[source]

Bases: PathComparison

A cost function that penalises paths that share edges.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathIsValid(path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths that are not valid for a given encoding.

A path may be invalid if

  • it contains an edge that is not in the graph,

  • it has an assignment incompatible with the encoding:

    • for One-Hot encoding, multiple vertices are assigned to a single position

    • for Domain-Wall encoding, a position bit string is of the form 1…10…1…0

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_one_hot(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for One-Hot encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_domain_wall(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Domain-Wall encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_binary(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Binary encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class MinimizePathLength(path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths based on their length.

A bigger total weight causes a bigger penalty.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class MaximizePathLength(path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths based on their length.

A lower total weight causes a bigger penalty.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

merge(cost_functions: list[CostFunction], optimisation_goals: list[CostFunction]) → CompositeCostFunction[source]

Merges a list of cost functions and a list of optimisation criteria into a single cost function.

Parameters:
Returns:

The resulting cost function.

Return type:

CompositeCostFunction