Converters for OptimizationProblem¶

Overview¶

This module provides various converters to transform optimization problems into different forms. These converters can be used to change variable types, objective functions, and constraints. In general, quantum algorithms require a specific formulation of an optimization problem, so we often need to convert our problem into the right type.

For example, the QUBO (Quadratic Unconstrained Binary Optimization) format is widely used in quantum computing. The OptimizationProblemToQubo converter transforms an OptimizationProblem into QUBO form by converting variables to binary and eliminating constraints. Some quantum algorithms can also handle higher-order terms. In such cases, the OptimizationProblemToHubo converter transforms an OptimizationProblem into a HUBO (Higher-order Unconstrained Binary Optimization) format.

Both QUBO and HUBO problems can be mapped to Ising Hamiltonians by the to_ising() function. Both binary variables and spin variables are supported. In Optimization add-on, these are represented by the qiskit.quantum_info.SparsePauliOp object.

The converters provided in this module include:

BinaryToSpin: Converts binary variables to spin variables.
SpinToBinary: Converts spin variables to binary variables.
IntegerToBinary: Converts integer variables to binary variables.
InequalityToEquality: Converts inequality constraints to equality constraints using slack variables.
EqualityToPenalty: Converts equality constraints to penalty terms in the objective function.
LinearInequalityToPenalty: Converts specific linear inequality constraints to penalty terms in the objective function with fewer additional variables.
MaximizeToMinimize: Converts a maximization objective to a minimization objective.
MinimizeToMaximize: Converts a minimization objective to a maximization objective.
OptimizationProblemToQubo: Converts OptimizationProblem in to a QUBO format. It’s a combination of several converters: IntegerToBinary, , InequalityToPenalty, InequalityToEquality, EqualityToPenalty, and MaximizeToMinimize. This converter will raise an exception if high-order terms are present.
OptimizationProblemToHubo: Converts an OptimizationProblem to a HUBO format. It’s also a combination of several converters: IntegerToBinary, InequalityToPenalty, EqualityToPenalty, and MaximizeToMinimize, while preserving higher-order terms in the objective function.

Code Examples¶

Integer to Binary Conversion¶

IntegerToBinary onverts integer variables into binary variables and adjusts the corresponding coefficients to eliminate integer variables from an OptimizationProblem. For this conversion, the bounded-coefficient encoding proposed in arxiv:1706.01945 (Eq. (5)) is used. In this encoding, an integer variable \(x\) with bounds \(l \leq x \leq u\) is represented using binary variables \(b_i\) as follows:

\(x = l + \sum_{i=0}^{k-1} 2^i b_i + (u - l + 1 - 2^k) b_k\) where \(k = \lceil \log_2(u - l + 1) \rceil\). This encoding minimizes the number of binary variables required to represent the integer variable while ensuring that the bounds are respected.

For more details on the encoding method, please refer to the paper.

[1]:

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import IntegerToBinary

# Create an optimization problem with integer variables
op = OptimizationProblem("Integer to Binary Example")
op.integer_var(name="x", lowerbound=0, upperbound=3)
op.binary_var(name="y")

op.minimize(linear={"x": 2}, quadratic={("x", "x"): 1}, higher_order={3: {("x", "x", "y"): 1}})
op.linear_constraint(linear={"x": 1, "y": 1}, sense="LE", rhs=2, name="c1")
print("Original Problem:")
print(op.prettyprint())
# Convert integer variables to binary variables
int_to_bin = IntegerToBinary()
op_bin = int_to_bin.convert(op)
print("\nConverted Problem:")
print(op_bin.prettyprint())

Original Problem:
Problem name: Integer to Binary Example

Minimize
  x^2*y + x^2 + 2*x

Subject to
  Linear constraints (1)
    x + y <= 2  'c1'

  Integer variables (1)
    0 <= x <= 3

  Binary variables (1)
    y


Converted Problem:
Problem name: Integer to Binary Example

Minimize
  x@0^2*y + 4*x@0*x@1*y + 4*x@1^2*y + x@0^2 + 4*x@0*x@1 + 4*x@1^2 + 2*x@0
  + 4*x@1

Subject to
  Linear constraints (1)
    x@0 + 2*x@1 + y <= 2  'c1'

  Binary variables (3)
    x@0 x@1 y

