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 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 usa el módulo qiskit.opflow, 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 ofrece una variedad de convertidores. En este tutorial proporcionamos una descripción general de esta funcionalidad. Actualmente, Qiskit 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 incluyeInequalityToEquality,IntegerToBinary,LinearEqualityToPenalty,LinearInequalityToPenaltyyMaximizeToMinimizepor 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
[2]:
qp = QuadraticProgram()
qp.binary_var("x")
qp.binary_var("y")
qp.integer_var(lowerbound=0, upperbound=7, name="z")
qp.maximize(linear={"x": 2, "y": 1, "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
2*x + 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
2*x + y + z
Subject to
Linear constraints (2)
x + [email protected]_slack + y + z == 5 'xyz_leq'
x - [email protected]_slack + y + z == 3 'xyz_geq'
Integer variables (3)
0 <= z <= 7
0 <= [email protected]_slack <= 5
0 <= [email protected]_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\).
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.
[5]:
print(qp_eq.prettyprint())
Problem name:
Maximize
2*x + y + z
Subject to
Linear constraints (2)
x + [email protected]_slack + y + z == 5 'xyz_leq'
x - [email protected]_slack + y + z == 3 'xyz_geq'
Integer variables (3)
0 <= z <= 7
0 <= [email protected]_slack <= 5
0 <= [email protected]_slack <= 6
Binary variables (2)
x y
Llama al método convert de IntegerToBinary para convertirlo.
[6]:
from qiskit_optimization.converters import IntegerToBinary
[7]:
int2bin = IntegerToBinary()
qp_eq_bin = int2bin.convert(qp_eq)
print(qp_eq_bin.prettyprint())
Problem name:
Maximize
2*x + y + [email protected] + 2*[email protected] + 4*[email protected]
Subject to
Linear constraints (2)
x + [email protected][email protected] + 2*[email protected][email protected] + 2*[email protected][email protected] + y
+ [email protected] + 2*[email protected] + 4*[email protected] == 5 'xyz_leq'
x - [email protected][email protected] - 2*[email protected][email protected] - 3*[email protected][email protected] + y
+ [email protected] + 2*[email protected] + 4*[email protected] == 3 'xyz_geq'
Binary variables (11)
x y [email protected] [email protected] [email protected] [email protected][email protected] [email protected][email protected] [email protected][email protected]
[email protected][email protected] [email protected][email protected] [email protected][email protected]
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.
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.
[8]:
print(qp_eq_bin.prettyprint())
Problem name:
Maximize
2*x + y + [email protected] + 2*[email protected] + 4*[email protected]
Subject to
Linear constraints (2)
x + [email protected][email protected] + 2*[email protected][email protected] + 2*[email protected][email protected] + y
+ [email protected] + 2*[email protected] + 4*[email protected] == 5 'xyz_leq'
x - [email protected][email protected] - 2*[email protected][email protected] - 3*[email protected][email protected] + y
+ [email protected] + 2*[email protected] + 4*[email protected] == 3 'xyz_geq'
Binary variables (11)
x y [email protected] [email protected] [email protected] [email protected][email protected] [email protected][email protected] [email protected][email protected]
[email protected][email protected] [email protected][email protected] [email protected][email protected]
Llama al método convert de LinearEqualityToPenalty para convertirlo.
[9]:
from qiskit_optimization.converters import LinearEqualityToPenalty
[10]:
lineq2penalty = LinearEqualityToPenalty()
qubo = lineq2penalty.convert(qp_eq_bin)
print(qubo.prettyprint())
Problem name:
Maximize
-22*x^2 + 22*x*[email protected][email protected] + 44*x*[email protected][email protected]
+ 66*x*[email protected][email protected] - 22*x*[email protected][email protected]
- 44*x*[email protected][email protected] - 44*x*[email protected][email protected] - 44*x*y - 44*x*[email protected]
- 88*x*[email protected] - 176*x*[email protected] - 11*[email protected][email protected]^2
- 44*[email protected][email protected]*[email protected][email protected]
- 66*[email protected][email protected]*[email protected][email protected] - 44*[email protected][email protected]^2
- 132*[email protected][email protected]*[email protected][email protected] - 99*[email protected][email protected]^2
- 11*[email protected][email protected]^2 - 44*[email protected][email protected]*[email protected][email protected]
- 44*[email protected][email protected]*[email protected][email protected] - 44*[email protected][email protected]^2
- 88*[email protected][email protected]*[email protected][email protected] - 44*[email protected][email protected]^2
+ 22*y*[email protected][email protected] + 44*y*[email protected][email protected]
+ 66*y*[email protected][email protected] - 22*y*[email protected][email protected]
- 44*y*[email protected][email protected] - 44*y*[email protected][email protected] - 22*y^2 - 44*y*[email protected]
- 88*y*[email protected] - 176*y*[email protected] + 22*[email protected]*[email protected][email protected]
+ 44*[email protected]*[email protected][email protected] + 66*[email protected]*[email protected][email protected]
- 22*[email protected]*[email protected][email protected] - 44*[email protected]*[email protected][email protected]
- 44*[email protected]*[email protected][email protected] - 22*[email protected]^2 - 88*[email protected]*[email protected] - 176*[email protected]*[email protected]
+ 44*[email protected]*[email protected][email protected] + 88*[email protected]*[email protected][email protected]
+ 132*[email protected]*[email protected][email protected] - 44*[email protected]*[email protected][email protected]
- 88*[email protected]*[email protected][email protected] - 88*[email protected]*[email protected][email protected] - 88*[email protected]^2
- 352*[email protected]*[email protected] + 88*[email protected]*[email protected][email protected] + 176*[email protected]*[email protected][email protected]
+ 264*[email protected]*[email protected][email protected] - 88*[email protected]*[email protected][email protected]
- 176*[email protected]*[email protected][email protected] - 176*[email protected]*[email protected][email protected] - 352*[email protected]^2
+ 178*x - 66*[email protected][email protected] - 132*[email protected][email protected]
- 198*[email protected][email protected] + 110*[email protected][email protected] + 220*[email protected][email protected]
+ 220*[email protected][email protected] + 177*y + 177*[email protected] + 354*[email protected] + 708*[email protected] - 374
Subject to
No constraints
Binary variables (11)
x y [email protected] [email protected] [email protected] [email protected][email protected] [email protected][email protected] [email protected][email protected]
[email protected][email protected] [email protected][email protected] [email protected][email protected]
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 por defecto \(M=1e5\). 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.
[11]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
Version Information
| Qiskit Software | Version |
|---|---|
qiskit-terra | 0.21.0.dev0+dbd3961 |
qiskit-aer | 0.10.4 |
qiskit-ibmq-provider | 0.19.1 |
qiskit-optimization | 0.4.0 |
| System information | |
| Python version | 3.10.4 |
| Python compiler | GCC 11.2.0 |
| Python build | main, Apr 2 2022 09:04:19 |
| OS | Linux |
| CPUs | 4 |
| Memory (Gb) | 14.577545166015625 |
| Wed May 18 16:03:30 2022 JST | |
This code is a part of Qiskit
© Copyright IBM 2017, 2022.
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.
[ ]: