Estudio de teoría de complejidad para computación cuántica: Algoritmo HHL para el problema cuántico de solución de sistemas lineales (QLSP) y reducción de circuitos cuánticos a QLSP
Este trabajo presenta una introducción a la teoría de complejidad asociada a los algoritmos cuánticos, tomando como marco principal el modelo de circuitos cuánticos. Se estudia cómo se mide la complejidad de un algoritmo cuántico, cómo se relacionan las clases de complejidad clásicas y cuánticas, y cómo ciertos problemas permiten caracterizar la dificultad computacional de una clase completa. Como punto de partida, se considera el papel del teorema de Cook–Levin en la teoría clásica de la complejidad, el cual establece que el problema SAT es completo para la clase . Este resultado proporciona un problema concreto cuya dificultad representa la de todos los problemas pertenecientes a dicha clase. De manera análoga, en el contexto cuántico se estudia el problema cuántico de solución de sistemas lineales, conocido como QLSP, y su relación con el modelo de circuitos cuánticos. En particular, se muestra cómo la ejecución de un circuito cuántico puede reducirse a una instancia de QLSP. Esta reducción permite comprender el papel central de dicho problema en la teoría de complejidad cuántica y establecer una conexión entre la simulación de circuitos cuánticos y la solución de sistemas lineales mediante algoritmos cuánticos.
Este trabajo presenta una introducción a la teoría de complejidad asociada a los algoritmos cuánticos, tomando como marco principal el modelo de circuitos cuánticos. Se estudia cómo se mide la complejidad de un algoritmo cuántico, cómo se relacionan las clases de complejidad clásicas y cuánticas, y cómo ciertos problemas permiten caracterizar la dificultad computacional de una clase completa. Como punto de partida, se considera el papel del teorema de Cook–Levin en la teoría clásica de la complejidad, el cual establece que el problema SAT es completo para la clase . Este resultado proporciona un problema concreto cuya dificultad representa la de todos los problemas pertenecientes a dicha clase. De manera análoga, en el contexto cuántico se estudia el problema cuántico de solución de sistemas lineales, conocido como QLSP, y su relación con el modelo de circuitos cuánticos. En particular, se muestra cómo la ejecución de un circuito cuántico puede reducirse a una instancia de QLSP. Esta reducción permite comprender el papel central de dicho problema en la teoría de complejidad cuántica y establecer una conexión entre la simulación de circuitos cuánticos y la solución de sistemas lineales mediante algoritmos cuánticos.
Este Trabajo Fin de Grado tiene como objetivo el estudio de la computación cuántica y el desarrollo de un algoritmo cuántico para la resolución de una variante del problema de satisfacibilidad booleana. La computación cuántica es una rama de investigación que está actualmente en sus inicios. Basa su funcionamiento en fenómenos de la física cuántica, que permite realizar cálculos de forma paralelizable. El interés por este campo surge por la capacidad que podrían alcanzar los ordenadores cuánticos de resolver problemas computacionalmente más rápido que los ordenadores clásicos. Tras la comprensión de los principios básicos de la computación cuántica se han estudiado en detalle algunos de los algoritmos cuánticos más conocidos, centrándose en el algoritmo de Grover. Finalmente se ha podido llevar a cabo el desarrollo de un algoritmo para resolver una variante del problema de satisfacibilidad booleana, el problema ‘Exactly-1 3-SAT’, que basa su funcionamiento en el algoritmo de Grover. Se han desarrollado tres posibles implementaciones de este algoritmo y se han realizado pruebas tanto en un simulador, como en un ordenador cuántico real. El problema ‘Exactly-1 3-SAT’ es un problema perteneciente a la clase de complejidad NP-completo, cuya resolución de forma cuántica reduce el tiempo de computación notablemente con respecto a la forma clásica.
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.
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.
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.
La Computación Cuántica se presenta como un paradigma de computación no clásico que hace uso de fenómenos cuánticos para la realización de cálculos computacionales. De entre sus distintas implementaciones o manifestaciones, la basada en puertas cuánticas se considera la más versátil o de aplicación general, por su posibilidad de construir circuitos a partir de componentes más elementales. Dichos componentes son las puertas cuánticas, conceptualmente equivalentes a sus homónimas en el paradigma de computación clásica o basada en bits. Mientras que las puertas lógicas clásicas permiten la transformación del estado presentado por un registro en n bits, y en ello basamos la práctica totalidad de los dispositivos electrónicos actuales, las puertas cuánticas permiten a su vez la transformación de los estados de registros de n qubits. A dichos estados, se los denomina estados cuánticos. A diferencia de lo que ocurre en el caso de un bit, que puede estar únicamente en los estados 0 o 1, un qubit puede encontrarse en cualquiera de ambos estados -denominados clásicos-, o en una superposición lineal de ambos. Dicha superposición, regida por coeficientes complejos, establece qué probabilidad tenemos de obtener el qubit un estado 0, o un estado 1, si le aplicamos un proceso de medición. En la gran variedad de formas en que podemos superponer los estados clásicos de cada n-qubit, reside la potencia de este paradigma. El modelo discreto de Computación Cuántica propone el uso de estados cuánticos que cumplen unas determinadas propiedades, simplificando así el modelo continuo y permitiendo el uso de nuevos parámetros para comprender la relación entre los distintos estados cuánticos y su transformación mediante puertas cuánticas. Concretamente, se destacan dos: el número mínimo de puertas necesarias para alcanzar un determinado estado cuántico discreto desde uno de la base computacional -complejidad c-, y el parámetro necesarios para mantener la norma unitaria del vector que representa el estado -novel k-. Su estudio será determinante par identificar familias de estados discretos con propiedades particulares, algoritmos para el uso o la exploración del modelo discreto, y conclusiones sobre la complejidad de los estados del modelo. Abstract: Quantum Computing presents itself as a non-classical computing paradigm that uses quantum phenomena to make computational calculations. Among its different implementations or manifestations, the one based on quantum gates is considered as the most versatile or general-purpose one, due to its ability to create circuits using other basic components as its building blocks. Those basic components are quantum logic gates, conceptually equivalent to their homonym counterpart in classical or bit-based computing. Whereas classical logic gates enable the transformation of any state of a register of n bits, and almost every current electronic device is based on this paradigm, quantum logic gates are used to transform the states allowed by a register of n qubits. We will refer to those states of a n-qubit as quantum states. Opposed to a bit, that can only be in either a 0 or 1 state, a qubit can be in any of those so-called classical states, but also in any linear superposition of both. That superposition, determined by complex coefficients, establishes the probability to obtain either a 0 or a 1 from the qubit, after applying a measuring procedure to it. The computational power of this paradigm is based on the huge number of configurations that every n-qubit can have. The discrete model of Quantum Computing suggets the use of quantum states that verify certain additional properties, therefore simplifying the continuous model, and en-abling the use of new parameters to understand the relationship between different quantum states, and its transformation with quantum logic gates. Specifically, two are highlighted: the minimum number of gates required to reach a quantum state from one of the computational base -complexity c-, and the parameter needed to ensure that the vector that represents a quantum state remains unitary -level k-. Their study will play a key role in identifying families of quantum states with relevant characteristics, algorithms that allow for the use or the exploration of the discrete model, and conclusions about the complexity of the states of this model.
La computación clásica forma parte de nuestro día a día y ha sido uno de los pilares que ha impulsado la innovación en las últimas décadas. Sin embargo, hay problemas que esta tecnología no es capaz de resolver o es muy poco eficiente hacerlo de esta manera. Aquí es donde entra en juego la computación cuántica, campo en el cual se están alcanzando progresos significativos. La principal diferencia entre la computación clásica y la cuántica es que en esta última se hace uso de fenómenos cuánticos, tales como la superposición y el entrelazamiento. Para ello la computación cuántica se basa en el uso de qubits o bits cuánticos, dejando de lado los bits clásicos y los sistemas lógicos empleados por los sistemas informáticos convencionales. Esta tecnología resulta de gran interés actualmente por su enorme potencial, que supone la posibilidad de revolucionar el mundo de la computación. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica, lo que ha dado lugar a una gran expectación. También permite la resolución de problemas intratables anteriormente. En general, los ordenadores cuánticos, debido a su gran capacidad de manejo de datos, nos ofrecen la posibilidad de impulsar grandes avances en diversos campos, desde la ingeniería hasta la investigación farmacéutica, por ejemplo. En este trabajo se aborda el estudio del algoritmo cuántico de Grover, que resuelve el problema de encontrar una entrada en una base de datos desestructurada. En primer lugar se introducen los conceptos básicos para la comprensión del algoritmo, tales como el oráculo y la amplificación de amplitud. Posteriormente se tratan las mejoras respecto de los algoritmos de búsqueda clásicos y el hecho de que el algoritmo de Grover es óptimo. Esto completa la parte de desarrollo teórico. Posteriormente se presenta una componente de simulación en la plataforma IBM Quantum Experience para las diferentes situaciones propuestas. Más tarde se lleva a cabo la implementación real del algoritmo en los ordenadores cuánticos de IBM así como la implementación mitigando en cierta medida el error propio de los ordenadores cuánticos. Finalmente, se comentan algunas aplicaciones dentro del gran abanico de aplicaciones existentes a día de hoy.