¿Por qué una computadora cuántica es de alguna manera más poderosa que una máquina de Turing no determinista?

La cuenta estándar de noticias populares de la computación cuántica es que una computadora cuántica (QC) funcionaría dividiendo exponencialmente muchas copias paralelas no interactivas de sí misma en diferentes universos y haciendo que cada uno intente verificar un certificado diferente, luego al final del cálculo , la copia única que encontró un certificado válido "anuncia" su solución y las otras ramas desaparecen mágicamente.

Las personas que saben algo sobre computación cuántica teórica saben que esta historia es una tontería absoluta, y que la idea aproximada descrita anteriormente corresponde más a una máquina de Turing no determinista que a una computadora cuántica. Además, la clase de problemas de competencia que los NTM pueden resolver de manera eficiente es NP y QC es BQP , y no se cree que estas clases sean iguales.

Las personas que intentan corregir la presentación popular con razón señalan que la narrativa simplista de "muchos mundos" exagera en gran medida el poder de los CC, que no se cree que sean capaces de resolver (digamos) problemas completos de NP . Se centran en la tergiversación del proceso de medición: en la mecánica cuántica, el resultado que mides está determinado por la regla de Born, y en la mayoría de las situaciones la probabilidad de medir una respuesta incorrecta empaña por completo la probabilidad de medir la correcta. (Y en algunos casos, como la búsqueda de recuadro negro, podemos demostrar que ningún circuito cuántico inteligente puede vencer la regla de Born y ofrecer una aceleración exponencial). Si pudiéramosmágicamente "decidir qué medir", entonces podríamos resolver eficientemente todos los problemas en la clase de complejidad PostBQP , que se cree que es mucho más grande que BQP .

Pero nunca he visto a nadie señalar explícitamente que hay otra forma en que la caracterización popular es incorrecta, que va en la otra dirección. Se cree que BQP no es un subconjunto estricto de NP , sino que es incomparable con él. Existen problemas como la comprobación de Fourier que se cree que no solo se encuentran fuera de NP , sino que, de hecho, están fuera de toda la jerarquía polinómica PH . Entonces, con respecto a problemas como estos, la narrativa popular en realidad está bajo los estados en lugar de exagerar el poder de los CC.

Mi ingenua intuición es que si pudiéramos "elegir qué medir", entonces la narrativa popular sería más o menos correcta, lo que implicaría que estas computadoras súper cuánticas serían capaces de resolver de manera eficiente exactamente la clase NP . Pero creemos que esto está mal; de hecho PostBQP = PP , que creemos que es un superconjunto estricto de NP .

¿Hay alguna intuición de lo que sucede detrás de escena que permite que una computadora cuántica sea (en algunos aspectos) más poderosa que una máquina de Turing no determinista? Presumiblemente, este poder "inherentemente cuántico", cuando se combina con la postselección (que en cierto sentido ya tienen NTM) es lo que hace que un súper QC sea mucho más poderoso que un NTM. (Tenga en cuenta que estoy buscando una intuición que contrasta directamente las NTM y QC con la postselección, sin "pasar" por la clase de complejidad clásica PP ).

speedup complexity-theory bqp tparker
fuente

Respuestas:

Desde un punto de vista pseudo-fundacional, la razón por la cual BQP es una clase diferente (para acuñar una frase) que NP , es que se puede considerar que las computadoras cuánticas hacen uso de interferencia destructiva.

Se pueden describir muchas clases de complejidad diferentes en términos de (propiedades más o menos complicadas de) el número de ramas de aceptación de una NTM. Dado un NTM en 'forma normal', lo que significa que el conjunto de ramas computacionales es un árbol binario completo (o algo similar) de cierta profundidad polinómica, podemos considerar clases de lenguajes definidos haciendo las siguientes distinciones:

¿El número de ramas aceptantes es cero o no cero? (Una caracterización de NP .)
¿El número de ramas aceptantes es menor que el máximo, o exactamente igual al máximo? (Una caracterización de coNP .)
¿Es el número de sucursales que aceptan como máximo un tercio, o al menos dos tercios, del total? (Una caracterización de BPP .)
¿El número de sucursales que aceptan es menos de la mitad, o al menos la mitad, del total? (Una caracterización de PP .)
¿Es el número de ramas aceptantes diferente de exactamente la mitad, o igual a exactamente la mitad del total? (Una caracterización de una clase llamada C ₌ P. )

Estas se llaman clases de conteo , porque en efecto se definen en términos del conteo de las ramas de aceptación.

