De Quantum Computing (conferencias de Scott Aaronson):
Computación cuántica y problemas NP-completos
Al leer periódicos, revistas, Slashdot, etc., uno podría pensar que una computadora cuántica podría “resolver problemas completos de NP en un abrir y cerrar de ojos” al “probar todas las soluciones posibles en paralelo”, y luego elegir al instante la correcta.
Bueno, eso es una loza. De hecho, podría decirse que es el problema central de la computación cuántica.
Obviamente, todavía no podemos probar que las computadoras cuánticas no puedan resolver problemas completos de NP de manera eficiente, en otras palabras, NP ⊄ BQP , ¡ya que ni siquiera podemos probar que P ≠ NP ! Tampoco tenemos idea de cómo demostrar que si P ≠ NP entonces NP ⊄ BQP .
Lo que sí tenemos es el resultado inicial de Bennett, Bernstein, Brassard y Vazirani, de que existe un oráculo con respecto al cual NP ⊄ BQP . Más concretamente, suponga que está buscando un espacio de 2n posibles soluciones para una única válida, y suponga que todo lo que puede hacer, dada una solución candidata, es alimentarlo a un ‘recuadro negro’ que le indica si esa solución es correcta o no. Entonces, ¿cuántas veces necesita consultar el cuadro negro para encontrar la solución válida? Clásicamente, está claro que necesita consultarlo ~ 2n veces en el peor de los casos (o ~ 2n / 2 veces en promedio). Por otro lado, Grover dio un famoso algoritmo de búsqueda cuántica que consulta el cuadro negro solo ~ 2n / 2 veces. Pero incluso antes de que se descubriera el algoritmo de Grover, Bennett et al. había demostrado que era óptimo! En otras palabras, cualquier algoritmo cuántico para encontrar una aguja en un pajar de tamaño 2n necesita al menos ~ 2n / 2 pasos. Por lo tanto, para los problemas de búsqueda “genéricos” o “no estructurados”, las computadoras cuánticas pueden acelerar un poco más que las computadoras clásicas, específicamente, una aceleración cuadrática, pero nada como la aceleración exponencial del algoritmo de factorización de Shor.
Quizás se pregunte: ¿por qué la aceleración debería ser cuadrática, en lugar de cúbica u otra cosa? Permítanme tratar de responder esa pregunta sin entrar en los detalles del algoritmo de Grover o de Bennett et al. prueba de optimación Básicamente, la razón por la que obtenemos una aceleración cuadrática es que la mecánica cuántica se basa en la norma L2 en lugar de la norma L1. Clásicamente, si hay N soluciones, solo una de las cuales es correcta, entonces después de una consulta tenemos una probabilidad de 1 / N de haber adivinado la solución correcta, después de dos consultas tenemos una probabilidad de 2 / N, después de tres consultas un 3 / N probabilidad, y así sucesivamente. Por lo tanto, necesitamos ~ N consultas para tener una probabilidad no despreciable (es decir, cercana a 1) de haber adivinado la solución correcta. Pero cuánticamente, podemos aplicar transformaciones lineales a vectores de amplitudes , que son las raíces cuadradas de las probabilidades. Entonces, la forma de pensarlo es la siguiente: después de una consulta tenemos una amplitud de 1 / √N de haber adivinado la solución correcta, después de dos consultas tenemos una amplitud de 2 / √N, después de tres consultas una amplitud de 3 / √N, y así. Entonces, después de las consultas T, la amplitud de haber adivinado una solución correcta es T / √N, y la probabilidad es | T / √N | 2 = T2 / N. Por lo tanto, la probabilidad será cercana a 1 después de solo T ≈ √N consultas.
Muy bien, aquellos de ustedes que leen mi blog deben estar cansados de las polémicas sobre las limitaciones de las computadoras cuánticas en problemas de búsqueda no estructurados. Así que me voy a tomar la libertad de terminar esta sección ahora.
Y…
Computación cuántica y muchos mundos
Dado que este curso es Computación Cuántica desde Demócrito , creo que debería terminar la conferencia de hoy con una pregunta filosófica profunda. Bien, entonces, ¿qué tal este: si logramos construir una computadora cuántica no trivial, eso demostraría la existencia de universos paralelos?
David Deutsch, uno de los fundadores de la computación cuántica en la década de 1980, ciertamente piensa que lo haría. (Aunque para ser justos, Deutsch piensa que el impacto sería “meramente” psicológico, ya que para él, ¡la mecánica cuántica ya ha demostrado la existencia de universos paralelos!) A Deutsch le gusta hacer preguntas como las siguientes: si el algoritmo de Shor logra factorizar un Entero de 3000 dígitos, entonces, ¿ dónde se factorizó el número? ¿De dónde provienen los recursos computacionales necesarios para factorizar el número, si no de algún tipo de ‘multiverso’ exponencialmente más grande que el universo que vemos? En mi opinión, Deutsch parece estar asumiendo tácitamente aquí que el factoring no está en BPP , pero no importa; para fines de argumentación, ciertamente podemos concederle esa suposición.
No debería sorprender a nadie que las opiniones de Deutsch sobre esto estén lejos de ser universalmente aceptadas. Muchos de los que están de acuerdo con la posibilidad de construir computadoras cuánticas, y el formalismo necesario para describirlos, no están de acuerdo con que el formalismo se interprete mejor en términos de “universos paralelos”. Para Deutsch, estas personas son simplemente cobardes intelectuales, como los eclesiásticos que acordaron que el sistema copernicano era prácticamente útil, siempre y cuando uno recuerde que obviamente la Tierra realmente no gira alrededor del sol.
Entonces, ¿cómo responden los cobardes intelectuales a los cargos? Por un lado, señalan que ver una computadora cuántica en términos de “universos paralelos” plantea serias dificultades propias. En particular, hay lo que aquellos condenados a preocuparse por tales cosas llaman el “problema de base preferida”. El problema es básicamente este: ¿cómo definimos una “división” entre un universo paralelo y otro? Hay infinitas maneras en que podrías imaginar dividir un estado cuántico, ¡y no está claro por qué una es mejor que otra!
Uno puede empujar más el argumento. La clave en la que confían las computadoras cuánticas para las aceleraciones, de hecho, lo que hace que la mecánica cuántica sea diferente de la teoría de probabilidad clásica en primer lugar, es la interferencia entre amplitudes positivas y negativas. Pero en cualquier medida, las diferentes “ramas” del multiverso pueden interferir de manera útil para la computación cuántica, ¡hasta ese punto no parecen ramas separadas en absoluto! Quiero decir, todo el punto de interferencia es mezclar ramas para que pierdan sus identidades individuales. Si conservan sus identidades, entonces exactamente por esa razón no vemos interferencia.
Por supuesto, un mundo de muchos podría responder que, para perder sus identidades separadas al interferir entre sí, ¡las ramas tenían que estar allí en primer lugar! Y la discusión podría continuar (de hecho, ha continuado) durante bastante tiempo.
En lugar de tomar partido en este debate tenso, fascinante, pero quizás sin sentido, me gustaría terminar con una observación que no está en discusión. Lo que el límite inferior de Bennett et al. Nos dice es que, si la computación cuántica respalda la existencia de universos paralelos, ¡ciertamente no lo hace de la manera en que la mayoría de la gente piensa! Como hemos visto, una computadora cuántica no es un dispositivo que pueda “probar todas las soluciones posibles en paralelo” y luego elegir instantáneamente la correcta. Si insistimos en ver las cosas en términos de universos paralelos, entonces todos esos universos tienen que “colaborar”, más que eso, deben fusionarse entre sí , para crear un patrón de interferencia que conduzca a que se observe la respuesta correcta con alta probabilidad .
