Mejorando los Algoritmos de Optimización Cuántica mediante la Relajación de Restricciones

La optimización cuántica es un área significativa de la investigación en computación cuántica con ventajas cuánticas anticipadas a corto plazo. Los algoritmos actuales de optimización cuántica, la mayoría de los cuales son algoritmos híbridos basados en variaciones Hamiltonianas, luchan por presentar dispositivos cuánticos debido al ruido y la decoherencia. Las técnicas existentes intentan mitigar estos problemas mediante el uso de diferentes codificaciones Hamiltonianas o la poda de cláusulas Hamiltonianas, pero a menudo se basan en suposiciones optimistas en lugar de un análisis profundo de la estructura del problema. Demostramos cómo formular el Hamiltoniano del problema para un algoritmo cuántico de optimización aproximada que satisface todos los requisitos para describir correctamente el problema considerado de deconflicción de aeronaves tácticas, logrando mayores probabilidades de encontrar soluciones en comparación con trabajos anteriores. Nuestros resultados indican que construir Hamiltonianos desde una perspectiva no convencional y específica de la cuántica con un alto grado de entrelazamiento resulta en un número lineal en lugar de exponencial de puertas de entrelazamiento y un rendimiento superior en comparación con formulaciones estándar. Específicamente, logramos una mayor probabilidad de encontrar soluciones factibles: encontrar soluciones en nueve de nueve instancias en comparación con formulaciones Hamiltonianas estándar y formulaciones de programación cuadrática conocidas de recocedores cuánticos, que solo encontraron soluciones en siete de nueve instancias. Estos hallazgos sugieren que hay un potencial sustancial para una mayor investigación en el diseño de Hamiltonianos cuánticos y que los enfoques basados en puertas pueden ofrecer un rendimiento de optimización superior sobre los recocedores cuánticos en el futuro.