Pourquoi les problèmes complets de l'AMQ doivent-ils être des problèmes prometteurs?

10

Je lis l'excellent document d'enquête de Watrous sur papier sur la théorie de la complexité quantique. Il y déclare qu'il serait surprenant qu'un problème complet de l'AMQ se révèle avoir une promesse vide de sens (c'est-à-dire être une langue). Pourquoi cela est-il ainsi?

Cela a-t-il à voir avec le fait que le problème hamiltonien k-local est un problème prometteur?

En outre, cela m'amène à une question connexe: y a-t-il des problèmes complets de QMA qui ne sont pas intrinsèquement «quantiques» dans la nature?

cc.complexity-theory quantum-computing Henry Yuen
la source
3
Je suppose que ce serait une chose intéressante car QMA est défini comme une classe sémantique, un problème aussi complet donnerait une caractérisation syntaxique. Consultez les questions connexes sur les classes de complexité syntaxique / sémantique sur cstheory / Mathoverflow.
Kaveh
3
De plus, ce phénomène n'est pas spécifique à l'AMQ en particulier. D'autres classes sémantiquement définies comme MA sont BPP ne sont pas non plus connues pour avoir des langages complets.
Robin Kothari
1
Je me demande quelles sont les conditions nécessaires et suffisantes en pratique pour qu'un problème ne soit "pas quantique". Je suppose que tout problème qui appelle une carte complètement positive ( par exemple une carte CP donnée est-il inversible, ou loin d'être inversible?) Ou une structure de produit tensorielle ( par exemple, un opérateur semi-défini positif, donné dans une présentation k-locale, a des valeurs propres inférieures à delta, ou sont-ils tous sensiblement plus grands que delta?) seraient des exemples de problèmes quantiques suspects, qu'ils soient présentés ou non en termes de canaux quantiques / évolution ou de l'espace d'état d'un système agrégé ...
Niel de Beaudrap

Réponses: