This subpackage contains the building blocks for formulating and solving models
with EQC devices. Many well known models in the space of quantum computing use
quadratic operators. Two generally accepted formats for quadratic models are
Ising Hamiltonian and QUBO operators. Ising models are not explicitly supported
because of the simple equivalence to QUBO models. Converters from Ising to QUBO
are readily available and may be added as a utility function in the future, but
for now are left out of the package. Other quadratic models, such as integer
or floating point models are supported using the domain and upper bound of the
model variables and the solver choice.
Polynomial models are used to support higher order interactions between
variables. These models are defined over non-negative variables with the
highest power interaction being the only restriction on variable interactions.
This is also known as all-to-all connectivity.
Subpackages
constraints
This module defines support for linear equality and inequality constraints.
It can be paired with the penalty multiplier algorithm to choose multiplier
values which satisfy the enforcement of constraints as penalties. The mixin
pattern is used to allow more complex classes to be built from these bases.
ConstraintMixIn
ConstraintModel
InequalitiesMixIn
InequalityConstraintModel
quadratic
This module defines the methods required to convert a linear vector and
quadratic matrix into the required operator, either QUBO or Polynomial, for
solving with EQC. The support for constraints is also incorporated.
ConstrainedQuadraticModel
QuadraticModel
polynomial
This module defines the classes and methods for conversion from arrays of
coefficients and indices to operators for solving with EQC. The support for
constriants is also incorporated.
PolynomialModel
ConstrainedPolynomialModel
base
This module defines abstract base classes for models and solvers.
EqcModel
ModelSolver
operators
This module defines the operator types to use for passing problems to EQC
devices.
Provides a constrained quadratic operator and device sum constraint support.
Parameters:
J (Quadratic hamiltonian array.)
C (Linear hamiltonian array.)
lhs (Left hand side of the linear constraints.)
rhs (Right hand side of the linear constraints.)
Examples
>>> C = np.array([1, 2])
>>> J = np.array([[2, 1], [1, 2]])
>>> lhs = np.array([[1, 1], [1, 1]])
>>> rhs = np.array([1, 1])
>>> from eqc_models.base.quadratic import ConstrainedQuadraticModel
>>> model = ConstrainedQuadraticModel(C, J, lhs, rhs)
>>> model.penalty_multiplier = 1
>>> model.upper_bound = np.array([1, 1])
>>> qubo = model.qubo
>>> qubo.Q
array([[1., 3.],
[3., 2.]])
propertyH:Tuple[ndarray,ndarray]
Return a pair of arrays, the linear and quadratic portions of a quadratic
operator that has the objective plus penalty functions multiplied by the
penalty multiplier. The linear terms are the first array and the quadratic
are the second.
indices are of the format [0, idx-1, …, idx-d] which must be non-decreasing
and each idx-j is a 1-based index of the variable which is a power in the
term. For a polynomial where the highest degree is 3 and specifying a term
such as x_1x_2, the index array is [0, 1, 2]. Another example, x_1^2x_2 is
[1, 1, 2].
Only linear equality constraints are supported. Translate Ax=b into
penalties using the superclass.
Take the polynomial form of the penalties from the penalties property
and evaluate the solution. The offset can be included by passing a True
value to the include_offset keyword argument.
Parameters:
solution (np.ndarray) – Solution to evaluate for a penalty value
include_offset (bool) – Optional argument indicating whether or not to include the offset value.
Returns:
Penalty value
Return type:
float
Examples
>>> coeff = np.array([-1.0, -1.0])
>>> indices = np.array([(0, 1), (0, 2)])
>>> lhs = np.array([[1.0, 1.0]])
>>> rhs = np.array([1.0])
>>> model = ConstrainedPolynomialModel(coeff, indices, lhs, rhs)
This mixin enables inequality constraints by automatically
generating slack variables for each inequality
This mixin adds a senses attribute which has a value for each
constraint. The values are one of ‘EQ’, ‘LE’ or ‘GE’ for equal
to, less than or equal to or greater than or equal to. The effect
of the value is to control whether a slack is added and what
the sign of the slack variable in the constraint is. Negative
is used for GE, positive is used for LE and all slack variables
get a coefficient magnitude of 1.
The constraints are modified on demand, so the class members,
lhs and rhs remain unmodified.
propertysenses:List[str]
Comparison operator by constraint
propertynum_slacks:int
The number of slack variables. Will match the number of inequality
constraints.
Returns:
number
Return type:
int
propertyconstraints:Tuple[ndarray,ndarray]
Get the general form of the constraints, add slacks where needed
and return a standard, equality constraint form.
EqcModel subclasses must provide these properties/methods.
Decode:
takes a raw solution and translates it into the original problem
formulation
H:
property which returns a Hamiltonian operator
Upper_bound:
Let D be an array of length n which contains the largest possible value
allowed for x[i], which is the variable at index i, 0<=i<n. This means that a x[i]
is in the domain [0,D[i]]. If the solution type of x[i] is integer, then x[i] is
in the set of integers, Z, and also 0<=x[i]<=floor(D[i]).
Represents an operator and evalute the operator at a point or set of points.
The operator must be a polynomial, possibly multivariate, with powers of up
to 5, at the time of this version. The representation of a polynomial uses
a sparse method with two components per term. A term is described by the
coefficient and a tuple of integers which indicate the variable indexes of
the term. The coefficients can be any value which fits in 32-bit floating
point representation, but the dynamic range of the coefficients should be
within the limit of the hardware’s sensitivity for best results. The term
index tuple length must be consistent across all terms. If a term does not
have a variable index for all positions, such as with a term which is the
square of a variable when other terms have third-order powers, then there
must be a placeholder of 0 for the unused power. The variable indexes must
be in the tuple in ascending order. Here are some examples (suppose the max
degree is 4):
x12: (0,0,1,1)
x1x2x3: (0,1,2,3)
x22x32: (2,2,3,3)
while it does not affect the optimiztion, a constant term can be applied to
the polynomial by using an index of all zeros (0,0,0,0). When
listing the coefficients, the position in the array must correspond to the
position in the array of indexes. Also, the indices must be ordered with
linear terms first, quadratic terms next and so forth. A polynomial operator
does not have an explicit domain. It could be evaluated on an array of any
real numbers.
Parameters:
coefficients (List, np.array) – Floating point values for the coefficients of a polynomial. Must
correspond to the entries in the indices array.
indices (List, np.array) – List of tuples or 2d np.array with integer values describing the term
which the corresponding coefficient value is used for.
Dirac3CloudSolver is a class that encapsulates the different calls to Qatalyst
for Dirac-3 jobs. Currently, there are two different jobs, one for integer and
another for continuous solutions. Calling the solve method with different arguments
controls which job is submitted. The continuous job requires sum_constraint
and optionally takes the solution_precision argument. The integer job
does not accept either of these parameters, so specifying a sum constraint forces
the job type to be continuous and not specifying it results in the integer job being
called.
Continuous Solver
Utilizing Dirac-3 as a continuous solver involves encoding the variables in single time bins
with the values of each determined by a normalized photon count value.
Integer Solver
Utilizing Dirac-3 as an integer solver involves encoding the variables in multiple time bins,
each representing a certain value for that variable, or “qudit”.
Examples
>>> C = np.array([[1], [1]])
>>> J = np.array([[-1.0, 0], [0, -1.0]])
>>> from eqc_models.base.quadratic import QuadraticModel
>>> model = QuadraticModel(C, J)
>>> model.upper_bound = np.array([1, 1]) # set the domain maximum per variable
model (EqcModel) – a model object which supplies a hamiltonian operator for the
device to sample. Must support the polynomial operator property.
tags (List) – a list of strings to save with the job
sum_constraint (float) – a value which applies a constraint to the solution, forcing
all variables to sum to this value, changes method to continuous
solver
relaxation_schedule (int) – a predefined schedule indicator which sets parameters
on the device to control the sampling through photon
measurement
solution_precision (float) – a value which, when not None, indicates the numerical
precision desired in the solution: 1 for integer, 0.1
for tenths place, 0.01 for hundreths and None for raw,
only used with continuous solver
num_samples (int) – the number of samples to take, defaults to 1
wait (bool) – a flag for waiting for the response or letting it run asynchronously.
Asynchronous runs must retrieve results directly using qci-client and
the job_id.
mean_photon_number (float) – an optional decimal value which sets the average number
of photons that are present in a given quantum state.
Modify this value to control the relaxation schedule more
precisely than the four presets given in schedules 1
through 4. Allowed values are decimals between 0.1 and 2.
normalized_loss_rate (int) – an integer value which Sets the amount of loss introduced
into the system for each loop during the measurement process.
Modify this value to control the relaxation schedule more
precisely than the four presets given in schedules 1
through 4. Allowed values range from 1 to 50.
model (EqcModel) – Instance of a model for solving.
name (str) – Name of the job; default is None.
tags (list) – A list of job tags; default is None.
num_samples (int) – Number of samples used; default is 1.
wait (bool) – The wait flag indicating whether to wait for the job to complete
before returning the complete job data otherwise return a job ID
as soon as a job is submitted; default is True.
job_type (str) – Type of the job; default is None. When None, it is constructed
from the instance job_type property.
Returns:
job response dictionary
This method takes the particulars of the instance model and handles
model (EqcModel) – a model object which supplies a hamiltonian operator for the
device to sample. Must support the polynomial operator property.
tags (List) – a list of strings to save with the job
relaxation_schedule (int) – a predefined schedule indicator which sets parameters
on the device to control the sampling through photon
measurement
num_samples (int) – the number of samples to take, defaults to 1
wait (bool) – a flag for waiting for the response or letting it run asynchronously.
Asynchronous runs must retrieve results directly using qci-client and
the job_id.
mean_photon_number (float) – an optional decimal value which sets the average number
of photons that are present in a given quantum state.
Modify this value to control the relaxation schedule more
precisely than the four presets given in schedules 1
through 4. Allowed values are decimals between 0.1 and 2.
normalized_loss_rate (int) – an integer value which Sets the amount of loss introduced
into the system for each loop during the measurement process.
Modify this value to control the relaxation schedule more
precisely than the four presets given in schedules 1
through 4. Allowed values range from 1 to 50.
Dirac3IntegerCloudSolver is a class that encapsulates the different calls to
Qatalyst for Dirac-3 jobs. Utilizing Dirac-3 as an integer solver involves
encoding the variables in multiple time bins, each representing a certain
value for that variable, or “qudit”.
model (EqcModel) – a model object which supplies a hamiltonian operator for the
device to sample. Must support the polynomial operator property.
tags (List) – a list of strings to save with the job
sum_constraint (float) – a value which applies a constraint to the solution, forcing
all variables to sum to this value
relaxation_schedule (int) – a predefined schedule indicator which sets parameters
on the device to control the sampling through photon
measurement
solution_precision (float) – a value which, when not None, indicates the numerical
precision desired in the solution: 1 for integer, 0.1
for tenths place, 0.01 for hundreths and None for raw
num_samples (int) – the number of samples to take, defaults to 1
wait (bool) – a flag for waiting for the response or letting it run asynchronously.
Asynchronous runs must retrieve results directly using qci-client and
the job_id.
mean_photon_number (float) – an optional decimal value which sets the average number
of photons that are present in a given quantum state.
Modify this value to control the relaxation schedule more
precisely than the four presets given in schedules 1
through 4. Allowed values are decimals between 0.1 and 2.
normalized_loss_rate (int) – an integer value which Sets the amount of loss introduced
into the system for each loop during the measurement process.
Modify this value to control the relaxation schedule more
precisely than the four presets given in schedules 1
through 4. Allowed values range from 1 to 50.
resource_usage (List of Lists or 2D np.ndarray) – rows represent tasks and columns represent resources,
specifying the amount of each resource required per task.
resource_limits (1D array or List) – specifying the limit on each resource.
cost_per_task (1D array List) – specifying the cost per task (or benefit with negative of value).
penalty_multiplier
value for weighting the penalties formed from the equality constraints
This class represents a resource allocation model for maximizing total benefit. In other words,
Given a list of resources and a list of tasks, allocate the resources among the tasks so as to
maximize the economic benefit.
Here’s an example. Five tasks must share 4 resources. Each task can use a different amount of
each resource.
resource_usage (List of Lists or 2D np.ndarray) – rows represent tasks and columns represent resources,
specifying the amount of each resource required per task.
resource_limits (1D array or List) – specifying the limit on each resource.
resource_rule (List) – ResourceRuleEnum values for each resource
cost_per_task (1D array List) – specifying the cost per task (or benefit with negative of value).
penalty_multiplier
value for weighting the penalties formed from the equality constraints
names of variables formed from tasks and assignments
Type:
List
This class represents a resource allocation model for maximizing total benefit. In other words,
Given a list of resources and a list of tasks, allocate the resources among the tasks so as to
maximize the economic benefit.
Adds resource_rule as an argument. This must be a list of strings specifying
constraints for each resource (LE, GE, or EQ).
Here’s an example. Five tasks must share 4 resources. Each task can use a different amount of
each resource.
A (np.array) – matrix of distances or costs between locations
B (np.array) – matrix of flows between facilities
C (np.array) – matrix pf fixed costs of assigning facilities to locations
Formulates a quadratic programming model from three inputs. The inputs are composed of:
a matrix which describes the unit cost of moving a single asset between locations. This
matrix can describe asynchronous costs that differ by direction of flow; a matrix which
describes the quantity of flow between facilities. This matrix describes the quantity
in the direction of flow; a matrix which desribes the fixed cost of assigning a facility
to a location.
Using these flows and costs, an optimization problem is formulated to determine a
solution which minimizes the total cost for positioning facilities at locations. The
facilities do not have to be buildings or campuses and the locations do not have to be
geographical locations. See Beckmann and and Koopmans (1957) for the original reference.
Using the Miller Tucker Zemlin (1960) formulation of TSP, create a model
instance that contains variables for node order (to eliminate subtours)
and edge choices.
Two constraints for every node, one for the
edge chosen to enter and another for the edge chosen to leave.
One constraint for every edge not leading to the depot.
Returns: 2-Tuple of numpy arrays, one as lefthand side and the other
model (ConstraintModel) – Instance of a model to search out a penalty multiplier value, must be constrained model.
solver (ModelSolver subclass) – Instance of a solver class to use to run the algorithm.
Properties
upper_boundfloat
Upper bound value for the objective function, this need not be a least upper bound,
but the tighter the value, the more efficient the search
solutionsList
The solutions found during the algorithm run
alphasList
The values of multiplier found at each algorithm iteration
penaltiesList
The values for penalties found at each algorithm iteration. A penalty of 0
indicates algorithm termination.
dynamic_rangeList
The values for the dynamic range of the unconstrained problem formulation,
which is useful for identifying difficulty in representation of the problem
on the analog device.
The penalty multiplier search algorithm uses an infeasible solution to select the next
value for the penalty multiplier. The algorithm depends upon good solutions and only
guarantees termination when the solution found for a given multiplier is optimal. For
this reason, the implementation will terminate when no progress is made, thus making
it a heuristic. Providing an exact solver for the solver instance will guarantee that
the algorithm is correct and the penalty mulktiplier found is the minimal multiplier
capable of enforcing the condition that an unconstrained objective value for a feasible
solution is less than an unconstrained objective value for an infeasible solution.
This example uses the quadratic assignment problem and the known multiplier to test
the implementation of the algorithm.
>>> from eqc_models.solvers.qciclient import Dirac3CloudSolver
>>> from eqc_models.assignment.qap import QAPModel
>>> A = np.array([[0, 5, 8, 0, 1],
... [0, 0, 0, 10, 15],
... [0, 0, 0, 13, 18],
... [0, 0, 0, 0, 0.],
... [0, 0, 0, 1, 0.]])
>>> B = np.array([[0, 8.54, 6.4, 10, 8.94],
... [8.54, 0, 4.47, 5.39, 6.49],
... [6.4, 4.47, 0, 3.61, 3.0],
... [10, 5.39, 3.61, 0, 2.0],
... [8.94, 6.49, 3.0, 2.0, 0.]])
>>> C = np.array([[2, 3, 6, 3, 7],
... [3, 9, 2, 5, 9],
... [2, 6, 4, 1, 2],
... [7, 5, 8, 5, 7],
... [1, 9, 2, 9, 2.]])
>>> model = QAPModel(A, B, C)
>>> solver = Dirac3CloudSolver() # must be configured with environment variables
The “problem type” is a string of three characters.
The first character indicates the type of objective function used. It must be one of the following:
L a linear objective function
D a convex quadratic objective function whose Hessian is a diagonal matrix
C a convex quadratic objective function
Q a quadratic objective function whose Hessian may be indefinite
The second character indicates the types of variables that are present. It must be one of the following:
C all the variables are continuous
B all the variables are binary (0-1)
M the variables are a mix of continuous and binary
I all the variables are integer
G the variables are a mix of continuous, binary and integer
The third character indicates the type of the (most extreme) constraint function used; other constraints may be of a lesser type. It must be one of the following:
N there are no constraints
B some of the variables lie between lower and upper bounds (box constraints)
L the constraint functions are linear
D the constraint functions are convex quadratics with diagonal Hessians
C the constraint functions are convex quadratics
Q the constraint functions are quadratics whose Hessians may be indefinite
Thus for continuous problems, we would have
LCL a linear program
LCC or LCQ a linear program with quadratic constraints
CCB or QCB a bound-constrained quadratic program
CCL or QCL a quadratic program
CCC or CCQ or a quadratic program with quadratic constraints
QCC or QCQ
QGL - Quadratic objective, General variable type, Linear constraints
Handles QCL, QIL, QBL, QML problems
:param :
:type : C: np.ndarray - linear portion of the objective
:param :
:type : J: np.ndarray - quadratic portion of the objective
:param :
:type : A: np.ndarray - left hand side of the linear constraints
:param :
:type : b: np.ndarray - right hand side of the linear constraints
Create a pair of lists describing a polynomial that
represents the file contained in the qplib-formatted file
descriptor fp. Sets a guess for the sum constraint when constructing
the model, but it has no effect on the polynomial file output.
Parameters
:fp: File descriptor for qplib-formatted file
:DTYPE: Default numeric datatype for non-integer numeric values