Revista Colombiana de Computación

Hipercomputación desde la computación cuántica

Andrés Sicard, Juan Ospina, Mario E. Vélez

Published Dec 1, 2006• 0 citations

Abstract

Un hipercomputador computa funciones que son incomputables por una máquina de Turing. Recientemente, Tien D. Kieu ha propuesto un algoritmo hipercomputacional cuántico, el cual emplea como referente físico el oscilador armónico cuántico y resuelve en principio el décimo problema de Hilbert. Se realiza un análisis del algoritmo de Kieu y se deduce que está sustentado en ciertas propiedades del álgebra Weyl-Heisenberg, la cual es el álgebra dinámica asociada al oscilador armónico cuántico; y en una cierta aplicación del teorema adiabático de la mecánica cuántica. Con base en el análisis realizado, se presenta una adaptación algebraica del algoritmo de Kieu, es decir, se presenta un algoritmo ála Kieu sobre el álgebra de Lie su(1, 1). Debido a que el álgebra su(1, 1) admite realizaciones en sistemas físicos en las áreas de la óptica cuántica, la materia condensada y la física matemática, entre otras; la adaptación realizada amplia el espectro de posibilidades de implementación del algoritmo sobre uno de estos sistemas.Palabras claves: Hipercomputación, computación cuántica, Décimo problema de Hilbert, teorema adiabático, álgebra de Lie su(1, 1).

DOI: 10.29375/25392115.1050

Related papers

Quantum algorithm of hypercomputation based on the pöschl-teller potential

Mario E. Vélez, Andrés Sicard, Juan Ospina

Se construye un algoritmo cuantico de hipercomputacion con base en los potenciales POschl-Teller, el algebra de Lie su(1,1) y una evolucion adiabatica. Este algoritmo resuelve en principio el decimo problema de Hilbert, un problema clasicamente no computable. Este algoritmo es una generalizacion del algoritmo propuesto por Tien D. Kieu, con base en el oscilador armonico; y del algoritmo propuesto por los autores, con base en la caja de potencial infinita

Revista de la Sociedad Colombiana de FísicaJan 1, 20061 citation

Es la computación cuántica el fin de la computación clásica

Jorge Zapata Godoy, Emilio Brenes Pacheco, César Rodríguez Bravo

La investigación se realiza con el objetivo de relacionar la computación clásica y la computación cuántica, así como determinar cuáles serán las implicaciones que podríamos ver en un futuro. Como consecuencia, surgen las preguntas: ¿Será la computación clásica eventualmente reemplazada por su contraparte cuántica? ¿Vendrá esta tecnología a revolucionar totalmente el viejo paradigma de las computadoras clásicas o tendrá una aplicación específica en ciertas industrias y se complementará con las computadoras actuales? En este artículo responderemos a ambas preguntas por medio de la ejecución de varios algoritmos de prueba cuyos resultados son la base de nuestro análisis. Cabe destacar que este artículo no se basa en simulaciones, sino en ejecuciones reales de algoritmos cuánticos en una computadora cuántica de 15-qubits.

LogosJan 14, 20210 citations

Algoritmos cuánticos para la resolución del problema de satisfacibilidad booleana

María Prieto Gil

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.

Jun 1, 20190 citations

Estudio comparativo de soluciones algorítmicas bajo el contexto de la computacion clásica y computación cuántica : estudio comparativo de soluciones algorítmicas bajo el contexto de la computacion clásica y computación cuántica para problemas de busqueda

Ivan Dario Simbaña Farinango

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.

May 28, 20260 citations

Computación Cuántica: Introducción al paradigma cuántico universal, situación actual, herramientas de desarrollo, estudio e implementación del algoritmo Quantum Counting clásico, desarrollo de una versión simplificada del algoritmo y aplicaciones prácticas

Todor Krasimirov Ivanov

La computación cuántica es un campo innovador en las ciencias de computación e información que actualmente se encuentra en vías de desarrollo con algoritmos e infraestructuras cada vez más elaborados. Este tipo de computación, en concreto la computación cuántica universal de puertas, posee un gran potencial de cálculo y, a lo largo de todo el proyecto, se detallan las características y propiedades que la hacen una computación alternativa y ventajosa frente a la computación clásica en problemas de cálculos masivos. Además de incluir la información más relevante sobre el contexto histórico de la mecánica cuántica, por la cual la computación cuántica se ha podido desarrollar, se introducen los conceptos principales de esta para la construcción de algoritmos con el paradigma de programación cuántico universal, analizando, a su vez, las ventajas que supone la utilización de dicho paradigma. También, se estudia el estado actual de la computación cuántica referente a tecnologías como los entornos de programación cuántica y las infraestructuras de máquinas cuánticas existentes de empresas relevantes como IBM o Microsoft. Una vez introducidos los conceptos fundamentales sobre computación cuántica, se detalla la construcción del algoritmo cuántico Quantum Counting con el cual se cuenta el número de soluciones de una determinada función objetivo abstracta, adaptable a muchos problemas reales, demostrando una ventaja cuántica frente a los algoritmos clásicos más eficientes que realizan el mismo trabajo. Análogamente, se investiga y se desarrolla un algoritmo cuántico muy reciente, más simple y eficiente que el Quantum Counting clásico, denominado Simpler Quantum Counting, el cual facilita la ejecución en ordenadores cuánticos reales por la reducción sustancial del número de operadores controlados. Estos dos algoritmos, el clásico y el simplificado, son ejecutados en simuladores y máquinas cuánticas utilizando funciones prueba con el correspondiente análisis de resultados. Finalmente, se enumeran una serie de aplicaciones prácticas del Quantum Counting útiles para la implementación de otros algoritmos cuánticos como el Quantum Amplitude Estimation o el algoritmo de Grover, además de otras utilidades en campos como la inteligencia artificial o problemas de explosión combinatoria, en los que la computación cuántica supone ventajas en cuanto a complejidad computacional. Abstract: Quantum computing is a breakthrough field in information and computation science whose quantum software and hardware are in a constant development process improving increasingly its possibilities. This type of computation, specifically the universal quantum gates computation, holds a great potential of calculation and its features and properties are explained all along the project, demonstrating the advantages against classical computation when it comes to massive calculation problems. Firstly, fundamental concepts of universal quantum computation are introduced focusing on algorithm construction using the quantum gate programming paradigm which advantages are analyzed. Also, an historic context of quantum mechanics is given to trace the evolution that brought quantum computing to reality. Moreover, quantum computing state-of-art is studied researching recent technologies as quantum programming environments and physical quantum devices of outstanding corporations as IBM or Microsoft. Once all fundamental concepts of quantum computing are explained, the construction of a quantum algorithm called Quantum Counting is detailed, whose purpose is to find the number of solutions of a given abstract function adaptable to real life problems. The quantum advantage of this algorithm is demonstrated by comparing it to the best classical algorithms with the same purpose. Then, a simplified version of the Quantum Counting algorithm is studied and implemented, named as Simpler Quantum Counting. It is a brand new quantum algorithm which reduces the number of controlled operators in its related quantum circuit easing, consequently, its physical execution in quantum machines. These two quantum algorithms, the classical version and the simplified one, are run in quantum simulators and physical quantum computers including their corresponding results and discussions. At last, several useful applications of the Quantum Counting are listed and presented as future jobs. Some of them are associated with other quantum algorithms implementation as Quantum Amplitude Estimation or Grover’s algorithm and the rest are aimed to artificial intelligence or combinatorial explosion problems where quantum computing is advantageous in terms of computational complexity.

Jan 1, 20200 citations

Algoritmos Cuánticos Variacionales: Teoría y Simulación

Rafael Blasco Lorenzo

La computación cuántica es un paradigma de computación basado en las propiedades de la mecánica cuántica. Su unidad básica de información es el qubit, que permite estar en una superposición de múltiples estados. Esta propiedad, entre otras, permite la representación y manipulación de información de maneras que presentan potenciales ventajas respecto de otros tipos de computación. Sin embargo los ordenadores cuánticos actuales están limitados por la cantidad de ruido que sufren sus qubits. Los algoritmos cuánticos variacionales son una familia de arquitecturas de algoritmos cuánticos que surgen como una oportunidad en esta situación ya que debido a sus propiedades son capaces de alcanzar buenos resultados a pesar del ruido. La efectividad de esta aproximación depende de diversos factores como la tarea a resolver, el circuito cuántico utilizado, la optimización clásica, etc. que deben ser adaptados en cada situación. El objetivo de este proyecto es comprender y estudiar esta familia de arquitecturas desde sus fundamentos teóricos, y posteriormente realizar simulaciones que pongan en práctica estos conceptos. Para ello en la primera sección se definen los principios teóricos de la computación cuántica, para luego definir la arquitectura común entre los algoritmos variacionales y finalmente concretar en tres implementaciones relevantes, que después de exponerse serán implementadas con herramientas software de simulación de computación cuántica.

Jul 31, 20260 citations