Recientemente me encontré con un artículo de Coudron y Yuen sobre la expansión de la aleatoriedad utilizando dispositivos cuánticos. El principal resultado del trabajo es que es posible generar aleatoriedad "infinita" a partir de un número constante de fuentes (es decir, el número de bits aleatorios generados depende solo del número de rondas del protocolo y no del número de fuentes )
Ingenuamente, esto me parece que el resultado permite la desrandomización de cualquier algoritmo aleatorio con fuentes cuánticas, e implicaría algún tipo de contención de clases de complejidad aleatorias dentro de una clase cuántica correspondiente.
Pero realmente no entiendo la teoría de la información cuántica, y estoy seguro de que me faltan muchas sutilezas. Sin mencionar que si tales afirmaciones fueran posibles, los autores lo habrían hecho. Entonces mi pregunta es:
¿La existencia de "expansión de aleatoriedad infinita" como se describe en el documento (y todo el trabajo relacionado) implica algún tipo de declaraciones de aleatorización para clases de complejidad aleatorias? Y si no, Pórque no ?
Actualización: Scott Aaronson me señaló esta excelente descripción general de alto nivel del área y del documento anterior. Lamentablemente todavía estoy confundido :).
fuente
Respuestas:
Esta es una gran pregunta, Suresh!
Nuestro resultado de expansión de aleatoriedad no implica ningún resultado teórico de complejidad. He aquí una manera de entender el resultado: creemos que la mecánica cuántica gobierna el mundo, y en este supuesto, no somos los dispositivos cuánticos que generan auténtica, verdadera, la aleatoriedad de información teórica.
Sin embargo, imagine que desconfía de estas cajas que afirman hacer estas cosas cuánticas inestables y generan aleatoriedad (para algunos, esto puede no tomar demasiado imaginar). No quieres lidiar con qubits. Todo lo que entiendes son cadenas de bits clásicas.
La expansión de aleatoriedad es un protocolo en el que usted, como verificador clásico, puede interactuar con un grupo de cuadros negros (piense en ellos como probadores que no se comunican ), y después de ejecutar un protocolo con estos cuadros negros, ha certificado que sus resultados contienen muy alta entropía, si los probadores pasan. Además, la cantidad de aleatoriedad con la que comenzó es mucho menor que la entropía de salida que certificó.
En otras palabras, es una prueba interactiva para la generación de aleatoriedad.
Por lo tanto, el único aspecto de "desrandomización" es argumentar que el protocolo en sí mismo requiere una pequeña aleatoriedad de inicio. Pero el resultado es muy poco aleatorizado: la salida producida por los cuadros es aleatoriedad verdadera, no pseudoaleatoriedad (es decir, sin supuestos computacionales).
fuente