En los hilos de 't Hooft se menciona varias veces la explosión exponencial. A nadie parece gustarle. Pero es parte integrante del formalismo estándar. Parece surgir de la regla del producto tensorial para los espacios de Hilbert.
¿Se conoce alguna alternativa que evite esta "explosión"? ¿Existe algún teorema que demuestre que es inevitable?
Respuesta
¿Demasiados anuncios?
heathrow
Puntos
25
El "teorema" no es exactamente un teorema, pero casi. El resultado principal lo descubrió Peter Shor y lo explica en una de las respuestas. Los sistemas cuánticos de tamaño N bits pueden resolver con seguridad unos cuantos problemas de búsqueda no triviales que se cree firmemente que son irresolubles por métodos clásicos sin probar exponencialmente muchas posibilidades, lo que requiere orden $2^N$ ensayos paralelos. Por lo tanto, es ciertamente (en el sentido físico, no matemático) inevitable hacer computación exponencial para simular la mecánica cuántica completa, ya que de lo contrario habría una solución clásica uniforme para todos los problemas que los ordenadores cuánticos pueden resolver, y esto es sumamente improbable, incluso en el improbable caso de que todos ellos sean resolubles mediante un complicado algoritmo probabilístico clásico inteligente separado.
El mejor ejemplo, por ser familiar, es la factorización de números enteros grandes. Clásicamente, se prueban un montón de factores hasta que se encuentra uno (no se puede fallar, ya que existe un algoritmo de tiempo polinómico recientemente descubierto que nos dice si existe un factor). La factorización se estudia mucho porque es importante en criptografía, y los mejores algoritmos son exponenciales en una potencia fraccionaria de la longitud del número. Si existe un buen algoritmo para factorizar, es probable que sea extremadamente complicado, y un algoritmo tan complicado seguramente no tendrá nada que ver con el algoritmo cuántico, que es relativamente simple comparado con cualquier algoritmo clásico hipotético (aunque encontrar el algoritmo cuántico ya fue un gran golpe de genio).
Si se dispone de un método para simular la mecánica cuántica sin la explosión exponencial, automáticamente se encuentra un buen algoritmo para la factorización y otros problemas relacionados que se pueden resolver mediante lo que ahora se conoce como la transformada cuántica de Fourier. Esto es extraordinariamente inverosímil, pero no es exactamente un teorema.
El problema de demostrar que la factorización es irresoluble en tiempo polinómico es que se demostraría automáticamente que P!=NP, que es una de las conjeturas matemáticas más desesperadamente difíciles. Así que no esperes una demostración rápida. Dado que la factorización está en NP, si demuestras que la factorización es no en P, entonces demuestras que P!=NP.
La clase de problemas eficientemente resolubles por los ordenadores cuánticos incluye problemas que ni siquiera están en NP, es decir, que no son resolubles por un ordenador potencialmente infinitamente paralelo. Así, mientras que para demostrar que la factorización es difícil hay que demostrar que P!=NP, para demostrar que la computación cuántica es difícil no hace falta tanto, sólo implicaría que PSPACE es mayor que P.
Lo anterior significa que cualquier subestructura clásica razonablemente pequeña de la mecánica cuántica se ve obligada a hacer una predicción comprobable experimentalmente que es diferente de la mecánica cuántica habitual, a saber, que los ordenadores cuánticos fallarán a partir de un determinado número no demasiado grande de qubits.
