Entendiendo QMA

Esta pregunta surge de una respuesta que Joe Fitzsimons dio a una pregunta diferente . La mayoría de las clases de complejidad natural tienen una "descripción intuitiva" de una línea que ayuda a caracterizar los problemas centrales de esa clase. NP es "verificación eficiente", #P se trata de "enumerar soluciones", PSPACE se trata de "juego", y así sucesivamente.

En general, he entendido MA como BP (NP), donde el paso M le da el adivinador de NP, y el paso A es la parte de BP, por lo que las preguntas sobre la relación entre MA y NP son realmente preguntas de aleatorización. Entonces mi pregunta es:

¿Hay alguna forma natural de entender lo que captura QMA?

cc.complexity-theory quantum-computing big-picture qma Suresh Venkat
fuente

Respuestas:

Es esencialmente lo mismo. QMA tiene un verificador cuántico A que le proporciona el bit de error acotado más la capacidad de procesar estados cuánticos, y M le permite elegir un estado de aceptación de manera no determinista si existe.

Sin embargo, un análogo cuántico de MA es mucho más natural que NP, ya que cualquier análogo de NP requeriría que la máquina sea capaz de escribir de manera no determinista un solo estado a partir de un número incontable de estados posibles. QMA solo requiere fidelidad finita, por lo que te deshaces de los infinitos. De hecho, QMA a menudo se trata como el análogo cuántico de NP (véase, por ejemplo, quant-ph / 0210077 ).

Joe Fitzsimons
fuente

@ Joe: ¿Por qué no hay un análogo cuántico de NP? ¿No podemos definir algo como "Cuando existe un estado que siempre se acepta, y cuando no hay ningún estado que se acepte"?

x \in L

$x \in L$

x \notin L

$x \notin L$

Robin Kothari

Sí, tienes razón, cometí un pequeño error allí. Sin embargo, lo no determinista se vuelve un poco extraño, ya que no está escribiendo de manera determinista un estado cuántico y si requiere un error cero, esto significa escribir uno de un número incontable de posibles estados. Esto parecería dificultar la contabilización adecuada de los recursos.

Joe Fitzsimons

Buen enlace a la encuesta.

Suresh Venkat

@ Joe, @ Robin: ¿Qué pasa si restringe su no determinismo de la siguiente manera? Dado | x0> en la base computacional, una puerta de "conjetura no determinista" genera | x0> o | x1>, de forma no determinista (en lugar de cuántica, por supuesto). Creo que esto le da la clase QCMA, que podría estar más cerca de un análogo cuántico de NP en el sentido en que Robin pregunta, pero no estoy completamente seguro de que no me haya perdido algo.

Joshua Grochow

Bueno, entonces es solo un caso de si quieres mensajes clásicos o cuánticos. El problema solo parece surgir para los mensajes cuánticos.

Joe Fitzsimons

La mayoría de las clases cuánticas que se estudian (como QMA, BQP, QIP y las exóticas como QMIP y QRG) tienen una contraparte clásica y obtienes la clase cuántica pensando cuánticamente y cambiando tu definición de "cálculo eficiente" a "tiempo polinómico en un computadora cuántica."

A menudo hay dos pasos a seguir para llegar de una clase conocida a una clase cuántica. El primer paso agrega aleatoriedad y error, y el siguiente paso agrega cuántica. Entonces, para NP, la cadena de clases es . En NP, el verificador es determinista, y el certificado o la prueba es una cadena de bits. En MA, modificamos el verificador para que sea una máquina BPP (le damos acceso a la aleatoriedad y le permitimos 1/3 de probabilidad de error), mientras que el certificado sigue siendo una cadena de bits. En QMA, permitimos que el verificador sea cuántico y que el certificado sea un estado cuántico. Dado que un verificador cuántico puede simular uno probabilístico, QMA contiene MA. $NP \subseteq MA \subseteq QMA$

La manera fácil de obtener una clase cuántica de la mayoría de las clases clásicas naturales es cambiar la noción de "cálculo eficiente" de P o BPP a BQP, y cambiar la noción de intercambio de información de bits a qubits. Entonces, por ejemplo, QIP es lo mismo que IP cuando el verificador BPP se convierte en BQP y la comunicación permite qubits en lugar de bits.

Finalmente, para volver a QMA: si realmente creía que BQP captura la computación eficiente en nuestro universo, entonces QMA es el conjunto de todos los problemas que tienen un procedimiento de verificación eficiente. Es decir, si conoces a un todopoderoso probador, podría convencerte con una alta probabilidad de suponiendo que puedes manejar qubits y hacer cálculos cuánticos. (Y, por supuesto, cuando , no hay casi nada que pueda decir para engañarte). $x \in L$ $x \notin L$

Robin Kothari
fuente