Nota

Esta página fue generada a partir de docs/tutorials/02_converters_for_quadratic_programs.ipynb.

Conversores para Programas Cuadráticos#

Los problemas de optimización en el módulo de optimización de Qiskit se representan con la clase QuadraticProgram, que es una representación genérica y poderosa de los problemas de optimización. En general, los algoritmos de optimización se definen para una determinada formulación de un programa cuadrático y necesitamos convertir nuestro problema al tipo correcto.

Por ejemplo, Qiskit Optimization proporciona varios algoritmos de optimización que pueden manejar problemas de Optimización Binaria Cuadrática Sin Restricciones (Quadratic Unconstrained Binary Optimization, QUBO). Estos se mapean a Hamiltonianos Ising, para los cuales Qiskit Optimization usa el objeto qiskit.quantum_info.SparsePauliOp, y luego se aproxima su estado fundamental. Para esta optimización, se pueden utilizar algoritmos comúnmente conocidos como VQE o QAOA como rutina subyacente. Consulta el siguiente tutorial sobre el Optimizador Propio Mínimo para obtener más detalles. Ten en cuenta que también existen otros algoritmos que funcionan de manera diferente, como por ejemplo el GroverOptimizer.

Para mapear un problema al formato de entrada correcto, el módulo de optimización de Qiskit Optimization ofrece una variedad de convertidores. En este tutorial proporcionamos una descripción general de esta funcionalidad. Actualmente, Qiskit Optimization contiene los siguientes convertidores.

  • InequalityToEquality: convertir restricciones de desigualdad en restricciones de igualdad con variables de holgura (slack) adicionales.

  • IntegerToBinary: convertir variables enteras en variables binarias y los coeficientes correspondientes.

  • LinearEqualityToPenalty: convertir las restricciones de igualdad en términos adicionales de la función objetivo.

  • LinearInequalityToPenalty: convertir las restricciones de desigualdad en términos adicionales de la función objetivo.

  • MaximizeToMinimize: convertir al problema de minimización equivalente.

  • MinimizeToMaximize: convertir al problema de maximización equivalente.

  • QuadraticProgramToQubo: un contenedor que incluye InequalityToEquality, IntegerToBinary, LinearEqualityToPenalty, LinearInequalityToPenalty y MaximizeToMinimize por conveniencia.

InequalityToEquality#

InequalityToEqualityConverter convierte las restricciones de desigualdad en restricciones de igualdad con variables de holgura adicionales para eliminar las restricciones de desigualdad del QuadraticProgram. Los límites superiores y los límites inferiores de las variables de holgura se calcularán a partir de la diferencia entre el lado izquierdo y el lado derecho de las restricciones. Los signos de las variables de holgura dependen de los símbolos en restricciones como \(\leq\) y \(\geq\).

A continuación se muestra un ejemplo de un problema de maximización con dos restricciones de desigualdad. Las variables \(x\) y \(y\) son variables binarias y la variable \(z\) es una variable entera.

Con QuadraticProgram, un modelo de optimización del problema se escribe de la siguiente manera.

[1]:

from qiskit_optimization import QuadraticProgram
from qiskit_optimization.translators.docplex_mp import to_docplex_mp

[2]:

qp = QuadraticProgram()
qp.binary_var("x")
qp.binary_var("y")
qp.integer_var(lowerbound=0, upperbound=7, name="z")

