Aproximación de soluciones del problema MAX-SAT usando cómputo cuántico adiabático

Abstract

Actualmente, se han propuesto tecnologías cuánticas basadas en el algoritmo de temple cuántico y cómputo cuántico adiabático con aplicaciones a problemas de optimización combinatorios. Diversos estudios teóricos y experimentales se han enfocado en determinar las ventajas y desventajas de resolver clases específicas de problemas tales como detección de fallas en redes de potencia, plegado de proteínas, satisfacción de restricciones, entre otros. En esta tesis se propone una formulación cuántica del problema de máxima satisfactibilidad booleana usando el algoritmo de temple cuántico y cómputo cuántico adiabático. Nuestra formulación consiste en la construcción de una función booleana cuadrática cuya optimización corresponde a la solución del problema de estudio. También, se proponen tres estrategias de mapeo directas para instancias del problema de máxima satisfactibilidad booleana sobre la topología de hardware cuántico de la computadora D-Wave. Para validar nuestra propuesta, realizamos simulaciones computacionales del modelo cuántico para aproximar soluciones del problema de estudio, y las comparamos con resultados obtenidos usando algoritmos clásicos. Los resultados de las simulaciones muestran que el problema de máxima satisfactibilidad booleana puede ser tratado por medios cuánticos con las tecnologías cuánticas actuales. Sin embargo, se tienen que llevar a cabo investigaciones futuras para determinar si el algoritmo de temple cuántico y el cómputo cuántico adiabático, para el problema de estudio, tienen ventajas en términos de complejidad cuando se comparan con los mejores algoritmos en el estado del arte.