Worldlex Wiki Les machines de Turing quantiques peuvent être reliées aux machines de Turing classiques et probabilistes dans un cadre basé sur les matrices de transition . Autrement dit, il est possible de définir une matrice dont le produit avec la matrice représentant une machine classique ou probabiliste fournit la matrice de probabilité quantique représentant la machine quantique. Ce résultat a été démontré par Lance Fortnow .
ordinateur quantique universel est-il suffisant pour simuler efficacement un système physique arbitraire ?On peut comprendre la machine de Turing quantique (MTT) comme une généralisation de la machine de Turing classique (MT), de la même manière que l' automate fini quantique (AFQ) généralise l' automate fini déterministe (AFD). En substance, les états internes d'une MT classique sont remplacés par des états purs ou mixtes dans un espace de Hilbert ; la fonction de transition est remplacée par un ensemble de matrices unitaires qui transforment l'espace de Hilbert en lui-même.
Autrement dit, une machine de Turing classique est décrite par un n-uplet de 7 éléments . Pour une compréhension plus détaillée de chaque élément de ce n-uplet, veuillez consulter la définition formelle d'une machine de Turing .
Pour une machine de Turing quantique à trois bandes (une bande contenant l'entrée, une deuxième bande contenant les résultats de calcul intermédiaires et une troisième bande contenant la sortie) :
- L'ensemble des états est remplacé par un espace de Hilbert .
- Les symboles de l'alphabet de la bande sont également remplacés par un espace de Hilbert (généralement un espace de Hilbert différent de l'ensemble des états).
- Le symbole vide est un élément de l'espace de Hilbert.
- Les symboles d'entrée et de sortie sont généralement considérés comme un ensemble discret, comme dans le système classique ; ainsi, ni l'entrée ni la sortie d'une machine quantique n'ont besoin d'être elles-mêmes un système quantique.
- La fonction de transition est une généralisation d'un semi-automate et est considérée comme une collection de matrices unitaires qui sont des automorphismes de l'espace de Hilbert .
- L'état initial peut être soit un état mixte , soit un état pur .
- L'ensemble des états finaux ou acceptants est un sous-espace linéaire de l'espace de Hilbert .
Ce qui précède n'est qu'une esquisse d'une machine de Turing quantique, et non sa définition formelle, car plusieurs détails importants restent flous : par exemple, la fréquence des mesures ; voir, par exemple, la différence entre un automate fini quantique à mesure unique et un automate à mesures multiples. Cette question de la mesure influe sur la définition des écritures sur la bande de sortie.
Histoire
En 1980 et 1982, le physicien Paul Benioff a publié des articles qui décrivaient pour la première fois un modèle quantique des machines de Turing . Un article de 1985 écrit par le physicien David Deutsch de l'Université d'Oxford a développé davantage l'idée des ordinateurs quantiques en suggérant que les portes quantiques pourraient fonctionner de manière similaire aux portes logiques binaires de l'informatique numérique traditionnelle .
Iriyama, Ohya et Volovich ont développé un modèle de machine de Turing quantique linéaire (LQTM). Il s'agit d'une généralisation d'une machine de Turing quantique classique comportant des états mixtes et autorisant des fonctions de transition irréversibles. Celles-ci permettent la représentation de mesures quantiques sans résultats classiques.
Une machine de Turing quantique avec postsélection a été définie par Scott Aaronson , qui a montré que la classe de temps polynomial sur une telle machine ( PostBQP ) est égale à la classe de complexité classique PP .