Programmes étendus, taille des témoins et complexité des certificats

Un programme span est une manière linéaire-algébrique de spécifier une fonction booléenne présentée ici . Récemment, ce modèle a été utilisé pour montrer que la méthode de l'adversaire négatif fournit une caractérisation étroite (au moins jusqu'à ) de la complexité des requêtes quantiques. $\log n/ \log \log n$

La mesure de la complexité reliant des programmes d'envergure à la complexité d'une requête quantique est la taille du témoin. Cette mesure semble assez similaire à la complexité du certificat. Existe-t-il des liens connus entre les deux mesures? Qu'en est-il de la mesure de la taille (nombre de vecteurs d'entrée) pour les programmes d'intervalle et d'autres mesures telles que la complexité des requêtes déterministes et randomisées? Quels sont les algorithmes classiques les plus connus pour évaluer les programmes span?

EDIT (après une réponse de Martin Schwarz):

Les connexions conceptuelles qui passent directement par des programmes d'envergure, par opposition à la correspondance entre la taille des témoins et la complexité des requêtes quantiques, sont particulièrement intéressantes. Existe-t-il des résultats classiques qui fournissent une intuition sur les programmes de durée / la taille des témoins et comment ils sont liés à la complexité des requêtes déterministes et randomisées?

cc.complexity-theory reference-request quantum-computing query-complexity Artem Kaznatcheev
la source

Réponses:

La taille minimale des témoins sur tous les témoins d'un programme span pour une fonction donnée est égale à la limite généralisée de l'adversaire, comme illustré par exemple dans le théorème 1.7 ici . De plus, le~~généralisé~~l'adversaire lié est juste un relâchement semi-défini de la complexité du certificat, voir par exemple la diapositive 40 dans le tutoriel de Reichardt . La relation avec la complexité des requêtes déterministes et randomisées est également discutée dans ces diapositives du didacticiel.

Martin Schwarz
la source

Je peux voir que la méthode de l'adversaire (positif) est un assouplissement SDP de la complexité du certificat, mais je ne comprends pas comment la méthode de l'adversaire (négatif) générale est un assouplissement de la complexité du certificat. Comme contre-exemple, il semble que l'on donne ici (p. 25) une fonction avec et .

f

$f$

C (f) = 3

$C(f) = 3$

A D V^{\pm} (f) = 2 + 3 \sqrt{5} / 5 > 3

$ADV^{\pm}(f) = 2 + 3\sqrt{5}/5 > 3$

Artem Kaznatcheev

OK je suis d'accord. L'argument de relaxation ne semble donc vraiment s'appliquer qu'à l'étape de C (f) à ADV (f). Quoi qu'il en soit, je pense que la diapositive 40 à laquelle je faisais référence ci-dessus résume bien les étapes de généralisation prises de C (f) via une relaxation vers ADV (f) puis via une autre généralisation vers ADV ± (f), qui est le lien entre C (f ) et ADV ± (f) dont vous parliez.

Martin Schwarz

Merci d'avoir répondu. Ce type de connexion passe directement par la complexité des requêtes et se rapporte à une question précédente , mais je pense que j'essaie de rechercher des connexions plus directes par le biais de programmes span. En particulier, j'essaie de mieux comprendre les programmes span eux-mêmes sans utiliser mes connaissances de la complexité des requêtes quantiques. Je vais modifier ma question pour la rendre plus claire et voir si elle génère des informations supplémentaires sur les programmes span.

Artem Kaznatcheev