Implementation of NP problems in quantum computers based on neutral atoms

Javier Peña Riosalido

Published Jan 1, 2026• 0 citations

Abstract

RESUMEN: La computación cuántica con átomos neutros se posiciona como una plataforma prometedora para la optimización combinatoria, gracias a su escalabilidad, a su flexibilidad geométrica y a la posibilidad de operar en modo analógico, en el que el sistema evoluciona de forma continua bajo la aplicación de un Hamiltoniano controlado por pulsos láser. En este trabajo se presentan los fundamentos de la plataforma, prestando especial atención al Hamiltoniano de Rydberg, que permite codificar restricciones lógicas de forma nativa en la geometría del registro atómico. Se introduce también el planteamiento de problemas de optimización a través de Hamiltonianos de Ising y su formulación QUBO. Por último, se exponen el teorema adiabático y el algoritmo cuántico adiabático (QAA), las bases de su implementación. Estos conceptos se aplican a la resolución del Minimal Maximal Matching (MMM), un problema NP-duro sobre grafos escogido para estudiar las capacidades y limitaciones de la plataforma. Tras formularlo en formato QUBO, se mapea al Hamiltoniano de Rydberg y se resuelve mediante el emulador cuántico Bloqade. La metodología se evalúa sobre un catálogo de grafos, analizando la dependencia de la probabilidad de éxito con el tiempo de barrido, la escala energética y las constantes de penalización. Finalmente, se discuten las dos principales limitaciones encontradas, el truncamiento de la matriz QUBO y la restricción geométrica del "embedding" 2D.

Related papers

Implementation of NP Problems in Quantum Computers Based on Neutral Atoms

Bruno Ríos López

RESUMEN: La resolución de problemas NP mediante computadores cuánticos tiene gran interés debido al coste que supone para sistemas clásicos. Se estudia cómo computadores cuánticos basados en átomos neutros pueden resolver este tipo de problemas haciendo uso de algoritmos cuánticos. En concreto, se resuelve el problema de optimización de carteas, con aplicación inmediata al mundo real. Mediante dos procedimientos distintos, se muestra la versatilidad de los átomos neutros como tecnología de computación cuántica. Finalmente, se analizan los resultados obtenidos, especificando ventajas y cuellos de botella de los métodos empleados.

Jan 1, 20260 citations

Estudio de la eficiencia y comportamiento de QAOA frente a algoritmos clásicos en problemas de optimización.

Alberto Martínez Gallardo

Este trabajo se centra en el estudio de algoritmos de computación cuántica, con una introducción general al marco teórico de la computación cuántica, su naturaleza, estado actual y potencial en la resolución de problemas complejos. En particular, se aborda el uso de algoritmos cuánticos en tareas de optimización, un área de gran relevancia. Se analizarán problemas de optimización de funciones, enfocándonos en la optimización de diferentes tipos de potenciales. Para ello, se implementará el algoritmo QAOA (Quantum Approximate Optimization Algorithm), uno de los algoritmos cuánticos más representativos en este ámbito. Con el objetivo de contextualizar su rendimiento, se compararán sus resultados con los obtenidos mediante algoritmos clásicos de optimización como el método del descenso del gradiente y el método de Newton. El estudio incluirá tanto una comparación cuantitativa en términos de precisión, tiem- po de ejecución y calidad de la solución, como un análisis cualitativo de las diferencias entre enfoques clásicos y cuánticos. Asimismo, se examinará la influencia de los hiperparámetros de cada algoritmo sobre su rendimiento, con el propósito de identificar patrones o relaciones que permitan optimizar su configuración para distintos tipos de problemas.

Jun 1, 20250 citations

Optimización cuántica para planificación minera con capacidad flexible: Implementación de QAOA con variables de holgura

Bairon Rojas-Castro, Aldo Quelopana

Este trabajo presenta un estudio exploratorio y preliminar sobre la aplicación de un algoritmo cuántico variacional para resolver problemas de planificación minera a cielo abierto con capacidad de extracción flexible. El objetivo principal es evaluar la viabilidad técnica de la formulación propuesta y su resolución mediante QAOA, más que comparar su rendimiento frente a métodos clásicos o cubrir un amplio rango de instancias. Se desarrolla una formulación Quadratic Unconstrained Binary Optimization (QUBO) que incorpora variables de holgura para modelar restricciones de capacidad del tipo “menor o igual”, permitiendo operaciones por debajo de la capacidad máxima sin penalizaciones. La metodología emplea el Quantum Approximate Optimization Algorithm (QAOA) para optimizar la selección de bloques maximizando la ganancia económica de la extracción mientras respeta restricciones de precedencia geológica y límites operativos flexibles. El enfoque se valida mediante un caso de estudio en un yacimiento sintético de cobre de 18 bloques resuelto en un simulador cuántico, demostrando la capacidad del algoritmo cuántico para manejar la complejidad adicional introducida por las variables auxiliares. Esta investigación establece fundamentos para aplicar computación cuántica a problemas de planificación minera con mayor flexibilidad operativa.

Ingeniare. Revista chilena de ingenieríaSep 4, 20260 citations

Principis físics i model matemàtic d'un ordinador quàntic de tres qubits

Diego Orlando

