Problema de conteo aproximado al capturar BQP

En el modelo de caja negra, el problema de determinar la salida de una máquina BPP en la entrada es el problema de conteo aproximado de determinar con error aditivo 1/3 (digamos). $M(x,r)$ $x$ $E_r M(x,r)$

¿Hay un problema similar para BQP? Este comentario de Ken Regan sugiere tal problema

Puede reducir una pregunta de BPP a una aproximación de una sola función #P, pero con BQP lo que obtiene es la diferencia de dos funciones #P, llámelas y . ¡Aproximar y separado no lo ayuda a aproximar cuando está cerca de cero! $f$ $g$ $f$ $g$ $f - g$ $f - g$

BQP te da un poco de ayuda: cuando la respuesta a la pregunta BQP en una entrada es sí, obtienes que está cerca de la raíz cuadrada de , donde los predicados de conteo definen y variables tienen m binarios después de que sustituyen a . (No hay barras de valor absoluto; “mágicamente” siempre obtienes . Bajo representaciones comunes de circuitos cuánticos para BQP, convierte en el número de puertas Hadamard.) Cuando la respuesta es no, el la diferencia está cerca de 0. $x$ $f(x) - g(x)$ $2^m$ $f$ $g$ $x$ $f(x) > g(x)$ $m$

¿Puede formular con precisión un problema tan cercano a BQP como sea posible? Espero algo como: dado el acceso de recuadro negro a las funciones mapeo de a , con la promesa de ..., estimar en . $f,g$ $X$ $Y$ $f-g$ $\varepsilon$

cc.complexity-theory quantum-computing black-box Manu
fuente

Creo que el comentario de Ken Regan se refiere al resultado BQP⊆AWPP de Fortnow y Rogers (JCSS 1999; people.cs.uchicago.edu/~fortnow/papers/quantum.pdf ).

Tsuyoshi Ito

Respuestas:

Emanuele: Desafortunadamente, no conocemos ningún problema de caja negra para capturar BQP tan simple como el que mencionaste capturar BPP.

Intuitivamente, esto se debe a que es difícil hablar de BQP sin incorporar la unitaridad de una forma u otra. ¡La capacidad de sumar números positivos y negativos es lo que hace que BQP sea más poderoso que BPP, pero luego la unitaridad es lo que hace que BQP sea menos poderoso que #P! :-)

Dicho esto, además de Dawson et al. el documento al que Martin Schwarz se vinculó, definitivamente debería ver esto y esto por Janzing y Wocjan, que dan problemas de promesa "de aspecto sorprendentemente clásico" que capturan BQP.

Además, deje S ⊆ {0,1} ⁿ , y considere una función booleana f: S → {0,1}. Luego tengo una conjetura de hace años que dice que Q (f), la complejidad de consulta cuántica de error acotado de f, está polinómicamente relacionada con el grado mínimo de un polinomio real p: R ⁿ → R tal que

(i) p (x) ∈ [0,1] para todos los x∈ {0,1} ⁿ , y

(ii) | p (x) -f (x) | ≤ ε para todos los x∈S.

Si esta conjetura se cumple, entonces un "problema de conteo aproximado al capturar BQP" sería simplemente aproximar el valor de un polinomio p de Polylog (n) -gree: R ⁿ → R, en un punto específico del cubo booleano, dado que p es limitado por todas partes en el cubo booleano. Esto podría ser lo más cerca que uno podría obtener una respuesta a su pregunta.

Scott Aaronson
fuente

Gracias. Verifiqué esta respuesta ya que "Esto podría ser lo más parecido a una respuesta a su pregunta". Pregunta: ¿cuál es el papel de "S" en su conjetura? Estoy confundido por (i) hablando de {0,1} ^ ny el resto hablando de S.

Manu

Emanuele: Si S = {0,1} ^ n, entonces f es una función booleana total. En ese caso, ya se sabe que la complejidad de la consulta cuántica está polinómicamente relacionada con el grado aproximado (así como con la complejidad de la consulta determinista y aleatoria). Entonces, el caso interesante es cuando f es una función booleana parcial : es decir, el algoritmo cuántico solo necesita trabajar en entradas que cumplan la promesa de que x pertenece a S. Esa es la situación en la que algoritmos cuánticos como el de Simon (que superan exponencialmente el mejor algoritmo clásico) ser posible

Scott Aaronson

¡Tenga en cuenta que, si bien el algoritmo cuántico solo necesita calcular f en las entradas que pertenecen al conjunto S, la probabilidad de aceptación del algoritmo en las entradas que no están en S todavía pertenece al intervalo [0,1]! Por tonto que parezca, a menudo ha sido una observación crucial para probar los límites inferiores cuánticos a través del método polinómico. Y si no hubiera requerido que el polinomio p estuviera limitado en [0,1] para todas las x en {0,1} ^ n (incluso x no en S), entonces mi conjetura habría sido trivialmente falsa.

Scott Aaronson

Este artículo desarrolla las ideas descritas anteriormente en detalle.

Martin Schwarz
fuente

Gracias por el enlace. La conexión con ecuaciones polinómicas sobre parece interesante.

Z_{2}

$Z_2$

Manu

@Emanuele Viola, @Martin Schwarz: Realmente no veo cómo este artículo responde a la pregunta original. Por un lado, este documento no habla sobre problemas de caja negra en absoluto. Parece que no puedo obtener una formulación nítida de un problema de caja negra del papel, del tipo que se hace en la pregunta. ¿Quizás alguno de ustedes podría arrojar algo de luz sobre esto?

Robin Kothari

@ Robin Kothari: Estoy de acuerdo, que el documento no produce un problema de caja negra, como se preguntó originalmente. Sin embargo, sí elabora el comentario de Ken Regan. Debería haber hecho esto un "comentario" en lugar de una "respuesta".

Martin Schwarz

Oh esta bien. No hay problema. Entonces supongo que la pregunta aún no se ha resuelto.

Robin Kothari