No es el caso de que las computadoras cuánticas puedan invertir TODAS las funciones unidireccionales.
La efectividad de la computadora cuántica para resolver funciones unidireccionales (Wikipedia) depende de la facilidad con la que se puede verificar una solución.
En informática, una función unidireccional es una función que es fácil de calcular en cada entrada, pero difícil de invertir dada la imagen de una entrada aleatoria.
- ¿Cuáles son las principales diferencias entre una computadora cuántica universal y una computadora clásica?
- No entiendo por qué el enredo cuántico no se puede usar para la comunicación. ¿Pueden algunos explicarlo?
- ¿La programación será diferente para las computadoras cuánticas, o solo habrá compiladores diferentes?
- ¿Cuáles son las ventajas de tener un título en física y trabajar como programador?
- ¿De qué está hecha la espuma cuántica?
Esta introducción del artículo de Wikipedia sobre funciones unidireccionales es fácil como si fuera una categoría bien definida. Las computadoras cuánticas pueden invertir algunas funciones unidireccionales cuando su potencia, basada en la superposición de qubits enredados, le permite presentar todas las soluciones posibles a la lógica que representa la función fácilmente calculada. Cuando ese es el caso, el algoritmo de Grover reduciría el tiempo de búsqueda de T a la raíz cuadrada de T. Además, un algoritmo inteligente podría reducir el tiempo por el orden de log (T) Es evidente que muchas funciones las consideramos unidireccionales; Los algoritmos de hash, por ejemplo, no son manejados fácilmente por unas pocas puertas de lógica cuántica. La complejidad de la lógica involucrada sugiere que pasará algún tiempo antes de mantener el enredo y la superposición para que muchos pasos sean factibles.
Aun así, el éxito en esa etapa del proceso de inversión puede no ser suficiente. Una vez que se encuentra la respuesta, el programa debe extraer los bits de la respuesta de la palabra qubit enredada. Aquí, nuevamente, el algoritmo de Grover proporciona un modelo, sin embargo, su tiempo de ejecución es del orden de sqrt (T). Para funciones criptográficas complejas de un solo sentido, la aplicación de la palabra fácil amplía un poco la definición de “poder”.
Si alguna función unidireccional dada se presta a un programa de computación cuántica que pueda resolver la inversión en el tiempo de registro (T) dependería de la invención de un algoritmo único tal como el Algoritmo de Shor resuelve el problema de factorización.
