Problems

class openqaoa.problems.problem.Problem[source]
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

abstract static random_instance(**kwargs)[source]

Creates a random instance of the problem.

Parameters:

**kwargs – Required keyword arguments

Returns:

A random instance of the problem.

class openqaoa.problems.qubo.QUBO(n, terms, weights, problem_instance={'problem_type': 'generic_qubo'}, clean_terms_and_weights=False)[source]

Creates an instance of Quadratic Unconstrained Binary Optimization (QUBO) class, which offers a way to encode optimization problems.

Parameters:
  • n (int) – The number of variables in the representation.

  • terms (List[Tuple[int, ...],List]) – The different terms in the QUBO encoding, indicating the different interactions between variables.

  • weights (List[float]) – The list of weights (or coefficients) corresponding to each interaction defined in terms.

  • clean_terms_and_weights (bool) – Boolean indicating whether terms and weights can be cleaned

Return type:

An instance of the Quadratic Unconstrained Binary Optimization (QUBO) class.

TERMS_CLEANING_LIMIT = 5000
asdict(exclude_keys=[])[source]

Returns a dictionary containing the serialization of the class.

Parameters:

exclude_keys (List[str]) –

Returns:

A dictionary containing the serialization of the class.

static clean_terms_and_weights(terms, weights)[source]

Goes through the terms and weights and group them when possible

static convert_qubo_to_ising(n, qubo_terms, qubo_weights)[source]

Convert QUBO terms and weights to their Ising equivalent

static from_dict(dict, clean_terms_and_weights=False)[source]
Parameters:
  • dict (dict) – The dictionary containing the serialization of the QUBO object.

  • clean_terms_and_weights (bool) –

Returns:

A QUBO object.

property hamiltonian

Returns the Hamiltonian of the problem.

property n
static random_instance(n, density=0.5, format_m='coo', max_abs_value=100, **kwargs)[source]
set_metadata(metadata={})[source]
Parameters:

metadata (dict) – The metadata of the problem. All keys and values will be stored in the metadata dictionary.

Built-in problems

class openqaoa.problems.tsp.TSP(city_coordinates=None, distance_matrix=None, G=None, A=None, B=1)[source]

Bases: Problem

The Traveling Salesman Problem (TSP) requires to find, given a list of cities and the distances between each pair of cities (or the cities coordinates), the shortest possible path that visits each city exactly once and returns to the origin city. Additionally, one can also specify how cities are connected together. Our implementation accepts three different kind of inputs:

  1. A list of the cities’ coordinates and, optionally, a (directed) graph specifiying the connectivity between cities

  2. A distance matrix encoding distances between each pair of cities and, optionally, a (directed) graph specifiying the connectivity between cities

  3. A weighted (directed) graph specifiying the connectivity and the distance between cities

Initializes a TSP object via three different methods:

  1. Give a list of coordinates for the cities and optionally the connectivity between them via a (directed) graph.

  2. Give a distance matrix and optionally the connectivity between cities via a (directed) graph.

  3. Directly give a (directed) weighted graph, where edge weights are interpreted as distances between cities

Whenever no graph connectivity is specified, it is assumed that all cities are connected.

Parameters:
  • city_coordinates (Optional[List[Tuple[float, float]]]) – List containing the coordinates of each city.

  • distance_matrix (Optional[List[List[float]]]) – Distance between cities given as list of list representing a matrix

  • G (Optional[nx.Graph]) – Graph encoding the connectivity between cities (can be directed)

  • A (Optional[float]) – Quadratic penalty coefficient to enforce that a path is a Hamiltonian cycle.

  • B (Optional[float]) – Penalty coefficient which accounts for the path cost.

Return type:

None

property graph
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Traveling Salesman problem with fully connected cities.

Parameters:

n_cities (int) – The number of cities in the TSP instance. This is a required keyword argument.

Returns:

A random instance of the Traveling Salesman problem.

terms_and_weights()[source]

Returns the terms and weights used in the QUBO formulation of this TSP instance. The QUBO formulation used is the one presented in Section 7.2 in https://arxiv.org/pdf/1302.5843.pdf, and sets the first city to be visited to be the first city in order to reduce the number of variables.

Returns:

Tuple containing a list with the terms and a list with the corresponding weights.

Return type:

Tuple[List[List[int]], List[float]]

static validate_coordinates(city_coordinates)[source]

Makes the necessary check given some city coordinates.

Parameters:

input_coordinates (List[Tuple[float, float]]) – List containing the coordinates of each city.

Returns:

None

static validate_distance_matrix(distance_matrix)[source]

Makes the necessary check given some distance matrix.

Parameters:

distance_matrix (List[List[float]]) – Distance between cities given as list of list representing a matrix

