¿Cuál es el siguiente paso más allá de la computación cuántica?

Aunque en cierto sentido esta pregunta y respuesta están más allá de la física, (como se analiza a continuación) parecería haber una respuesta muy natural a esta pregunta, a saber:

Beyond Quantum Computers son computadoras que pueden superar la tesis de Church-Turing (consulte la página de Wikipedia con este nombre) y, de manera más general, pueden calcular el valor de verdad de las proposiciones que son indecidibles mediante un cálculo finito o, de manera equivalente, no derivables en un finito. número de pasos de un sistema de axioma fijo. Estos últimos son comúnmente (y un tanto descarados, en mi opinión) llamados "Oráculos" (consulte la página de Wikipedia para "Oracle Machine") por científicos informáticos, lógicos y otros investigadores de los fundamentos de las matemáticas.

La posición de la física convencional en las máquinas de Oracle

Hasta donde yo sé, todavía no hay dudas serias sobre si la clase de problemas que pueden resolver las computadoras cuánticas podría ser mayor que la clase que pueden resolver las máquinas deterministas de Turing. De hecho, parece que la corriente principal de la física cree que es probable que las computadoras que trascienden la tesis CT estén fuera de la física (ver esta Physics SE pregunta la hipótesis de Church-Turing como una ley fundamental de la física ). Creo que la mayoría de los trabajadores en este campo creerían, según la evidencia hasta ahora, que las computadoras cuánticas no superarán la tesis de Church-Turing, es decirque ningún algoritmo "implementado en cualquier computadora física" puede calcular nada que una máquina de Turing clásica no pueda en principio (el bit entre comillas es mi adición a la declaración habitual de la tesis CT). Tenga en cuenta que digo en principio: las secuencias en serie de los estados de la máquina de estado de Turing que componen muchos cálculos son tan fantásticamente largos que ninguna computadora clásica podría hacerlos en el lapso de vida de un universo físico que cumple con las leyes físicas conocidas. Las computadoras cuánticas pueden cambiar todo eso y llevar muchos cálculos que antes se consideraban prohibitivamente complejos para cualquier solución práctica al ámbito factible. Entonces, los factores que pueden diferenciar a las computadoras cuánticas de las clásicas son:

1. Almacenamiento masivo que surge del producto tensorial de estados cuánticos: un$N$qubit state vive en un espacio vectorial de$2^N$vectores de base cuántica, por lo que incluso si usamos solo dos niveles digitales de peso de superposición para cada vector de base separado en una superposición cuántica general, el espacio de estado finito almacena$2^N$bits o tiene$2^{2^N}$estados distinguibles;
2. Consumo de energía extremadamente bajo: las evoluciones del estado cuántico son unitarias, por lo tanto, reversibles, por lo tanto, no consumen energía según el principio de Landauer , aunque se requerirá energía para inicializar los qubits cuando la computadora se enciende por primera vez, de acuerdo con el principio de Landauer;
3. Velocidad masiva que surge del paralelismo masivo inherente a la evolución del espacio de computación representado por el estado cuántico;

Pero trascender la tesis de Church-Turing hasta ahora no parece ser un atributo de la computación cuántica.

Futuros especulativos basados ​​en física aún por descubrir

Ahora, la corriente principal de la física no tiene idea de cómo se podría implementar una máquina de oráculo, de hecho, algo que puede realizar una cantidad infinita de pasos de cómputo en un tiempo finito, por lo que, en este sentido, su pregunta está completamente más allá de la física. Sin embargo, si el punto de vista adoptado por fuertes platónicos matemáticos como Gödel es el correcto (una visión más extrema aún es la Hipótesis del Universo Matemático de Mark Tegmark ), entonces es concebible (pero aún no es necesario, fíjate) que tales oráculos son físicamente realizables. en alguna física aún desconocida. Para dar una idea de lo fantástico que es esto: si de hecho desarrolláramos tal tecnología, ¡la observación de verdaderos infinitos en el laboratorio se convertiría en una idea común y cotidiana!

Lo que Current Physics tiene que decir sobre los límites de Oracle Machines

Incluso si esto piensa en la física aún por descubrir (si es que es válida), hay algunas cosas que podemos decir sobre una máquina de oráculo u otra computadora que trasciende la tesis de Church-Turing, principalmente basada en la termodinámica y el principio de Landauer :

