SMT Generation

generate(graph, feasible_configurations, decision_variables, linear_energy_ranges, quadratic_energy_ranges, min_classical_gap, smt_solver_name=None)[source]

Generates the Ising model that induces the given feasible configurations. The code is based on the papers 1 and 2.

Parameters

  • graph (nx.Graph) – The target graph on which the Ising model is to be built.

  • feasible_configurations (dict) – The set of feasible configurations of the decision variables. The key is a feasible configuration as a tuple of spins, the values are the associated energy.

  • decision_variables (list/tuple) – Which variables in the graph are assigned as decision variables.

  • linear_energy_ranges (dict, optional) – A dict of the form {v: (min, max), …} where min and max are the range of values allowed to v.

  • quadratic_energy_ranges (dict) – A dict of the form {(u, v): (min, max), …} where min and max are the range of values allowed to (u, v).

  • min_classical_gap (float) – The minimum energy gap between the highest feasible state and the lowest infeasible state.

  • smt_solver_name (str/None) – The name of the smt solver. Must be a solver available to pysmt. If None, uses the pysmt default.

Returns

A 4-tuple containing:

dict: The linear biases of the Ising problem.

dict: The quadratic biases of the Ising problem.

dimod.BinaryQuadraticModel

float: The classical energy gap between ground and the first excited state.

Return type

tuple

Raises

ImpossiblePenaltyModel – If the penalty model cannot be built. Normally due to a non-zero infeasible gap.

1

Bian et al., “Discrete optimization using quantum annealing on sparse Ising models”, https://www.frontiersin.org/articles/10.3389/fphy.2014.00056/full

2

Z. Bian, F. Chudak, R. Israel, B. Lackey, W. G. Macready, and A. Roy “Mapping constrained optimization problems to quantum annealing with application to fault diagnosis” https://arxiv.org/pdf/1603.03111.pdf