Como no se dio respuesta, se ha establecido una bandera solicitando que esta pregunta se convierta en una wiki comunitaria.
Los comentarios de Aaron Sterling, Sasho Nikolov y Vor se sintetizaron en la siguiente resolución, que está abierta para la discusión de la wiki comunitaria:
Resuelto: con respecto a los algoritmos clásicos que generan números, muestras o trayectorias de simulación, la lógica matemática estricta requiere que se acepten las cuatro proposiciones siguientes, o ninguna de ellas:
- Podemos descartar un algoritmo clásico de tiempo polinómico para generar números aleatorios. [1]
- "Podemos descartar un algoritmo clásico de tiempo polinómico para muestrear la distribución de salida de una computadora cuántica, bajo el único supuesto de que la jerarquía polinómica es infinita". [2]
- "No podemos simular [una trayectoria mecánica cuántica] de la manera habitual ... hay demasiadas variables". [3]
- La tesis extendida de la Iglesia de Turing (TCE) se descarta, por la rigurosa razón de que los algoritmos clásicos no pueden generar números aleatorios. [4]
Para iniciar la discusión, aquí hay respuestas afirmativas y negativas que, aunque cada una es defendible, se exageran deliberadamente. Un argumento fuertemente afirmativo podría ser:
Afirmativo: estas cuatro afirmaciones reflejan teoremas que, para respetar el rigor, requieren que nunca hablemos de algoritmos clásicos que generen números aleatorios, muestras aleatorias o simulaciones cuánticas, sino que hablemos solo de algoritmos clásicos que generan números pseudoaleatorios y (por extensión) muestras pseudoaleatorias y simulaciones pseudocuánticas.
Habiendo entendido esto, las cuatro afirmaciones son verdaderas. Además, para evitar ambigüedades y evitar confusiones, los matemáticos deberían alentar a los científicos e ingenieros a colocar el prefijo "pseudo-" en casi todos los usos de "simulación cuántica", "aleatoria".
Un argumento fuertemente negativo podría ser:
Negativo: Estas afirmaciones (y sus teoremas formales asociados) son mensajes que nos dirigen a un distrito matemático de “luz roja” al estilo Lakatos donde se nos invita a abrazar (lo que podría llamarse) con entusiasmo las disciplinas de la seudoaleatoriedad. , pseudo-muestreo y pseudo-simulación ... prácticas matemáticas que son divertidas por una razón deliciosamente pecaminosa: logran efectos matemáticos que la lógica formal dice que son imposibles. Por lo tanto, ¿qué podría ser más mágico y más divertido que esta conclusión: las cuatro declaraciones de la resolución son formalmente verdaderas, pero prácticamente falsas?
Habiendo entendido esto, las cuatro declaraciones son falsas. Además, dado que la mayoría de los abrazos prácticos de "aleatoriedad", "muestreo" y "simulación cuántica" ocurren en este entorno mágico, en el que los temas asociados con la complejidad de Kolmogorov y las evaluaciones oraculares se pasan por alto deliberadamente, son los matemáticos quienes deberían alterar su uso.
Sin embargo, de manera realista, ¿cómo deberían los teóricos de la complejidad expresar sus hallazgos en relación con la aleatoriedad, la muestra y la simulación ... por un lado, con miras a mantener un equilibrio razonable de claridad, concisión y rigor ... y por otro lado, con una visión para mantener una comunicación de bajo ruido con otras disciplinas STEM El último objetivo es especialmente importante, ya que las capacidades prácticas aumentan constantemente en campos como la criptografía, las pruebas estadísticas, el aprendizaje automático y la simulación cuántica.
Sería muy útil (y divertido también) leer respuestas bien razonadas, ya sea afirmativas o negativas.
La pregunta que se hace es
¿Cuál es / son los roles generalmente aceptados de verificación en las definiciones teóricas de complejidad asociadas al muestreo, la simulación y la prueba de la tesis de Turing de la Iglesia extendida (TCE)?
La respuesta preferida son las referencias a artículos, monografías o libros de texto que analizan estos temas en profundidad.
Si esta literatura resulta ser escasa o insatisfactoria, entonces (después de dos días) convertiré esta pregunta en un wiki de la comunidad preguntando:
¿Cuál es / son los roles razonables y adecuados de verificación en las definiciones teóricas de complejidad asociadas al muestreo, la simulación y la prueba de la tesis extendida de Turing de la Iglesia (TCE)?
Antecedentes
La pregunta formulada está motivada por el hilo reciente "¿Qué significaría refutar la tesis de Church-Turing? , específicamente las respuestas (excelente en mi humilde opinión) dadas por Gil Kalai y por Timothy Chow
En la pregunta formulada, la frase "definiciones teóricas de la complejidad correctas y / o aceptadas" debe interpretarse como que restringe a Alice de afirmaciones inverosímiles como las siguientes:
Alice: Aquí está mi muestra experimental de dígitos binarios verdaderamente aleatorios calculados por mi red óptica lineal (un fotón).
Bob: Aquí está mi muestra simulada de dígitos pseudoaleatorios calculada por una máquina clásica de Turing.
Alice: Lo siento, Bob ... tu muestra es algorítmicamente compresible, y la mía no lo es. ¡Por lo tanto, mis datos experimentales demuestran que la TEC es falsa! "
En ausencia de cualquier asociación de verificación con muestreo, el razonamiento de Alice es impecable. En otras palabras, ¿deberían los teóricos de la complejidad considerar que la TEC ya había sido refutada formalmente ... hace décadas?
Desde un punto de vista práctico, los métodos de simulación asociados al muestreo de trayectoria cuántica en espacios de estado varietales están siendo ampliamente utilizados en muchas disciplinas de la ciencia y la ingeniería. Es por eso que las definiciones teóricas de la complejidad del muestreo que respetan el papel central de la verificación (que es inseparable de la replicabilidad) en ciencia e ingeniería serían muy bienvenidas para los científicos e ingenieros en ejercicio ... especialmente si estas definiciones estuvieran acompañadas de teoremas que describan la complejidad computacional de muestreo verificado
Edición agregada: gracias a una colaboración entre la Universidad de Ginebra y la compañía id Quantique , es perfectamente factible completar este ejercicio en realidad.
Aquí hay 1024 bits aleatorios que están certificados por id Quantique como algorítmicamente incompresibles:
0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011
¿Deberíamos aceptar ahora la afirmación: "La tesis de TEC está refutada"?
Si no, ¿qué motivos debemos dar?
fuente
Respuestas:
La esencia de la pregunta es, dado que la probabilidad cuántica es una fuente de aleatoriedad verdadera, ¿cómo afecta eso a la tesis extendida (o eficiente, o de tiempo polinómico) de Church-Turing?
La respuesta es que, por conjetura, no lo afecta. Las personas conjeturan que BPP = P, es decir, que los algoritmos aleatorizados pueden ser aleatorizados con generadores de números pseudoaleatorios con sobrecarga polinómica. La fe en los PRNG como un reemplazo para la verdadera aleatoriedad es una razón por la cual las personas creerían la tesis extendida de Church-Turing si no fuera por el cálculo cuántico.
fuente