1. Tendría que estar contenido en un espacio de memoria finito: la inicialización de$N$bits de memoria (ya sea clásica o qubit) requiere, de acuerdo con el principio de Landauer, el gasto de trabajo útil$N\,k_B\,T\,\log 2$. Entonces, si nuestra física especulativa todavía está restringida por la termodinámica actual, la máquina del oráculo debe tener necesidades de energía finitas y, por lo tanto, debe estar contenida en una memoria limitada;
2. Curiosamente, una vez que hemos inicializado esta memoria, la ejecución de un número infinito de pasos reversibles en una computadora de este tipo puede no necesitar una cantidad infinita de energía. Por el contrario, cualquier algoritmo de oráculo no reversible no puede implementarse porque sus necesidades de energía serían infinitas debido a la necesidad de borrar la memoria y la necesidad de energía concomitante del principio de Landauer cada vez que ocurriera un borrado irreversible.

Por supuesto, en la Relatividad General no existe la conservación de la energía global, por lo que incluso puede haber una física especulativa especulativa que no esté sujeta a las restricciones anteriores.

Ejemplos de proposiciones indecidibles, es decir, aquellas que necesitan oráculos para la decisión

Dado que hace esta pregunta, supongo que la idea de proposiciones indecidibles e incomputables no le es habitual. Así que empieza mirando hacia arriba:

1. El problema de la detención en Wikipedia: la prueba es simple y se da allí: se puede demostrar que es imposible decidir con una máquina de Turing si cualquier programa de computadora general terminará normalmente o se quedará atascado en un ciclo infinito;
2. El cálculo de la Complejidad de Kolmogorov : vea nuevamente este, con la prueba de la siguiente declaración, en Wikipedia: aproximadamente: no existe un algoritmo que pueda decidir si una especificación completa de un objeto puede hacerse más pequeña y seguir siendo una especificación completa. Esta es una variación matemáticamente rigurosa de la paradoja de Berry .
3. Proposiciones indecidibles de Gödel : a grandes rasgos: que siempre hay relaciones entre los números naturales cuya verdad o falsedad no puede ser decidida por una máquina de Turing.
4. Uno que me gusta (más de acuerdo con lo que consideraría como mi experiencia) es el teorema de Novikov-Boone de que uno no puede decidir mediante la máquina de Turing si dos palabras en una presentación de grupo finito están hablando del mismo elemento de grupo o no;
5. Los números constantes e incomputables de Chaitin y los números reales indefinibles (¡eso es "la mayoría" de ellos, en la medida en que los computables son contables!) en general.

La mayoría de estos problemas implican calcular algo mediante el procedimiento de barra oblicua de Cantor (el procedimiento utilizado para mostrar que$\mathbb{R}$es incontable), así que daré una idea de ellos de la siguiente manera al mostrar la existencia de una función no computable (la prueba de la no computabilidad de la complejidad de Kolmogorov se destaca como un poco diferente de esta técnica; consulte la página Wiki). Supongamos que tenemos un lenguaje de programación. Ahora listamos todos los programas sintácticamente válidos en orden de su número de Gödel (podemos tomar esto como el "valor" del código como una cadena de dígitos ASCII). Esta lista está claramente en correspondencia biunívoca con los números enteros positivos. Luego seleccionamos los programas que calculan una función entera de una variable entera y los ponemos en una lista condensada: estos también son claramente una lista que se puede poner en correspondencia biyectiva con los enteros positivos.$\{f_i:\mathbb{N}\to\mathbb{N}\}_{i=1}^\infty$de funciones enteras computables con valores enteros. Estos incluyen todas las funciones que se pueden calcular en ese lenguaje informático en particular. Así que ahora consideramos la función:

y mostrar fácilmente que no está en la lista ($f_x(x) \neq f_x(x)+1 = f(x)$). Así que tendríamos que ampliar nuestro lenguaje informático para calcular esta función. Pero entonces nuestro nuevo lenguaje también tendría funciones no computables, precisamente por el mismo argumento.

Puede que le interese este artículo , Problemas NP-completos y Realidad física, de Scott Aaronson. No analiza el siguiente paso "después de las computadoras cuánticas" per se, pero compara el poder computacional de varias teorías físicas. Examina la física newtoniana, la mecánica cuántica no relativista, las correcciones no lineales de QM, las teorías de variables ocultas, la relatividad especial, la gravedad cuántica, la relatividad general y la interpretación de muchos mundos.

Por ejemplo, la sección 5 (en la página 7) examina lo que sucede si la mecánica cuántica no fuera estrictamente lineal (respuesta: si pudiéramos realizar cálculos sin errores, podríamos resolver problemas NP-completos en tiempo polinomial; si esto se puede hacer en una falla -Se desconoce la forma tolerante).

