Pensándolo bien...

Ya estamos acostumbrados a las referencias a la computación cuántica y la potencialidad de la misma. Lo que es menos usual es la verificación de que un proceso de computación cuántica ha tenido lugar. La incertidumbre cuántica y el hecho de que la medición de un sistema cuántico puede cambiar su estado, convierte la verificación cuántica en un proceso, en gran medida, inalcanzable. En todo caso viene siendo una ocupación de los científicos de la computación desde hace un tiempo.

Hasta ahora, este cometido se ha abordado desde alternativas, en gran medida clásicas, como son, comparando con una simulación clásica, útil en sistemas cuánticos pequeños. En el caso de que los resultados de la computación cuántica coincidan con los de la simulación clásica, se evidencia que el proceso cuántico se realizó correctamente. En otros casos, se repite el proceso cuántico varias veces y se observa la consistencia de los resultados. En otros casos se usan protocolos de verificación cuántica, como el debido a Mahadev que permiten a un ordenador clásico verificar los resultados de uno cuántico, haciendo uso de interacciones criptográficas entre ambos ordenadores. Finalmente, cabe destacar las demostraciones de supremacía cuántica que suponen llevar a cabo un cálculo extremadamente difícil o imposible para un ordenador clásico, pero factible para uno cuántico. Estas técnicas, aunque pueden proporcionar evidencias de que ha tenido lugar un proceso cuántico, pero no son una prueba definitiva, ya que hay inherente la incertidumbre cuántica de la Mecánica Cuántica.

