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.
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?
fuente