La idea es implementar algo como el algoritmo de búsqueda de Grover. Supongamos que nos dan una función de caja negra$f : {0,1}^n \to {0,1}$y queremos encontrar una entrada$x$tal que$f(x) = 1$. Usando$n$qubits podemos formar una superposición sobre todos$2^n$estados de entrada y evaluar$f$en él por lo que tenemos el estado$\sum_x |x\rangle |f(x)\rangle$; el problema ahora es que los "estados de respuesta" que queremos, donde el último qubit$|f(x)\rangle$tiene valor$1$, podría estar en superposición con aproximadamente$2^n$"estados de no respuesta". El algoritmo de Grover amplifica la diferencia entre estos estados en$O(2^{n/2})$pasos, pero esto es lo mejor que podemos hacer porque la evolución del tiempo en QM conserva el ángulo entre estados. En QM no lineal, esta restricción se elimina y potencialmente podemos amplificar la diferencia mucho más rápido.

La Sección 8 analiza el poder computacional de las curvas temporales cerradas, o viajes en el tiempo, que después de todo satisfacen todas las leyes de la relatividad general. Específicamente, algunas personas han tratado de resolver la paradoja del abuelo diciendo que solo se permiten historias consistentes; entonces la idea es arreglar las cosas para que encontrar una historia consistente, que el universo hace por nosotros "gratis", también resuelva un problema muy difícil, por ejemplo$\text{3SAT}$.

La parte que aborda su pregunta de manera más directa es la sección sobre gravedad cuántica, pero desafortunadamente, también es la sección que contiene la menor cantidad de resultados concretos.

Este tema es considerado, directa o indirectamente, en otras cuestiones de la física.SE.

La pregunta de la hipótesis de Church-Turing como ley fundamental de la física es casi lo contrario de la pregunta formulada aquí y mi respuesta plantea la posibilidad de que la física pueda permitir otros modelos computacionales, siendo las máquinas oraculares uno de ellos.

Luego respondiendo Teoría final en Física: ¿una prueba matemática de la existencia? , planteo la cuestión de que, precisamente por razones computacionales, no es obvio saber lo que podría ser una Teoría del Todo (que abarque toda la física). Traté de continuar con este punto haciéndome la pregunta ¿Qué es una Teoría del Todo (TOE)? .

También se abordaron puntos similares en una pregunta anterior . ¿Gödel excluye un TdE viable? .

En realidad, hay investigaciones técnicas que intentan evaluar los límites físicos de la calculabilidad. por ejemplo ,

varios investigadores [...] han señalado que la teoría cuántica no prohíbe, en principio, que algunas evoluciones rompan la tesis física de Church-Turing.

No repetiré el contenido detallado de las otras respuestas. Parece que un problema importante que limita la computabilidad es el carácter numerable de nuestras actividades mentales y teorías, todas ellas basadas en el lenguaje, en la sintaxis. Podemos hablar de entidades no numerables, como los números reales, pero no podemos mostrarlas, salvo algunas de ellas mediante dispositivos numerables ("es la raíz de esta ecuación"), y eso tiene limitaciones.

Parte de la investigación se ha dedicado a evaluar qué propiedad del universo físico podría imponer un límite similar a la computabilidad. Una de esas propiedades sería una limitación de la densidad de información en el espacio-tiempo , que parecen creer compatible con la física existente. Se pueden considerar varios dispositivos para hacer compatibles las ecuaciones de la física con la numerabilidad, como el uso de reales computables , que permiten desarrollar una forma de cálculo con números numerables, aunque no sin limitaciones.

También existe la posibilidad de que la física permita ir más allá de la limitación de Church-Turing. Esto en sí mismo puede tener una profunda implicación en nuestra forma de desarrollar las teorías. Las matemáticas axiomáticas que se utilizan para construir teorías físicas se basan fundamentalmente en la numerabilidad. A partir de los axiomas, podemos enumerar teoremas, esencialmente con una máquina de Turing. ¿Podría ser que modelos de computación más poderosos abrieran la puerta a un enfoque diferente para formalizar las matemáticas y la física? Otra forma de verlo es el isomorfismo de Curry-Howard que asocia pruebas de teoremas y programas de computadora. Si existieran nuevos modelos de computación, ¿corresponderían a nuevas formas de probar resultados matemáticos?

O por el contrario, podría darse el caso de que nuestro encierro en el discurso numerable nos impidiera percibir alternativas existentes en el mundo físico.

En una escala menos ambiciosa, existe la posibilidad de que algún fenómeno físico pueda mover las barreras de la complejidad, como parece ser capaz de hacerlo la computación cuántica. Esto en sí mismo es una hazaña con la que sería difícil soñar si no supiéramos la mecánica cuántica. Entonces, la física puede tener otras sorpresas guardadas.