Algoritmo de Shor para niños
El algoritmo de Shor es un método especial que usa la computación cuántica para encontrar los números que, al multiplicarse, dan un número más grande. Esto se llama "descomponer en factores" o "factorizar". Fue creado por un científico llamado Peter Shor.
Este algoritmo es muy rápido para encontrar los factores de un número, mucho más rápido que los métodos que usan las computadoras normales para números muy grandes.
Si el algoritmo de Shor se pudiera usar en una computadora cuántica real, podría hacer que algunos sistemas de seguridad que usamos hoy en día, como el RSA, ya no fueran tan seguros. El sistema RSA protege mucha de nuestra información en internet, como cuando compramos algo o enviamos mensajes. Funciona usando un número muy grande que es el resultado de multiplicar dos números primos muy grandes. Las computadoras normales tardarían muchísimo tiempo en encontrar esos dos números primos, pero el algoritmo de Shor podría hacerlo rápidamente.
El algoritmo de Shor es un método que usa probabilidades. Esto significa que da la respuesta correcta con una probabilidad muy alta. Si por alguna razón no acierta a la primera, se puede repetir para asegurar el resultado.
En 2001, un grupo de científicos de IBM logró usar el algoritmo de Shor en una computadora cuántica pequeña. Consiguieron descomponer el número 15 en sus factores 3 y 5. Fue un gran avance para la computación cuántica.
Datos para niños Algoritmo de Shor |
||
---|---|---|
Problema que resuelve | Factorización | |
Clase de complejidad | Algoritmo cuántico | |
Tiempo de ejecución | ||
Complejidad espacial | O(log N) |
Contenido
¿Qué es la factorización de números?
La factorización es como un rompecabezas de números. Consiste en encontrar los números más pequeños (llamados factores) que, al multiplicarse entre sí, dan como resultado un número más grande. Por ejemplo, los factores del número 15 son 3 y 5, porque 3 multiplicado por 5 es igual a 15.
Para números pequeños, es fácil encontrar los factores. Pero cuando los números son muy, muy grandes, esta tarea se vuelve increíblemente difícil para las computadoras normales.
¿Por qué es importante el algoritmo de Shor?
El algoritmo de Shor es muy importante por su relación con la seguridad en internet.
La seguridad en internet y los números primos
Muchos de los sistemas que protegen nuestra información en línea, como el sistema RSA, se basan en que es muy difícil factorizar números grandes. Estos sistemas usan números que son el resultado de multiplicar dos números primos enormes. Esos números primos son como la "clave secreta".
Las computadoras normales tardarían miles de millones de años en encontrar esos números primos si el número original es lo suficientemente grande. Esto hace que nuestros datos estén seguros.
El impacto de la computación cuántica
El algoritmo de Shor, al ser ejecutado en una computadora cuántica, podría encontrar esos números primos mucho más rápido. Esto significa que podría "romper" la seguridad de sistemas como RSA. Por eso, los científicos están investigando nuevas formas de proteger la información que sean seguras incluso frente a las computadoras cuánticas.
¿Cómo funciona el algoritmo de Shor? (De forma sencilla)
El algoritmo de Shor tiene dos partes principales:
La parte clásica
Esta parte se puede hacer con una computadora normal. Su trabajo es preparar el problema de factorización para la parte cuántica. El objetivo es transformar el problema de encontrar los factores de un número en un problema diferente: encontrar el "período" de una función matemática.
- Primero, se elige un número al azar.
- Luego, se comprueba si ese número comparte algún factor con el número grande que queremos factorizar. Si lo hace, ¡ya encontramos un factor!
- Si no, se usa la parte cuántica para encontrar el "período" de una función especial.
La parte cuántica: Encontrar el período
Aquí es donde entra en juego la computación cuántica. Las computadoras cuánticas pueden hacer cosas que las computadoras normales no pueden, como estar en muchos estados al mismo tiempo (esto se llama superposición cuántica).
- Una computadora cuántica puede evaluar una función en muchos puntos a la vez.
- Luego, usa una técnica especial llamada "transformada cuántica de Fourier". Esta técnica ayuda a organizar la información de la superposición de tal manera que, al hacer una medición, es muy probable que obtengamos el "período" que necesitamos.
- Una vez que se encuentra el período, la parte clásica puede usarlo para calcular los factores del número original.
Si el algoritmo falla en algún paso, se puede repetir hasta que se encuentre el factor.
Galería de imágenes
Véase también
En inglés: Shor's algorithm Facts for Kids
- Computación cuántica
- Algoritmo de Grover