Quelle est la différence entre la MT quantique et la TM non déterministe?

Je passais par la discussion sur la question Comment définir les machines de Turing quantiques? et je sens que TM quantique et TM non déterministe sont une seule et même chose. Les réponses à l'autre question ne touchent pas à cela. Ces deux modèles sont-ils identiques?

Sinon,

1. Quelles sont les différences entre quantum TM et NDTM?
2. Existe-t-il un calcul qu'un NDTM ferait plus rapidement que Quantum TM?
3. Si c'est le cas, alors quantum TM est un DTM, alors pourquoi y a-t-il tant de fuzz sur cette technologie, nous avons déjà tellement de DTM. Pourquoi finalement concevoir un nouveau DTM?

En tant que préambule général, les QTM, TM et NTM sont toutes des choses différentes (prenant d'énormes libertés avec un tas d'hypothèses tacites).

Je suppose que vous savez ce qu'est une machine de Turing.

1. Un NTM est un TM où, à n'importe quel état, avec n'importe quel symbole, la fonction de transition peut avoir un certain nombre de choix d'action qui ne sont pas précisément , c'est-à - dire ou plus de (un TM déterministe doit avoir exactement une action pour chaque symbole à chaque état, bien que le cas soit facile à gérer). Face à une situation où il y a plusieurs choix de transition, une MNT fera le choix qui la mènera finalement à un état acceptant, si une telle option existe. En revanche, un QTM est un modèle de calcul quantique , comme détaillé dans le fil que vous avez lié. Ce n'est pas0 1 $1$ $0$$1$$0$
   
   non déterministe, pas tous. Les principales différences de haut niveau entre un QTM et un TM sont probablement qu'un QTM a pour état une combinaison linéaire des états de base (encore une fois, tout est dans cet autre thread) et qu'il est probabiliste, c'est-à-dire la précision de sa sortie est limité par une probabilité inférieure à (au sens large). Juste pour être vraiment très clair sur un point qui attire beaucoup de gens, le non-déterminisme n'est pas le hasard, ce n'est pas le parallélisme, c'est une construction théorique qui n'a rien à voir avec l'un ou l'autre. $1$
   
   
2. La réponse complète à cela dépend de certaines hypothèses théoriques de complexité. En prenant un point de vue particulier (que et N P ⊃ P ), la réponse est oui. Les problèmes N P- complétés peuvent être résolus par un NTM en temps polynomial, et il semble également que N P -complets ∩ B Q P = ∅ , donc ils ne peuvent pas être résolus par un QTM en temps polynomial. Encore une fois, tout dépend de la façon dont les cartes tombent avec une variété de classes de complexité. S'il s'avère que Q M A = $QMA \supset BQP$$NP \supset P$$NP$$NP\text{-complete} \cap BQP = \emptyset$
   
   alors la réponse est non, par exemple. $QMA = BQP$
3. La première chose à dire ici est de faire attention à ne pas confondre les MT (de toute nature) et les ordinateurs. Une MT n'est pas un ordinateur, une QTM n'est pas un ordinateur quantique. Calcul de modèles de MT (de tout type). Ce qu'un ordinateur donné peut faire est régi par cela, mais cela est très différent de dire que la chose sur laquelle je tape ceci est une MT.
   
   Cela dit, si nous parlons de façon lâche et paresseuse des QTM avec des ordinateurs quantiques et des MT avec des ordinateurs standard, alors (encore une fois sous certaines hypothèses de complexité), il semble que les ordinateurs quantiques peuvent rapidement effectuer certaines tâches qui semblent difficiles pour les ordinateurs standard (factorisation, journaux discrets , un type de recherche vraiment particulier, et quelques autres). Cependant, ces problèmes ne sont pas connus pour être difficiles dans le $NP$- sens complet non plus, il semble que les ordinateurs quantiques offrent des capacités qui étendent un ordinateur standard, mais dans une direction différente de ce qui serait nécessaire pour résoudre rapidement les problèmes complets. $NP$

Encore une fois, pour être vraiment clair, j'ai glissé sur beaucoup de complexité informatique ici, si vous voulez vraiment comprendre comment tout s'emboîte, vous devrez commencer à fouiller dans la littérature.

Sur le sens du non-déterminisme

Il y a deux sens différents de «non-déterminisme» en cause ici. La mécanique quantique est généralement décrite comme «non déterministe», mais le mot «non déterministe» est utilisé de manière spécialisée en informatique théorique.

1. Un sens, qui s'applique à la mécanique quantique, n'est simplement pas « déterministe ». C'est généralement une façon raisonnable d'interpréter le mot, et en fait, ni les machines de Turing quantiques ni même les machines de Turing probabilistes ne sont déterministes dans la façon dont elles résolvent les problèmes de décision.

2. Cependant, lors de la description de modèles de calcul, non déterministe est utilisé spécifiquement pour signifier que la machine peut (en un sens) faire des choix qui ne sont pas déterminés par son état ou son entrée, pour obtenir un objectif particulier. Cette signification est utilisée ailleurs dans la description de modèles de calcul, tels que les automates finis non déterministes .

Ainsi, les machines de Turing quantiques sont un modèle de calcul qui n'est pas déterministe, mais qui est différent d'une " machine de Turing non déterministe ".

Machines de Turing non déterministes

