Cómo convertir una computadora cuántica en un generador de números aleatorios perfecto

La coincidencia pura y verificable es difícil de encontrar. Dos nuevas oraciones muestran cómo hacer fábricas de números aleatorios a partir de computadoras cuánticas.

Diga "excelencia cuántica" en cualquier reunión de informáticos, y probablemente los verá rodar los ojos. Esta frase se refiere a la idea de que las computadoras cuánticas pronto cruzarán la línea, más allá de la cual podrán realizar tareas que son extremadamente difíciles para las computadoras clásicas con relativa facilidad. Y hasta hace poco, estas tareas se consideraban de poca utilidad para aplicaciones reales, de ahí el giro de los ojos.

Pero ahora que se dice que el procesador de Google está cerca de ese objetivo, la superioridad cuántica inminente puede tener un uso importante: generar aleatoriedad pura.

La aleatoriedad es importante para casi todo lo que sucede en la infraestructura informática y de comunicaciones. En particular, se utiliza para cifrar datos que protegen todo, desde conversaciones ordinarias hasta transacciones financieras y secretos de estado.

La aleatoriedad real confirmada (imagínela como una propiedad que existe en una secuencia de números y hace imposible predecir el próximo número en una secuencia) es extremadamente difícil de encontrar.

Pero esta situación puede cambiar cuando las computadoras cuánticas demuestran su superioridad. Estas primeras tareas, que desde el principio simplemente tenían que demostrar la superioridad de la tecnología, también pueden dar una verdadera coincidencia certificada. "Estamos felices de recibir esto", dijo John Martinis , físico de la Universidad de California en Santa Bárbara, que dirige el proyecto de computación cuántica en Google. "Esperamos que este sea el primer uso de una computadora cuántica".

Aleatoriedad y entropía

Aleatoriedad y teoría cuántica van de la mano como truenos y relámpagos. En ambos casos, el primero es una consecuencia inevitable del segundo. En el mundo cuántico, a menudo se dice que los sistemas se encuentran en una combinación de varios estados, los llamados "Superposición". Cuando mide un sistema, se "colapsa" en uno de estos estados. Y aunque la teoría cuántica le permite calcular las probabilidades de lo que descubrirá en una medición, el resultado exacto siempre será fundamentalmente aleatorio.

Los físicos han estudiado esta conexión para crear generadores de números aleatorios. Todos se basan en mediciones de algún tipo de superposición cuántica. Y aunque para la mayoría de los métodos de generación de números aleatorios que las personas necesitan, estos sistemas son suficientes, puede ser difícil trabajar con ellos. Además, es muy difícil demostrar al escéptico la aleatoriedad real de estos generadores de números aleatorios. Finalmente, algunos de los métodos más efectivos para generar aleatoriedad confirmada requieren diseños sofisticados de múltiples dispositivos separados por grandes distancias.


Google AI Lab presenta el procesador cuántico Bristlecone 72-Qubit en 2018

Una propuesta reciente para extraer la aleatoriedad de un solo dispositivo, una computadora cuántica, utiliza el llamado. la tarea de muestreo, que será una de las primeras pruebas de superioridad cuántica. Para entenderlo, imagina que te dieron una caja de azulejos. En cada mosaico hay varias unidades y varios ceros: 000, 010, 101, etc.

Si solo hay tres bits, entonces hay ocho opciones posibles. Sin embargo, puede haber varias copias de cada mosaico en la caja. Puede haber 50 fichas con la etiqueta 010 y 25 fichas con la etiqueta 001. La distribución de las fichas determina la probabilidad de que extraiga accidentalmente una ficha en particular. En nuestro caso, puede extraer el mosaico 010 con una probabilidad dos veces mayor que el mosaico 001.

La tarea de muestreo incluye un algoritmo informático equivalente a extraer aleatoriamente fichas de la caja con una distribución de fichas específica. Cuanto mayor sea la probabilidad definida para cualquier mosaico en la distribución, más probable es que el algoritmo extraiga ese mosaico.

Por supuesto, el algoritmo no extrae mosaicos reales de un cuadro real. Simplemente produce aleatoriamente un número binario de 50 bits de longitud, después de haber recibido una distribución que determina la probabilidad deseada para cada una de las posibles líneas de 50 bits de longitud.

