Les algorithmes quantiques à accélération exponentielle peuvent-ils être redéfinis à l'aide de programmes étendus?

L'adversaire général de la borne inférieure est désormais connu pour caractériser la complexité des requêtes quantiques grâce aux travaux révolutionnaires de Reichardt et al. La même ligne de travail établit également des connexions avec le cadre du programme span pour concevoir des algorithmes quantiques.

De nombreux algorithmes quantiques intéressants, y compris ceux avec une accélération exponentielle comme l'algorithme de Simon et l'algorithme de Shor pour la recherche de période peuvent être exprimés dans le modèle de requête quantique.

Existe-t-il des travaux montrant des limites inférieures pour ces algorithmes dans le modèle général de l'adversaire? Y a-t-il un travail dérivant des algorithmes de Simon ou Shor dans le cadre du programme span?

Apparemment, seuls les algorithmes quantiques avec une accélération polynomiale, comme celle de Grover, ont été dérivées à l'aide du cadre de programmes span (ou du graphique d'apprentissage de Belov).

Il existe des travaux de Korian et al. montrant des limites inférieures pour Simon en utilisant la méthode polynomiale, mais il n'y a apparemment aucun moyen connu de traduire les limites inférieures de la méthode polynomiale en limites inférieures adversaires générales.

Je suppose qu'il y a au moins 3 questions dans votre question. Je n'ai pas de réponse satisfaisante à tous, donc ce n'est pas une réponse complète. J'espère qu'il y aura plus de réponses qui répondront à toutes vos questions.

La question dans le titre: les algorithmes quantiques à accélération exponentielle peuvent-ils être redéfinis à l'aide de programmes étendus?

Comme vous l'avez noté, la limite générale de l'adversaire caractérise la complexité des requêtes quantiques de tous les problèmes de décision, y compris les problèmes de promesse pour lesquels nous avons des accélérations exponentielles. Donc, en principe, il existe un programme span qui résout le problème du sous-groupe caché abélien, qui est le problème de requête utilisé dans les algorithmes de Simon et Shor. Mais s'il existe un programme d'intervalle explicite pour cela, c'est votre prochaine question.

Y a-t-il un travail dérivant des algorithmes de Simon ou Shor dans le cadre du programme span?

Je n'ai pas entendu parler de tels résultats. Je ne connais pas de programme span pour le problème de Simon ou tout autre AHSP.

Existe-t-il un moyen de traduire les bornes inférieures de la méthode polynomiale en bornes inférieures de l'adversaire général?

Oui, je crois que oui. Je n'arrive pas à trouver le papier qui a ce résultat, mais je peux vous donner un lien vers une conférence donnée par Jérémie Roland . Dans le résumé de la conférence, il dit ce qui suit:

... Plus précisément, nous montrerons que la méthode de l'adversaire multiplicatif, une variation de la méthode de l'adversaire d'origine, généralise non seulement la méthode de l'adversaire généralisé, mais aussi la méthode polynomiale, de sorte qu'elle englobe essentiellement toutes les méthodes de borne inférieure connues. Par conséquent, cela fournit une approche constructive pour intégrer des bornes inférieures polynomiales dans le cadre de la méthode de l'adversaire.

Mise à jour : l'article est maintenant disponible en ligne: relation explicite entre toutes les techniques de limite inférieure pour la complexité des requêtes quantiques par Loïck Magnin et Jérémie Roland