Estudio del problema del subgrupo oculto y sus implicaciones en algoritmos cuánticos

David Alejandro Rey Contreras

Published Jul 15, 2026• 0 citations

Abstract

Este documento estudia el problema del subgrupo oculto (HSP) en grupos abelianos finitos, un problema central en la computación cuántica que sirve como marco unificador para varios algoritmos cuánticos de gran relevancia. Para ello, desarrolla los fundamentos de análisis de Fourier en grupos abelianos finitos y los conceptos básicos de computación cuántica, introduce la transformada cuántica de Fourier y explica su implementación mediante circuitos cuánticos. Finalmente, presenta el algoritmo cuántico para resolver el HSP, analiza su correctitud y complejidad, y muestra cómo algoritmos como los de Deutsch, Simon y Shor pueden interpretarse como aplicaciones de este mismo enfoque, destacando la ventaja computacional que ofrece frente a los métodos clásicos.

Related papers

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

Nicolás Contreras Ortiz

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.

Jun 23, 20260 citations

Implementación Cuántica de un Algoritmo Genético

Mauricio Solar, Vicente Figueroa, Francisco Manriquez +2 more

Este trabajo proporciona una visión generalizada del estado actual de los algoritmos genéticos cuánticos (QGAs), mostrando los avances realizados en esta área de investigación los últimos 24 años. Los QGAs combinan conceptos de la computación cuántica y los algoritmos genéticos clásicos (CGAs), lo que les permite abordar problemas complejos de optimización y búsqueda de manera eficiente. Se presentan los principales hallazgos y contribuciones de estos algoritmos cuánticos destacando las tendencias y los enfoques más prometedores, así como los desafíos y limitaciones que deben superarse. Se presentan nuevos enfoques y técnicas de implementación de QGAs, incluyendo operadores genéticos cuánticos y esquemas de codificación eficientes que contribuyen a mejorar el rendimiento y la convergencia de los algoritmos. Se comparan los QGAs y otros enfoques similares, como los CGAs y los algoritmos cuánticos puros, destacando las ventajas y desventajas relativas de los QGAs en comparación a sus versiones clásicas. Se muestra también una implementación de QGA utilizando la biblioteca Qiskit. Se presentan la selección de los métodos usados para la generación de la población inicial, el cruzamiento y la mutación de las distintas poblaciones de los circuitos cuánticos simulados en los experimentos realizados, ejemplificando las ventajas significativas que estos pueden traer en comparación con los enfoques clásicos.

Memoria Investigaciones en IngenieríaDec 13, 20242 citations

Fundamentos de lenguajes de programación cuántica y sus consecuencias en sistemas clásicos

Alejandro Díaz-Caro, Pablo E. Martínez López

La computación cuántica plantea un nuevo modelo de computación que incorpora formas inéditas de pensar los problemas. Conceptos claves para ello son el enredo cuántico, el paralelismo y el no clonado. Si bien estos conceptos no tienen un correlativo en la computación clásica, su estudio puede tener consecuencias en el estudio del comportamiento probabilista y no-determinista de programas clásicos. Asimismo, la simple observación de estas nuevas formas de pensar los problemas es fuente de inspiración para resolver problemas clásicos. Este proyecto se centra en el diseño de lenguajes de programación cuántica como fin en sí mismo, y como medio para el desarrollo de lenguajes de programación clásica con características novedosas.

Jun 6, 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

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

Una conjetura cuántica

Ramón Rebull Camarasa

La información cuántica se ha convertido en un área central de la investigación científica y tecnológica, impulsada por la posibilidad de algoritmos que superan claramente a sus equivalentes clásicos. En este artículo, se introducen los fundamentos matemáticos básicos de este modelo y se revisan algunos ejemplos que ilustran su potencial. Pero más allá de estas primeras ventajas, surge una cuestión esencial: ¿cuáles son los verdaderos límites de la computación cuántica? La Conjetura Cuántica ofrece un marco teórico para analizar hasta dónde puede llegar realmente la aceleración cuántica frente al cómputo clásico y en qué tipos de problemas no cabe esperar tal ventaja.

Jan 1, 20260 citations