Use Case Collection
Arbitrage Edge Based problem
Description
In economics and finance, arbitrage is the practice of taking advantage of a difference in prices in two or more markets; striking a combination of matching deals to capitalize on the difference. The edge based Arbitrage problem tries to find the best cycle in a directed and complete graph. In this graph, each node corresponds to an asset and each directed edge is weighted with the corresponding conversion rate. It creates a QUBO with the size nedges x nedges, which produces a solution vector where each binary position maps to an edge.
Links
Attributes
graph: Dict[str, Dict[str, Dict[str, float]]]
The input graph as described above in the form of nested dictionaries.
Example for three different currencies:
{
0: `{1: {'weight': 1.31904}`, 2: `{'weight': 6.72585}`},
1: `{0: {'weight': 0.75799}`, 2: `{'weight': 5.10327}`,
2: `{0: {'weight': 0.14864}`, 1: `{'weight': 0.19586}`}
}
penalty: Optional[float] = None
The penalty term for the QUBO matrix. Has to be greater than 0.
Arbitrage Node Based problem
Description
In economics and finance, arbitrage is the practice of taking advantage of a difference in prices in two or more markets; striking a combination of matching deals to capitalize on the difference. The node based Arbitrage problem tries to find the best cycle in a directed and complete graph. In this graph, each node corresponds to an asset and each directed edge is weighted with the corresponding conversion rate. The problem creates a QUBO with the size (nnodes * cyclelength) x (nnodes * cyclelength), which produces a solution vector where each binary position maps to to a node and its position in the cycle.
Links
Attributes
graph: Dict[str, Dict[str, Dict[str, float]]]
The input graph as described above in the form of nested dictionaries.
Example for three different currencies:
{
0: `{1: {'weight': 1.31904}`, 2: `{'weight': 6.72585}`},
1: `{0: {'weight': 0.75799}`, 2: `{'weight': 5.10327}`,
2: `{0: {'weight': 0.14864}`, 1: `{'weight': 0.19586}`}
}
penalty: Optional[float] = None
The penalty term for the QUBO matrix. Has to be greater than 0.
K: Optional[int] = None
The maximum length of the arbitrage cycle.
Binary Integer Linear Programming problem
Description
For a binary decision vector x and some vector c of length N, the Binary Integer Linear Programming problem maximizes c * x, given the constraint Sx = b with S being an m x N matrix and b a vector with m components.
Q-Bit Interpretation
The vector of qubits is simply the decision vector x.
Links
Attributes
S: List[List[int]]
The m x N matrix.
b: List[int]
Vector with m components.
c: List[int]
Custom vector of length N.
A: int
A constant enforcing, if possible, that Sx = b.
B: int
A constant (B << A) helping maximize c * x.
Binary Paint Shop Problem
Description
The Binary Paint Shop Problem tries to minimize the color change of a paint job with two colors of a sequence of cars. The sequence consists of a fixed number of cars, in which each car type occurs exactly twice and these are to be colored in different colors. Therefore, the car sequence consists of exactly twice as many cars as there are car types.
Links
Attributes
ncars: int
Amount of different car types.
sequence: List[int]
Sequence of the cars.
Feature Selection for Credit Scoring problem
Description
Find the optimal feature subset with regard to independence and influence of features for credit scoring of credit applicants.
Links
Attributes
U: List[List[float]]
The matrix U is the design matrix, where each column represents a feature
and each row represents the specific values for a feature set.
V: List[int]
The binary label vector for the respective row in matrix U.
alpha: float
The balance between feature influence and feature independence in the range
[0, 1].
Dynamic Portfolio Optimization problem
Description
The Dynamic Portfolio Optimization problem tries to find the optimal portfolio for a given set of assets and a fixed investment amount. It aims to find the portfolio with optimal returns for a given risk tolerance. It considers transaction costs when rebalancing across multiple time steps. The optimal portfolio is defined by the binary choices whether to invest in a specific asset and how much to invest in it. The investment amount is split into several so called packages defined as 2^(package number). The total number of packages determines the granularity of the result. It defines the amount of possible investment sums in one asset as well as the maximum possible investment in any one asset, which is 2^(Number of packages) - 1.
Links
Attributes
tickers: List
Tickers of assets being tested.
mu: List[List[float]]
Expected Returns of the assets.
Shape: [timesteps][numberofassets]
sigma: List[List[List[float]]]
Coviariance Matrix of the assets.
Shape: [timesteps][numberofassets][numberofassets]
packages: int
Number of packages per asset, determines granularity of investment.
Package value = 2^(package number)
K: int
Total investment amount, which is fixed.
gamma: float
Risk Aversion Coefficient.
Range: Risk Seeking 0-100 Very Risk Averse.
Divided by factor 2 as a convention, as stated in paper.
nu: float
Transaction Cost percentage, e.g., 0.01 = 1% of transaction size.
rho: float
Total investment size constraint factor, Lagrange Multiplier.
Exact Cover problem
Description
Given a set S and a list of subsets of S, an exact cover is a family C of these subsets so that all elements of S are contained in exactly one subset of C. For a set S and a list of subsets of S, the Exact Cover problem tries to find the smallest exact cover, i.e. the one that uses the least subsets.
Q-Bit Interpretation
Subset i is part of the exact cover iff. qubit i is 1.
Links
Attributes
subsetmatrix: List[List[float]]
A matrix containing all subsets.
e.g. for the set `{1, 2, 3}` and the subsets `{1, 2}`, `{2, 3}`, and `{3}`:
[[1, 1, 0], [0, 1, 1], [0, 0, 1]]
or:
ExactCover.gensubsetsmatrix([1, 2, 3], [[1, 2], [2, 3], [3]])
A: int
A constant enforcing the exact cover of the solution.
B: int
A constant (A > nB) helping find the smallest exact cover.
Flight Gate Assignment problem
Description
Flight Gate Assignment is a highly relevant optimization problem in airport management. It tries to minimize the total transit time of passengers, considering three typical parts of passenger flow in an airport:
-
After a flight, passengers claim their baggage and leave the airport.
-
Other passengers switch from one plane to another to get a connecting flight.
-
A third group of passengers pass the security check and leave with a flight.
Links
Description and Transformation
Attributes
nflights: int
Number of flights.
ngates: int
Number of gates.
npassengers: List[Tuple[int, int]]
Number of passengers arriving and departing with each flight.
Example: npassengers[3][departureindex], gives us the number of
passengers departing with flight 3.
timegates: List[Tuple[float, float]]
The time it takes between every gate and check-in (when leaving) or the gate
and baggage claim (when arriving).
Example: timegates[0][arrivingindex], gives us the time it takes to go
from gate 0 to baggage claim.
timeflights: List[Tuple[float, float]]
The time at which a flight arrives/leaves.
Example: timeflights[2][departureindex], gives us the time at which
flight 2 departs.
transferpassengers: List[List[int]]
Matrix with the information of the passengers transferring from one flight to
another.
Example: transferpassengers[2][5], gives the number of passengers
transferring from flight 2 to flight 5.
timebetweengates: List[List[float]]
Gives the time it takes to go from one gate to another.
tbuf: float
Time needed for a gate to be free after a flight has departed.
arrivalindex, departureindex: int
Index to subscribe the variables timegates, npassengers,
timegates, timeflights.
One of these variables needs to be 0, the other 1.
Graph Coloring problem
Description
The Graph Coloring problem tries to color the nodes of a graph with a given number of different colors so that no adjacent nodes have the same color.
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the graph coloring problem in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
ncolors: int
Number of different colors.
Graph Isomorphism problem
Description
The Graph Isomorphism problem tries to find out whether two graphs G1 and G2are isomorphic, i.e. there exists a bijective, edge-invariant vertex mapping from G1 to G2.
Links
Attributes
graph1: Dict[int, Dict[int, Dict[str, float]]]
The first graph (in form of nested dictionaries) to check for isomorphism.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
graph2: Dict[int, Dict[int, Dict[str, float]]]
The second graph (in form of nested dictionaries) to check for isomorphism.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
a: float
A penalty value enforcing the bijectivity of the isomorphism.
b: float
A penalty value (b > a) enforcing the edge-invariance of the isomorphism.
Graph Partitioning problem
Description
The Graph Partitioning problem tries to find two equal sized partitions for a given undirected graph with an even number of vertices, so that the number of edges connecting the two subsets is minimized.
Links
Attributes
#graph : Dict[int, Dict[int, Dict[str, float]]]
The graph, for which the partitions are to be foundin form of nested
dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
A : Optional[int]
Penalty parameter A panalizes violation of the constraint that makes sure
both partitions are of equal size. It can be left "None" to be estimated from
the problem graph via the papers suggestion.
B : Optional[int]
Optimization penalty parameter B penalizes each edge connecting two nodes of
different partitions. If not given it defaults to 1.
Hamiltonian Cycle problem
Description
The Hamiltonian Cycle problem, either for a directed or undirected graph, asks the following: starting at an arbitrary node in the graph, can one travel along the edges of the graph so that each graph will be visited exactly once and there is an edge between the starting node and the last node?
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the hamiltonian cycle problem in form of nested
dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
A: Optional[float]
Positive penalty value which enforces that each node is visited exactly once.
Default: 1.0
Induced Subgraph Isomorphism Problem
Description
Given two graphs the induced subgraph isomorphism problem is to decide if there exists an edge invariant injective mapping from the vertices of the first graph to the second graph. The task is slightly different from the subgraph isomorphism problem, because here additional edges present between two vertices in the second graph to which the isomorphism maps, are prohibited.
This Implementation is heavily based on the subgraph isomorphism problem implementation. It uses slack variables to counterbalance unnecessary penalties.
Links
Attributes
graph1: Dict[int, Dict[int, Dict[str, float]]]
The first graph in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
graph2: Dict[int, Dict[int, Dict[str, float]]]
The second graph, on which the first one is to be mapped, also in form of
nested dictionaries.
Job Shop Scheduling problem
Description
Consider a number of jobs, each of which consists of a number of operations which have to be processed in a specific order. Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. Also, each machine can only execute one job at a time. The objective of the Job Shop Scheduling problem is to schedule all operations in a valid sequence while minimizing the makespan of the jobs, i.e. the completion time of the last running job.
Links
Attributes
jobs: Dict[int, List[Tuple[int, int]]]
A dictionary containing all jobs. Each job is a list of operations and each
operation is tuple containing the machine and the processing time.
T: int
Strict upper bound when all jobs should be finished.
K-Medoids Clustering problem
Description
The authors are concerned with k-medoids clustering and propose a quadratic unconstrained binary optimization (QUBO) formulation of the problem of identifying k medoids among n data points without having to cluster the data. Given our QUBO formulation of this NP-hard problem, it should be possible to solve it on adiabatic quantum computers.
Q-Bit Interpretation
"The qubit vector at index k is 1 iff. data point k from the distance matrix is chosen as medoid of a cluster. The step of assigning the remaining data points to clusters is not covered in this problem but can be easily done in linear time with respect to the number of data points."
Links
Attributes
D : List[List[float]]
The (*n x n*) similarity matrix (diagonal elements are *1* (*one*)).
k : int
The number of medoids.
gamma : float
Penalty coefficient to enforce feasibility.
Knapsack with Integer Weights problem
Description
Given a knapsack that can only carry a weight W and a set of objects, each object having a weight w and a value c, the Knapsack with Integer Weights problem tries to find objects so that the sum of their values is maximized while, at the same time, the sum of their weights does not exceed the capacity of the knapsack.
Links
Description and Transformation
Attributes
w: List[int]
The weight of each object.
c: List[float]
The value of each object.
W: int
The weight that the knapsack can carry.
B: float
A positive constant to reward putting an object into the knapsack.
Default: 1
A: Optional[float]
A positive penalty value, enforcing that the maximal weight will not be
exceeded. If specified, the equation A > B max(c) must hold. If not
specified, will be computed automatically as A = 1 + B max(c).
linearencoding: bool
If false, the number of qubits will be highly reduced, using the log trick
from section 2.4 of the paper linked above.
Linear Regression problem
Description
In statistics, linear regression is a linear approach to modelling the relationship between a real-valued dependent variable and one or more real-valued independent variables.
Q-Bit Interpretation
For interpretation, the qubit vector has to be cut into (nfeatures + 1) sublists of length K (specified below). The sum of each of the product of each of these sublists and the precision vector gives an estimated feature weight.
Links
Attributes
X: List[List[float]]
Training data set in form of a nested list.
All inner lists have to be of the same length.
(e.g. 3 data points with 2 features:
[[1.1, 4.23], [0.1, -2.4], [-2.3, 1.11]] )
Y: List[int]
Regression labels of the training data set.
(e.g. for 3 data points:
[1.2, -3.4, 2.41] )
K: int
Length of the precision vector.
As the problem outputs are supposed to be real values but the qubo only gives
a binary vector, we need a precision vector, consisting of powers of 2, to
simulate real values. This parameter determines the length of this vector.
(e.g. for K = 6, the precision vector is [-2, -1, -0.5, 0.5, 1, 2])
This parameter also determines the size of the qubo matrix together with the
number of features d:
size = (d + 1) * K
Labeled Maximum Weighted Common Subgraph problem
Description
The Labeled Maximum Weighted Common Subgraph (LMWCS) problem finds, given two graphs G1 and G2, the largest subgraph of G1 that is isomorphic to a subgraph of G2. A weight is associated with each possible mapping between a node in G1 and a node in G2 to model a difference in importance for different mappings between nodes in the first graph and the second graph. The vertex pairs with assigned value 1 form the common subgraph. Besides the constraint on the mappings which follow from requiring bijectivity, one can also define user-defined constraints.
Notes: There is an error in definition of C (bijectivity constraint): condition one should be: ((i == m) or (j == n)) and not ((i == j) and (j == n)).
We need to map the binary vector elements b{i, j}, where i and j describe a
node in the graphs 1 and 2 respectively, to an entry in a
(graph1.order() * graph2.order()) dimensional vector. Here, we say that the
element b{i, j} is mapped to the (i * graph2.order() + j)th entry of the
vector.
Generally, we have to fulfill a{(i, j), (m, n)} > min(w{i, j}, w{m, n}) with
w being the weights for the pairs (i, j). Here, we choose a > max(weights) as
if a fulfills this condition for all a{(i, j), (m, n)}.
Q-Bit Interpretation
The tuple (i, j) is part of the mapping iff. qubit i * graph2.order() + j is 1.
Links
Attributes
graph1: Dict[int, Dict[int, Dict[str, float]]]
First problem graph for the lmwcs problem in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
graph2: Dict[int, Dict[int, Dict[str, float]]]
Second problem graph for the lmwcs problem in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
weigths: List[float]
Weights for all pairs (i, j) in graph1.nodes x graph2.nodes.
a: float
Penalty for mapping violating bijectivity or user constraints.
userconstraints: List[Tuple[Tuple[int, int], Tuple[int, int]]]
User given constraints on the vertex mapping.
((i, j), (m, n)) being part of the user constraints means that (i, j) and
(m, n) must not be part of the mapping at the same time.
Longest Path problem
Description
The longest path problem is the problem of finding a simple path of maximum length from a given start node to a given terminal node in a given graph. A path is called simple if it does not have any repeated vertices.
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the longest path problem in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
startnode:
At which node to start.
terminalnode:
At which node to stop.
steps:
How many nodes to include in the path.
Market Graph Clustering problem
Description
The authors formulate the index-tracking problem as a QUBO graph-clustering problem. Their formulation restricts the number of assets while identifying the most representative exemplars of an index. Their thesis is that a portfolio consisting of the most representative set of exemplars will minimize tracking-error. Initial results are very encouraging. Their tests show they accurately replicate the returns of broad market indices, using only a small subset of their constituent assets. Moreover, their QUBO formulation allows us to take advantage of recent hardware advances to overcome the NP-hard nature of the clustering problem. Using these novel architectures they obtain better solutions within small fractions of the time required to solve equivalent problems formulated in traditional constrained form and solved on traditional hardware. Their initial results certainly offer hope and set the stage for larger-scale problems, in finance and beyond.
Their implementation is based on the work of Bauckhage et al..
Q-Bit Interpretation
"The qubit vector at index k is 1 iff. stock k from matrix G (see below) is chosen as medoid of a cluster. The step of assigning the remaining stocks to clusters is not covered in this problem but can be easily done in linear time with respect to the number of data points."
Links
Transformation (Market Graph Clustering via QUBO and Digital Annealing), Bauckhage et al. (A QUBO Formulation of the k-Medoids Problem)
Attributes
G: List[List[float]]
An *n x m* matrix, where *n* is the number of stocks and *m* is the number of
time units with returns for the respective stock at this time.
k: int
The number of representatives desired.
gamma: float
Penalty coefficient to enforce feasibility of the solution.
Maximum 2-SAT problem
Description
For a formula in conjunctive normal form (CNF) with two literals per clause, the Maximum 2-SAT problem determines the maximum number of clauses that can be simultaneously satisfied by an assignment.
Q-Bit Interpretation
Each qubit corresponds to the truth value of one of the variables, to be precise: sorted(variables)[i] == True iff. qubits[i] == 1.
Links
Attributes
clauses: List[Tuple[Tuple[int, bool], Tuple[int, bool]]]
A list containing all clauses of the formula in CNF in form of tuples.
(e.g. the formula x0 * x1 + -x1 * x2:
[((0, True), (1, True)), ((1, False), (2, True))] )
It is possible to use arbitrary variable indices.
nvars: Optional[int]
The number of different variables. Can be used to check whether the input
clauses have the desired number of different variables.
Maximum 3-SAT problem
Description
For a formula in conjunctive normal form (CNF) with three literals per clause, the Maximum 3-SAT problem determines the maximum number of clauses that can be simultaneously satisfied by an assignment.
Q-Bit Interpretation
Let n be the number of different variables and let m be the number of clauses. Then, each of the first n qubits corresponds to the truth value of one of the variables, to be precise: sorted(variables)[i] == True iff. qubits[i] == 1. Each of the last m qubits tells whether the corresponding clause is fulfilled, formally: clauses[i] is fulfilled iff. qubits[n + i] == 1.
Links
Attributes
clauses: List[Tuple[Tuple[int, bool], Tuple[int, bool], Tuple[int, bool]]]
A list containing all clauses of the formula in CNF in form of tuples.
(e.g. the formula x0 * x1 * -x2 + -x1 * x2 * x3:
[((0, True), (1, True), (2, False)), ((1, False), (2, True), (3, True))] )
It is possible to use arbitrary variable indices.
nvars: Optional[int]
The number of different variables. Can be used to check whether the input
clauses have the desired number of different variables.
Maximum Clique problem
Description
The Maximum Clique problem describes the task of finding the largest sized clique in a given graph. A clique is a set of nodes in a graph, where every node has an edge to every other node in the clique. A k-clique denotes a clique with exactly k nodes. The maximum clique of a graph is the clique with the highest possible k value.
There is a closely related problem, the decisional clique problem, which describes the challenge of determining whether a clique of at least size k exists in the given graph.
Math
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the maximum clique problem in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
hardconstraints: Dict
Hard constraints that must be fulfilled by any valid instance. They are
defined in aqcore.transformator.specifications.graphspecifications.
softconstraints: Optional[Dict]
Desirable traits that instances should fulfill.
checksoftconstraints: bool
Defines whether soft constraints should also be fulfilled. Default is
False.
Maximum Cut problem
Description
The Maximum Cut problem tries to find a cut that maximizes the number of intersecting edges in an undirected graph.
Q-Bit Interpretation
A cut defines two sets of nodes, 0 and 1. The qubits x = (x0, x1, ..., xn) can be interpreted like this: xi = 0 iff. node i belongs to set 0 and xi = 1 iff. it belongs to set 1.
Math
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the maximum cut problem in form of nested dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
Maximum Independent Set problem
Description
An independent set of a graph G is a set of vertices of G, where every two vertices are not connected by an edge in G. The Maximum Independent Set problem tries to find the largest independent set of a graph.
Links
Description and Transformation
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the maximum independent set problem in form of nested
dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
Minimal Maximal Matching problem
Description
For a graph G = (V, E), the Minimal Maximal Matching problem tries to find a "coloring" C ⊆ E with the following three constraints:
-
For each edge in C, the incident vertices shall be colored and the union of all these vertices shall be called D.
-
No two edges in C share a vertex.
-
If u, v ∈ D, then (uv) ∉ E.
Links
Description and Transformation
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the minimal maximal matching problem in form of nested
dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
A: int
A positive constant enforcing that no vertex has two colored edges.
B: int
A constant to penalize when an edge is uncolored although it would not
violate the coloring condition. For d being the maximal degree in the graph,
choose A > (d - 2)B.
C: int
A constant (C < B) to minimize the number of colored edges.
Minimal Spanning Tree problem with maximal degree constraint
Description
The Minimal Spanning Tree problem tries to find a spanning tree over all nodes in a given input graph such that the cost of the covered edges (the sum of the weights inside the tree) is minimal. The addition maximal degree constraint, i.e. limiting the degree of the tree at each node to a maximum value, makes this problem NP-hard.
Convention on depth index of vertex and edge: Zero index is vertex root and all the edges leaving from root, etc. That means there are N/2 possible depths for edges and N/2 + 1 possible depths for vertices.
Q-Bit Interpretation
Assume we have a graph with m nodes, n edges, a max degree of k, and the qubit vector q. Then, for i = 0, ..., n-1, q[i] = 1 iff. edge i is included in the tree. Variables n, ..., n + ⌈ m / 2 ⌉ keep track of the depth of a node in the tree. Now, let a := n + ⌈ m / 2 ⌉. Variables a, ..., a + 2 * n tell for each edge in the graph which vertex is closer to the root of the tree. Finally, with b := a * 2 * n, the variables b, ..., b + m * ⌊ log2(maxDegree) + 1 ⌋ count the degree of a node in the tree.
Links
Wikipedia, Without degree constraint, Transformation
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]
Problem graph for the minimal spanning tree problem in form of nested
dictionaries. Each vertex needs to be weighted.
(e.g. Wikipedia example
{
0: `{1: {"weight": 1}`, 3: `{"weight": 4}`, 4: `{"weight": 3}`},
1: `{3: {"weight": 4}`, 4: `{"weight": 2}`},
2: `{4: {"weight": 4}`, 5: `{"weight": 5}`},
3: `{4: {"weight": 4}`},
4: `{5: {"weight": 7}`}
} )
maxdegree : int
The maximum degree at one joint of the tree. (e.g. 2 is a special case of the
travelling salesman problem).
A : Optional[float] = None.
The penalty factor for constraints. Can be left None to be estimated from
the problem graph via the papers suggestion.
Default: None
B : Optional[float] = 1.
The optimization penalty factor.
Deafult: 1
baratio : Optional[float] = 0.1
A factor that increases or decreases the ratio between constraint and
optimization penalty factors in the automatic estimation. If constraints are
violated, this ratio needs to be decreased as the A penalty needs to be
increased. 0.1 is a good starting point.
Default: 0.1
Minimum Vertex Cover problem
Description
A vertex cover of an undirected graph is a set of vertices that includes at least one endpoint of every edge of this graph. The Minimum Vertex Cover problem tries to find the smallest vertex cover in a given graph. The smallest vertex cover is the one that contains the least amount of nodes.
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the minimum vertex cover problem in form of nested
dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
P: int
Positive, scalar penalty value to penalize edges that are not covered.
Default: 8
Number Partitioning problem
Description
The Number Partitioning problem partitions a set of numbers into two subsets such that the difference of the subset sums is minimized.
Links
Attributes
numbers: List[int]
The set of numbers which has to be partitioned.
Portfolio Optimization problem
Description
The Portfolio Optimization problem tries to find the optimal portfolio of assets which achieves an equal or higher return than the target return with the lowest risk possible. The optimal portfolio is defined by the binary choices whether to invest in a specific asset or not.
Links
Attributes
returns: List[List[float]]
Returns matrix which contains time-series of returns per asset i.
R: float
Target for overall return of portfolio.
n: int
Number of wanted assets in set.
lambda0: int = 1
Default lagrange multiplier.
Portfolio Optimization problem with Investment Bands and Target Volatility
Description
The Portfolio Optimization problem tries to find the optimal portfolio of assets which achieves an equal or higher return than the target return with the lowest risk possible. The optimal portfolio is defined by the binary choices whether to invest in a specific asset or not.
This special case of portfolio optimization handles to additional constraints. On the one hand, it tries to find optimal investment portfolios with a fixed volatility. On the other hand, it imposes investment bands in the computed portfolios, i.e. the investment for each asset is between a minimum and a maximum.
Links
Attributes
logreturns: List[float]
Log return of each asset.
sigma: List[List[float]]
Risk matrix.
investmentbands: List[Tuple[float, float]]
Investment bands for each asset.
targetvolatility: float
Target volatility of portfolio.
maxbudget: int
Maximum budget.
budgetweight: float
Budget penalty factor.
volatilityweight: float
Volatility penalty factor.
Quadratic Assignment problem
Description
There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified. The Quadratic Assignment problem assigns all facilities to different locations with the goal of minimizing the sum of products of the distances and the corresponding flows.
Links
Attributes
flowmatrix: List[List]
A matrix denoting the flow (or weight) between the facilities.
e.g. for two facilities with a flow of 3, the flowmatrix will be
[[0, 3], [3, 0]].
distancematrix: List[List]
A matrix denoting the distance between the locations.
e.g. for two places with a distance of 8, the flowmatrix will be
[[0, 8], [8, 0]].
P: int
Positive, scalar penalty value to penalize when a facility is mapped to two
different locations or vice versa.
Default: 200
Quadratic Knapsack problem
Description
Given an upper bound of budget and a set of potential projects, each having a certain cost, a certain value, and value interactions with the other projects, the Quadratic Knapsack problem selects the combination of projects with the highest total value, without exceeding the budget restraint.
Links
Attributes
projects: List[List[float]]
A double nested list with entries projects[i][j] corresponding to the value
gain of choosing both projects i and j at the same time.
costs: List[float]
The individual costs of each project.
budget: float
Budget restraint (upper bound) on projects.
P: int
The weight of the penalty term.
Default: 10
Satellite Scheduling problem
Description
We assume a satellite can occupy three states: charging (c), downlink (d) and
experiment (e). We discretize the time and assume time steps t ∈ {0,1,...,T}.
The variable xst tells us if the satellite is in the state s ∈ {c,d,e} at time
t. With this, the time sequence of these variables represents the schedule we want
to optimize. The optimization goal is to record as much data as possible during the
mission. [1]
There are two satellite variables which may change over time: The charge of the battery C and the data stored on the memory D. The rate with which these variables are changing depending on state s are denoted by cs and ds respectively. [1]
For example the experiment state will increase the data dd > 0 and decrease the
charge dc < 0. Both the battery and the memory define an upper and lower limit
for the charge and the data, respectively. Not every state can be occupied at each
instance in time. For example, the charging through solar panels is only possible
in sunlight, or the downlink is only possible in the vicinity of a ground station.
Therefore for each state s there is a subset of times τs ⊆ {0,1,...,T}* at which
the satellite can occupy this state. To enforce this constraint, we remove all
variables xst ∈ {xst |t ∈ τs}. [1]
For the sake of simplicity, we assume that each state has minimum duration of 1.
Links
Transformation (Experiences with Scheduling Problems on Adiabatic Quantum Computers)
Attributes
T: int
T is the latest included time step. Note that the earliest included time step
is always *0*.
P: Tuple[int, int, int, int, int, int]
The penalties for each constraint.
Tau: List[List[int]]
Times to be removed for each state.
d: Dict
Dict describing downlink state which includes entries *rate*, *initial*,
*max*, *min*.
c: Dict
Dict describing charging state which includes entries *rate*, *initial*,
*max*, *min*.
S: int
*S* is the total number of possible states.
Sensor Placement problem
Description
The Sensor Placement problem finds the optimal placement of pressure sensors on a water distribution network, which is modelled by a graph where the edges have weights assigned to them. A higher weight corresponds to a higher importance that a sensor is placed on one of the nodes of the edge. Placing a sensor at a given node has a cost attached to it. The total cost of placing the sensors should also be minimized. As a constraint, there is a predetermined number of sensors s, which should be placed on the network.
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the sensor placement problem in form of nested
dictionaries.
(e.g. network with 3 nodes:
`{0: {2: {'weight': 1.0}`}, 1: `{2: {'weight': 6.0}`},
2: `{0: {'weight': 1.0}`, 1: `{'weight': 6.0}`}}
or networkx.todictofdicts(networkx.Graph(...)) )
costs: List[float]
Cost of placing a sensor on specific node.
s: int
Number of sensors.
A: float
Lagrange multiplier in front of constraint in eq. (15).
B: float
Lagrange multiplier in front of constraint in eq. (13).
Set Cover problem
Description
Given a set S and a list of subsets of S, so that each element of S is contained in at least one of the subsets, the Set Cover problem tries to find the smallest possible family C of these subsets so that all elements of S are contained in at least one subset of C.
Q-Bit Interpretation
Let n be the number of elements of S and let N be the number of subsets of S. Then, the qubit vector x will have length N + N * n. For x[:N], x[i] = 1, iff. subset i is contained in the set cover. For x[N:], x[i] = 1, iff. the number of subsets which include element a is m > 0 and i = N + a * N + m.
Links
Attributes
subsetmatrix: List[List[float]]
A matrix containing all subsets.
e.g. for the set `{1, 2, 3}` and the subsets `{1, 2}`, `{2, 3}`, and `{3}`:
[[1, 1, 0], [0, 1, 1], [0, 0, 1]]
or:
SetCover.gensubsetsmatrix([1, 2, 3], [[1, 2], [2, 3], [3]])
A: int
A positive constant enforcing that each element of S is contained in at
least one subset.
B: int
A constant (0 < B < A) minimizing the number of subsets included.
Set Packing problem
Description
Given a set S and a list of subsets of S, a packing is a family C of these subsets so that all sets in C are pairwise disjoint. For a set S and a list of subsets of S, the Set Packing problem assigns a weight to each set and tries to find a packing so that the sum of the weights of the used sets is maximized.
Note that, in contrast to the transformation mentioned below, our QUBO formulation searches for min x^t Q x instead of max x^t Q x and thus all signs are flipped.
Q-Bit Interpretation
Subset i is part of the packing iff. qubit i is 1.
Links
Attributes
subsetmatrix: List[List[int]]
A matrix containing all subsets.
e.g. for the set `{1, 2, 3}` and the subsets `{1, 2}`, `{2, 3}`, and `{3}`:
[[1, 1, 0], [0, 1, 1], [0, 0, 1]]
weights: List[int]
An array of length nsubsets which assigns a weight to each subset.
P: int
Positive, scalar penalty value to penalize subsets that are not disjoint.
Default: 6
Set Partitioning problem
Description
The Set Partitioning problem partitions a set of items into a selection of possible subsets so that each item of the set occurs in one and only one subset and the cost of the chosen subsets is minimized.
Q-Bit Interpretation
Subset i is part of the partitioning iff. qubit i is 1.
Links
Description and Transformation
Attributes
set: List[int]
The set of items which has to be partitioned.
subsets: List[List[int]]
The possible subsets of set.
e.g. for set=[1, 2, 3] and the possible subsets `{1, 2}` and `{3}` one
has to specify subsets=[[1, 2], [3]].
costs: List[int]
The cost of each possible subset. Has to be of the same length as subsets.
P: int
Positive, scalar penalty value to penalize items that occur in more than one
subset.
Default: 10
Subgraph Isomorphism problem
Description
The Subgraph Isomorphism problem tries to find out whether, for two graphs G1 and G2, G2 contains a subgraph G3 that is isomorphic to G1, i.e. there exists a bijective, edge-invariant vertex mapping from G1 to G3. It returns the best such mapping it is able to find.
Links
Attributes
graph1: Dict[int, Dict[int, Dict[str, float]]]
The graph (in form of nested dictionaries) for which to check whether it is
isomorphic to a subgraph of graph2.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
graph2: Dict[int, Dict[int, Dict[str, float]]]
The graph (in form of nested dictionaries) for which to check whether it
contains a subgraph that is isomorphic to graph1.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
a: float = 1
A penalty value enforcing the bijectivity of the isomorphism.
b: float = 2
A penalty value (b > a) enforcing the edge-invariance of the isomorphism.
Subset Sum problem
Description
The Subset Sum problem finds a subset of numbers from a given set of integers where
the total sum over the subset is equal or maximally close to a target value t.
Example: Set {5, 8, 4, 6} and Target 9 returns the Subset {5, 4}
Links
Wikipedia, Transformation (section 3.2.3)
Attributes
numbers: List[int]
Set of integers from which the subset is chosen.
t: int
Target value for sum over all numbers in subset.
Support Vector Machine problem
Description
In machine learning, support vector machines are supervised learning models that perform linear classification in such a way that the seperating hyperplane is as far away from each data point as possible.
Note that, in this implementation, the model always assumes the separating hyperplane to be unbiased, i.e. it goes through the origin.
Q-Bit Interpretation
For interpretation, the qubit vector has to be cut into N sublists of length K (specified below). The sum of each of the products of each of these sublists and the precision vector gives a lagrangian multiplier for each data point.
Links
Attributes
X: List[List[float]]
Training data set in form of a nested list.
All inner lists have to be of the same length.
(e.g. 3 data points with 2 features:
[[1.1, 4.23], [0.1, -2.4], [-2.3, 1.11]]
Y: List[int]
Classification labels of the training data set.
e.g. for 3 data points:
[-1, 1, 1]
K: int
Length of the precision vector.
As the problem outputs are supposed to be real values but the qubo only
gives a binary vector, we need a precision vector, consisting of positive powers
of 2, to simulate real values. This parameter determines the length of this
vector.
(e.g. for K = 5, the precision vector is [0.25, 0.5, 1, 2, 4])
This parameter also determines the size of the qubo matrix together with the
number of data points N:
size = N * K
Traffic Flow Optimization problem
Description
The Traffic Flow Optimization problem tries to minimize the total time for a given set of cars to travel between their individual sources and destinations. This is achieved by minimizing the number of overlapping segments between assigned routes for each car.
Links
Description and Transformation
Attributes
carroutes: List[List[List[int]]]
The route segments of each possible route for each car.
(e.g. for two cars, where car 1 can take either route 0, 1, 2 or route 0, 3,
4 and car 2 can take either route 3, 0, 5 or route 6, 7, 5:
[[[0, 1, 2], [0, 3, 4]], [[3, 0, 5], [6, 7, 5]]]
Travelling Salesman problem
Description
The Travelling Salesman problem, either for a directed or undirected graph, asks the following: given a graph, where the edges are labeled with the distances between the corresponding nodes, what is the shortest possible route that visits each node exactly once and returns to the origin node?
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the travelling salesman problem in form of nested
dictionaries.
(e.g. fully connected graph with 3 nodes:
`{0: {1: {}`, 2: `{}`}, 1: `{0: {}`, 2: `{}`}, 2: `{0: {}`, 1: `{}`}}
or networkx.todictofdicts(networkx.completegraph(3)) )
A: Optional[float]
Positive penalty value which enforces that each node is visited exactly once.
if None, will be calculated with the equation: A = B * maxweight + 1
Default: None
B: Optional[float]
Positive penalty value (B * maxweight) < A) which helps find the
shortest route.
Default: 1.0
Weighted Maximum Cut problem
Description
The Weighted Maximum Cut problem tries to find a cut that maximizes the weight of intersecting edges in an undirected weighted graph.
Links
Attributes
graph: Dict[int, Dict[int, Dict[str, float]]]
Problem graph for the weighted maximum cut problem in form of nested
dictionaries.
Every edge has to have an assigned weight.
(e.g. fully connected graph with 3 nodes and edge weights:
`{0: {1: {"weight": 1}`, 2: `{"weight": 1}`}, 1: `{0: {"weight": 1}`,
2: `{"weight": 1}`}, 2: `{0: {"weight": 1}`, 1: `{"weight": 1}`}} )