Algoritmo de grover
Páginas: 8 (1937 palabras)
Publicado: 8 de diciembre de 2011
| Algoritmo de Grover. |
| “Informe Trabajo de Investigación para la asignatura de Análisis de Algoritmos” |
| |
Cristian Pasten A.
2011
-------------------------------------------------
Índice
*
1. Introducción 3
2. Conceptos relevantes 4
2.1.- La Computación Cuántica 5
3. Algoritmo de Grover 6
3.1 Definición 6
3.2 Procedimiento 7
4. Conclusión 8
5.Bibliografía 9
* -------------------------------------------------
Introducción
El presente documento pretende explicar al lector, junto a diversos conceptos básicos sobre ciencias cuánticas, el algoritmo de Grover, un veloz algoritmo mecánico cuántico de búsqueda, creado para trabajar en una máquina que aún no existe, pero que según la evolución de los computadores en el transcurso de losúltimos 20 años y considerando que el primer computador que me tocó operar, en el año 1992, tenía 768Kb. de RAM, 20 Mb. de disco y corría a una velocidad de 66Mhz, en comparación con la potencia de los actuales equipos disponibles en el mercado, es perfectamente esperable que el primer computador cuántico, active sus circuitos al mundo antes de lo que pensamos.
Ante tal supuesto y cuando latecnología lo permita, el algoritmo de Grover seguramente podrá ser utilizado para problemas cotidianos de búsqueda obteniendo resultados muy superiores a los que entregan en la actualidad, los clásicos algoritmos de búsqueda, consolidándose como el primer algoritmo cuántico aplicable en algo útil.
* -------------------------------------------------
Conceptos relevantes
La definición del término"cuántico" se refiere a todo lo que existe en medidas diminutas, específicamente y para este estudio, partículas que forman frecuencias a partir de un comportamiento en forma de ondas, constituidas por energía a un nivel subatómico.
La teoría cuántica (rama de la física que trata con las partículas elementales y las propiedades microscópicas de la materia), según David Deutsch, sugiere que laspartículas elementales no se localizan en una única posición en un momento dado, sino que recorren varias trayectorias de forma simultánea, aceptando la interpretación de “universos múltiples”, donde lo que se observa como una sola partícula, es en realidad una, de innumerables entidades similares en diferentes universos, afectándose entre sí a través de un proceso llamado “interferenciacuántica”, el autor sugiere además, que los fenómenos cuánticos no pueden observarse de manera directa, pero que es posible deducir su existencia y atributos midiendo los efectos que ellos tienen, en cosas que sí son observables directamente.
“El cómputo cuántico es posible, según ese punto de vista, porque un ordenador cuántico realiza grandes cantidades de cómputos separados en diferentes universos yentonces comparte los resultados a través de la interferencia cuántica.” (Deutsch, 2008).
Entre las posibles aplicaciones del cómputo cuántico destacan las "búsquedas algorítmicas" para descifrar códigos. Como un ejemplo práctico de aplicación para nuestra época, podríamos tomar las claves WPA para redes wirefire, desencriptables a través de ataques de diccionario (a fuerza bruta) pero que sinembargo, continúan siendo un problema debido al excesivo uso de recursos que exigen los algoritmo clásicos, ya que se requiere ir probando las claves del diccionario una a una, entonces los recursos necesarios son proporcionales al número de respuestas posibles.
-------------------------------------------------
2.1.- La Computación Cuántica
Enfocando el estudio hacia la computación cuántica,un primer acercamiento la define como un paradigma distinto al de la computación digital, a la que estamos acostumbrados y en la que todo el procesamiento de información se basa en una combinación de ceros y unos porque trabaja con voltajes. Actualmente se considera que la tecnología de transistores, está limitada por los materiales de fabricación de los microchips y por el tamaño, ya que...
| “Informe Trabajo de Investigación para la asignatura de Análisis de Algoritmos” |
| |
Cristian Pasten A.
2011
-------------------------------------------------
Índice
*
1. Introducción 3
2. Conceptos relevantes 4
2.1.- La Computación Cuántica 5
3. Algoritmo de Grover 6
3.1 Definición 6
3.2 Procedimiento 7
4. Conclusión 8
5.Bibliografía 9
* -------------------------------------------------
Introducción
El presente documento pretende explicar al lector, junto a diversos conceptos básicos sobre ciencias cuánticas, el algoritmo de Grover, un veloz algoritmo mecánico cuántico de búsqueda, creado para trabajar en una máquina que aún no existe, pero que según la evolución de los computadores en el transcurso de losúltimos 20 años y considerando que el primer computador que me tocó operar, en el año 1992, tenía 768Kb. de RAM, 20 Mb. de disco y corría a una velocidad de 66Mhz, en comparación con la potencia de los actuales equipos disponibles en el mercado, es perfectamente esperable que el primer computador cuántico, active sus circuitos al mundo antes de lo que pensamos.
Ante tal supuesto y cuando latecnología lo permita, el algoritmo de Grover seguramente podrá ser utilizado para problemas cotidianos de búsqueda obteniendo resultados muy superiores a los que entregan en la actualidad, los clásicos algoritmos de búsqueda, consolidándose como el primer algoritmo cuántico aplicable en algo útil.
* -------------------------------------------------
Conceptos relevantes
La definición del término"cuántico" se refiere a todo lo que existe en medidas diminutas, específicamente y para este estudio, partículas que forman frecuencias a partir de un comportamiento en forma de ondas, constituidas por energía a un nivel subatómico.
La teoría cuántica (rama de la física que trata con las partículas elementales y las propiedades microscópicas de la materia), según David Deutsch, sugiere que laspartículas elementales no se localizan en una única posición en un momento dado, sino que recorren varias trayectorias de forma simultánea, aceptando la interpretación de “universos múltiples”, donde lo que se observa como una sola partícula, es en realidad una, de innumerables entidades similares en diferentes universos, afectándose entre sí a través de un proceso llamado “interferenciacuántica”, el autor sugiere además, que los fenómenos cuánticos no pueden observarse de manera directa, pero que es posible deducir su existencia y atributos midiendo los efectos que ellos tienen, en cosas que sí son observables directamente.
“El cómputo cuántico es posible, según ese punto de vista, porque un ordenador cuántico realiza grandes cantidades de cómputos separados en diferentes universos yentonces comparte los resultados a través de la interferencia cuántica.” (Deutsch, 2008).
Entre las posibles aplicaciones del cómputo cuántico destacan las "búsquedas algorítmicas" para descifrar códigos. Como un ejemplo práctico de aplicación para nuestra época, podríamos tomar las claves WPA para redes wirefire, desencriptables a través de ataques de diccionario (a fuerza bruta) pero que sinembargo, continúan siendo un problema debido al excesivo uso de recursos que exigen los algoritmo clásicos, ya que se requiere ir probando las claves del diccionario una a una, entonces los recursos necesarios son proporcionales al número de respuestas posibles.
-------------------------------------------------
2.1.- La Computación Cuántica
Enfocando el estudio hacia la computación cuántica,un primer acercamiento la define como un paradigma distinto al de la computación digital, a la que estamos acostumbrados y en la que todo el procesamiento de información se basa en una combinación de ceros y unos porque trabaja con voltajes. Actualmente se considera que la tecnología de transistores, está limitada por los materiales de fabricación de los microchips y por el tamaño, ya que...
Leer documento completo
Regístrate para leer el documento completo.