Interpretando las ramas de una NTM como generadas aleatoriamente, son preguntas sobre la probabilidad de aceptación (incluso si estas propiedades no son comprobables de manera eficiente con ninguna confianza estadística). Un enfoque diferente para describir las clases de complejidad es considerar, en cambio, la brecha entre el número de ramas de aceptación y el número de ramas de rechazo de una NTM. Si el conteo de la acumulación de ramas computacionales de NTM corresponde a las probabilidades, se podría sugerir que la cancelación de ramas de aceptación contra ramas de rechazo modela la cancelación de 'rutas' computacionales (como en la suma de las rutas) en el cálculo cuántico, es decir, como modelado de interferencia destructiva .

Los límites superiores más conocidos para BQP , a saber, AWPP y PP , se pueden definir fácilmente en términos de 'brechas de aceptación' de esta manera. La clase NP , sin embargo, no tiene una caracterización tan obvia. Además, muchas de las clases que se obtienen de las definiciones en términos de brechas de aceptación parecen ser más poderosas que NP . Uno podría tomar esto para indicar que la "interferencia destructiva no determinista" es un recurso computacional potencialmente más poderoso que el simple no determinismo; de modo que incluso si las computadoras cuánticas no aprovechan al máximo este recurso computacional, sin embargo, puede resistir la fácil contención en clases como NP .

Niel de Beaudrap
fuente

¿Las clases P y PSPACE cuentan? Ingenuamente parece que sí para P , ya que podría definirse como el conjunto de problemas que cada ruta acepta, pero no estoy seguro acerca de PSPACE .

tparker

PSPACE no es una clase de conteo, no. Está en el camino correcto con P --- debe exigir que cada ruta acepte o cada rechazo pah (o un requisito similarmente fuerte), o de lo contrario podría terminar con coNP , coRP o alguna otra clase desconocida para igual P .

Niel de Beaudrap

Presumiblemente, el PH tampoco es una clase de conteo, ya que está naturalmente formulado en términos de una máquina de Turing alterna en lugar de no determinista.

tparker

Si BPP requiere que acepten dos tercios de las ramas, PP requiere la mitad para aceptar, y NP solo requiere una para aceptar, ¿no implicaría eso que ? Pero, de hecho, , y se cree que ambas inclusiones son estrictas.

B P P \subset P P \subset N P

$\mathbf{BPP} \subset \mathbf{PP} \subset \mathbf{NP}$

B P P \subset N P \subset P P

$\mathbf{BPP} \subset \mathbf{NP} \subset \mathbf{PP}$

tparker

@tparker: le faltan algunos detalles, por ejemplo, el comportamiento de NO instancias en la definición de BPP (vea la publicación). En resumen, estos umbrales no se asignan de manera lineal a la amplitud de las instancias que se consideran instancias SÍ. (Y que yo sepa, no se conoce ninguna relación como --- en el mejor de los casos sabemos . )

B P P \subseteq N P

$\mathsf {BPP \subseteq NP}$

B P P \subseteq N P^{N P} \cap c o N P^{N P}

$\mathsf {BPP \subseteq NP^{NP} \cap coNP^{NP}}$

Niel de Beaudrap

-1

Esta respuesta fue 'migrada' de cuando se hizo esta pregunta en Ciencias de la Computación (el autor sigue siendo el mismo)

Bueno, una razón principal es que no hay algoritmos cuánticos que resuelvan problemas NP-hard en tiempo polinómico.

Otra es que el recocido cuántico adiabético (como en Dwave) apenas puede vencer al recocido cuántico clásico.

Además, la mayoría de los investigadores piensan que P NP. Muchos creen que P BQP. Sin embargo, P PostBQP. ¿PostBQP NP ahora es contradictorio? No. Solo sabemos que P NP es una declaración más débil que (¡no implica mucho más!) PostBQP P! Entonces, ¿por qué tanto alboroto por una pregunta más difícil que P vs. NP! $\neq$ $=$ $\neq$ $\neq$ $=$ $=$

En cuanto a por qué creer P BQP, algunos creen que cualquier mejora no será asintótica o simplemente una constante, como en diferentes implementaciones. $=$

Entonces, hay algunas razones para creer PostBQP NP. Pero todo esto es especulación y probablemente siga siendo especulación por un tiempo. Puedes creer lo que quieras, por ahora, al menos. $\neq$

Existen problemas como la comprobación de Fourier que se cree que no solo se encuentran fuera de NP, sino que de hecho están fuera de toda la jerarquía polinómica. Entonces, con respecto a problemas como estos, la narrativa popular realmente subestima en lugar de exagerar el poder de los CC.

En cuanto a esto, ¡no he visto un resultado que indique que una computadora cuántica puede resolver esto de manera eficiente ! Además, que la máquina pueda resolver problemas extraños rápidamente (simulándose a sí mismo en , por ejemplo) no es más sorprendente que una cascada simulándose a sí misma en (siendo n el número de pasos de simulación) $O(n)$ $O(n)$

Lagarto discreto
fuente