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.
- 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
- property hamiltonian
Returns the Hamiltonian of the problem.
- property n
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:
A list of the cities’ coordinates and, optionally, a (directed) graph specifiying the connectivity between cities
A distance matrix encoding distances between each pair of cities and, optionally, a (directed) graph specifiying the connectivity between cities
A weighted (directed) graph specifiying the connectivity and the distance between cities
Initializes a TSP object via three different methods:
Give a list of coordinates for the cities and optionally the connectivity between them via a (directed) graph.
Give a distance matrix and optionally the connectivity between cities via a (directed) graph.
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.
- static validate_coordinates(city_coordinates)[source]
Makes the necessary check given some city coordinates.
- 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.
- 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:
- 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.
- 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:
- 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:
- 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.
- class openqaoa.problems.shortestpath.ShortestPath(G, source, dest)[source]
Bases:
Problem
Creates an instance of the Shortest Path problem.
- Parameters:
- 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.
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.
- 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:
- 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