qp.maximize(linear={"x": 3, "y": 2, "z": 1})
qp.linear_constraint(linear={"x": 1, "y": 1, "z": 1}, sense="LE", rhs=5.5, name="xyz_leq")
qp.linear_constraint(linear={"x": 1, "y": 1, "z": 1}, sense="GE", rhs=2.5, name="xyz_geq")
print(qp.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z

Subject to
  Linear constraints (2)
    x + y + z <= 5.5  'xyz_leq'
    x + y + z >= 2.5  'xyz_geq'

  Integer variables (1)
    0 <= z <= 7

  Binary variables (2)
    x y

Llama al método convert de InequalityToEquality para convertirlo.

[3]:

from qiskit_optimization.converters import InequalityToEquality

[4]:

ineq2eq = InequalityToEquality()
qp_eq = ineq2eq.convert(qp)
print(qp_eq.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack + y + z == 5  'xyz_leq'
    x - xyz_geq@int_slack + y + z == 3  'xyz_geq'

  Integer variables (3)
    0 <= z <= 7
    0 <= xyz_leq@int_slack <= 5
    0 <= xyz_geq@int_slack <= 6

  Binary variables (2)
    x y

Después de la conversión, la formulación del problema se parece al resultado anterior. Como podemos ver, las restricciones de desigualdad se reemplazan con restricciones de igualdad con variables de holgura (variables slack) enteras adicionales, \(xyz\_leg\text{@}int\_slack\) y \(xyz\_geq\text{@}int\_slack\).

Expliquemos cómo funciona la conversión. Por ejemplo, el límite inferior del lado izquierdo de la primera restricción es \(0\) que es el caso de \(x=0\), \(y=0\), y \(z=0\). Por lo tanto, el límite superior de la variable entera adicional debe ser \(5\) para poder satisfacer incluso el caso de \(x=0\), \(y=0\), y \(z=0\). Ten en cuenta que cortamos la parte después del punto decimal en la formulación convertida, ya que el lado izquierdo de la primera restricción en la formulación original puede ser solo valores enteros. Para la segunda restricción, básicamente aplicamos el mismo enfoque. Sin embargo, el símbolo en la segunda restricción es \(\geq\), por lo que agregamos un signo menos antes de \(xyz\_geq\text{@}int\_slack\) para poder satisfacer incluso el caso de \(x=1, y=1\), y \(z=7\).

Veamos cómo funciona el método interpret. El propósito de este método es convertir la solución del problema convertido a la del problema original. Para utilizar este método, primero necesitaríamos resolver el problema. Para los fines de este tutorial, usaremos docplex para resolverlo. Primero traduciremos el problema cuadrático a un modelo docplex.mp.

[5]:

from qiskit_optimization.algorithms import CplexOptimizer

cplex_optimizer = CplexOptimizer()

[6]:

result_orig = cplex_optimizer.solve(qp)
print(result_orig)

fval=8.0, x=1.0, y=1.0, z=3.0, status=SUCCESS

[7]:

result_eq = cplex_optimizer.solve(qp_eq)
print(result_eq)

fval=8.0, x=1.0, y=1.0, z=3.0, xyz_leq@int_slack=0.0, xyz_geq@int_slack=2.0, status=SUCCESS

El resultado result_eq de qp_eq tiene 5 valores variables (x=1.0, y=1.0, z=3.0, xyz_leq@int_slack=0.0, xyz_geq@int_slack=2.0) mientras que el resultado result_orig del qp original tiene tres valores (x=1.0, y=1.0, z=3.0). Podemos llamar al método InequalityToEquality.interpret pasando una lista o una matriz al método que tiene valores de qp_eq.variables de la siguiente manera. result_eq.x tiene la lista de valores que toma cada variable en la solución en correspondencia con su posición en la lista de variables qp_eq.variables.

[8]:

print("interpreting values of result_eq:", ineq2eq.interpret(result_eq.x))
print("values of result_orig:", result_orig.x)

interpreting values of result_eq: [1. 1. 3.]
values of result_orig: [1. 1. 3.]

Notamos que \([1., 1., 3.]\) son los valores tomados en la solución del problema convertido para las variables comunes entre los problemas convertidos y originales (variables: \(x\), \(y\), \(z\)). El método de interpretación muestra que los mismos valores son la solución del problema original. Esto se debe a que la función objetivo para los problemas originales y convertidos es exactamente la misma. Las variables de holgura (slack) solo garantizan la igualdad en las restricciones del problema convertido, donde las restricciones también son exactamente iguales entre los problemas original y convertido, excepto que el problema original tiene restricciones de desigualdad.

IntegerToBinary#

IntegerToBinary convierte variables enteras en variables binarias y coeficientes para eliminar las variables enteras del QuadraticProgram. Para convertir, se usa la codificación de coeficiente acotado propuesta en arxiv:1706.01945 (Eq. (5)). Para obtener más detalles sobre el método de codificación, consulta el documento dado.

Usamos el resultado de InequalityToEquality como punto de partida. Las variables \(x\) e \(y\) son variables binarias, mientras que la variable \(z\) y las variables de holgura \(xyz\_leq\text{@}int\_slack\) y \(xyz\_geq\text{@}int\_slack\) son variables enteras. Imprimimos el problema nuevamente como referencia.

[9]:

print(qp_eq.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack + y + z == 5  'xyz_leq'
    x - xyz_geq@int_slack + y + z == 3  'xyz_geq'

  Integer variables (3)
    0 <= z <= 7
    0 <= xyz_leq@int_slack <= 5
    0 <= xyz_geq@int_slack <= 6

  Binary variables (2)
    x y

Llama al método convert de IntegerToBinary para convertirlo.

[10]:

from qiskit_optimization.converters import IntegerToBinary

[11]:

int2bin = IntegerToBinary()
qp_eq_bin = int2bin.convert(qp_eq)
print(qp_eq_bin.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z@0 + 2*z@1 + 4*z@2

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack@0 + 2*xyz_leq@int_slack@1 + 2*xyz_leq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 5  'xyz_leq'
    x - xyz_geq@int_slack@0 - 2*xyz_geq@int_slack@1 - 3*xyz_geq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 3  'xyz_geq'

  Binary variables (11)
    x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
    xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2

Después de la conversión, la variable entera \(z\) se reemplaza con tres variables binarias \(z\text{@}0\), \(z\text{@}1\) y \(z\text{@}2\) con los coeficientes 1, 2 y 4, respectivamente, como los anteriores. Las variables de holgura \(xyz\_leq\text{@}int\_slack\) y \(xyz\_geq\text{@}int\_slack\) que fueron introducidas por InequalityToEquality también se reemplazan por tres variables binarias con los coeficientes 1, 2, 2 y 1, 2, 3, respectivamente.

Nota: En esencia, los coeficientes significan que la suma de estas variables binarias con coeficientes puede ser la suma de un subconjunto de \(\{1, 2, 4\}\), \(\{1, 2, 2\}\), y \(\{1, 2, 3\}\) para representar los valores aceptables \(\{0, \ldots, 7\}\), \(\{0, \ldots, 5\}\), y \(\{0, \ldots, 6\}\), que respeta correctamente el límite inferior y el límite superior de las variables enteras originales.

IntegerToBinary también provee el método interpret que es la funcionalidad para traducir un resultado binario dado de nuevo a la representación original. Veamos cómo funciona el método interpret.

[12]:

result_eq = cplex_optimizer.solve(qp_eq)
print(result_eq)

fval=8.0, x=1.0, y=1.0, z=3.0, xyz_leq@int_slack=0.0, xyz_geq@int_slack=2.0, status=SUCCESS

[13]:

result_eq_bin = cplex_optimizer.solve(qp_eq_bin)
print(result_eq_bin)

fval=8.0, x=1.0, y=1.0, z@0=1.0, z@1=1.0, z@2=0.0, xyz_leq@int_slack@0=0.0, xyz_leq@int_slack@1=0.0, xyz_leq@int_slack@2=0.0, xyz_geq@int_slack@0=0.0, xyz_geq@int_slack@1=1.0, xyz_geq@int_slack@2=0.0, status=SUCCESS

result_eq_bin tiene más variables binarias debido a la conversión mediante IntegerToBinary.convert. IntegerToBinary.interpret los traduce nuevamente a valores enteros agregando valores de variables binarias asociadas con las variables enteras originales de qp_eq.

[14]:

print("interpreting values of result_eq_bin:", int2bin.interpret(result_eq_bin.x))
print("values of result_eq:", result_eq.x)

interpreting values of result_eq_bin: [1. 1. 3. 0. 2.]
values of result_eq: [1. 1. 3. 0. 2.]

LineEqualityToPenalty#

LineeEqualityToPenalty convierte las restricciones de igualdad lineal en términos de penalización cuadráticos adicionales de la función objetivo para mapear el QuadraticProgram a una forma sin restricciones. Una entrada al convertidor tiene que ser un QuadraticProgram con sólo restricciones lineales de igualdad. Estas restricciones de igualdad, por ejemplo, \(\sum_i a_i x_i = b\) donde \(a_i\) y \(b\) son números y \(x_i\) es una variable, se agregará a la función objetivo en la forma de \(M(b - \sum_i a_i x_i)^2\) donde \(M\) es un número grande como factor de penalización. Por defecto, \(M= 1e5\). El signo del término depende de si el tipo de problema es de maximización o minimización.

Utilizamos la salida de IntegerToBinary como punto de partida, donde todas las variables son variables binarias y todas las restricciones de desigualdad se han mapeado con restricciones de igualdad. Volvemos a imprimir el problema como referencia.

[15]:

print(qp_eq_bin.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z@0 + 2*z@1 + 4*z@2

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack@0 + 2*xyz_leq@int_slack@1 + 2*xyz_leq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 5  'xyz_leq'
    x - xyz_geq@int_slack@0 - 2*xyz_geq@int_slack@1 - 3*xyz_geq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 3  'xyz_geq'

  Binary variables (11)
    x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
    xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2

Llama al método convert de LinearEqualityToPenalty para convertirlo.

[16]:

from qiskit_optimization.converters import LinearEqualityToPenalty

[17]:

lineq2penalty = LinearEqualityToPenalty()
qubo = lineq2penalty.convert(qp_eq_bin)
print(qubo.prettyprint())

Problem name:

Maximize
  -26*x^2 + 26*x*xyz_geq@int_slack@0 + 52*x*xyz_geq@int_slack@1
  + 78*x*xyz_geq@int_slack@2 - 26*x*xyz_leq@int_slack@0
  - 52*x*xyz_leq@int_slack@1 - 52*x*xyz_leq@int_slack@2 - 52*x*y - 52*x*z@0
  - 104*x*z@1 - 208*x*z@2 - 13*xyz_geq@int_slack@0^2
  - 52*xyz_geq@int_slack@0*xyz_geq@int_slack@1
  - 78*xyz_geq@int_slack@0*xyz_geq@int_slack@2 - 52*xyz_geq@int_slack@1^2
  - 156*xyz_geq@int_slack@1*xyz_geq@int_slack@2 - 117*xyz_geq@int_slack@2^2
  - 13*xyz_leq@int_slack@0^2 - 52*xyz_leq@int_slack@0*xyz_leq@int_slack@1
  - 52*xyz_leq@int_slack@0*xyz_leq@int_slack@2 - 52*xyz_leq@int_slack@1^2
  - 104*xyz_leq@int_slack@1*xyz_leq@int_slack@2 - 52*xyz_leq@int_slack@2^2
  + 26*y*xyz_geq@int_slack@0 + 52*y*xyz_geq@int_slack@1
  + 78*y*xyz_geq@int_slack@2 - 26*y*xyz_leq@int_slack@0
  - 52*y*xyz_leq@int_slack@1 - 52*y*xyz_leq@int_slack@2 - 26*y^2 - 52*y*z@0
  - 104*y*z@1 - 208*y*z@2 + 26*z@0*xyz_geq@int_slack@0
  + 52*z@0*xyz_geq@int_slack@1 + 78*z@0*xyz_geq@int_slack@2
  - 26*z@0*xyz_leq@int_slack@0 - 52*z@0*xyz_leq@int_slack@1
  - 52*z@0*xyz_leq@int_slack@2 - 26*z@0^2 - 104*z@0*z@1 - 208*z@0*z@2
  + 52*z@1*xyz_geq@int_slack@0 + 104*z@1*xyz_geq@int_slack@1
  + 156*z@1*xyz_geq@int_slack@2 - 52*z@1*xyz_leq@int_slack@0
  - 104*z@1*xyz_leq@int_slack@1 - 104*z@1*xyz_leq@int_slack@2 - 104*z@1^2
  - 416*z@1*z@2 + 104*z@2*xyz_geq@int_slack@0 + 208*z@2*xyz_geq@int_slack@1
  + 312*z@2*xyz_geq@int_slack@2 - 104*z@2*xyz_leq@int_slack@0
  - 208*z@2*xyz_leq@int_slack@1 - 208*z@2*xyz_leq@int_slack@2 - 416*z@2^2
  + 211*x - 78*xyz_geq@int_slack@0 - 156*xyz_geq@int_slack@1
  - 234*xyz_geq@int_slack@2 + 130*xyz_leq@int_slack@0 + 260*xyz_leq@int_slack@1
  + 260*xyz_leq@int_slack@2 + 210*y + 209*z@0 + 418*z@1 + 836*z@2 - 442

Subject to
  No constraints

  Binary variables (11)
    x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
    xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2

Después de la conversión, las restricciones de igualdad se añaden a la función objetivo como términos adicionales con el factor de penalización predeterminado provisto por Qiskit Optimization. El problema resultante es ahora un QUBO y es compatible con muchos algoritmos de optimización cuántica como VQE, QAOA y otros.

Esto da el mismo resultado que antes.

Como hicimos con los otros convertidores, veamos cómo funciona el método interpret en este caso.

[18]:

result_eq_bin = cplex_optimizer.solve(qp_eq_bin)
print(result_eq_bin)

fval=8.0, x=1.0, y=1.0, z@0=1.0, z@1=1.0, z@2=0.0, xyz_leq@int_slack@0=0.0, xyz_leq@int_slack@1=0.0, xyz_leq@int_slack@2=0.0, xyz_geq@int_slack@0=0.0, xyz_geq@int_slack@1=1.0, xyz_geq@int_slack@2=0.0, status=SUCCESS

[19]:

result_qubo = cplex_optimizer.solve(qubo)
print(result_qubo)

fval=8.0, x=1.0, y=1.0, z@0=1.0, z@1=1.0, z@2=0.0, xyz_leq@int_slack@0=0.0, xyz_leq@int_slack@1=0.0, xyz_leq@int_slack@2=0.0, xyz_geq@int_slack@0=0.0, xyz_geq@int_slack@1=1.0, xyz_geq@int_slack@2=0.0, status=SUCCESS

[20]:

print("interpreting values of result_eq_bin:", lineq2penalty.interpret(result_qubo.x))
print("values of result_eq_bin:", result_eq_bin.x)

interpreting values of result_eq_bin: [1. 1. 1. 1. 0. 0. 0. 0. 0. 1. 0.]
values of result_eq_bin: [1. 1. 1. 1. 0. 0. 0. 0. 0. 1. 0.]

Podemos ver que el resultado del método interpret implica que tanto el problema original como el convertido tienen exactamente la misma solución. Esto es de esperarse porque el problema convertido tiene exactamente las mismas variables que el problema original, el objetivo se ha modificado de tal manera que ya no tenemos las restricciones en el problema convertido.

Finalmente, veamos cómo interpretamos el resultado de QUBO hasta la solución del problema original qp. El siguiente código muestra que los valores interpretados son equivalentes al resultado del problema original qp.

[21]:

print("result_orig.x", result_orig.x)

x = result_qubo.x
for conv in [lineq2penalty, int2bin, ineq2eq]:
    x = conv.interpret(x)
print("interpreting result_qubo.x", x)

result_orig.x [1. 1. 3.]
interpreting result_qubo.x [1. 1. 3.]

[22]:

import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

SoftwareVersion
qiskit0.44.1
qiskit-terra0.45.0.dev0+dcec79e
qiskit_optimization0.6.0
qiskit_algorithms0.3.0
System information
Python version3.10.13
Python compilerClang 14.0.3 (clang-1403.0.22.14.1)
Python buildmain, Aug 24 2023 22:36:46
OSDarwin
CPUs10
Memory (Gb)64.0
Thu Sep 07 12:33:31 2023 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2023.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.

[ ]: