Búsqueda no estructurada mediante cómputo cuántico

Alfredo Miguel Arteaga Cruz

CITEDI IPN INICIO
→
CITEDI Community
→
Tesis
→
Ver ítem

dc.provenance	Arteaga Cruz, Alfredo Miguel. (2022). Búsqueda no estructurada mediante cómputo cuántico. (Maestría en Ciencias en Sistemas Digitales). Instituto Politécnico Nacional, Centro de Investigación y Desarrollo de Tecnología Digital, México.
dc.contributor	Oscar Humberto Montiel Ross
dc.contributor	Ulises Orozco Rosas
dc.creator	Alfredo Miguel Arteaga Cruz
dc.date.accessioned	2023-02-22T01:33:16Z
dc.date.available	2023-02-22T01:33:16Z
dc.date.created	2023-02-21
dc.date.issued	2023
dc.identifier.citation	Arteaga Cruz, Alfredo Miguel. (2022). Búsqueda no estructurada mediante cómputo cuántico. (Maestría en Ciencias en Sistemas Digitales). Instituto Politécnico Nacional, Centro de Investigación y Desarrollo de Tecnología Digital, México.	es_US
dc.identifier.uri	http://mexculture.citedi.mx/handle/123456789/1529
dc.description	RESUMEN: En este trabajo de tesis se presenta un algoritmo híbrido cuántico capaz de resolver el problema de las N-Reinas mediante el algoritmo de Grover. Se realizaron comparaciones de funcionamiento con algoritmos clásicos como: Backtracking, Branch and Bound y Programación Lineal, capaces de resolver el problema para diferente número de reinas. En Backtracking las soluciones se identifican mediante la recursividad, omite las combinaciones que no satisfacen con las restricciones y avanza cuando la posición sea considerada como parte de la solución o retrocede en caso contrario. En Branch and Bound se optimiza el uso del método de la fuerza bruta, identificando soluciones óptimas mediante divisiones en el conjunto de combinaciones, se delimita el espacio de búsqueda eliminando las ramificaciones que no favorecen a la solución. La Programación Lineal es un método matemático que optimiza máximos o mínimos en una función objetivo, trabaja con restricciones e identifica las combinaciones seguras y delimita el área de búsqueda para colocar al menos una reina por _la, columna o diagonal (positiva o negativa). El cómputo cuántico permitió procesar la información mediante qubits, identficando una o varias soluciones. Las soluciones se codificaron mediante un registro cuántico en donde los estados representaban las posiciones. Se identifica las combinaciones que cumplieron con las restricciones antes mencionadas. Las circuitos cuánticos base para esta investigación fueron el oráculo y el algoritmo de Grover. La integración de los elementos antes mencionados permitió desarrollo del algoritmo híbrido cuántico, comprobándose que existe disminución en complejidad computacional y en consecuencia disminución en tiempo de procesamiento. ABSTRACT: This thesis work presents a hybrid quantum algorithm capable of solving the N-Queens problem using Grover's algorithm. Performance comparisons were made with classical algorithms such as Backtracking, Branch and Bound, and Linear Programming, which can solve the problem for diffrent numbers of queens. In Backtracking, the solutions are identified by recursion, and it omits the combinations that do not satisfy the constraints and move forward when the position is considered as part of the solution or backward otherwise. Branch and Bound optimizes the use of the brute force method, identifying optimal solutions through divisions in the set of combinations; the search space is delimited by eliminating the branches that do not favor the solution. Linear Programming is a mathematical method that optimizes maxima or minima in an objective function, works with constraints, identifies safe combinations, and delimits the search area to place at least one queen per row, column, or diagonal (positive or negative). Quantum computation allows processing the information using qubits, identifying one or more solutions. Then, the solutions were encoded using a quantum register where the states represented the positions. Finally, the combinations that complied with the restrictions mentioned above were identified. The base quantum circuits for this research were the oracle and Grover's algorithm. The integration of the elements mentioned above allowed the development of the hybrid quantum algorithm, proving that there is a decrease in computational complexity and, consequently,a decrease in processing time.	es_US
dc.language	spa
dc.language.iso	es	es_US
dc.publisher	IPN	es_US
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	http://creativecommons.org/licenses/by-nc-nd/4.0
dc.subject	Cómputo cuántico	es_US
dc.subject	Algoritmo híbrido cuántico	es_US
dc.subject	Implementación cuántica	es_US
dc.subject	Búsqueda no estructurada	es_US
dc.title	Búsqueda no estructurada mediante cómputo cuántico	es_US
dc.type	info:eu-repo/semantics/masterThesis
dc.audience	generalPublic
dc.contributorcvu	OSCAR HUMBERTO MONTIEL ROSS, 201311, asesorTesis
dc.contributorcvu	ULISES OROZCO ROSAS, 278020, AsesorTesis
dc.creatorcvu	ALFREDO MIGUEL ARTEAGA CRUZ, 1015354
dc.subjectrepo	info:eu-repo/classification/cti/7