Binary to Spin Conversion¶

The BinaryToSpin converter transforms binary variables (0/1) into spin variables (-1/+1) using the relation \(b = (1 - s)/2\), where \(b\) is a binary variable and \(s\) is a spin variable. This conversion is particularly useful in quantum computing contexts, where spin variables are often preferred.

[2]:

from qiskit_addon_opt_mapper.converters import BinaryToSpin

# Convert binary variables to spin variables
op_bin = OptimizationProblem("Binary to Spin Example")
op_bin.binary_var(name="b1")
op_bin.binary_var(name="b2")
op_bin.minimize(linear={"b1": 1, "b2": 1}, quadratic={("b1", "b2"): 1})
print("Original Binary Problem:")
print(op_bin.prettyprint())

# Convert binary variables to spin variables
bin_to_spin = BinaryToSpin()
op_spin = bin_to_spin.convert(op_bin)
print("\nConverted Spin Problem:")
print(op_spin.prettyprint())

Original Binary Problem:
Problem name: Binary to Spin Example

Minimize
  b1*b2 + b1 + b2

Subject to
  No constraints

  Binary variables (2)
    b1 b2


Converted Spin Problem:
Problem name: Binary to Spin Example

Minimize
  0.25*b1@spin*b2@spin - 0.75*b1@spin - 0.75*b2@spin + 1.25

Subject to
  No constraints

  Spin variables (2)
    -1 <= b1@spin <= 1
    -1 <= b2@spin <= 1

Spin to Binary Conversion¶

The SpinToBinary converter transforms spin variables (-1/+1) into binary variables (0/1) using the relation \(s = 1 - 2b\), where \(s\) is a spin variable and \(b\) is a binary variable. This conversion is useful when an optimization problem needs to be expressed in terms of binary variables for certain algorithms or solvers.

[3]:

from qiskit_addon_opt_mapper.converters import SpinToBinary

op_spin2 = OptimizationProblem("Spin to Binary Example")
op_spin2.spin_var(name="s1")
op_spin2.spin_var(name="s2")
op_spin2.minimize(linear={"s1": 1, "s2": 1}, quadratic={("s1", "s2"): 1})
print("Original Spin Problem:")
print(op_spin2.prettyprint())
# Convert spin variables to binary variables
spin_to_bin = SpinToBinary()
op_bin2 = spin_to_bin.convert(op_spin2)
print("\nConverted Binary Problem:")
print(op_bin2.prettyprint())

Original Spin Problem:
Problem name: Spin to Binary Example

Minimize
  s1*s2 + s1 + s2

Subject to
  No constraints

  Spin variables (2)
    -1 <= s1 <= 1
    -1 <= s2 <= 1


Converted Binary Problem:
Problem name: Spin to Binary Example

Minimize
  4*s1@bin*s2@bin - 4*s1@bin - 4*s2@bin + 3

Subject to
  No constraints

  Binary variables (2)
    s1@bin s2@bin

Inequality to Equality Conversion¶

The InequalityToEquality converter transforms inequality constraints into equality constraints by introducing slack variables. For example, an inequality constraint of the form: \(ax + by \leq c\) is converted to an equality constraint: \(ax + by + s = c\) where \(s\) is a slack variable that is constrained to be non-negative (\(s \geq 0\)). This conversion allows the optimization problem to be expressed entirely in terms of equality constraints, which can be beneficial for certain optimization algorithms that require equality constraints.

[4]:

from qiskit_addon_opt_mapper.converters import InequalityToEquality

# Create an optimization problem with an inequality constraint
op2 = OptimizationProblem("Inequality to Equality Example")
op2.binary_var(name="x")
op2.binary_var(name="y")
op2.minimize(linear={"x": 1, "y": 1})
op2.linear_constraint(linear={"x": 1, "y": 1}, sense="LE", rhs=5, name="c1")
op2.linear_constraint(linear={"x": 10}, sense="GE", rhs=3, name="c2")
print("Original Problem:")
print(op2.prettyprint())
# Convert inequality constraints to equality constraints
ineq_to_eq = InequalityToEquality()
op_eq = ineq_to_eq.convert(op2)
print("\nConverted Problem:")
print(op_eq.prettyprint())

Original Problem:
Problem name: Inequality to Equality Example