Returns:

None

static validate_graph(G)[source]

Makes the necessary check given some (weighted) graph.

Parameters:

G (nx.Graph) – Graph encoding the connectivity between cities (can be directed)

Returns:

None

class openqaoa.problems.numberpartition.NumberPartition(numbers=None)[source]

Bases: Problem

Creates an instance of the Number Partitioning problem.

Parameters:

numbers (List[int]) – The list of numbers to be partitioned.

Return type:

An instance of the Number Partitioning problem.

property numbers
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Number Partitioning problem.

Parameters:

n_numbers (int) – The number of numbers to be partitioned. This is a required keyword argument.

Returns:

A random instance of the Number Partitioning problem.

class openqaoa.problems.maximumcut.MaximumCut(G)[source]

Bases: Problem

Creates an instance of the Maximum Cut problem.

Parameters:

G (nx.Graph) – The input graph as NetworkX graph instance.

Return type:

An instance of the Maximum Cut problem.

DEFAULT_EDGE_WEIGHT = 1.0
property G
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Maximum Cut problem, whose graph is random following the Erdos-Renyi model.

Parameters:

**kwargs

Required keyword arguments are:

n_nodes: int

The number of nodes (vertices) in the graph.

edge_probability: float

The probability with which an edge is added to the graph.

Returns:

A random instance of the Maximum Cut problem.

class openqaoa.problems.knapsack.Knapsack(values, weights, weight_capacity, penalty)[source]

Bases: Problem

Creates an instance of the Kanpsack problem.

Parameters:
  • values (List[int]) – The values of the items that can be placed in the kanpsack.

  • weights (List[int]) – The weight of the items that can be placed in the knapsack.

  • weight_capacity (int) – The maximum weight the knapsack can hold.

  • penalty (float) – Penalty for the weight constraint.

Return type:

An instance of the Knapsack problem.

property penalty
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Knapsack problem.

Parameters:

n_items (int) – The number of items that can be placed in the knapsack.

Returns:

A random instance of the Knapsack problem.

terms_and_weights()[source]
property values
property weight_capacity
property weights
class openqaoa.problems.knapsack.SlackFreeKnapsack(values, weights, weight_capacity, penalty)[source]

Bases: Knapsack

A slack variable free approach to the Knapsack problem Hamiltonian. The Hamiltonian consists of decision qubits with a quadratic penalty term centred on W, i.e. the maximum Knapsack Capacity. Creates an instance of the SlackFreeKanpsack problem.

Parameters:
  • values (List[int]) – The values of the items that can be placed in the kanpsack.

  • weights (List[int]) – The weight of the items that can be placed in the knapsack.

  • weight_capacity (int) – The maximum weight the knapsack can hold.

  • penalty (float) – Penalty for the weight constraint.

Return type:

An instance of the SlackFreeKnapsack problem.

property penalty
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Knapsack problem.

Parameters:

n_items (int) – The number of items that can be placed in the knapsack.

Returns:

A random instance of the Knapsack problem.

terms_and_weights()[source]

Implementation of single and two-qubit terms in the slack-free Hamiltonian for the Knapsack problem.

property values
property weight_capacity
property weights
class openqaoa.problems.minimumvertexcover.MinimumVertexCover(G, field, penalty)[source]

Bases: Problem

Creates an instance of the Minimum Vertex Cover problem.

Parameters:
  • G (nx.Graph) – The input graph as NetworkX graph instance.

  • field (float) – The strength of the artificial field minimizing the size of the cover.

  • penalty (float) – The strength of the penalty enforcing the cover constraint.

Return type:

An instance of the Minimum Vertex Cover problem.

property G
property field
property penalty
property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Minimum Vertex Cover problem, whose graph is random following the Erdos-Renyi model. By default the artificial field is set to 1.0 and the default penalty os taken to be 10 times larger.

Parameters:

**kwargs

Required keyword arguments are:

n_nodes: int

The number of nodes (vertices) in the graph.

edge_probability: float

The probability with which an edge is added to the graph.

Return type:

A random instance of the Minimum Vertex Cover problem.

terms_and_weights()[source]

Creates the terms and weights for the Minimum Vertex Cover problem

Returns:

terms_weights – Tuple containing list of terms and list of weights.

Return type:

tuple(list[list],list[float])

class openqaoa.problems.shortestpath.ShortestPath(G, source, dest)[source]

Bases: Problem

Creates an instance of the Shortest Path problem.

Parameters:
  • G (nx.Graph) – The input graph as NetworkX graph instance.

  • source (int) – The index of the source node.

  • dest (int) – The index of the destination node.

Return type:

An instance of the Shortest Path problem.

