Computación Cuántica Adiabática aplicada a la solución del Problema de la Mochila Binaria

Abstract

Adiabatic Quantum Computing applied to the solution of the Binary Knapsack Problem Abstract: The problems humanity faces are day by day ever more complex and the tools provided by classical computing are beginning to be insufficient to solve certain of these, such as optimization problems in which the search space grows exponentially. [...]a comparison is presented of the quantum algorithm obtained with a classic simulated annealing version. The results show the effectiveness of the quantum algorithm and the slight superiority it offers compared to its classical counterpart. Keywords: Quantum computing; Knapsack problem; Adiabatic quantum computing; Ising model; Optimization problems.

Headnote

Pages: 214-227

Resumen: Día a día los problemas que enfrenta la humanidad son más complejos, y las herramientas que nos brinda la computación clásica empiezan a ser insuficientes para resolverlos, como por ejemplo los problemas de optimización donde el espacio de búsqueda crece exponencialmente. En este contexto, la computación cuántica ha empezado a mostrar su dominio y en los últimos años empresas como IBM empiezan a ofertar servicios de cómputo cuántico para tareas de optimización y análisis de datos. Este artículo presenta y detalla los pasos seguidos para construir una solución al problema de la mochila binaria utilizando un algoritmo de Computación Cuántica Adiabática haciendo uso de las librerías de Qiskit y su implementación en Python. Por último, presenta una comparación del algoritmo cuántico obtenido con una versión clásica de recocido simulado. Los resultados obtenidos muestran la efectividad del algoritmo cuántico y una leve superioridad frente a su contraparte clásica.

Palabras-clave: Computación cuántica; Problema de la mochila; Computación cuántica adiabática; Modelo de Ising; Problemas de optimización.

Adiabatic Quantum Computing applied to the solution of the Binary Knapsack Problem

Abstract: The problems humanity faces are day by day ever more complex and the tools provided by classical computing are beginning to be insufficient to solve certain of these, such as optimization problems in which the search space grows exponentially. Quantum computing has begun to show its dominance in this realm and in recent years companies like IBM have begun to offer quantum computing services for data analysis and optimization tasks. This paper presents and details the steps followed to build a solution to the binary knapsack problem using an Adiabatic Quantum Computing algorithm making use of the Qiskit libraries, and their implementation in Python. Finally, a comparison is presented of the quantum algorithm obtained with a classic simulated annealing version. The results show the effectiveness of the quantum algorithm and the slight superiority it offers compared to its classical counterpart.

Keywords: Quantum computing; Knapsack problem; Adiabatic quantum computing; Ising model; Optimization problems.

(ProQuest: ... denotes formulae omitted.)

1.Introducción

El problema de la mochila es un conocido problema de optimización combinatoria que pertenece a la clase de problemas NP-completos (Karp, 2010). Existen diferentes variantes de este problema que se utilizan como guía para resolver una gran variedad de problemas, entre ellos, problemas de empaque y reducción de existencias, toma de decisiones financieras, titulización respaldada por activos, subastas combinatorias (Coffey, 2017), control de presupuestos, toma de decisiones y corte de material (H. Wang, Ma, Zhang, & Li, 2009).

Entre las variantes más conocidas del problema de la mochila se encuentran: la mochila binaria (Binary Knapsack Problem, BKP), el problema de la suma de subconjuntos (Pi = Wi), el problema de la mochila sin límite, el problema de la mochila acotada (Martello & Toth, 1987), el problema de la mochila d-dimensional (d-KP), el problema de las múltiples mochilas (MKP) (Gurski, Rehs, & Rethmann, 2019), el problema de la mochila de elección múltiple multidimensional y el problema de la mochila cuadrática (Assi & Haraty, 2019). A la fecha se han desarrollado una variedad de técnicas para resolver estas variantes, las cuales se pueden agrupar de la siguiente manera: (i) exactos, (ii) programación dinámica, (iii) programación entera, (iv) métodos metaheurísticos, (v) métodos lagrangianos, (vi) métodos basados en árboles de búsqueda con back tracking y (vii) enfoques de red (Salkin & de Kluyver, 1975).