Minimize
  x + y

Subject to
  Linear constraints (2)
    x + y <= 5  'c1'
    10*x >= 3  'c2'

  Binary variables (2)
    x y


Converted Problem:
Problem name: Inequality to Equality Example

Minimize
  x + y

Subject to
  Linear constraints (2)
    c1@int_slack + x + y == 5  'c1'
    -c2@int_slack + 10*x == 3  'c2'

  Integer variables (2)
    0 <= c1@int_slack <= 5
    0 <= c2@int_slack <= 7

  Binary variables (2)
    x y

Equality to Penalty Conversion¶

The EqualityToPenalty converter transforms equality constraints into penalty terms added to the objective function.

where \(P\) is a large positive/negative constant that penalizes deviations from the equality constraint (When the problem is a minimizing problem, \(P\) should be a large positive constant. Conversely, when the problem is a maximizing problem, \(P\) should be a large negative constant). This approach effectively incorporates the equality constraints into the objective function, allowing the optimization algorithm to focus on minimizing or maximizing the modified objective function while still respecting the original constraints. If \(P\) is not specified, it is automatically set to a value larger than the sum of the absolute values of the coefficients in the objective function.

[5]:

from qiskit_addon_opt_mapper.converters import EqualityToPenalty

# Create an optimization problem with an equality constraint
op3 = OptimizationProblem("Equality to Penalty Example")
op3.binary_var(name="x")
op3.binary_var(name="y")
op3.linear_constraint(linear={"x": 1, "y": 1}, sense="EQ", rhs=3, name="c1")
print("Original Problem:")
print(op3.prettyprint())
# Convert equality constraints to penalty terms in the objective function
eq_to_penalty = EqualityToPenalty(penalty=1e5)
op_penalty = eq_to_penalty.convert(op3)
print("\nConverted Problem:")
print(op_penalty.prettyprint())

Original Problem:
Problem name: Equality to Penalty Example

Minimize
  0

Subject to
  Linear constraints (1)
    x + y == 3  'c1'

  Binary variables (2)
    x y


Converted Problem:
Problem name:

Minimize
  100000*x^2 + 200000*x*y + 100000*y^2 - 600000*x - 600000*y + 900000

Subject to
  No constraints

  Binary variables (2)
    x y

[6]:

# Automatic penalty value
eq_to_penalty_auto = EqualityToPenalty()
op_penalty_auto = eq_to_penalty_auto.convert(op3)
print("\nConverted Problem with Automatic Penalty:")
print(op_penalty_auto.prettyprint())


Converted Problem with Automatic Penalty:
Problem name:

Minimize
  x^2 + 2*x*y + y^2 - 6*x - 6*y + 9

Subject to
  No constraints

  Binary variables (2)
    x y

Linear Inequality to Penalty Conversion¶

The LinearInequalityToPenalty converter transforms specific binary linear inequality constraints into penalty terms added to the objective function with a fewer number of additional variables compared to the InequalityToEquality converter followed by the EqualityToPenalty converter.

Note that x, y, z and ``x_i`` are binary variables, and P is a penalty factor,where the value of P is automatically determined or supplied by users.

[7]:

# Linear Inequality to Penalty Conversion
from qiskit_addon_opt_mapper.converters import LinearInequalityToPenalty

# Create an optimization problem with a specific linear inequality constraint
op4 = OptimizationProblem("Linear Inequality to Penalty Example")
op4.binary_var(name="x")
op4.binary_var(name="y")
op4.linear_constraint(linear={"x": 1, "y": -1}, sense="LE", rhs=0, name="c1")  # x <= y
print("Original Problem:")
print(op4.prettyprint())
# Convert specific linear inequality constraints to penalty terms in the objective function
lin_ineq_to_penalty = LinearInequalityToPenalty(penalty=1e5)
op4_penalty = lin_ineq_to_penalty.convert(op4)
print("\nConverted Problem:")
print(op4_penalty.prettyprint())

Original Problem:
Problem name: Linear Inequality to Penalty Example

Minimize
  0

Subject to
  Linear constraints (1)
    x - y <= 0  'c1'

  Binary variables (2)
    x y


Converted Problem:
Problem name: Linear Inequality to Penalty Example

Minimize
  -100000*x*y + 100000*x

