Pourquoi un ordinateur quantique est-il à certains égards plus puissant qu'une machine de Turing non déterministe?

Le compte-rendu standard de l'informatique quantique est qu'un ordinateur quantique (CQ) fonctionnerait en se divisant en plusieurs exponentiellement copies parallèles sans interaction de lui-même dans différents univers et en demandant à chacun d'essayer de vérifier un certificat différent, puis à la fin du calcul , la copie unique qui a trouvé un certificat valide "annonce" sa solution et les autres branches disparaissent comme par magie.

Les gens qui savent quoi que ce soit sur le calcul quantique théorique savent que cette histoire est un non-sens absolu, et que l'idée approximative décrite ci-dessus correspond plus étroitement à une machine de Turing non déterministe (NTM) qu'à un ordinateur quantique. De plus, la classe de complexité des problèmes pouvant être résolus efficacement par les MNT est NP et par les QC est BQP , et ces classes ne sont pas considérées comme égales.

Les personnes qui tentent de corriger la présentation populaire soulignent à juste titre que le récit simpliste des "mondes multiples" surestime considérablement la puissance des QC, qui ne sont pas censés être en mesure de résoudre (disons) des problèmes complets liés au NP . Ils se concentrent sur la fausse représentation du processus de mesure: en mécanique quantique, le résultat que vous mesurez est déterminé par la règle de Born, et dans la plupart des situations, la probabilité de mesurer une réponse incorrecte submerge complètement la probabilité de mesurer la bonne. (Et dans certains cas, comme la recherche dans la boîte noire, nous pouvons prouver qu'aucun circuit quantique intelligent ne peut battre la règle de Born et fournir une accélération exponentielle.) Si nous le pouvionsmagiquement "décider quoi mesurer", alors nous serions en mesure de résoudre efficacement tous les problèmes dans la classe de complexité PostBQP , qui est considérée comme beaucoup plus grande que BQP .

Mais je n'ai jamais vu personne souligner explicitement qu'il existe une autre manière dont la caractérisation populaire est erronée, qui va dans l'autre sens. On pense que BQP n'est pas un sous-ensemble strict de NP , mais plutôt incomparable avec lui. Il existe des problèmes comme la vérification de Fourier qui ne se situent pas seulement en dehors de NP , mais en fait en dehors de toute la hiérarchie polynomiale PH . Donc, en ce qui concerne des problèmes comme ceux-ci, le récit populaire sous les États plutôt que surévalue le pouvoir des QC.

Mon intuition naïve est que si nous pouvions "choisir quoi mesurer", alors le récit populaire serait plus ou moins correct, ce qui impliquerait que ces ordinateurs super-quantiques seraient capables de résoudre efficacement la classe NP . Mais nous pensons que c'est faux; en fait PostBQP = PP , que nous pensons être un sur-ensemble strict de NP .

Y a-t-il une intuition pour ce qui se passe dans les coulisses qui permet à un ordinateur quantique d'être (à certains égards) plus puissant qu'une machine de Turing non déterministe? Vraisemblablement, cette puissance "intrinsèquement quantique", lorsqu'elle est combinée avec la post-sélection (qui dans un sens, les NTM ont déjà) est ce qui rend un super-QC tellement plus puissant qu'un NTM. (Notez que je recherche une intuition qui contraste directement les NTM et les QC avec la post-sélection, sans "traverser" la classe de complexité classique PP .)

D'un point de vue pseudo-fondateur, la raison pour laquelle BQP est une classe (pour inventer une phrase) différemment puissante que NP , est que les ordinateurs quantiques peuvent être considérés comme faisant usage d'interférences destructrices.

De nombreuses classes de complexité différentes peuvent être décrites en termes de (propriétés plus ou moins compliquées) du nombre de branches acceptantes d'un MNT. Étant donné un MNT sous une `` forme normale '', ce qui signifie que l'ensemble des branches de calcul est un arbre binaire complet (ou quelque chose de similaire) d'une certaine profondeur polynomiale, nous pouvons considérer des classes de langages définies en faisant les distinctions suivantes:

• Le nombre de branches acceptantes est-il nul ou non nul? (Une caractérisation de NP .)
• Le nombre de succursales acceptantes est-il inférieur au maximum ou exactement égal au maximum? (Une caractérisation de coNP .)
• Le nombre de succursales acceptant est-il au maximum un tiers, ou au moins deux tiers du total? (Une caractérisation de BPP .)
• Le nombre de succursales acceptantes est-il inférieur à la moitié ou au moins à la moitié du total? (Une caractérisation de PP .)
• Le nombre de succursales acceptantes est-il différent d'exactement la moitié ou exactement de la moitié du total? (Une caractérisation d'une classe appelée C ₌ P. )

Celles-ci sont appelées classes de comptage , car elles sont en fait définies en termes de nombre de branches acceptantes.

Interprétant les branches d'une MNT comme générées aléatoirement, ce sont des questions sur la probabilité d'acceptation (même si ces propriétés ne sont pas testables efficacement avec une quelconque certitude statistique). Une approche différente pour décrire les classes de complexité consiste à considérer à la place l' écart entre le nombre de branches d'acceptation et le nombre de branches de rejet d'une MNT. Si le comptage du cumul des branches de calcul NTM correspond à des probabilités, on pourrait suggérer que l'annulation de branches d'acceptation contre les branches de rejet modélise l'annulation de `` chemins '' de calcul (comme dans la somme sur les chemins) dans le calcul quantique - c'est-à-dire, comme la modélisation d'interférences destructives .

Les limites supérieures les plus connues pour BQP , à savoir AWPP et PP , sont facilement définissables en termes de «lacunes d'acceptation» de cette manière. La classe NP , cependant, n'a pas une caractérisation aussi évidente. De plus, bon nombre des classes que l'on obtient à partir des définitions en termes de lacunes d'acceptation semblent être plus puissantes que NP . On pourrait considérer cela comme indiquant que «l'interférence destructive non déterministe» est une ressource informatique potentiellement plus puissante que le simple non-déterminisme; de sorte que même si les ordinateurs quantiques ne tirent pas pleinement parti de cette ressource de calcul, elle peut néanmoins résister à un confinement facile dans des classes telles que NP .

Cette réponse a été «migrée» à partir du moment où cette question a été posée sur l' informatique (l'auteur reste le même)

Eh bien, l'une des principales raisons est qu'il n'y a pas d'algorithmes quantiques qui résolvent les problèmes NP-difficiles en temps polynomial.

Un autre est que le recuit quantique adiabétique (comme dans le Dwave) ne peut que battre à peine le recuit quantique classique.

$\neq$$=$$\neq$$\neq$$=$$=$

$=$

$\neq$

Il existe des problèmes tels que la vérification de Fourier qui ne se situent pas seulement en dehors de NP, mais en fait en dehors de toute la hiérarchie polynomiale. Donc, en ce qui concerne des problèmes comme ceux-ci, le récit populaire sous-estime en fait plutôt qu'il n'exagère le pouvoir des QC.

$O(n)$$O(n)$