Un algoritmo cuántico muy popular es el denominado algoritmo de Shor para factorizar números. Lo propuso Peter Shor en 1994 y es más eficiente que cualquier otro, para factorizar números enteros. La servidumbre es que requiere muchos qubits y presenta una alta tasa de corrección de errores en los ordenadores cuánticos actualmente en uso. Los pasos que concreta son:  1) Elegir un número aleatorio, a, menor que N, el número a factorizar; 2) verificar si a y N tienen un factor en común. Si es así, entonces se ha encontrado un factor de N. (Es recomendable el uso del algoritmo extendido del máximo común divisor que, además de encontrar el máximo común divisor de dos números, también encuentra la forma de expresar el MCD en términos de los dos números originales, es decir, encuentra unos coeficientes x e y tales que: ax + by = mcd(a, b). (Un ejemplo simplificado del algoritmo extendido del MCD, lo concretamos en obtener el MCD de 48 y 30, así como los coeficientes x e y. 1) Primero, dividimos el número más grande (48) por el más pequeño (30) para obtener un cociente (q) y un resto (r). 48 = 1(30) + 18; 2) Reemplazamos el número más grande por el número más pequeño, y el número más pequeño por el resto del paso anterior, y repetimos el proceso. 30 = 1(18) + 12. 3). Continuamos este proceso hasta que el resto sea cero. 18 = 1(12) + 6 y luego 12 = 2(6) + 0. 4) Llegados a este punto, el último resto no nulo es el MCD de los dos números originales. Así que el MCD de 48 y 30 es 6. Para obtener los coeficientes x e y, partimos de las últimas dos ecuaciones (no las que tienen resto cero) y las resolvemos para el resto. Luego sustituimos hacia atrás hasta llegar a una ecuación que expresa el MCD en términos de los dos números originales: así, empezamos con 18 = 1(12) + 6, lo que se puede reescribir como 6 = 18 - 1(12). Ahora sustituimos 12 de la ecuación anterior, obteniendo 6 = 18 - 1(30 - 1(18)) = 2(18) - 1(30). Finalmente, sustituimos 18 de la primera ecuación, obteniendo 6 = 2(48 - 1(30)) - 1(30) = 2(48) - 3(30). De esta forma, los coeficientes son x = 2 e y = -3 y el MCD de 48 y 30 es 6).  Vemos que es un algoritmo eficaz dispuesto para la programación en ordenadores convencionales. 3) Si con la aplicación del anterior algoritmo del mcd extendido,  a y N no tienen factores en común, hay que calcular el periodo de la función mod N. Este es un problema difícil para los ordenadores clásicos, pero en los cuánticos se puede hacer de forma eficiente, usando la transformada de Fourier cuántica. Esto nos deja una superposición de estados, cada uno de los cuales representa un valor de f(x). (La transformada de Fourier cuántica es una operación cuántica equivalente de la transformada de Fourier discreta. Es un algoritmo fundamental en la computación cuántica y es un componente clave del algoritmo de Shor para la factorización de números enteros. En términos generales, la transformada de Fourier clásica, parte de una función de tiempo (o espacio) y la descompone en sus frecuencias componentes. De manera similar, la Transformada de Fourier cuántica, toma un estado cuántico, que puede ser visto como una superposición de diferentes estados de base, y lo transforma en una superposición de estados de base en el espacio de frecuencias. La forma operativa se concreta en: 1) tenemos un estado cuántico de n qubits en el estado |x⟩, la transformada de Fourier cuántica lo lleva al estado |y⟩, donde |y⟩ = TFC(|x⟩) |j⟩, siendo N=, Σ es el símbolo de suma, ω = exp(2π i / N), i es la unidad imaginaria, y |j⟩ son los estados de la base. Una de las propiedades notables de la TFC es que puede realizarse de manera eficiente en un ordenador cuántico. Mientras que una transformada de Fourier discreta clásica, tiene una complejidad de tiempo de O(N log N), la TFC puede realizarse en una complejidad de tiempo de O(n²), donde n es el número de qubits. La TFC es esencial en el algoritmo de Shor porque transforma el problema de encontrar el período de una función, que es un problema difícil para un ordenador clásico, en el problema de encontrar la frecuencia de un estado cuántico, que es algo que un ordenador cuántico puede hacer eficientemente. Finalmente, destacar que la TFC es un algoritmo bastante abstracto y requiere un conocimiento sólido de la computación cuántica y la mecánica cuántica para comprenderlo cabalmente. Además, su implementación práctica en un ordenador cuántico real es un desafío debido a problemas como el ruido y los errores de corrección de fase, que complican el tratamiento de una parte central del algoritmo de Shor. Aquí, el período es el número más pequeño r tal que  = 1 (mod N). Como hemos dicho es un problema complicado para los ordenadores convencionales, especialmente para números grandes. Sin embargo, los ordenadores cuánticos, que en el caso del algoritmo de Shor es del siguiente modo: 1) Se inicializa un sistema cuántico de dos registros en un estado de superposición; 2) Se aplica la transformación de la función f(x)=mod N a la superposición, lo que da lugar a un estado entrelazado donde cada estado en el primer registro está asociado con el estado correspondiente f(x) en el segundo registro. 2) Se mide el segundo registro. Dada la naturaleza del entrelazamiento cuántico, el estado del primer registro colapsa a una superposición de estados que corresponden a los valores de x para los cuales f(x) es igual al valor medido en el segundo registro. Este conjunto de valores x forman una secuencia periódica. 3) A continuación, se aplica la TFC al primer registro, que transforma el estado del primer registro a un estado en el que es probable medir los valores que corresponden a la frecuencia de la secuencia periódica, es decir, el inverso del período. 3) Finalmente, se mide el primer registro. Este paso tiene una alta probabilidad de producir un valor que es un múltiplo de 1/r, donde r es el período de la función f(x). Este valor se puede utilizar para determinar r usando técnicas clásicas. Así se puede obtener de forma eficiente el período de la función f(x)=mod N, que es un paso crucial en el algoritmo de Shor para la factorización de números. Una vez que disponemos del período r de la función, podemos encontrar un factor de N calculando el máximo común divisor de N y  ± 1. Repitiendo los pasos indicados podremos encontrar todos los factores de N