Para una computadora clásica, la complejidad de esta tarea crece exponencialmente con un aumento en el número de bits en una cadena. Pero para una computadora cuántica, se espera que la tarea permanezca aproximadamente igual para 5 bits y 50.

Una computadora cuántica comienza diciendo que todos sus bits cuánticos, qubits, están en un cierto estado. Supongamos que todos comienzan con 0. Cómo las computadoras clásicas pueden trabajar con bits clásicos usando el llamado. puertas lógicas y computadoras cuánticas manipulan qubits usando sus puertas cuánticas equivalentes cuánticas.

Sin embargo, las puertas cuánticas pueden colocar qubits en estados extraños. Por ejemplo, un tipo de puerta puede colocar un qubit que comienza con un valor de 0 en una superposición de 0 y 1. Si luego mide el estado de un qubit, se colapsa aleatoriamente a 0 o 1 con la misma probabilidad.

Aún más extraño, las puertas cuánticas que pueden trabajar con dos o más qubits al mismo tiempo pueden hacer que los qubits se enreden entre sí. En este caso, los estados de los qubits están entrelazados de modo que ahora todos estos qubits pueden describirse utilizando solo un estado cuántico.

Si lleva un grupo de puertas cuánticas a un lugar y luego las hace funcionar con un conjunto de qubits en una secuencia determinada, este será un circuito cuántico. En nuestro caso, para derivar una cadena aleatoria de 50 bits, puede construir un circuito cuántico que coloque 50 qubits en una superposición de estados que describa la distribución que necesita.

Al medir qubits, toda la superposición se colapsa aleatoriamente en una sola cadena de 50 bits. La probabilidad de que colapse en una determinada línea está determinada por la distribución determinada por el contorno cuántico. La medición de qubits es similar a la forma en que un hombre con los ojos vendados alcanza una bolsa y accidentalmente saca una línea con la distribución.


Scott Aaronson, Especialista en Informática, Universidad de Texas en Austin

¿Y cómo se relaciona todo esto con los números aleatorios? Es importante que la cadena de 50 bits seleccionada por la computadora cuántica contenga mucha entropía, una medida de desorden o imprevisibilidad y, por lo tanto, aleatoriedad. "Y esto, de hecho, puede tener consecuencias muy graves", dijo Scott Aaronson , un especialista en TI de la Universidad de Texas en Austin, quien ideó un nuevo protocolo. "No porque sea el uso más importante de las computadoras cuánticas, creo que está lejos de serlo, sino porque parece ser quizás el primer uso de las computadoras cuánticas que se puede poner en práctica".

El protocolo de Aaronson para generar números aleatorios es bastante simple. Una computadora clásica primero recolecta algunos bits aleatorios de alguna fuente confiable, y luego usa esta "semilla de aleatoriedad" para generar una descripción del contorno cuántico. Los bits aleatorios determinan el tipo de puertas cuánticas y la secuencia en la que deben actuar en qubits. Una computadora clásica envía una descripción a una computadora cuántica que implementa un circuito cuántico, mide qubits y devuelve una cadena de 50 bits. Por lo tanto, resulta ser seleccionado al azar de la distribución definida por el contorno.

Luego repita este proceso varias veces, por ejemplo, 10 veces para cada circuito cuántico. Una computadora clásica utiliza pruebas estadísticas para garantizar que las líneas de salida contengan una buena cantidad de entropía. Aaronson demostró (en parte en un trabajo publicado escrito en colaboración con Lijie Chen y en parte en un trabajo aún por publicar) que, bajo ciertas suposiciones razonables de que tales tareas son computacionalmente complejas, ninguna computadora clásica puede generar tal entropía en tiempo comparable al tiempo durante el cual una computadora cuántica crea una selección tan aleatoria de la distribución. Después de las comprobaciones, la computadora clásica recolecta todas las cadenas de 50 bits y las alimenta al conocido algoritmo clásico. "Produce una cadena larga, casi perfectamente aleatoria", dijo Aaronson.

Trampa cuántica

