Separar NP de BQP en relación con un oráculo

10

Estaba buscando en esta conferencia nota donde el autor da una separación entre el oráculo BQP y NP . Él insinúa cómo "las técnicas de diagonalización estándar se pueden utilizar para hacer esto riguroso".

BQPANPABQPA

BlackHat18
fuente

Respuestas:

2

Me parece que los argumentos de diagonalización que se pueden usar son solo ligeramente diferentes de los estándares, por ejemplo  , como se puede encontrar en estas notas sobre el Teorema de Baker-Gill-Solovay ( es decir , que hay oráculos para los cuales y también oráculos para los cuales ). Básicamente, tiene que describir cómo 'diseñar' una entrada de confrontación de manera un poco diferente.APA=NPAAPANPA

Así es como podríamos utilizar este método para probar la existencia de un oráculo A para el cual NPABQPA . Para cualquier oráculo A , defina un lenguaje

LA={1n|z{0,1}n:A(z,0)=(z,1)}.
Está claro queLANPA por la sencilla razón de que una máquina de Turing no determinista puede examinar si la entrada tiene la forma1n para algunan , y luego adivinar una cadenaz{0,1}n para la cualA(z,0)=(z,1) si talz existe. El objetivo es mostrar queLA no puede decidirse en tiempo polinómico, con error acotado, por una familia de circuitos unitarios uniforme, utilizando ellímite inferiorO(2n/2) en el problema de búsqueda.

  1. Deje c,N>0 sea tal que el problema de búsqueda de oráculos con n entradas -bit requiere al menos c2n/2 consultas de Oracle para decidir correctamente (con una probabilidad de al menos 2/3), para toda n>N .

  2. Dejar C(1), C(2), ser una enumeración de todas las familias de circuitos oracle unitarios C(k)={Cn(k)}n0 , de modo que la secuencia de puerta del circuitoCn(k)actuando sobre entradas de n bits puede producirse en tiempo estrictamente inferior a c2n/2 . (Este límite de tiempo se relaciona con la condición de 'uniformidad', donde nos interesará que los circuitos puedan ser calculados por una máquina de Turing determinista en tiempo polinómico, una condición más fuerte que la que imponemos aquí. La enumeración de estas familias de circuitos podría hacerse, por ejemplo, mediante la representación de ellos indirectamente por la máquina de Turing determinista T(k) que producen sus secuencias de compuerta, y la enumeración de los ). Nos enumerar las familias de circuitos de modo que se produce cada familia circuito infinitamente a menudo en la enumeración.

    • De los límites de tiempo de ejecución en la descripción de la secuencia de compuerta, se deduce en particular que Cn(k) tiene menos de c2n/2 compuertas para todos los k , y en particular hace menos de c2n/2 consultas para El oráculo.

    • Para cualquier n , considere el circuito Cn(n). Desde el límite inferior del problema de búsqueda, sabemos que para n>N hay valores posibles de la función del oráculo f:{0,1}n{0,1} evaluado por el oráculo, de modo que con probabilidad 2/3 , la salida producida por Cn(n)en la entrada 1n no es la respuesta correcta a si z{0,1}n:f(z)=1 .

    • Para cada n>N , seleccione dicha función fn para la cual Cn(n) "falla" de esta manera.

  3. Sea A un oráculo que, en entradas de tamaño n>N , evalúa fn.

Habiendo construido A de esta manera, cada familia de circuitos C(n) no puede decidir correctamente LA con probabilidad de al menos 2/3, para algunos n>N (y de hecho infinitos tales n ). Entonces ninguna de las familias de circuitos C(k) decide correctamente LA con una probabilidad de éxito limitada por debajo de 2/3 en todas las entradas, de modo que LA no puede resolverse con tales límites por ninguna familia de circuitos unitarios uniformes construible en el tiempo p(n) .

Por lo tanto, LABQPA , de la que se deduce que NPABQPA .

Niel de Beaudrap
fuente