El problema de la mochila binaria se define formalmente en la Ecuación (1), y se describe así: dada una mochila con una capacidad limitada C e Z+, y un conjunto de n elementos (artículos), cada uno con un beneficio P. e Z y un peso W. e Z (i = 1, 2, ..., n), se debe seleccionar un subconjunto de m elementos (m < tt) de modo que se genere la mayor (máxima) ganancia o beneficio posible sujeto a una restricción principal, que los pesos totales de los elementos seleccionados no excedan la capacidad C de la mochila (H. Wang et al., 2009). En este artículo se trabajará el problema de la mochila binaria, donde x¡ es un valor binario {0,1} que indica si el elemento i debe ir o no en la mochila.

... (1)

La dimensión del problema se puede definir de acuerdo con el número n de artículos y en la literatura se puede encontrar como pequeñas si n < 100, medianas si 100 < n < 1000, o grandes si n > 1000, aunque esta definición no es del todo aceptada, ya que otros autores la definen como pequeñas si n < 20, medianas si n < 200 y grandes si n > 200 (Blado & Toriello, 2019). Una forma más aceptada de clasificación se hace basado en la complejidad de las instancias, esto es, la relación o no de los pesos de cada ítem con su ganancia, y se definen como: instancias No correlacionadas, débilmente correlacionadas, casi fuertemente correlacionadas, fuertemente correlacionadas, Inversa y fuertemente & Srinivas, 2016; H. Wang et al., 2009). Además recientemente se trata con algoritmos cuánticos

como el algoritmo evolucionario cuántico (Li & Li, 2019), el algoritmo genético cuántico (R. Wang, Guo, Xiang, & Mao, 2012) y el algoritmo cuántico Variational Quantum Eigensolver (VQE) (Bolos, 2019). La computación cuántica nace como una alternativa al paradigma computacional clásico basado en máquinas de Turing y de Von Neumann, la cual ha demostrado su superioridad ante la computación clásica para algunos problemas específicos (Albash & Lidar, 2018; Nielsen & Chuang, 2010). Con este nuevo paradigma se pueden estudiar problemas de alta complejidad que requieren gran cantidad de operaciones y manejan gran cantidad de variables, para esto, se hace uso de algunas propiedades de la física cuántica como el entrelazamiento cuántico o la superposición cuántica, con las cuales se pueden

realizar más operaciones en una misma unidad de tiempo disminuyendo radicalmente los tiempos de respuesta (Vega Fernández & Ramírez Celis, 2017). A la fecha se han definido algoritmos cuánticos eficientes para problemas discretos como la factorización entera, la simulación cuántica, la estimación del valor propio, la integración, la solución de ecuaciones diferenciales parciales y la solución a problemas numéricos de álgebra lineal (Hadfield, 2018), además la dificultad especial de resolver problemas de optimización ha generado mucha expectativa sobre la posibilidad de usar dispositivos cuánticos para resolverlos aproximadamente (menos tiempo con mejores soluciones). Un algoritmo que ha ido evolucionando mediante la combinación de metaheurísticas y conceptos cuánticos particularmente destacado es el algoritmo

de Computación Cuántica Adiabática (Adiabatic Quantum Computing, AQC) (Hadfield, 2018), el cual utiliza un enfoque equivalente al modelo de circuito de computación cuántica, adecuado para problemas de optimización combinatoria, incluyendo particiones, coberturas, particionado de árboles y grafos. Una búsqueda en la literatura reveló que existen pocos artículos publicados sobre algoritmos cuánticos que se apliquen al problema de la mochila binaria, debido a esto, el propósito de este documento es detallar los pasos a seguir para solucionar problemas de optimización mediante computación cuántica a través del enfoque AQC, solucionando el problema de la mochila binaria mapeándolo a un modelo de Ising y realizando su implementación en el lenguaje de programación Python, haciendo uso de la librería Qiskit Aqua. Se utiliza específicamente el algoritmo VQE desarrollado por el equipo

de IBM para solucionar problemas cuánticos. Los aportes principales del presente documento son: 1) detallar la forma como se aborda un problema de optimización mediante el enfoque AQC, 2) dar a conocer el funcionamiento de un algoritmo adiabático cuántico aplicado al problema de la mochila Computación Cuántica Adiabática aplicada a la solución del Problema de la Mochila Binaria correlacionadas, e instancias con pesos y beneficios iguales (subconjuntos de instancias de suma) (Pisinger, 2005). Debido a la importancia y el reto que representa el problema de la mochila binaria, en los últimos años se han reportado un

gran número de algoritmos que buscan su solución, estos se agrupan en: exactos, de programación dinámica, basados en back-tracking (incluidos ramificación y poda), y metaheurísticos. Entre los algoritmos metaheurísticos más destacados se encuentran los algoritmos genéticos, el recocido simulado, binaria, y 3) comparar los resultados obtenidos frente a una implementáción clásica de recocido simulado en instancias de baja complejidad (n < 20).