El interés de un problema como este radica en la velocidad a la que se factorizan los números, con mucha mayor rapidez que los algoritmos clásicos. Recordemos que muchos sistemas de criptografía actuales, incluyendo el RSA (Rivest-Shamir-Adleman) es uno de los primeros sistemas de criptografía de clave pública que se utiliza ampliamente para la transmisión segura de datos, desarrollado en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman. La encriptación y la desencriptación se realizan utilizando dos tipos de claves: una clave pública, que puede ser conocida por cualquiera, y una clave privada, que solo conoce el receptor del mensaje. De forma simplificada, el funcionamiento consiste en 1) Generación de claves: el receptor elige dos números primos grandes, p y q, y los multiplica para obtener n. Luego, elige un número e, que es coprimo (no tiene factores comunes excepto 1) con (p-1)(q-1). La clave pública es entonces el par (n, e). El receptor también calcula un número d, tal que (ed) mod ((p-1)*(q-1)) = 1. Este número d es la clave privada. 2) Encriptación: cualquiera puede enviar un mensaje seguro al receptor. Para hacer esto, convierte su mensaje en un número m (esto se puede hacer de varias maneras, como por ejemplo usando el código ASCII para las letras), luego se calcula c = mod n. El número c es el mensaje cifrado. Y, finalmente, 3) Desencriptación: cuando el receptor recibe el mensaje cifrado c, puede descifrarlo usando su clave privada d. Esto se hace calculando m =  mod n. El número m es el mensaje original. Justamente, la cuestión radica en que lo que hace que RSA sea seguro (hasta cierto punto) es el hecho de que, aunque es fácil calcular n a partir de p y q, es extremadamente difícil hacer lo contrario: es decir, factorizar n en p y q. Esto se denomina la "dureza" del problema de factorización, y es el principal pilar de seguridad de RSA. Precisamente, con la llegada de las computadoras cuánticas, esta dureza se puede superar; el algoritmo de Shor proporciona una forma eficiente de factorizar un número entero en un ordenador cuántico, lo que podría romper la seguridad de RSA.

Es ésta un área de investigación activa en el campo de la criptografía cuántica. Una cuestión relevante, como decíamos, es la verificación de que ha tenido lugar un proceso cuántico. En suma, estando al mando de un ordenador cuántico al que se le solicita un cálculo como el indicado, como sabemos si ha hecho algo cuántico. Una forma de detectarlo es la velocidad, como hemos precisado en el algoritmo de Shor. ¿Cómo saber si los cálculos se han hecho correctamente? En un ordenador clásico se pueden seguir los pasos de forma minuciosa. Los sistemas cuánticos resisten estos exámenes. Desde su funcionamiento interno, que es sumamente complejo, dado que la descripción del estado interno de un ordenador cuántico con solo unos cientos de qubits, requeriría una memoria del calibre del universo visible. Es más, en el hipotético caso de que se pudiera llegar a la descripción el estado interno de un ordenador cuántico, es una superposición de muchos estados clásicos diferentes, con la servidumbre de que cuando se mide un estado cuántico, colapsa a uno de los estados clásicos. La apariencia íntima de un ordenador cuántico es idéntica a la de un ordenador clásico del mismo número de bits clásicos.

Mahadev, hoy investigadora postdoctoral en Berkeley, es una de las investigadoras interesadas en esta cuestión y la ha abordado con éxito reconocido por los más acreditados investigadores del área, que coinciden en afirmar que su aportación es “una de las ideas más destacadas que han surgido en la interfaz de la computación cuántica y la informática teórica en años recientes." Básicamente, implica el uso de la criptografía clásica en el entorno cuántico, formulando un protocolo para verificar un cálculo cuántico. El que un ordenador cuántico pueda resolver un problema que no puede resolver uno clásico, no implica que la solución sea difícil de verificar. En los problemas de factorización que henos ilustrado, la factorización de números grandes la puede resolver eficientemente un ordenador cuántico, estando fuera del alcance de un ordenador clásico, pero un ordenador clásico, aunque no lo pueda hacer, puede verificar si la factorización es correcta, ya que solamente tiene que multiplicar los factores obtenidos por el cuántico y comprobar si la respuesta es correcta. Otra cosa es que todos los problemas que puede resolver un ordenador cuántico tengan estas características. Muchos investigadores mantienen esta posición. De aquí surgió el interrogante de si es posible encontrar algún protocolo mediante el cual un ordenador cuántico pueda probar a un no-observador cuántico que realmente ha hecho lo que decía.

