Une machine de Turing peut-elle simuler un ordinateur quantique?

62

Je sais qu'une machine de Turing 1 peut théoriquement simuler "n'importe quoi", mais je ne sais pas si elle pourrait simuler quelque chose d'aussi fondamentalement différent qu'un ordinateur quantique. Y a-t-il des tentatives en ce sens ou quelqu'un l'a-t-il prouvé possible / impossible?

J'ai cherché sur Google, mais je ne suis pas un expert en la matière, je ne sais donc pas où chercher. J'ai trouvé l'article de Wikipedia sur la machine de Turing quantique , mais je ne suis pas certain de la différence entre cet article et un MT classique. J'ai aussi trouvé le papier Universal's Turing Machine de Deutsch , de W. Fouché et al., Mais c'est assez difficile à comprendre pour moi.

1. Dans le cas où ce n'est pas clair, par machine de Turing, j'entends le concept théorique, pas une machine physique (c'est-à-dire une implémentation du concept théorique).

simulation quantum-turing-machine computability-theory Riker
la source

Réponses:

44

Oui , un ordinateur quantique pourrait être simulé par une machine de Turing , bien que cela ne signifie pas que les ordinateurs quantiques du monde réel ne pourraient pas bénéficier d’ un avantage quantique , c’est-à-dire d’un avantage significatif en termes de mise en œuvre par rapport aux ordinateurs classiques du monde réel.

En règle générale, si un humain peut décrire ou imaginer manuellement comment quelque chose doit fonctionner, cette imagination peut être mise en œuvre sur une machine de Turing. Les ordinateurs quantiques entrent dans cette catégorie.

À l'heure actuelle, l'une des grandes motivations de l'informatique quantique est que les qubits peuvent exister en superpositions , permettant essentiellement un calcul massivement parallèle. Ensuite, il y a le recuit quantique et d'autres petites astuces qui sont essentiellement des tactiques informatiques analogiques .

(1)|ψ⟩=α|0⟩+β|1⟩,

Mais ces avantages concernent l'efficacité. Dans certains cas, cette efficacité dépasse le cadre astronomique, permettant ainsi des choses qui n’auraient pas été pratiques avec du matériel classique. Cela fait que l'informatique quantique a des applications majeures en cryptographie et autres.

Cependant, l'informatique quantique n'est pas motivée par le désir de choses que nous ne pouvions fondamentalement pas faire auparavant. Si un ordinateur quantique peut effectuer une opération, une machine de Turing classique pourrait alors simuler un ordinateur quantique effectuant cette opération.

Le hasard n'est pas un problème. Je suppose que deux grandes raisons:

  1. De toute façon, le hasard peut être capturé plus précisément en utilisant les mathématiques de distribution .

  2. Le hasard n'est pas une vraie " chose " pour commencer; c'est simplement de l'ignorance. Et nous pouvons toujours produire de l'ignorance.

Nat
la source
7

Pour simuler l’effondrement de la fonction wave, vous avez besoin d’une source aléatoire. Donc, vous auriez besoin d'une machine probabiliste de Turing .

Bjørn Kjos-Hanssen
la source
6
Les appareils classiques peuvent utiliser des générateurs de nombres aléatoires typiques, ou ce qui convient à leurs objectifs. Le hasard n'est pas une qualité fondamentale qui doit provenir de la mécanique quantique (ce qui est un assez gros malentendu conceptuel que les gens tirent souvent de l' interprétation de Copenhague , qui est peut-être mieux comprise comme une approximation simplificatrice).
Nat
3
En général, si vous ne vous souciez pas de l'efficacité, vous pouvez simplement essayer chaque élément d'un espace au lieu d'en prélever un échantillon, en évitant le recours au hasard.
Tavian Barnes
2
Si vous souhaitez réellement créer tous les effets quantiques pertinents, vous devez pouvoir violer l'inégalité de Bell et, par conséquent, une machine de Turing probabiliste est insuffisante. Si vous souhaitez uniquement faire correspondre la puissance de calcul de la machine de Turing quantique, vous pouvez utiliser une machine de Turing sans aucun aléa. Dans tous les cas, une machine probabiliste de Turing ne sera pas utile.
Lézard discret
4

Pour compléter ce que d’autres ont dit: à notre connaissance, une machine de Turing (classique) ne peut véritablement simuler des corrélations quantiques . Ceci est explicitement affirmé dans la section Propriétés de l'ordinateur quantique universel par le document fondateur de David Deutsch La théorie quantique, le principe de Church-Turing et l'ordinateur quantique universel (Actes de la Royal Society of London, A 400, pp. 97-117 (1985). )).

Les détails dépendront de la mise en œuvre ou de vos définitions exactes pour la machine de Turing, de l'ordinateur quantique, et en particulier de la simulation (si vous êtes assez généreux avec ce qui est simulé , tout peut simuler n'importe quoi). De manière générale, il est possible de concevoir un ordinateur quantique qui, lorsqu’il est actionné de manière répétée en partant du même état de départ (ou des bits d’entrée), génère dans chaque opération des bits de sortie aléatoires présentant certaines corrélations quantiques entre eux.

Autant que je sache, une machine de Turing ne peut pas le faire.

Agaitaarino
la source
1
Cela vaut peut-être la peine d’ajouter (c’est peut-être plus une reformulation, mais je pense qu’elle est utile): ajouter la «génération de nombres aléatoires» à une machine de Turing (comme un oracle) n’aide pas à la simulation de Turing quantique. machine, car il ne peut pas simuler de bits qui violent l’inégalité de Bell, alors qu’une machine de Turing quantique peut (comme le dit Deutsch dans le document, si je le lis correctement).
Lézard discret