A continuación, en la sección 2 se introducen algunos conceptos básicos de computación cuántica. En la sección 3, se presenta la solución del problema de la mochila binaria realizada con el enfoque AQC. Luego, en la sección 4 se describe brevemente la experimentación y los resultados obtenidos junto con la comparación de dichos resultados frente a un recocido simulado clásico. Finalmente, en la sección 5 se presentan las conclusiones del trabajo realizado y el trabajo futuro que el grupo de investigación espera desarrollar en el futuro cercano.

2.Conceptos Cuánticos aplicados al problema de la mochila

2.1.Computación Cuántica

La computación cuántica es un nuevo paradigma de computación que surgió como resultado de la fusión de la informática y la mecánica cuántica. El origen de la computación cuántica se remonta a principios de los 80's cuando Richard Feynman observó que algunos efectos de la mecánica cuántica no se pueden simular de manera eficiente en una computadora clásica. Durante la última década, la computación cuántica ha atraído un interés generalizado y ha inducido intensivas investigaciones, ya que ha demostrado su superioridad en ciertos tipos de algoritmos a su contraparte clásica, en especial destaca su paralelismo innato que reduce la complejidad algorítmica. Tal capacidad de procesamiento en paralelo se puede utilizar para resolver problemas de optimización combinatoria que requieren la exploración de grandes espacios de soluciones (Layeb, 2011).

Qubit: Un bit cuántico (Quantum bit) es la unidad de información más pequeña almacenada en una computadora cuántica de dos estados (Hey, 1999). Al contrario del bit clásico el cual tiene dos valores posibles, "0" o "1", un qubit puede estar en el estado "1", en el estado "0" o en cualquier superposición de los dos. El estado de un qubit se puede representar mediante la notación de corchetes (Bra-Ket) presentada en la Ecuación (2).

... (2)

Donde T> denota más de un vector T aen algún espacio vectorial y representa una superposición lineal de la partícula dados los vectores de estado cuántico individuales. 0} y 11} representan los valores de bit clásicos o y 1 respectivamente, a y P son números complejos tales que a|: + |ß|: = 1, los cuales especifican las amplitudes de probabilidad de los estados correspondientes. Cuando se mide el estado del qubit, se puede obtener cero con una probabilidad al: o uno con una probabilidad Ißl:; Esta medición se realiza al observar el estado cuántico de un qubit, momento en el que colapsa a un solo estado, cero (0) o uno (1) (Narayanan, 1999).

Entre los algoritmos cuánticos más famosos se encuentran el algoritmo de Shore's (Shor, 1994) utilizado para factorización numérica y el algoritmo de Grover's (Grover, 1996) utilizado para búsquedas en una base de datos no ordenada. Ambos algoritmos redujeron la complejidad de la solución al problema (Laboudi & Chikhi, 2012). Un sistema de n-qubits puede representar 2" estados al mismo tiempo. Este crecimiento exponencial del espacio de estado con el número de qubits es lo que sugiere una aceleración exponencial de la computación en las computadoras cuánticas sobre las computadoras tradicionales.

2.2.Computación Cuántica Adiabática (AQC)

La computación cuántica adiabática (Adiabatic Quantum Computation, AQC) es un enfoque equivalente al modelo de circuito de computación cuántica, adecuado para problemas del tipo de optimización combinatoria, incluyendo particiones, coberturas y particionado de árboles y grafos (Coffey, 2017).

Debido a sus inicios, la AQC puede considerarse como una clase particular de Recocido cuántico (Quantum Annealing, QA), la cual utiliza los principios de la mecánica cuántica para resolver problemas de optimización sin restricciones (Albash & Lidar, 2018). Desde la propuesta inicial de QA, ha habido mucho interés en la búsqueda de problemas prácticos donde pueda ser ventajoso con respecto a los algoritmos clásicos, particularmente el recocido simulado (Simulating annealing, SA). Muchos de estos enfoques transforman un problema computacional en un problema donde se debe encontrar el estado fundamental de un modelo de Ising Spin Glass (ISG) cuántico, el cual, en el peor de los casos es NP-completo (Cao, Jiang, Perouli, & Kais, 2016).

