Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/3602| Jumbled matching cuántico | |
| Julio César Juárez Xochitemol | |
| Edgar Leonel Chávez González | |
| Acceso Abierto | |
| Atribución | |
| computación cuántica, algoritmo de Grover, emparejamiento entremezclado, aceleración cuadrática quantum computing, Grover’s algorithm, jumbled matching, quadratic speed-up | |
| La computación cuántica nace de la observación de Richard Feynman de la dificultad de simular sistemas cuánticos en la máquina RAM. El interés por este modelo de cómputo llegó con el algoritmo de Shor, donde la factorización de números, un problema en la intersección entre NP y co-NP, y del cual dependen muchos sistemas criptográficos, se pudo hacer en tiempo polinomial. Otra sorpresa fue el algoritmo de Grover, que permite encontrar un objeto en una colección en menos pasos que el tamaño de la colección; contrario incluso a la intuición natural. Con esta motivación, se aborda un problema que también requiere una cantidad lineal de pasos; pero en donde la condición de paro es más compleja que la condición de igualdad. En este trabajo se estudia el problema de jumbled pattern matching (JPM), donde dada una cadena w y un patrón p tales que w, p ∈ ∑ ∗ y |p| ≤ |w|, buscamos los sub-patrones de que estén construidos con los mismos elementos que p; es decir, todos los sub-patrones que sean una permutación de p. El JPM es especialmente útil en problemas de biocomputación relacionados con análisis de patrones, como espectrometría de masa para interpretación de datos, descubrimientos de SNP, alineamiento de secuencias, y aplicaciones de biosecuenciación. Explorando la computación cuántica, se presenta un algoritmo de complejidad O(√N) que genera la solución al problema de jumbled pattern matching casi seguramente; por tanto, acelerando las mejores soluciones clásicas en un factor cuadrático. Quantum computing was born from Richard Feynman’s observation of the difficulty of simulating quantum systems in the RAM machine. The interest in this computational model arose with the Shor’s algorithm, where the integer factorization, a problem in the intersection between NP and co-NP, on which many cryptography systems depend, it can be performed in polynomial time. Another surprise was the Grover’s algorithm, which allows finding an object among a collection in fewer steps than the size of the collection; contrary even to natural intuition. With this motivation we work on a problem that also requires a linear number of steps; but where the halting condition is more complex than the equality condition. In this work we approach the jumbled pattern matching problem, where given a text and a pattern p such that w, p ∈ ∑ ∗ and |p| ≤ |w|, we search for the sub-patterns in built with the same elements of p; that is, all sub-patterns that are a permutation of p. JPM is specially useful in bio computing problems related to pattern analysis, as mass spectrometry for data interpretation, SNP discovery, sequence alignment, and bio sequencing applications. Exploring quantum computing, we present an algorithm whose complexity is O(√ N) that generates the solution for jumbled pattern matching almost certainly; therefore, speeding-up the best classical solutions in a quadratic factor. | |
| CICESE | |
| 2021 | |
| Tesis de maestría | |
| Español | |
| Juárez Xochitemol, J.C. 2021. Jumbled matching cuántico. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 74 pp. | |
| TECNOLOGÍA DE LA AUTOMATIZACIÓN | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_ Julio César Juárez Xochitemol_25 ago 2021.pdf | Versión completa de la tesis | 720.19 kB | Adobe PDF | Visualizar/Abrir |