property problem_instance

Returns a dictionary containing the serialization of the class and the problem type name, which will be passed as metadata to the QUBO class.

Returns:

  • A dictionary containing the serialization of the class

  • and the problem type name.

property qubo

Returns the QUBO encoding of this problem.

Return type:

The QUBO encoding of this problem.

static random_instance(**kwargs)[source]

Creates a random instance of the Shortest problem, whose graph is random following the Erdos-Renyi model. By default the node and edge weights are set to 1.0 and the default constraint is taken to be as large.

Parameters:

**kwargs

Required keyword arguments are:

n_nodes: int

The number of nodes (vertices) in the graph.

edge_probability: float

The probability with which an edge is added to the graph.

Return type:

A random instance of the Shortest Path problem.

terms_and_weights()[source]

Creates the terms and weights for the Shortest Path problem

Returns:

terms_weights – Tuple containing list of terms and list of weights

Return type:

tuple(list[list],list[float])

Utils and Converters

openqaoa.problems.helper_functions.create_problem_from_dict(problem_instance)[source]

Creates an object of the class corresponding to the problem type in the input instance, with the same attributes as the input instance.

Parameters:

problem_instance (dict) – The input instance.

Return type:

Problem

Returns:

An object of the class corresponding to the problem type in the input instance.

class openqaoa.problems.converters.FromDocplex2IsingModel(model, multipliers=None, unbalanced_const=False, strength_ineq=[0.1, 0.5])[source]

Bases: object

static bounds(linear_expression)[source]

Generates the limits of a linear term

Parameters:

linear_exp (generator) – Iterable term with the quadratic terms of the cost function.

Returns:

  • l_bound (float) – Lower bound of the quadratic term.

  • u_bound (float) – Upper bound of the quadratic term

static equality_to_penalty(expression, multiplier)[source]

Add equality constraints to the cost function using the penality representation. The constraints should be linear.

Parameters:
  • expression (docplex.mp.linear.LinearExpr) – docplex equality constraint “expression == 0”.

  • multiplier (float) – Lagrange multiplier of the penalty

Returns:

penalty – Penalty that will be added to the cost function.

Return type:

docplex.mp.quad.QuadExpr

get_models(multipliers=None)[source]

Creates a QUBO docplex model, QUBO dict OQ model, and an Ising Model form a Docplex quadratic program.

Parameters:

model (Docplex model) – It is an object that has the mathematical expressions (Cost function, Inequality and Equality constraints) of an optimization problem.

Return type:

qubo_docplex, ising_model

inequality_to_equality(constraint)[source]

Transform inequality contraints into equality constriants using slack variables.

Parameters:

constraint (docplex.mp.constr.LinearConstraint) – DESCRIPTION.

Returns:

new_exp – The equality constraint representation of the inequality constraint.

Return type:

docplex.mp.linear.LinearExpr

inequality_to_unbalanced_penalty(constraint)[source]

Inequality constraint based on an unbalanced penality function described in detail in the paper: https://arxiv.org/abs/2211.13914

Parameters:

constraint (DOcplex inequality constraint) – Inequality constraints in a DOcplex format.

Returns:

penalty – Quadratic programing penalization term.

Return type:

DOcplex term

linear_constraints(multipliers=None)[source]

Adds the constraints of the problem to the objective function.

Parameters:

multiplier (List) – For each constraint a multiplier, if None it automatically is selected.

Return type:

None.

linear_expr(expr)[source]

Adds linear expresions to the objective function stored in self.qubo_dict.

Parameters:

expr (model.objective_expr) – A docplex model attribute.

multipliers_generators()[source]

Penality term size adapter, this is the Lagrange multiplier of the cost function penalties for every constraint if the multiplier is not indicated by the user.

Returns:

the multiplier resized by the cost function limits.

Return type:

float

static quadratic_bounds(iter_exp)[source]

Generates the limits of the quadratic terms

Parameters:

iter_exp (generator) – Iterable term with the quadratic terms of the cost function.

Returns:

  • l_bound (float) – Lower bound of the quadratic term.

  • u_bound (float) – Upper bound of the quadratic term

quadratic_expr(expr)[source]

Adds quadratic terms to the objective function stored in self.qubo_dict.

Parameters:

expr (model.objective_expr) – A docplex model attribute.

static qubo_to_ising(n_variables, qubo_terms, qubo_weights)[source]

Converts the terms and weights in QUBO representation ([0,1]) to the Ising representation ([-1, 1]).

Parameters:
  • n_variables (int) – number of variables.

  • qubo_terms (List) – List of QUBO variables.

  • qubo_weights (List) – coefficients of the variables

Return type:

Ising Model stored on QUBO class