¿Crees que las computadoras cuánticas pueden violar la tesis extendida de Church-Turing?

Sí, las computadoras cuánticas parecen violar la tesis extendida de Church-Turing (la que trata sobre la complejidad computacional y no solo sobre la computabilidad, la que dice que hay traducciones eficientes entre todas las máquinas de Turing). Es por eso que ahora hay un dispositivo teórico más, la máquina Quantum Turing, que es distinta y más poderosa que la máquina Turing.

En la entrada de Wikipedia sobre la tesis de Iglesia-Turing dice:

Si se demuestra que BQP es un superconjunto estricto de BPP, invalidaría la Tesis de la Iglesia Teórica de Complejidad-Turing. En otras palabras, habría algoritmos cuánticos eficientes que realizan tareas que no tienen algoritmos probabilísticos eficientes. Sin embargo, esto no invalidaría la tesis original de Iglesia-Turing, ya que una computadora cuántica siempre puede ser simulada por una máquina de Turing, pero invalidaría la tesis clásica de la Iglesia Teórica de Complejidad por razones de eficiencia. En consecuencia, la tesis de la Iglesia Teórica de la Complejidad Cuántica establece:

“Una máquina cuántica de Turing puede simular eficientemente cualquier modelo realista de computación”.

Ahora, observe que hay una parte importante sobre “si BQP es un superconjunto estricto de BPP”. Si esto no es cierto, puede simular eficientemente las computadoras cuánticas en las clásicas, y todos nuestros problemas desaparecen; no habrá necesidad de construirlos, pero aún obtenemos todos los beneficios de saber cómo resolver eficientemente problemas extra difíciles (como la factorización de números para romper toda la criptografía del mundo, de una manera relativamente sencilla). Sin embargo, al menos para mí, esto parece más improbable que los QTM simplemente sean más poderosos que los TM 🙂

PD: si estás interesado en esas cosas, definitivamente deberías leer Quantum Computing desde Demócrito: Scott Aaronson