Programas de extensión, tamaño de testigo y complejidad del certificado

10

Un programa span es una forma lineal-algebraica de especificar una función booleana presentada aquí . Recientemente, este modelo se usó para mostrar que el método negativo del adversario proporciona una caracterización estricta (al menos hasta ) de la complejidad de la consulta cuántica.logn/loglogn

La medida de complejidad que conecta los programas span con la complejidad de la consulta cuántica es el tamaño del testigo. Esta medida parece bastante similar a la complejidad del certificado. ¿Existen conexiones conocidas entre las dos medidas? ¿Qué pasa con la medida del tamaño (número de vectores de entrada) para los programas span y otras medidas como la complejidad de consultas deterministas y aleatorias? ¿Cuáles son los algoritmos clásicos más conocidos para evaluar programas span?

EDITAR (después de una respuesta de Martin Schwarz):

De particular interés son las conexiones conceptuales que van directamente a través de los programas span en lugar de a través de la correspondencia entre el tamaño del testigo y la complejidad de la consulta cuántica. ¿Hay resultados clásicos que brindan intuición sobre los programas de extensión / tamaño del testigo y cómo se relacionan con la complejidad de consultas deterministas y aleatorias?

Artem Kaznatcheev
fuente

Respuestas:

5

El tamaño mínimo de testigo sobre todos los testigos de un programa span para una función dada es igual al límite del adversario generalizado, como se muestra, por ejemplo, en el Teorema 1.7 aquí . Además, elgeneralizadoel límite del adversario es solo una relajación semi-definida de la complejidad del certificado, vea, por ejemplo, la diapositiva 40 en el tutorial de Reichardt . La relación con la complejidad de consultas aleatorias y deterministas también se discute en estas diapositivas del tutorial.

Martin Schwarz
fuente
fC(f)=3ADV±(f)=2+35/5>3
OK estoy de acuerdo. Por lo tanto, el argumento de relajación parece aplicarse solo al paso de C (f) a ADV (f). De todos modos, creo que la diapositiva 40 a la que me refería anteriormente resume muy bien los pasos de generalización tomados de C (f) a través de una relajación a ADV (f) y luego a través de otra generalización a ADV ± (f), que es la conexión entre C (f ) y ADV ± (f) sobre el que estaba preguntando.
Martin Schwarz
Gracias por la respuesta. Este tipo de conexión pasa directamente a través de la complejidad de la consulta y se relaciona con una pregunta anterior , pero creo que estoy tratando de buscar conexiones más directas a través de los programas span. En particular, estoy tratando de obtener más información sobre los programas span sin usar mi conocimiento de la complejidad de consultas cuánticas. Editaré mi pregunta para aclararla y ver si genera más información sobre los programas span.
Artem Kaznatcheev