Cet article implique-t-il que Turing-Computability n'est pas la même chose que «effectivement calculable»?

Tout d'abord, je m'excuse si cela a été demandé, mais je n'ai vraiment rien trouvé.

Je suis tombé sur cet article . Il indique qu'il existe un problème que seuls les ordinateurs quantiques peuvent résoudre. À ma connaissance, cela devrait signifier, intuitivement, que ce problème est "effectivement calculable", car nous avons une méthode réelle et efficace pour le calculer: construire un ordinateur quantique et le résoudre. Mais, comme une machine de Turing (les machines de Turing ne sont pas des ordinateurs quantiques, je pense?) Ne peut pas le résoudre, ce n'est pas calculable par Turing.

Par conséquent, cela signifie-t-il que «effectivement calculable» et «turing-calculable» ne sont pas le même concept? Alors, la thèse de Church-Turing est-elle fausse? Mon intuition dit "non", car dans ce cas, ce serait une très grosse nouvelle. Sinon, pourquoi pas?

Aussi, je suis conscient qu'il existe déjà des modèles de calcul plus puissants que les machines de Turing, mais ceux-ci ne sont que "théoriques", n'est-ce pas? Les ordinateurs quantiques, en revanche, sont physiquement constructibles.

Il existe de nombreuses significations différentes du mot "peut". Existe-t-il un algorithme qui peut briser le cryptage AES-512? Une stratégie consisterait à prendre les 2 ^ 512 blocs possibles de 512 bits, à les chiffrer tous avec la clé publique et à vérifier pour chacun s'ils correspondent au texte chiffré. Dans un sens purement abstrait, il s'agit d'un algorithme qui "peut" casser AES-512. D'un point de vue pratique, la conversion de toute la matière de l'univers connu en ordinateurs, et l'exécution du programme sur eux jusqu'à la mort par la chaleur de l'univers, ne serait pas en mesure de vérifier tous les 2 ^ 512 blocs.

Ainsi, il existe un concept théorique abstrait de «peut» qui ne prend pas en compte la quantité de ressources nécessaires, et une signification pratique qui le fait.

La calculabilité de Turing concerne le premier type de «boîte». Une machine de Turing est un appareil autorisé à fonctionner pendant une durée illimitée avec une mémoire illimitée. Il s'agit d'un modèle abstrait utilisé pour formuler des affirmations théoriques. Aucune vraie MT n'existe réellement dans le monde réel.

Ainsi, il n'y a pas de contradiction entre affirmer, d'une part, que tout ce qu'un ordinateur quantique peut faire, une MT peut aussi faire, et d'autre part affirmer qu'il existe des problèmes qu'un ordinateur quantique peut résoudre, mais aucun ordinateur classique ne peut résoudre; un ordinateur réel aura des restrictions d'alimentation d'ordinateur qu'un MT n'a pas.

Tout d'abord, les ordinateurs quantiques (ou plutôt les modèles théoriques de calcul quantique) ne sont en fait pas plus puissants que les machines Turing, en ce sens qu'ils peuvent être émulés sur une machine Turing et peuvent émuler eux-mêmes une machine Turing. Notez que l'article lui-même n'utilise pas le mot «calculable», et pour une bonne raison. La calculabilité n'est pas ce dont ils parlent.

La différence entre les ordinateurs quantiques et les ordinateurs classiques est la vitesse. C'est là qu'intervient la théorie de la complexité. Ici, tous les problèmes que nous considérons sont calculables, mais certains peuvent être très inefficaces à résoudre en termes de temps d'exécution asymptotique ou d'utilisation de la mémoire.

La Hiérarchie polynomiale (PH) est une grande classe qui contient des problèmes qui sont fondamentalement un jeu alternant entre deviner de manière non déterministe une solution et en trouver une (ou plutôt, alterner des quantificateurs existentiels et universels), mais tous en temps polynomial. P est la classe la plus élémentaire du PH et correspond grosso modo aux problèmes que nous pouvons résoudre en un temps raisonnable sur les ordinateurs classiques. NP est une autre sous-classe de base de PH.

BQP est l'analogue de P pour les ordinateurs quantiques. Eh bien, pas entièrement, BQP est plus proche de BPP, où nous permettons à notre ordinateur classique de donner une mauvaise réponse avec seulement une faible probabilité. Les effets quantiques ne peuvent pas vraiment être exploités sans impliquer la probabilité de manière significative. Dans tous les cas, BPP est toujours dans PH.

Cet article concerne un problème dont il a été prouvé qu'il ne réside pas dans PH, mais dans BQP. D'une certaine manière, le «pas quantique» permet de résoudre un problème qui n'est même pas proche de P ou BPP classiquement, pas même dans la même hiérarchie infinie, en temps polynomial sur un ordinateur quantique. Il s'agit donc d'une preuve solide de la puissance (théorique) du modèle informatique quantique.

Quant à la thèse de Church-Turing, le calcul quantique étant plus rapide que le classique ne le contredit pas, car la thèse ne se soucie pas du temps de calcul. Cependant, la thèse de Church-Turing plus étendue est contredite par ce résultat (c'est-à-dire si des ordinateurs quantiques évolutifs sont réellement construits)