Subject to
  No constraints

  Binary variables (2)
    x y

Maximize to Minimize Conversion¶

The MaximizeToMinimize converter transforms a maximization objective into a minimization objective by negating the coefficients of the objective function.

The MinimizeToMaximize converter performs the inverse operation, converting a minimization objective into a maximization objective by negating the coefficients of the objective function.

[8]:

from qiskit_addon_opt_mapper.converters import MaximizeToMinimize, MinimizeToMaximize

# Create an optimization problem with a maximization objective
op5 = OptimizationProblem("Maximize to Minimize Example")
op5.binary_var(name="x")
op5.binary_var(name="y")
op5.maximize(linear={"x": 1, "y": 2})
print("Original Problem:")
print(op5.prettyprint())
# Convert maximization objective to minimization objective
max_to_min = MaximizeToMinimize()
op5_min = max_to_min.convert(op5)
print("\nConverted Problem:")
print(op5_min.prettyprint())

Original Problem:
Problem name: Maximize to Minimize Example

Maximize
  x + 2*y

Subject to
  No constraints

  Binary variables (2)
    x y


Converted Problem:
Problem name: Maximize to Minimize Example

Minimize
  -x - 2*y

Subject to
  No constraints

  Binary variables (2)
    x y

[9]:

# Minimize to Maximize Conversion
min_to_max = MinimizeToMaximize()
op5_max = min_to_max.convert(op5_min)
print("\nRe-converted Problem:")
print(op5_max.prettyprint())


Re-converted Problem:
Problem name: Maximize to Minimize Example

Maximize
  x + 2*y

Subject to
  No constraints

  Binary variables (2)
    x y

QUBO Conversion¶

The OptimizationProblemToQubo converter transforms an OptimizationProblem in quadratic format (quadratic objective function with linear constraints) into QUBO form by converting variables to binary and eliminating constraints. It combines several converters: IntegerToBinary, SpinToBinary, InequalityToPenalty, InequalityToEquality, EqualityToPenalty, and MaximizeToMinimize. The resulting QUBO problem can be directly mapped to an Ising Hamiltonian using the to_ising() function.

[10]:

from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

# Create a optimization problem with various constraints
op6 = OptimizationProblem("Quadratic Program to QUBO Example")
op6.integer_var(name="x", lowerbound=0, upperbound=3)
op6.binary_var(name="y")
op6.minimize(linear={"x": 2}, quadratic={("x", "y"): 1})
op6.linear_constraint(linear={"x": 1, "y": 1}, sense="LE", rhs=5, name="c1")
print("Original Problem:")
print(op6.prettyprint())
# Convert the optimization problem to QUBO format
qubo_converter = OptimizationProblemToQubo(penalty=1e5)
op6_qubo = qubo_converter.convert(op6)
print("\nConverted QUBO Problem:")
print(op6_qubo.prettyprint())
print(f"penalty: {qubo_converter.penalty}")

Original Problem:
Problem name: Quadratic Program to QUBO Example

Minimize
  x*y + 2*x

Subject to
  Linear constraints (1)
    x + y <= 5  'c1'

  Integer variables (1)
    0 <= x <= 3

  Binary variables (1)
    y


Converted QUBO Problem:
Problem name:

Minimize
  100000*c1@int_slack@0^2 + 400000*c1@int_slack@0*c1@int_slack@1
  + 400000*c1@int_slack@0*c1@int_slack@2 + 400000*c1@int_slack@1^2
  + 800000*c1@int_slack@1*c1@int_slack@2 + 400000*c1@int_slack@2^2
  + 200000*x@0*c1@int_slack@0 + 400000*x@0*c1@int_slack@1
  + 400000*x@0*c1@int_slack@2 + 100000*x@0^2 + 400000*x@0*x@1 + 200001*x@0*y
  + 400000*x@1*c1@int_slack@0 + 800000*x@1*c1@int_slack@1
  + 800000*x@1*c1@int_slack@2 + 400000*x@1^2 + 400002*x@1*y
  + 200000*y*c1@int_slack@0 + 400000*y*c1@int_slack@1 + 400000*y*c1@int_slack@2
  + 100000*y^2 - 1000000*c1@int_slack@0 - 2000000*c1@int_slack@1
  - 2000000*c1@int_slack@2 - 999998*x@0 - 1999996*x@1 - 1000000*y + 2500000