Une machine de Turing non déterministe est une machine qui peut explorer plusieurs transitions possibles. La transition qu'il effectue à une étape donnée dépend, mais n'est pas déterminée, de l'état dans lequel il se trouve et du symbole qu'il lit. Il y a deux façons de présenter cela couramment:

• Surtout pour définir la classe de complexité NP , on peut décrire la machine comme faisant des choix (ou des suppositions) à chaque étape afin d' essayer d'atteindre un état d'acceptation. Si vous pensez à ce que fait la machine non déterministe en explorant un arbre de décision, elle cherche un chemin d'acceptation dans l'arbre. Bien qu'aucun mécanisme qui soit décrit pour suggérer comment un tel chemin devrait être trouvé, nous imaginons qu'il trouvera un chemin d'acceptation s'il n'en existe qu'un seul.

• Il est également assez courant de dire qu'une machine non déterministe explore tous les chemins possibles dans l'arbre de décision en parallèle et donne une réponse «oui» si l' un d'eux s'avère être un chemin acceptant.

Des traitements plus modernes du non-déterminisme ne tiennent pas seulement compte de l'existence, mais du nombre de voies d'acceptation; et cela est bien adapté à la description de l'exploration de tous les chemins en parallèle. Nous pouvons imposer des contraintes supplémentaires, par exemple que tous les chemins de calcul ont la même longueur (que la machine prend toujours le même temps pour effectuer un calcul) et que chaque chemin effectue une supposition à chaque étape, ou à chaque deuxième étape, même si la supposition n'est pas utilisée. Si nous le faisons, nous pouvons formuler des modèles probabilistes de calcul, tels que des machines de Turing aléatoires (motivant des classes de complexité telles que BPP ), en termes de nombred'accepter les chemins d'une machine de Turing non déterministe. Nous pouvons également inverser la tendance et décrire les machines de Turing non déterministes en termes d'ordinateurs randomisés qui peuvent en quelque sorte distinguer les résultats qui ont une probabilité nulle de ceux qui ont une probabilité non nulle .

Machines de Quantum Turing

La principale différence entre une machine de Turing quantique et une machine non déterministe est la suivante: au lieu de `` choisir '' de façon non déterministe une seule transition sur deux ou plus à chaque étape, une machine de Turing quantique effectue une transition vers une superposition d'une ou plusieurs transitions possibles. L'état complet de la machine est défini comme un vecteur unitaire dans un espace vectoriel complexe, défini par des combinaisons linéaires d'états de base décrits par des états classiques de la bande, la position de la tête de machine et "l'état interne" de la tête de machine . (Voir par exemple page 9, Définition 3.2.2, de la théorie de la complexité quantiquepour la description complète de la façon dont les machines de Turing quantiques effectuent des transitions.) La condition dans laquelle la machine de Turing quantique accepte une entrée est également plus restrictive, et implique intrinsèquement la probabilité, nécessitant une probabilité substantielle d'observer le résultat correct pour réussir.

En conséquence, les machines quantiques de Turing diffèrent des machines non déterministes en ce que la façon dont elles effectuent leurs transitions n'est pas complètement indéterminée. Même si la transition "semble mystérieuse", c'est aussi le même genre d'évolution avec le temps que notre meilleure théorie de la matière indique qu'elle se produit dans le monde réel. S'il est courant de décrire les ordinateurs quantiques comme "explorant différents chemins de calcul en parallèle", ce n'est pas particulièrement utile: les amplitudes sur les différents chemins signifient qu'ils n'ont pas tous la même importance, et contrairement aux machines de Turing non déterministes, il n'est pas suffisant pour avoir une amplitude non nulle sur certains résultats; il doit être possible d'obtenir une très grande probabilité d'obtenir le résultat correct, comme 2/3. (La classe de problèmes BQPqu'une machine de Turing quantique peut résoudre efficacement nécessite un écart de probabilité du même type que celui de BPP pour le calcul aléatoire.) En outre, contrairement aux machines de Turing non déterministes, une machine de Turing quantique peut interférer entre elles après leur séparation , ce qui est tout simplement impossible dans la formulation typique d'une machine de Turing non déterministe (et cela rend la description en termes d'arbre de décision moins utile en premier lieu).

Comparaison des deux modèles

Nous ne savons pas si l'une de ces machines est plus puissante que l'autre; les différentes manières dont elles ne sont pas déterministes semblent différentes les unes des autres et difficiles à comparer.

Quant aux problèmes que chaque machine peut faire rapidement, que l'autre ne peut pas (à notre connaissance):

• Nous ne savons pas comment une machine de Turing quantique pourrait résoudre rapidement le problème de SATISFACILITÉ . Une machine de Turing non déterministe peut, facilement.
• Les travaux d'Aaronson et Archipov ( La complexité computationnelle de l'optique linéaire ) suggèrent qu'il est peu probable que les machines de Turing non déterministes soient capables de simuler efficacement certaines expériences d'optique linéaire qui pourraient être simulées par une machine de Turing quantique.

Mais même si quelqu'un montre comment relier les deux types de machines entre elles - et même dans le scénario extrêmement improbable que quelqu'un montre que BQP  =  NP (les problèmes qu'une machine de Turing quantique et une machine de Turing non déterministe peuvent respectivement résoudre rapidement ) - les deux machines qui définissent ces modèles de calcul sont assez différentes l'une de l'autre.