Limitando la brecha entre la complejidad de consulta cuántica y determinista

Aunque las separaciones exponenciales entre la complejidad cuántica de consultas con error limitado ( ) y la complejidad de consulta determinista ( D ( f ) ) o la complejidad aleatoria de consultas con error limitado ( R ( f ) ) son conocidas, solo se aplican a ciertas funciones parciales. Si las funciones parciales tienen algunas estructuras especiales, entonces también están polinómicamente relacionadas con D ( f ) = O ( Q ( f ) 9 ) ) . Sin embargo, me preocupan principalmente las funciones totales.$Q(f)$$D(f)$$R(f)$$D(f) = O(Q(f)^9))$

En un artículo clásico se demostró que está delimitado por O ( Q ( f ) 6 ) para funciones totales, O ( Q ( f ) 4 ) para funciones totales monótonas y O ( Q ( f ) 2 ) para Funciones totales simétricas. Sin embargo, no se conocen separaciones mayores que cuadráticas para este tipo de funciones ( O R logra esta separación$D(f)$$O(Q(f)^6)$$O(Q(f)^4)$$O(Q(f)^2)$$OR$por ejemplo). Según tengo entendido, la mayoría de las personas conjeturan que para funciones totales tenemos $D(f) = O(Q(f)^2)$ . ¿En qué condiciones se ha demostrado esta conjetura (aparte de las funciones simétricas)? ¿Cuáles son los mejores límites actuales en la complejidad del árbol de decisión en términos de complejidad de consulta cuántica para funciones totales?

$D(f) = O(Q_E(f))^3$$Q_E(f)$$f$

$n$$\Omega(\sqrt{n})$

Aunque este progreso ha sido limitado, ha habido un progreso considerable en el límite inferior de la complejidad de consulta cuántica de funciones específicas ; ver esta revisión para los detalles (o, por ejemplo el más reciente documento de Reichardt, lo que demuestra que la versión general, la mayor parte del '' adversario '' Caracteriza con destino cuántica complejidad de la consulta).

Me gusta la respuesta de Ashley Montanaro, pero pensé que también incluiría un conjunto de funciones para las cuales se conoce la conjetura.

$OR$

$f$$D(f) = O(Q(f)^2)$

Detalles:

$x$$S \subseteq \{1,...,n\}$$y$$(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$$C_x(f)$$x$$C_1(f) = \max_{x | f(x) = 1} C_x(f)$$f(x) = 0$

Puede mostrar que . A continuación, puede utilizar el algoritmo presentado en Buhrman y de lobo de encuesta para demostrar que:$Q(f) \geq \sqrt{bs(f)} \geq 2C_0(f)/2^{C_1(f)} + 1$$D(f) \leq C_1(f)bs(f) \leq C_0(f)C_1(f)$

Si restringimos la atención a las propiedades del gráfico, entonces podemos probar límites ligeramente mejorados en comparación con los límites generales que menciona:

En un artículo clásico se demostró que está delimitada por para funciones totales, para funciones totales monótonas y para funciones totales simétricas.$D(f)$$O(Q(f)^6)$$O(Q(f)^4)$$O(Q(f)^2)$

Primero, creo que la sexta potencia se puede mejorar a la cuarta potencia para las propiedades del gráfico. Esto se deduce de [1], donde muestran que cualquier propiedad de gráfico tiene una complejidad de consulta al menos , donde es el tamaño de entrada, que es cuadrático en el número de vértices. Por supuesto, la complejidad consulta clásica es como máximo .$\Omega(N^{1/4})$$N$$N$

La cuarta potencia limitada para las funciones totales monótonas se puede mejorar a la tercera potencia para las propiedades de gráficos monótonos. Esto se desprende de una observación inédita de Yao y Santha (mencionada en [2]) de que todas las propiedades de gráficos monótonos tienen complejidad de consulta cuántica .$\Omega(N^{1/3}\log^{1/6}N)$

[1] Sol, X .; Yao, AC .; Shengyu Zhang, "Propiedades gráficas y funciones circulares: ¿qué tan bajo puede ir la complejidad de la consulta cuántica?", Complejidad computacional, 2004. Procedimientos. 19a Conferencia Anual IEEE, vol., No., Pp.286,293, 21-24 de junio de 2004 doi: 10.1109 / CCC.2004.1313851

[2] Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2005), "Algoritmos cuánticos para el problema del triángulo", Actas del decimosexto simposio anual ACM-SIAM sobre algoritmos discretos, Vancouver, Columbia Británica: Society for Industrial and Applied Mathematics, págs. 1109–1117, arXiv: quant -ph / 0310134.

Se ha avanzado mucho en esta cuestión en 2015.

Primero, en arXiv: 1506.04719 [cs.CC] , los autores han mejorado la separación cuadrática al mostrar una función total con$f$

Por otro lado, en arXiv: 1512.04016 [quant-ph] , se demostró que la relación cuadrática entre la complejidad de consulta cuántica y determinista se mantiene cuando el dominio de la función es muy pequeño.