El protocolo Aaronson es el más adecuado para computadoras cuánticas con una cantidad de qubits de 50 a 100. Cuando la cantidad de qubits excede estos límites, la complejidad computacional no permite el uso de este protocolo incluso para las supercomputadoras clásicas. En este caso, otro esquema para generar números aleatorios verificables usando computadoras cuánticas entra en escena. Utiliza una técnica matemática existente con el nombre complejo trapdoor libre de garras. "Esto suena peor que la realidad", dijo Umesh Wazirani , especialista en TI de la Universidad de California en Berkeley, quien desarrolló una nueva estrategia que fue ayudada por Zvika Brackerski , Paul Cristiano , Urmila Mahadev y Thomas Vidik .

Introduce nuestra caja. En lugar de entrar en él y extraer una cadena, le arrojamos una cadena de n bits, lo llamamos x, y luego eliminamos otra cadena de n bits. El cuadro de alguna manera coincide con la línea de entrada y la línea de salida. Pero tiene una propiedad especial: para cada x hay otra línea de entrada y, que produce exactamente la misma línea de salida.

En otras palabras, hay dos líneas de entrada únicas, x e y, para las cuales el cuadro devuelve la misma línea de salida z. Este triple, x, y y z, se llama garra. Cuadro en el lenguaje de la informática: una función. Esta función es fácil de calcular, es decir, para cualquier x e y es fácil calcular z. Pero si solo toma xyz, entonces encontrar y, y toda la garra, es imposible incluso para una computadora cuántica.


Urmila Mahadev, Umesh Vazirani y Thomas Vidik

La única forma de obtener toda la garra es encontrar información adicional, la llamada una trampa

Vazirani y sus colegas quieren usar tales funciones no solo para obligar a las computadoras cuánticas a generar números aleatorios, sino también para verificar que las computadoras cuánticas realmente funcionen de acuerdo con las leyes cuánticas, lo cual es necesario para generar confianza en secuencias aleatorias.

El protocolo comienza con una computadora cuántica que coloca n qubits en una superposición de todas las cadenas de n bits. Luego, la computadora clásica envía una descripción del contorno cuántico, determinando la función que se aplicará a la superposición: la función trampa sin garras. Una computadora cuántica implementa un circuito sin saber nada sobre la trampa.

En esta etapa, la computadora cuántica entra en un estado en el que un conjunto de sus qubits está en una superposición de todas las cadenas de n bits, y el otro contiene el resultado de aplicar la función a esta superposición. Dos conjuntos de qubits están enredados entre sí.

Una computadora cuántica que mide un segundo conjunto de qubits colapsa aleatoriamente una superposición en un determinado resultado z. El primer conjunto de qubits se contrae en una superposición similar de dos cadenas de n bits, x e y, ya que cualquiera de ellos puede servir como entrada para una función que emite z.

Una computadora clásica recibe un valor de salida de z, y luego hace una de dos cosas. En la mayoría de los casos, le pide a la computadora cuántica que mida los qubits restantes. Esto colapsa la superposición en xo en y, con una probabilidad del 50%. Esto es equivalente a obtener aleatoriamente 0 o 1.

A veces, para probar una computadora cuántica para cuántica, una computadora clásica solicita una medición especial. La medición y su resultado están diseñados para que una computadora clásica con la ayuda de una trampa a la que solo él tenga acceso pueda garantizar que el dispositivo que responde a sus solicitudes sea verdaderamente cuántico. Vazirani y sus colegas demostraron que si el dispositivo da la respuesta correcta a una dimensión particular sin usar el colapso de qubits, será equivalente a encontrar una garra sin trampa. Y esto es imposible. Por lo tanto, al menos un qubit (dando 0 o 1 al azar) debería colapsar en el dispositivo. "El protocolo crea un qubit probado dentro de una computadora cuántica en la que no confiamos", dijo Vazirani.

Este qubit probado proporciona un bit de información verdaderamente aleatorio para cada encuesta; Se puede usar una secuencia de tales consultas para crear largas cadenas aleatorias.

Este esquema puede funcionar más rápido que el protocolo Aaronson, pero tiene un defecto claro. "Con un conteo de qubits de 50 o 70, no será práctico", dijo Aaronson.

Aaronson todavía está esperando la aparición de un sistema de Google. "Si la calidad de lo que nos muestran es suficiente para lograr realmente la superioridad cuántica es una gran pregunta", dijo.

Si la empresa tiene éxito, entonces la aleatoriedad cuántica garantizada ya está en nuestra puerta. "Creemos que será un mercado útil y prometedor, y esto es lo que nos gustaría ofrecer a la gente", dijo Martinis.