Vazirani propuso usar criptografía "post-cuántica", es decir, criptografía que los investigadores creen que está más allá de la capacidad de un ordenador cuántico. En 2016, mientras trabajaban en un problema diferente, Mahadev y Vazirani hicieron un avance crucial. En colaboración con otros científicos de la computación, desarrollaron una forma de usar la criptografía para obtener un ordenador cuántico para construir lo que se denomina un "estado secreto", cuya descripción es conocida por el verificador clásico, pero no por el ordenador cuántico. El método propuesto se basa en lo que se llama una función de "trampilla", que es fácil de realizar, pero difícil de revertir a menos que posea una clave criptográfica secreta.  Se requiere que la función sea "dos a uno", ya que cada salida corresponde a dos entradas diferentes. Por ejemplo, en la función que eleva al cuadrado dos números: además del número 0, cada salida tiene dos entradas correspondientes (por ejemplo, el 4 requiere 2 y −2). Un estado secreto se crea del siguiente modo: primero se le pide al ordenador que construya una superposición de todas las entradas posibles para la función. Luego, se le pide al ordenador que aplique la función a esta superposición gigante, creando un nuevo estado, que es una superposición de todas las salidas posibles de la función. Las superposiciones de entrada y salida se entrelazarán, lo que significa que una medición en una de ellas afectará instantáneamente a la otra. Luego, se le pide al ordenador que mida el estado de salida y nos dé el resultado. Esta medida colapsa el estado de salida a solo una de las posibles salidas, al tiempo que el estado de entrada se colapsa instantáneamente para que coincida, ya que están enredados; por ejemplo, si usa la función de elevar al cuadrado, entonces si la salida es el estado 4, la entrada colapsará hasta una superposición de los estados 2 y −2.  Como estamos usando un estado trampilla, disponemos de la clave secreta, con lo que podremos descifrar fácilmente los dos estados que componen la superposición. El ordenador cuántico no puede hacer esto. No puede medir la superposición de entrada para deducir de que está compuesto, porque la medida colapsaría el sistema, dejando al ordenador con una de las dos entradas, pero sin posibilidad de averiguar la otra.

Estas funciones trampilla es lo que Mahadev ha logrado en 2017, haciendo uso de la criptografía denominada aprendizaje con errores. Así creó una versión cuántica de computación a ciegas, gracias al cual los usuarios de la computación en la nube, pueden enmascarar los datos para que el ordenador no pueda leerlos en la nube, incluso aun cuando esté calculando con ellos. El método del estado secreto lo han usado varios científicos de la computación como Mahadev, Vazirani y Christiano y Vidick y Zvika Brakerski, del Instituto Weizmann, para refinar aún más estas funciones de trampilla, buscando desarrollar una forma infalible para para generar números aleatorios en un ordenador cuántico.

Una auténtica audacia lograr que un verificador clásico obligue a un ordenador cuántico a realizar las mediciones que él no podría realizar por sí mismo. La parte complicada radica en lograr que el ordenador cuántico comprometiera el estado que iba a medir, antes de saber qué tipo de medición iba a pretender medir el verificador. Si no fuere así, el ordenador podría engañar al verificador. Ahí es donde juega su papel el estado secreto. El protocolo de Mahadev requiere que el ordenador cuántico cree en primer lugar un estado secreto y que lo entrelace con el estado que se supone que vamos a medir y solamente entonces es cuando el ordenador sabe qué tipo de medición vamos a realizar. Al no conocer el ordenador el estado secreto, aunque el verificador si lo conoce, es imposible que el ordenador cuántico pueda hacer trampa sin dejar rastro. Si el resultado de la medición parece correcto, podemos estar seguros de que lo es.

La aportación de Mahadev se sitúa en las promesas de futuro. Requiere una potencia de cálculo enorme para ser práctico. Todo es cuestión de que las capacidades de los ordenadores se vean incrementadas. La unificación de la computación cuántica y la criptografía de Mahadev abren una ventana con aire fresco al porvenir de la computación y evidencian que los avances estimulan nuevos descubrimientos y ninguna dificultad parece, en suma, insalvable.