vs

Le problème central de la théorie de la complexité est sans doute vs N P .$P$$NP$

Cependant, comme la nature est quantique, il semblerait plus naturel de considérer les classes (c'est-à-dire les problèmes de décision pouvant être résolus par un ordinateur quantique en temps polynomial, avec une probabilité d'erreur d'au plus 1/3 pour toutes les instances) et Q M A (l'équivalent quantique de N P ) à la place.$BQP$$QMA$$NP$

Mes questions:

1) Une solution au problème vs N P donnerait-elle une solution à B Q P vs Q M A ?$P$$NP$$BQP$$QMA$

2) Les trois barrières de la relativisation, des preuves naturelles et de l'algèbre s'appliquent-elles également au problème vs Q M A ?$BQP$$QMA$

1) Aucune implication n'est connue dans les deux sens. Nous savons que P = NP implique P = PH. Mais nous ne savons pas si BQP et QMA sont en PH, alors peut-être que P pourrait être égal à NP mais que BQP et QMA ne s'effondreraient toujours pas. (D'un autre côté, notez que QMA⊆PP⊆P ^#P , donc certainement P = P ^#P impliquerait BQP = QMA.) Montrer que BQP = QMA implique P = NP semble encore plus désespéré dans l'état actuel des connaissances .

2) Absolument, les trois barrières s'appliquent avec force à BQP vs. QMA (et même au problème "plus facile" de prouver P ≠ PSPACE). Premièrement, par rapport à un oracle PSPACE (ou même à l'extension à faible degré d'un oracle PSPACE), nous avons

P = NP = BQP = QMA = PSPACE,

il faudra donc certainement des techniques non relativisantes et non algébriquantes pour séparer ces classes. Deuxièmement, pour obtenir une barrière de preuves naturelles pour mettre des choses en dehors de BQP, tout ce dont vous avez besoin est une famille de fonctions pseudo-aléatoires qui est calculable en BQP, qui est une exigence formellement plus faible qu'une famille de fonctions pseudo-aléatoires calculable en P.

Addendum: Permettez-moi de dire quelque chose à propos d'une "métaquestion" que vous n'avez pas posée, mais qui a laissé entendre, pourquoi les gens se concentrent toujours sur P contre NP, même si nous pensons que la nature est quantique. Personnellement, j'ai toujours considéré P vs NP comme rien de plus que le «vaisseau amiral» pour tout un tas de questions de barrière en théorie de la complexité (P vs PSPACE, P vs BQP, NP vs coNP, NP vs BQP, l'existence de fonctions unidirectionnelles, etc.), aucunedont nous savons comment répondre, et qui sont tous liés en ce sens que toute percée avec l'un entraînerait très probablement des percées avec les autres (même lorsque nous n'avons pas d'implications formelles entre les questions, ce que dans de nombreux cas nous faire). P contre NP n'est pas intrinsèquement plus fondamental que les autres - mais si nous devons choisir une question pour servir d'enfant d'affiche de la complexité, alors c'est un bon choix.