El modelo Ising (Una clase conveniente, restringida y ciertamente no universal de hamiltonianos) tiene la versatilidad de codificar eficientemente muchos problemas NP y ha motivado la realización física de QA. En general las computadoras cuánticas universales no pueden resolver problemas NP-hard de manera eficiente, pero se ha encontrado evidencia en los sistemas experimentales de Ising cuántico que sugieren una aceleración cuántica sobre la computación clásica debido al efecto del túnel cuántico1 (Cao et al., 2016).

Optimización Cuántica Adiabática: En un modelo de circuito de computación cuántica, un cálculo puede evolucionar en todo el espacio de Hilbert2 y está codificado en una serie de puertas de lógica cuántica unitarias (Albash & Lidar, 2018). Por otro lado, en un modelo AQC el cálculo se realiza mediante un Hamiltoniano inicial (¾), cuyo estado fundamental codifica la solución a un problema de interés, y otro hamiltoniano (?), cuyo estado fundamental es trivial. Entonces, si se prepara un sistema cuántico para estar en el estado fundamental de ? y luego se cambia adiabáticamente el hamiltoniano por un tiempo T de acuerdo con la Ecuación (3) y T es lo suficientemente grande, al final, el estado cuántico en T devolverá una solución al problema de interés (Albash & Lidar, 2018)(Lucas, 2014)(Cao et al., 2016).

... (3)

Donde s e [o, i], es un parámetro de tiempo considerado como una función dependiente del tiempo s(t) = f para un tiempo total de evolución T (en general se puede considerar cualquier función que satisfaga s(o)=o y s(t)=t), yfí(y Hn no conmutan3. Con esta definición y debido al teorema adiabático de la mecánica cuántica el sistema cuántico permanecerá en el estado fundamental todo el tiempo.

2.3.Modelo Ising

Uno de los modelos más utilizados en física se llama el modelo Ising. Propuesto entre 1920 У 1930 por Ernst Ising y Wilhelm Lenz como una forma de entender el funcionamiento de los materiales magnéticos. El enfoque modela un material magnético como una colección de moléculas, cada una de las cuales tiene un espín que puede alinearse o alinearse con campo magnético aplicado h¡, y que interactúan entre sí con base en un campo de interacción (Brush, 1967).

En la Ecuación (4) se representa el modelo clásico de Ising, el cual se puede escribir como una función cuadrática de un conjunto de n giros, donde si e {-1, +1} representa el spin de la i-ésima partícula.

... (4)

La Ecuación (5) representa un FUmiltoniano (H0) como la versión cuántica del modelo Ising, donde q se reemplaza por cr. en la Ecuación (4).

... (5)

... es una matnZ ? Pauli4 que actúa sobre el i-ésimospin en un espacio de Hilbert de N qubits ( -f } , donde I es una matriz identidad de 2 x 2 y ?, Ja Î R son coeficientes (Lucas, 20t4)(Cao et al., 2016). ? es la fuerza del campo aplicado sobre el i-ésimo spin y /N- actúa como el campo de interacción entre los spines vecinos i, j (Bian, Chudák, Macready, & Rose, 2010). Un estado fundamental Hc. es una superposición de todos los estados posibles en la base propia de ? (Lucas, 2014) donde cr. es la puerta NOT sobre el i-ésimo qubit (Coffey, 2017).

3.Solución cuántica al problema de la mochila binaria

En esta sección se presentan dos modelos Ising para solucionar el problema de la mochila (Lucas, 2014). Los dos modelos se explican en (Lucas, 2014), el segundo además se detalla en (Coffey, 2017) y su hamiltoniano cuántico se implementa en (Bolos, 2019).

3.1. Solución con (n + C) qubits

Teniendo en cuenta la definición del problema de la mochila propuesta en la Ecuación (1) y trabajando con la versión binaria de esta, se tienen n variables ·¡ donde 1 <i< n, las cuales denotan valores binarios que se fijan con uno (1) si un determinado elemento debe ir en la mochila o cero (o) en caso contrario, y j variables y, donde 1 <j < C que denotan una variable binaria la cual es 1 si el peso de la mochila es j, o cero (o) en caso contrario. La cantidad de qubits requerida para modelar la solución es (n + C) -> [·1.*** Jfc].

La solución al problema consiste en construir un modelo de Ising H = ? + HB, con ? como el término que controla el cumplimiento o no de la restricción del problema, cómo se define en la Ecuación (6).

... (6)

Con ? se obliga a que el peso solo pueda tomar un valor y que el peso de los objetos en la mochila sea igual al valor que se desea. Por ejemplo, si una solución da un valor igual a 10 para la variable peso, solo ? = 1, el resto de ? = 0 para los otros valores de k. Si la capacidad de la mochila (C) fuese de 20, esta solución es factible y en ese caso ? sería igual а 4(1 -l}: + .4(10 - 10J2 = 0, eliminando así a ?. Pero si C tuviera u valor igual a 8, esta solución no sería factible y en este caso ? sería igual а 4(1 - 0): -f 4(0 - 10): = 1014 haciendo que el valor de ? sea grande (positivo, alejando la solución del mínimo), y entre más se supere el peso máximo de la mochila, mayor será el valor de ?. Finalmente se tiene HB en la Ecuación (7).

... (7)

El término ? sirve para maximizar el beneficio (a mayor beneficio más se acerca al optimo o mínimo del Hamiltoniano) y el término ? asegura que se cumpla la restricción de peso total. Debido a que se requiere que no sea posible encontrar una solución donde ? no se cumpla a expensas de que ? se vuelva más negativo, se requiere fijar la condición: o < В · Max (fi) < A. El número de qubits requeridos para esta formulación es de n + C, número de artículos más capacidad (Lucas, 2014).

3.2. Solución con (n + Llog2 C_l + 1) qubits

Realizando una modificación a la solución planteada anteriormente, la cual requiere (n + C) qubits, se desea reducir drásticamente la cantidad de giros y, adicionales que deben agregarse. Así, codificando la magnitud del peso máximo (C) como un valor binario, se define una variable entera M tal que < C < 2M+L, con M = Üog, Cj; De esta manera solo se necesitan (M+t) variables binarias: [>? ... ?], en lugar de C variables binarias: [yL ... ? ], para codificar una variable que puede tomar C valores (C >> M).

Aplicando la nueva configuración, para resolver el problema de la mochila, se requieren (n+Llog; Cj+i) qubits (Lucas, 20Г4). En la Ecuación (8) se presenta ? construido de acuerdo a la nueva representación de y, (Coffey, 20Г7).

... (8)

Si se tiene una solución con un peso de 10 y una capacidad máxima C = 20, entonces la cantidad de qubits requeridos para representar el peso de la solución es M=Llog;20j+r=5, por lo tanto se tiene el vector y - [01Ū 10] = ro, que corresponde a la representación de to en binario de izquierda a derecha; Así, se cumple la condición ró < C = 20 < 32. Esta solución es factible, por lo que ? = A (10 + (20 + 1 - 32)0 - 10): = 0, quedando eliminado ?. Por otro lado, si C = 9, se tendría el vector y =[010 1] = 10 соп#л = Л(Д + (9 + 1- 8)1 - 10)- = 36 А, que representa un valor alto de contrapeso ya que se supera la capacidad máxima permitida. Este valor crecerá entre más se rebase la capacidad de la mochila.

Este segundo hamiltoniano es el que se toma en el presente trabajo como solución del problema de la mochila binaria. En resumen, el Hamiltoniano H = ? + HB esta dado por la Ecuación (9), que utiliza una representación en base cero (o) para los vectores.

... (9)

Los diferentes valores implicados se representan de la siguiente manera (Bolos, 2019):

* La solución se representa como un vector Я = [xĒ... ·n_i] e {o, r} en donde cada elemento se representa en un índice del vector. Si el valor es r, entonces el elemento se almacena en la mochila y si es cero (o) el elemento queda fuera.

* Elpesodelasoluciónserepresentaenbinariodeizquierdaaderechacomounvector y = b'o ...?] e {o, t}.

* El valor del peso de los elementos se representa como un vector W= [IVD...

* El beneficio de los elementos se representa como un vector P = [P: .. Pn _ J.

* La variable C representa la capacidad de la mochila.

* La variable A representa un número lo suficientemente grande para dominar la multiplicación del valor B por la suma de los pesos de todos los elementos.

Para construir una función de costo C(ÜT) se debe tener en cuenta que se desea maximizar la Ecuación (t) mientras se cumple con su respectiva restricción (Bolos, 20Г9). De la definición de H, se tienen M+t nuevas variables binarias que se representarán en el vector y = [yD ... |fc], donde los elementos pueden tomar valores diferentes de cero simultáneamente (Coffey, 20Г7). La solución en la función de costo se representará en un vector К compuesto por los vectores X y Y, con К = [xr... -t'f]_i..yf] ... ? +.\j- J* En la Ecuación (ro) se presenta la función de costo C(K) definida por (Bolos, 20Г9) y su polinomio expandido.

... (10)

Se puede observar que para llevar el primer término de la Ecuación (10) a cero, se debe cumplir que C > Efr,,1 y se tenga un S = C - W-jq. El valor de L debe dominar la suma de los valores de P, esto es, L > P¡. Si por el contrario C < ? el primer término nunca será cero que multiplicado por L evitará seleccionar soluciones no factibles. El valor mínimo de la función de costo será uno donde la restricción es respetada y la suma de los valores se maximice (Bolos, 2019).

3.3.Mapeo de la función de costo a su Hamiltoniano cuántico

Al realizar el mapeo de las variables x, por (I -Z¡)/2,y¡ por(I -?)/2 y eliminar el primer término que es constante, se obtiene la Ecuación (11), donde 11 es una matriz identidad de orden n+m y Z¡ es la matriz resultante de tensorizar n+m matrices donde en cada posición diferente de i los factores del tensor son matrices identidad y la posición i es una matriz de Pauli Z.

La matriz de Pauli se compone de dos vectores, un vector X y un vector Z, para este caso se modifica el vector Z únicamente. Para hallar los coeficientes de la matriz se debe resolver cada sumatoria resultante en la Ecuación (11), encontrar el respectivo índice para cada valor de la sumatoria e ir adicionándolo a una lista. Por ejemplo, para el término ¾?11(-f1) x ¾?1 и-', (-A'r, se muestra su algoritmo en la Figura 1.

... (11)

Hay que tener en cuenta que no es necesario calcular los tensores por cuenta propia, ya que Qiskit tiene incorporado un objeto que toma los índices de la matriz de Pauli Z en el tensor y realiza los cálculos restantes.

Como resultado se obtiene una lista de objetos de Pauli, cada una con sus respectivos índices, y un valor shift que se encarga se acumular la diferencia de las magnitudes de la operación de cada sumatoria. Esos valores se envían al algoritmo Variational Quantum Eigensolver (VQE) con el objetivo de minimizar la función y retornar una solución X' donde los primeros n términos son la solución al problema de la mochila. La solución completa está a disposición de la comunidad en https://bit.ly/3kA4dJl.

4.Resultados

Para realizar la evaluación del algoritmo, se contó con un conjunto de 11 problemas disponibles en archivos de texto. Cada archivo contiene el número de elementos (n), la capacidad de la mochila (C), los pesos y valores para cada elemento y el valor óptimo conocido para el problema. Los valores de n, C y el resultado óptimo se muestran en la parte izquierda de la Tabla 1.

Para realizar las pruebas con un algoritmo cuántico se partió del algoritmo presentado en (Bolos, 2019), realizado en el marco del Qiskit Camp Asia 2019 que se celebró en el mes de noviembre, se migro a programación orientada a objetos y se le realizaron las adiciones pertinentes para poder ejecutar las instancias de los problemas dados. El algoritmo hace uso de la librería Qiskit-Aqua, la cual contiene una biblioteca de algoritmos cuánticos de dominios cruzados sobre los que se pueden construir aplicaciones para computación cuántica.

Cada problema se resolvió 30 veces (repeticiones del mismo experimento) con el algoritmo para obtener el valor óptimo promedio encontrado, el tiempo promedio de ejecución en segundos y la tasa promedio de éxito (porcentaje de las veces que encontró el óptimo ideal o conocido). Los resultados se encuentran en la parte central de la Tabla 1. En esta tabla también se incluye una columna de tiempo de ejecución para la solución del problema con un algoritmo exhaustivo "clásico", que en este caso es posible encontrar ya que son pocos objetos o elementos en cada problema.

En la parte derecha de la Tabla 1 se muestran los resultados para una implementación de recocido simulado clásico que usa decremento geométrico de la temperatura y una mutación basado en deseleccionar (sacar) al azar un elemento que está en la mochila e incluir aleatoriamente tantos como sea necesario para llenar la mochila (solución del problema evolucionando soluciones factibles).

Los resultados muestran que la solución cuántica tiene un 5,4% más de tasa de éxito (resolviendo 10 de los 11 problemas en todas las repeticiones del experimento) y el tiempo de ejecución es aproximadamente el mismo que el requerido por el recocido simulado. El problema donde la solución cuántica se queda atrapado en un óptimo local, es una donde la mochila desperdicia la cuarta parte de su capacidad para obtener el mayor beneficio, esto debe ser considerado para proponer una mejora a la formulación del problema.

Dado que la cantidad de qubits necesarios para solucionar el problema de la mochila mediante lógica cuántica es proporcional al peso de la mochila y a la cantidad de elementos, actualmente se hace imposible tratar problemas con más de 15 elementos en entornos simulados cuánticos sobre computadores personales; esto debido a que un sistema con n-qubits puede representar 2n estados al mismo tiempo, lo cual se convierte en una tarea difícil de realizar con la actual capacidad de procesamiento en estas computadores. Las pruebas se realizaron sobre un equipo personal con 16 Gigabytes de memoria RAM y un procesador Intel(R) Core (TM) i7-6700HQ CPU @ 2.60 GHz.

5.Conclusiones

En este documento se ha detallado una estrategia para dar solución al problema de optimización de la mochila binaria (un problema NP-completo), haciendo uso del algoritmo de Computación Cuántica Adiabática, detallando la manera como se mapea el problema a un modelo de Ising.

El algoritmo cuántico encuentra la misma solución en cada ejecución (repetición) del experimento, lo que demuestra la estabilidad del proceso que se ejecuta. De los 11 casos de prueba utilizados, se encontró la solución óptima en 10 de ellos, obteniendo resultados de tiempo similares a los del recocido simulado con una sutil mejora en la tasa de éxitos, lo que alienta el desarrollo de nuevas investigaciones en el área. Es preciso comentar que se está usando un entorno de computación cuántica simulado y no una computadora cuántica real donde el procesamiento paralelo natural de estos computadores debe demostrar su superioridad.

Observando los valores de los promedios arrojados en el experimento, se puede ver que no existe una diferencia significativa entre los resultados de los dos algoritmos comparados, esto esencialmente debido a que se esta trabajando con instancias de baja dimensionalidad, con lo cual a los algoritmos les toma muy poco tiempo en resolver el problema; pero alienta el desarrollo de investigaciones debido a los resultados prometedores obtenidos por el algoritmo cuántico, el cual obtiene una mejor tasa de éxito.

Para abordar problemas de mayor complejidad (mayor número de elementos) se hace necesario utilizar un computador clásico de mayor capacidad o idealmente un computador cuántico con una gran cantidad de qubits. Para tomar el segundo camino, se hace necesario establecer alianzas con empresas como IBM o Google quienes están desarrollando y probando los computadores cuánticos de mayor capacidad que existen hoy en día.

Teniendo en cuenta que el algoritmo cuántico mostró una debilidad concreta en la solución de un problema donde el óptimo se encuentra cuando la mochila queda desocupada en un 25% de su capacidad, se hace necesario que el Grupo se centre en mejorar la formulación de la función de costo y ampliar los tipos de problemas (instancias) que se usan en la evaluación para poder tener un panorama completo del rendimiento real del algoritmo.

Footnote

1 En algoritmos cuánticos se refiere a pasar de un estado A a un estado B no contiguo para evitar estancarse en óptimos locales.

2 Espacio de Hilbert: espacio vectorial complejo con un producto interno que también está completo.

3 Dos operadores no conmutan cuando se cumple: [A, B] = AB - BA Ф o (Benenti, Casaţi, & Strini, 2007).

4 Matriz de 2x2 cuyo primo [(I + cr. J j 2j tiene vectores propios | ОД } con valores propios 0,1 (Lucas, 2014)

References

Referencias

Albash, T., & Lidar, D. A. (2018). Adiabatic quantum computation. Reviews of Modern Physics, 90(1), 015002-1, 015002-015064. https://doi.org/10.1103/ RevModPhys.90.015002

Assi, M., & Haraty, R. A. (2019). A Survey of the Knapsack Problem. ACIT2018 - 19th International Arab Conference on Information Technology, 1-6. https://doi. org/10.1109/ACIT.2018.8672677

Benenti, G., Casati, G., & Strini, G. (2007). Principles of quantum computation and information: Volume II: Basic tools and special topics. Principles of Quantum Computation and Information - Volume II: Basic Tools and Special Topics (Vol. I). https://doi.org/10.1142/5838

Bian, Z., Chudak, F., Macready, W., & Rose, G. (2010). The Ising model: teaching an old problem new tricks. D-Wave Systems, 1-32. Retrieved from https://www. dwavesys.com/sites/default/files/Bian.pdf

Blado, D., & Toriello, A. (2019). Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes. SIAM Journal on Optimization, 29(1), 1-30. https://doi.org/10.1137/16M1101209

Bolos, S. (2019). GitHub - sorin-bolos/QiskitCampAsia2019.

Brush, S. G. (1967). History of the Lenz-Ising model. Reviews of Modern Physics, 39(4), 883-893. https://doi.org/10.1103/RevModPhys.39.883

Cao, Y., Jiang, S., Perouli, D., & Kais, S. (2016). Solving Set Cover with Pairs Problem using Quantum Annealing. Scientific Reports, 6(September), 1-15. https://doi.org/10.1038/srep33957

Coffey, M. W. (2017). Adiabatic quantum computing solution of the knapsack problem, 1-22. Retrieved from http://arxiv.org/abs/1701.05584

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of 28th Annual ACM Symposium on the Theory of Computing, 41(3), 212-221. https://doi.org/10.1007/BF01913177

Gurski, F., Rehs, C., & Rethmann, J. (2019). Knapsack problems: A parameterized point of view. Theoretical Computer Science, 775, 93-108. https://doi.org/10.1016/j. tcs.2018.12.019

Hadfield, S. (2018). Quantum Algorithms for Scientific Computing and Approximate Optimization. Columbia University. https://doi.org/10.7916/D8X650C9

Hey, T. (1999). Quantum computing: an introduction. Computing Control Engineering, 10(3), 105-112. https://doi.org/10.1049/cce:19990303

Karp, R. (2010). Reducibility Among Combinatorial Problems. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, 1-804. https://doi.org/10.1007/978-3-540-68279-0

Laboudi, Z., & Chikhi, S. (2012). Comparison of genetic algorithm and quantum genetic algorithm. International Arab Journal of Information Technology, 9(3), 243-249.

Layeb, A. (2011). A novel quantum inspired cuckoo search for knapsack problems. International Journal of Bio-Inspired Computation, 3(5), 297-305. https://doi.org/10.1504/IJBIC.2011.042260

Li, J., & Li, W. (2019). A new quantum evolutionary algorithm in 0-1 knapsack problem. Communications in Computer and Information Science (Vol. 986). Springer Singapore. https://doi.org/10.1007/978-981-13-6473-0_13

Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2, 1-14. https://doi.org/10.3389/fphy.2014.00005

Martelio, S., & Toth, P. (1987). Algorithms for Knapsack Problems. North-Holland Mathematics Studies, 132(C), 213-257. https://doi.org/10.1016/S03040208(08)73237-7

Narayanan, A. (1999). Quantum computing for beginners. Proceedings of the 1999 Congress on Evolutionary Computation, CEC 1999, 3, 2231-2238. https://doi.org/10.1109/CEC.1999.785552

Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information (Vol. 52). Cambridge, MA, USA: Cambridge University Press. https://doi.org/10.10 80/00107514.2011.587535

Pisinger, D. (2005). Where are the hard knapsack problems? Computers and Operations Research, 32(9), 2271-2284. https://doi.org/10.1016/j.cor.2004.03.002

Salkin, H. M., & de Kluyver, C. A. (1975). The knapsack problem: a survey·. Naval Research Logistics, 22(1), 127-144. https://doi.org/10.1002/nav.3800220110

Shor, P. W. (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, 59(3), 124-134. https://doi.org/10.1016/0024-3205(96)00287-1

Vega Fernández, C. A., & Ramírez Celis, J. S. (2017). Computación Cuántica: Implementación de Algoritmos de Short y Grover en el Computador Cuántico de IBM. Escuela Colombiana de Ingeniería Julio Garavito.

Vickram, P., Krishna, A. S., & Srinivas, V. S. (2016). A Survey on Design Paradigms to solve 0/1 Knapsack Problem. International Journal of Scientific & Engineering Research, 7(11), 112-117. Retrieved from https://www.ijser.org/researchpaper/ASurvey-on-Design-Paradigms-to-solve-0-1-Knapsack-Problem.pdf

Wang, H., Ma, L., Zhang, H., & Li, G. (2009). Quantum-inspired ant algorithm for knapsack problems. Journal of Systems Engineering and Electronics, 20(5), 1012-1016. Retrieved from https://ieeexplore.ieee.org/stamp/stamp. jsp?arnumber=6074538

Wang, R., Guo, N., Xiang, F., & Mao, J. (2012). An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem. In Proceedings of 2012 International Conference on Measurement, Information and Control (Vol. 1, pp. 484-488). https://doi.org/10.1109/MIC.2012.6273347