[ES] En este trabajo, describiremos físicamente, modelaremos matemáticamente, y probaremos el funcionamiento práctico de un ordenador cuántico de tres qubits, SpinQ Triangulum, adquirido en un proyecto con investigadores principales de la Universitat Politécnica de Valéncia y la Universidad CEU Cardenal Herrera. Tras una breve introducción matemática sobre los fundamentos de la computación cuántica, presentaremos los algoritmos cuánticos que ejecutaremos en la computadora. Estos son el algoritmo de Grover para la búsqueda en bases de datos no estructuradas y el algoritmo Harrow-Hassidim-Lloyd (HHL) para resolver sistemas lineales de ecuaciones. Una vez hecho esto, nos adentraremos en la física de las diferentes propuestas de computación cuántica. Se discutirán los más comunes antes de centrar nuestra atención en la computación usando resonancia magnética nuclear (NMR). En la última sección de este trabajo, discutimos la física de SpinQ Triangulum y la implementación de los algoritmos que hemos visto. Como otra prueba, también vamos a probar si la desigualdad de Bell está o no verificada, para ver si hay entrelazamiento. Finalmente, haremos pruebas practicas y evaluaremos el comportamiento del ordenador.

Sep 20, 20240 citations

Optimización de la trayectoria de ascenso de aeronaves A320 mediante reducción de dimensionalidad y computación cuántica

Marco Aurelio Erazo Rosero

En este trabajo se aborda el problema físico de la trayectoria de ascenso del A320 y su modelo maten ático de optimización, partiendo del planteamiento original de Airbus en el documento Airbus Quantum Computing Challenge. El problema busca minimizar la cantidad ϕ (consumo de combustible penalizado por el tiempo), compuesta por ecuaciones altamente no lineales dependientes de múltiples incógnitas. Analizado inicialmente como un sistema acoplado de 364 variables, se demuestra su simplificación mediante la evaluación del jacobiano de las ecuaciones dinámicas para distinguir grados de libertad de parámetros temporales, logrando una formulación analítica de ϕ reducida a 104 variables independientes. El éxito en la reducción permite los planteamientos posteriores y plasmarla en un solo script para el trabajo computacional. La obtenida es una función en variables continuas, cuyos altos tiempos de resolución clásica hace pertinente el uso de computación cuántica; para este hardware se justifica el reemplazo de variables continuas por binarias construyendo un modelo de Optimización Cuadrática Binaria sin Restricciones (QUBO) en variables reducidas; la función binaria análoga contiene la información original pero de naturaleza matemática diferente. Se comparan los comportamientos de optimizadores clásicos (evolución diferencial) y el método cuántico (mediante un simulador de recocido cuántico como propuesta para el hardware requerido) para cada función, tanto en variables continuas como discretas. Finalmente se muestra una comparativa de parámetros e indicadores de dificultad (como tiempo y variabilidad) que dan cuenta de la fortaleza de la perspectiva cuántica por su principio de búsqueda de un óptimo global, exponiendo la debilidad del optimizador clásico y su caída sistemática en mínimos locales. Se describe además una optimización alterna hecha con métodos clásicos de la función completa de 104 variables continuas, finalizando con la postulación del resultado obtenido: un candidato físicamente factible a óptimo local de −58706.51 kg para el problema general planteado bajo cumplimiento estricto de las restricciones operacionales.

Jan 1, 20240 citations

Quantum computing with Rydberg atoms : control and modelling for quantum simulation and practical algorithms

Lucas Leclerc

Calcul quantique avec des atomes de Rydberg : contrôle et modélisation pour simulation et algorithmes quantiques Améliorer sa compréhension d'un système en le modélisant permet d'espérer le contrôler de manière plus optimale et ouvre la voie à une myriade d'applications potentielles, exploitant les effets jusqu'alors énigmatiques de ce système désormais familier. Cette thèse applique ce paradigme au calcul quantique analogique avec des atomes de Rydberg, montrant comment à l'aide d'une modélisation minutieuse du bruit, de protocoles de contrôle optimaux et de techniques d'apprentissage automatique, on peut espérer améliorer des expériences de simulation de magnétisme quantique ou la résolution de problèmes d'optimisation et de classification de graphes. Après avoir décrit la plateforme expérimentale permettant de contrôler les atomes de Rydberg, nous introduisons des outils classiques tels que les jumeaux numériques de systèmes enclins à des erreurs, la modélisation d'un grand nombres d'atomes par réseaux de tenseurs, le contrôle optimal robuste et l'optimisation bayésienne pour les algorithmes variationnels. Nous appliquons ces outils à plusieurs applications prometteuses. Nous améliorons la préparation d'états antiferromagnétiques dans le modèle d'Ising et réalisons une évaluation détaillée de l'influence d'erreurs sur l'étude de phases magnétiques du modèle dipolaire XY et lors de la tomographie d'états quantiques. En utilisant des techniques d'optimisation et des méthodes d'apprentissage automatique, nous abordons également des cas d'usage industriels tels que la résolution du problème de stable maximum sur des graphes représentant des tâches de planification de charge de batteries de voitures électriques, la classification de composés moléculaires toxiques ou inoffensifs, et des tâches de prédiction dans la gestion des risques financiers.

Sep 19, 20240 citations