En el siguiente trabajo se aborda el estudio comparativo de dos métodos de optimización dentro del Quantum Approximation Optimization Algorithm (QAOA), estos métodos de optimización son la Búsqueda Exhaustiva y la heurística de Búsqueda Local Iterada o Iterativa. Ambos métodos son probados en varios problemas, estos problemas se separan en dos categorías, la primera categoría son los problemas de Ising Spin Model (ISM) y la segunda categoría son los problemas de Max-Cut. Dentro de cada categoría se tienen tres problemas distintos, cada uno difiere en el tipo de configuración que tiene, estas configuraciones son de tipo: lineal, cíclico y completo. Además, la comparativa también se extiende a experimentaciones utilizando computadoras clásicas (simulaciones locales) y computadoras cuánticas (simulaciones reales), estas experimentaciones locales y reales permiten analizar la aplicabilidad de estos métodos de optimización dado el estado actual del hardware cuántico.
En el siguiente trabajo se aborda el estudio comparativo de dos métodos de optimización dentro del Quantum Approximation Optimization Algorithm (QAOA), estos métodos de optimización son la Búsqueda Exhaustiva y la heurística de Búsqueda Local Iterada o Iterativa. Ambos métodos son probados en varios problemas, estos problemas se separan en dos categorías, la primera categoría son los problemas de Ising Spin Model (ISM) y la segunda categoría son los problemas de Max-Cut. Dentro de cada categoría se tienen tres problemas distintos, cada uno difiere en el tipo de configuración que tiene, estas configuraciones son de tipo: lineal, cíclico y completo. Además, la comparativa también se extiende a experimentaciones utilizando computadoras clásicas (simulaciones locales) y computadoras cuánticas (simulaciones reales), estas experimentaciones locales y reales permiten analizar la aplicabilidad de estos métodos de optimización dado el estado actual del hardware cuántico.
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.
El presente trabajo de integración curricular tiene como objetivo analizar y comparar el desempeño de un algoritmo de búsqueda clásico y de un cuántico, en específico el algoritmo de Grover, con el fin de analizar y contrastar la ventaja computacional teórica y asintótica que proporciona la computación cuántica frente a los algoritmos clásicos, considerando las limitaciones del hardware cuántico actual. Se analizan las bases teóricas de estos dos enfoques, su complejidad temporal y su comportamiento frente a conjuntos de datos de tamaño distinto. La metodología que se emplea es la simulación de ambos algoritmos, es experimental, ya que permite observar y realizar comparaciones de tiempo y eficiencia para la localización de un elemento objetivo. En el caso del algoritmo cuántico, se implementa el algoritmo de Grover mediante simuladores cuánticos, analizando el impacto del número de qubits y de las iteraciones en los resultados obtenidos. Los resultados muestran que para la búsqueda clásica la complejidad de tiempo es O(n) en cambio en el caso del algoritmo de Grover esta se reduce a O(√n) siendo una mejora interesante que se centra en un n grande. A pesar de esto, existen limitaciones en la implementación de ordenadores cuánticos en la actualidad. Por último, se concluyó que el algoritmo de Grover es una alternativa bastante interesante para resolver problemas de búsqueda no estructurada y se muestra el potencial de la computación cuántica como una tecnología emergente con aplicaciones en la ingeniería.
En la última década, se ha logrado un progreso significativo en el desarrollo de computadoras NISQ (Noisy Intermediate-Scale Quantum), aunque se requieren mejoras en el hardware para que los algoritmos cuánticos a gran escala se ejecuten sin errores. Mientras tanto, los investigadores continúan enfocándose en el desarrollo de algoritmos efectivos para el hardware actual, con énfasis en aplicaciones a corto plazo como la optimización combinatoria. Este estudio presenta un análisis comparativo del Algoritmo Cuántico de Optimización Aproximada (QAOA) aplicado al problema de Reasignación de Puestos de Trabajo (JRP), que consiste en asignar n trabajadores a m trabajos vacantes para maximizar la realización de tareas de alta prioridad y la satisfacción de los trabajadores con sus asignaciones. El análisis, realizado mediante la simulación clásica en 105 instancias de JRP, indica un resultado prometedor, con razones de aproximación notablemente altas que oscilan principalmente entre 0, 86 y 0, 97. Esto contribuye a tener un incremento medio del 12% en la productividad organizacional, al mejorar la asignación de tareas de alta prioridad y la satisfacción de los trabajadores con sus asignaciones.
El objetivo de esta investigación es proponer una implementación del algoritmo de Grover, un método cuántico que permite reducir significativamente el tiempo de búsqueda en bases de datos no estructuradas. Se aplicó una metodología que integró diferentes experimentos en simuladores y una computadora cuántica en el cual se incluyó el análisis del algoritmo cuántico, y se compara con los algoritmos clásicos deterministas en diferentes escenarios de búsquedas. Se estructura la arquitectura del algoritmo ajustando los parámetros que lo constituyen y tipo de búsqueda. Por ende, dando una versión de los fundamentos de la computación cuántica, destacando los principios de superposición y entrelazamiento como elementos clave para abordar problemas de búsquedas en listas no ordenadas con tecnologías cuánticas. Asimismo, se introducen los conceptos de qubits, compuertas cuánticas, circuitos cuánticos, y se describe la interpretación geométrica de su acción sobre los estados cuánticos mediante la esfera de Bloch. Se detalla el funcionamiento del algoritmo de Grover con la utilización de simuladores cuánticos y su escalabilidad en la computadora cuántica ibmbrisbane, para la estructuración de la solución a problemas de búsqueda en listas no ordenadas, explicando cómo logra una aceleración cuadrática al reducir la complejidad de búsqueda de ( O(N) ) a ( O(sqrt{N}) ). Esta investigación siguió un enfoque cuantitativo, experimental y comparativo, visualizando como este algoritmo representa una ventaja computacional significativa en la resolución de problemas de búsqueda en estructuras de datos no organizadas y con el objeto experimental del tamaño de la búsqueda.
1 Objectivos y contenidos básicos del trabajo. Esta tesis explora dos desafíos relacionados con la simulación de la ecuación no lineal de Schrodinger (NLSE) desde la perspectiva de la informática: (1) técnicas computacionales eficientes y algoritmos que explotan detalles de bajo nivel de CPUs y GPU modernas, y (2) visualización novedosa del solución mediante gráficos de computadora modernos con un motor de animación 3D. Ambos son problemas desafiantes cuya solución tendría un amplio impacto en otros campos de la ciencia computacional. Para un físico cuyo objetivo es estudiar el comportamiento de los procesos físicos descritos por NLSE, desarrollar software cuidadosamente diseñado y optimizado que gestione adecuadamente la CPU subyacente y el hardware de la GPU está más allá del alcance de sus objetivos. Para esto, se requieren conocimientos técnicos especializados de hardware multiproceso - dentro del ámbito de las ciencias de la computación - para que las rutinas de bajo nivel escritas cuidadosamente accedan a la memoria a fin de minimizar los requisitos de ancho de banda y contención. También se requiere altos conocimientos en informática para aprovechar las representaciones de animaciones 3D en la actualidad. Por lo tanto, es en esta interfaz entre la física computacional y la informática pura donde esta tesis pretende hacer contribuciones prácticas y fundamentales. Los objetivos específicos y las contribuciones de la tesis son los siguientes: Realizar simulaciones PDE no lineales con el método pseudo-espectral lo más rápido posible, disponible a través de un Kernel JIT personalizado: Desarrollar un código multihilo personalizado de bajo nivel optimizado para la GPU al que se pueda acceder como Kernel JIT de alto nivel basado en Numba, que utilice técnicas numéricas y de computación que se asignan directamente al hardware de CPU / GPU, específicamente para el problema de resolver PDE con los métodos pseudo-espectrales split-step . Desarrollar métodos que aceleren el cálculo para casos de NLSE que causan inestabilidades. Para esto se explorarán algoritmos numéricos que combinan el método pseudo-espectral con el método de malla adaptable. Se hará especial hincapié en el aspecto informático de dividir el problema de manera eficiente. Realizar nuevas visualizaciones para ondas cuánticas: desarrollar un conjunto de métodos novedosos para la visualización científica en la propagación de ondas mecánicas cuánticas, simuladas numéricamente con técnicas de animación en 3D. Se debe desarrollar una herramienta software que sea una extensión de un editor en 3D, que permita interactuar a través de fly-thrus con soluciones PDE simuladas y renderizadas, a través del motor 3D. Este trabajo también impactará directamente los resultados de un proyecto recientemente aceptado "Ondas no lineales y materia oscura emergente".
La computación cuántica tiene una base teórica de más de tres décadas que muestra aceleraciones polinómicas y exponenciales sobre los algoritmos clásicos. Los procesadores que se construyen hoy, sin embargo, son ruidosos, pequeños y de conectividad limitada, aún lejos de aprovechar esa ventaja en problemas de escala real. Este trabajo es un estudio experimental que mide qué tan profunda es esa brecha para cuatro algoritmos cuánticos fundamentales: Bernstein–Vazirani, Simon, Grover sobre instancias de k-SAT y la estimación cuántica de fase. Para cada algoritmo se construyó una contraparte clásica de referencia y se evaluaron, por cada tamaño de entrada, todas las combinaciones posibles de tres modelos de ruido (error de lectura, despolarizante y relajación térmica) con tres topologías de hardware (ideal, lineal de 20 qubits y heavy-hex de 127 qubits, esta última inspirada en el chip ibm_brisbane). El estudio se hizo enteramente en simulación porque permite controlar de forma independiente cada parámetro del ruido y de la conectividad, condición necesaria para hacer comparaciones limpias entre escenarios. Cada uno de los 39 escenarios resultantes por tamaño se repitió 25 veces y los resultados se reportan con intervalo de confianza al 95 % calculado con la t de Student. Toda la infraestructura (algoritmos, generador de instancias, modelos de ruido, scripts de análisis e interfaz gráfica para exploración interactiva) queda reproducible y abierta. Los hallazgos principales son tres. Primero, la ventaja teórica sobrevive en los algoritmos de poca profundidad como Bernstein–Vazirani, mientras que en Grover y en la estimación de fase el ruido deteriora rápidamente el speedup a medida que crece el número de iteraciones. Segundo, el tipo de ruido importa tanto como su nivel: el error de lectura es el menos agresivo porque no se acumula con la profundidad del circuito, mientras que el despolarizante es el más severo. Tercero, la topología influye de forma indirecta pero significativa porque condiciona la cantidad de compuertas SWAP que el compilador debe insertar y, por esa vía, aumenta la profundidad efectiva del circuito. El framework, los datos y los análisis quedan disponibles para quien quiera prototipar pruebas de algoritmos cuánticos en la era NISQ sin depender de tiempo en hardware real.