Subject to
  No constraints

  Binary variables (6)
    x@0 x@1 y c1@int_slack@0 c1@int_slack@1 c1@int_slack@2

penalty: 100000.0

HUBO Conversion¶

The OptimizationProblemToHubo converter transforms an OptimizationProblem into a HUBO format (higher-order objective function with no constraints) by converting variables to binary and eliminating constraints. It combines several converters: IntegerToBinary, SpinToBinary, InequalityToPenalty, EqualityToPenalty, and MaximizeToMinimize, while preserving higher-order terms in the objective function. The resulting HUBO problem can be directly mapped to an Ising Hamiltonian using the to_ising() function.

[11]:

from qiskit_addon_opt_mapper.converters import OptimizationProblemToHubo

# Create an optimization problem with higher-order terms and constraints
op7 = OptimizationProblem("Optimization Problem to HUBO Example")
op7.integer_var(name="x", lowerbound=0, upperbound=3)
op7.binary_var(name="y")
op7.binary_var(name="z")

op7.minimize(linear={"x": 2}, quadratic={("x", "y"): 1}, higher_order={3: {("x", "y", "z"): 1}})
op7.higher_order_constraint(higher_order={3: {("x", "y", "z"): 1}}, sense="EQ", rhs=2, name="c1")
print("Original Problem:")
print(op7.prettyprint())
# Convert the optimization problem to HUBO format
hubo_converter = OptimizationProblemToHubo(penalty=1e5)
op7_hubo = hubo_converter.convert(op7)
print("\nConverted HUBO Problem:")
print(op7_hubo.prettyprint())
print(f"penalty: {hubo_converter.penalty}")

Original Problem:
Problem name: Optimization Problem to HUBO Example

Minimize
  x*y*z + x*y + 2*x

Subject to
  Higher-order constraints (1)
    x*y*z == 2  'c1'

  Integer variables (1)
    0 <= x <= 3

  Binary variables (2)
    y z


Converted HUBO Problem:
Problem name:

Minimize
  100000*x@0^2*y^2*z^2 + 400000*x@0*x@1*y^2*z^2 + 400000*x@1^2*y^2*z^2
  - 399999*x@0*y*z - 799998*x@1*y*z + x@0*y + 2*x@1*y + 2*x@0 + 4*x@1 + 400000

Subject to
  No constraints

  Binary variables (4)
    x@0 x@1 y z

penalty: 100000.0

Ising transformation¶

Both QUBO and HUBO problems can be mapped to Ising Hamiltonians by the to_ising() function. In Optimization add-on, these are represented by the qiskit.quantum_info.SparsePauliOp object. In transforming to the Ising Hamiltonian, the binary variables are mapped to spin variables using the relation \(b_i = (1 - Z_i)/2\), where \(b_i\) is a binary variable and \(Z_i\) is a pauli Z operator acting on the \(i\)-th qubit. The resulting Ising Hamiltonian can then be used in quantum algorithms to approximate the ground state.

[12]:

from qiskit_addon_opt_mapper.translators import to_ising

ising_hubo, offset = to_ising(op7_hubo)
print("\nIsing Hamiltonian from HUBO:")
print(f"Ising Hamiltonian: {ising_hubo}")
print(f"Offset: {offset}")


Ising Hamiltonian from HUBO:
Ising Hamiltonian: SparsePauliOp(['IIIZ', 'IIZI', 'IZIZ', 'IZII', 'IZZI', 'ZIII', 'ZIIZ', 'ZZII', 'ZZIZ', 'ZIZI', 'ZZZI', 'IIII', 'IIZZ', 'IZZZ', 'ZIZZ', 'ZZZZ'],
              coeffs=[ 12498.625+0.j,  24997.25 +0.j, -12499.625+0.j,  62498.875+0.j,
 -24999.25 +0.j,  62499.625+0.j, -12499.875+0.j, -62499.625+0.j,
  12499.875+0.j, -24999.75 +0.j,  24999.75 +0.j,  73437.5  +0.j,
  25000.   +0.j, -25000.   +0.j, -25000.   +0.j,  25000.   +0.j])
Offset: 264066.625

[ ]: