Cómo la física cuántica conduce al descifrado de algoritmos comunes

El auge de la computación cuántica y su implicaciones porque los estándares de cifrado actuales son bien conocidos. Pero, ¿por qué exactamente las computadoras cuánticas deberían ser especialmente hábiles para descifrar el cifrado? La respuesta es un ingenioso juego de malabares matemáticos llamado el algoritmo de Shor. La pregunta que aún queda es: ¿Qué es lo que hace este algoritmo que hace que las computadoras cuánticas sean mucho mejores para descifrar el cifrado? En este video, YouTubero minimo de fisica lo explica en su tradicional estilo de dibujos animados de pizarra.

“La computación cuántica tiene el potencial de hacer que sea muy, muy fácil acceder a datos encriptados, como tener un sable de luz que puedes usar para atravesar cualquier candado o barrera, sin importar cuán fuerte sea”, dice minutephysics. "El algoritmo de Shor es ese sable de luz".

De acuerdo con el video, el algoritmo de Shor funciona con el entendimiento de que para cualquier par de números, eventualmente multiplicando uno de ellos por sí mismo llegará a un factor del otro número más o menos 1. Por lo tanto, adivina el primer número y lo factoriza. sumando y restando 1, hasta llegar al segundo número. Eso desbloquearía el cifrado (específicamente RSA aquí, pero funciona en algunos otros tipos) porque entonces tendríamos ambos factores.

Una de las razones por las que este proceso aparentemente simple se basa en el desarrollo de poderosas computadoras cuánticas es que encontrar la potencia correcta para multiplicar el primer número para encontrar un factor del segundo número (N) ± 1 requiere una enorme cantidad de intentos. La clave de cifrado es un número bastante largo y, por lo tanto, la potencia puede ser de 1 a millones. Pero la fuerza bruta no es la razón por la que las computadoras cuánticas funcionan tan bien aquí.

Los superpoderes de las superposiciones

Brevemente, gracias a la superposición cuántica, una computadora cuántica puede calcular muchas respuestas para una sola entrada. Sin embargo, el video dice que solo obtienes una salida de respuesta a la vez, con probabilidades adjuntas. Para resolver ese problema, el cálculo se configura de modo que las respuestas incorrectas interfieran entre sí, de modo que es probable que solo se genere la respuesta correcta (o al menos una buena suposición). Ese cálculo, que se centra en encontrar la potencia adecuada p, es el algoritmo de Shor.

Todo es extremadamente matemático e involucra la ayuda de Algoritmo de Euclides, así como una transformada cuántica de Fourier que convierte una serie de superposiciones de superposiciones en ondas sinusoidales que interfieren constructivamente (se suman entre sí) o destructivamente, es decir, se anulan entre sí. El video dice que, esencialmente, puedes manipularlo para que solo 1/p se guarda, con todas las demás respuestas interferidas destructivamente fuera de la contienda. Una vez que estás allí, es un paseo por el parque para encontrar p, lo que hace que encontrar los dos factores de cifrado sea mucho más fácil. Mire el video completo para obtener más detalles y tal vez para sentirse un poco más inteligente.

Por cierto, Peter Shor es sigue prosperando, y si está interesado en una inmersión profunda en cómo rompió Internet, aquí hay otro video donde el hombre mismo explica cómo se dio cuenta su obra maestra homónima.