Existe-t-il un équivalent quantique du théorème de la hiérarchie temporelle?

Mon théorème préféré en théorie de la complexité est le théorème de la hiérarchie temporelle. Cependant, cela a été fait en 1965.

Je voulais alors savoir s'il y avait quelque chose de similaire pour l'informatique quantique.

Si ce n'est pas le cas, quelles sont les personnes / groupes qui travaillent dans ce sens!

Une citation plus récente pour les théorèmes de la hiérarchie temporelle est "Une hiérarchie temporelle générique pour les modèles sémantiques avec un conseil" de Dieter van Melkebeek et Konstantin Pervyshev que vous pouvez obtenir sur la page Web de Dieter. Les techniques y donnent une hiérarchie temporelle avec 1 bit de conseil pour un "modèle sémantique raisonnable" de calcul, y compris des algorithmes quantiques.

De plus, il est normalement relativement facile d'obtenir une hiérarchie pour les problèmes de promesse calculés par les modèles sémantiques. Un problème de promesse nécessite uniquement un algorithme pour "se comporter correctement" (par exemple, avoir une erreur limitée) sur certaines entrées - celles qui sont choisies pour faire partie du problème de promesse. Pour les entrées non choisies pour faire partie de la promesse, l'algorithme peut se comporter de manière arbitraire (par exemple, ne pas avoir d'erreur bornée). Une hiérarchie pour les problèmes de promesse est un résultat folklorique; une preuve du paramètre BPP est donnée dans «Résultats de la hiérarchie spatiale pour les modèles aléatoires et autres modèles sémantiques» de Dieter van Melkebeek et Jeff Kinne (moi-même) que vous pouvez obtenir sur Dieter ou sur ma page Web. Cela devrait également s'appliquer aux algorithmes quantiques.

La réponse est donc que les théorèmes de hiérarchie décents sont connus pour les algorithmes quantiques qui obtiennent 1 bit de conseil ou sont autorisés à ignorer les entrées problématiques. Certaines des techniques utilisées pour ces résultats reposent sur les propriétés d'algorithmes randomisés. Il serait intéressant d'essayer d'exploiter les propriétés des algorithmes quantiques dans le domaine des théorèmes de hiérarchie.

Un domaine quelque peu apparenté où il existe des résultats spécifiques aux algorithmes quantiques est celui des limites inférieures de l'espace-temps. Il y a une enquête de Dieter van Melkebeek: "Une enquête sur les limites inférieures pour la satisfaction et les problèmes connexes".

La réponse est non. Nous n'avons même pas de théorème de hiérarchie temporelle pour le temps polynomial probabiliste à erreurs bornées (c.-à-d. BPTIME). Les théorèmes de la hiérarchie temporelle déterministe et non déterministe ont un argument de diagonalisation, qui ne semble pas fonctionner pour les classes sémantiques. C'est pourquoi nous n'avons pas de théorèmes de hiérarchie forts pour les classes sémantiques.

Le meilleur résultat que je connaisse est un théorème de hiérarchie pour BPTIME avec 1 conseil: Fortnow, L .; Santhanam, R. (2004). Théorèmes de hiérarchie pour le temps polynomial probabiliste .

Je ne connais aucun groupe travaillant sur un théorème de hiérarchie temporelle quantique. Je suppose que c'est parce qu'il semble que le problème de la hiérarchie BPTIME est plus facile, donc les chercheurs s'attaqueraient plutôt à ce problème.

(Questions assez liées: existe-t-il une caractérisation syntaxique pour BPP, BQP ou QMA? Sur MathOverflow et les classes de complexité sémantique contre syntaxique sur cstheory.)

Les classes quantiques non déterministes dans le temps et dans l'espace sont celles où les langages sont les ensembles de chaînes acceptés par les machines quantiques de Turing fonctionnant dans les limites correspondantes avec une probabilité non nulle.

Dans la section 8 de " prouver le pouvoir de la post-sélection ", nous montrons qu'il existe des hiérarchies étroites pour les classes quantiques non déterministes temporelles et spatiales.