En logique non quantique, vous montrez qu'un autre ensemble d'opérateurs booléens connu pour être universel peut être simulé par l'ensemble en question. Je ne sais pas si c'est la même chose dans le monde quantique, mais je pense que oui.
Raphael
8
En logique quantique, la porte de Toffoli n'est pas universelle, car vous ne pouvez faire que des calculs classiques avec elle. Vous avez également besoin d'une porte quantique qui, si l'entrée est dans un état de base, place la sortie dans une superposition d'états de base.
Peter Shor
Je me rends compte que la question peut prêter à confusion, peut-être devrait-elle être modifiée pour demander la différence entre l'universalité dans le monde quantique / classique.
Ran G.
J'ai édité ma réponse pour couvrir le cas quantique. Que pensez-vous maintenant?
Victor Stafusa
1
@A sonné. Nous sommes censés montrer la voie pour les questions futures, cette question est étiquetée devoirs, mais il semble que vous n'expliquez pas pourquoi vous n'avez pas pu le résoudre vous-même (et où se situe le problème). Je pense que ce n'est pas une bonne question pour la bêta privée (voir la méta discussion ). Je vote pour clore cette question.
Gopi
Réponses:
13
Toffoli est universel pour le calcul classique (comme le montre @Victor). Cependant, Toffoli n'est PAS universel pour le calcul quantique (sauf si nous avons quelque chose de fou comme ).P=BQP
Pour être universel pour le calcul quantique (selon la définition habituelle), le groupe généré par vos portes doit être dense dans les unitaires. En d' autres termes, étant donné un arbitraire et cible unitaire U il y a un moyen d'appliquer un nombre fini de vous quantiques portes pour obtenir un unitaire U ' tel que | | U - U ′ | | < ϵ .ϵUU′||U−U′||<ϵ
Toffoli en soi n'est clairement pas universel selon cette définition car il prend toujours des états de base en états de base, et ne peut donc pas implémenter quelque chose qui prend par exemple. En d'autres termes, il ne peut pas créer de superposition.|0⟩→12√(|0⟩+|1⟩)
La porte Toffoli est universelle; cela signifie que pour toute fonction booléenne f (x1, x2, ..., xm), il existe un circuit composé de portes Toffoli qui prend x1, x2, ..., xm et quelques bits supplémentaires mis à 0 ou 1 et sort x1, x2, ..., xm, f (x1, x2, ..., xm) et quelques bits supplémentaires (appelés ordures). Essentiellement, cela signifie que l'on peut utiliser les portes de Toffoli pour construire des systèmes qui effectueront tout calcul de fonction booléenne souhaité de manière réversible.
Ce qui signifie en termes simples que toute fonction booléenne ne peut être construite qu'avec des portes Toffoli.
Les fonctions booléennes sont généralement construites à partir de portes OU, ET et NON, qui peuvent être combinées pour former n'importe quelle fonction booléenne. Il est largement connu que la même chose n'est possible qu'avec des portes NOR ou uniquement avec des portes NAND.
EDIT, car la question a été modifiée et son champ d'application a changé:
Tout d'abord, je ne comprends pas l'informatique quantique, donc s'il y a quelque chose qui ne va pas, veuillez ajouter un commentaire. J'ai fait un peu de recherche pour essayer de compléter cette réponse et j'ai terminé avec ceci:
La porte Toffoli est réversible (mais pas celle utilisée ci-dessus). Cela signifie que tout calcul effectué avec lui peut être annulé. C'est:
( a , b , c ) = T o fFo l i ( T o fFo l i (a,b,c))
Ce qui signifie que pour tout triple (a, b, c) si le Toffoli est appliqué deux fois, l'entrée d'origine est obtenue comme sortie.
La réversibilité est importante car les portes quantiques doivent être réversibles, de sorte que la porte (classique) de Toffoli peut être utilisée comme porte quantique pour cette raison.
Comme démontré ici , la porte Deutsch est définie de la même manière que la porte Toffoli, mais au lieu d'une porte classique, elle est quantique:
Deutsch( a , b , c ) = | a , b , c ⟩ ↦ { i cos( θ ) | a , b , c ⟩ + sin(θ)|a,b,1−c⟩|a,b,c⟩for a=b=1otherwise.
De cette façon, la porte Toffoli est un cas particulier de la porte Deutsch où:
Toffoli(a,b,c)=Deutsch(π2)(a,b,c)
π2
Un ensemble quantique universel de Tgate peut être obtenu, si nous combinons la porte Toffoli avec la porte Hadamard. C'est exactement ce que fait la porte Deutsch.
Des références intéressantes peuvent être trouvées ici , ici et ici . Une référence précieuse possible, montrant les fondements de la transformation Deutsch devrait être ici , mais le lien est protégé par mot de passe.
Toffolli n'est pas universel pour le calcul quantique, ni CNOT par eux-mêmes. Ceci est facile à voir car ils ne peuvent pas créer de superposition.
Artem Kaznatcheev
{}
Votre référence dans EDIT 2 est incorrecte. Cet article indique clairement que Toffoli + Hadamard est universel, pas Toffoli en soi
Artem Kaznatcheev
@ArtemKaznatcheev: L'article dit "Toffoli et Hadamard". Puis j'ai pensé que cela signifiait "Toffoli est un exemple et Hadamart en est un autre". Quoi qu'il en soit, c'est clair maintenant.
Réponses:
Toffoli est universel pour le calcul classique (comme le montre @Victor). Cependant, Toffoli n'est PAS universel pour le calcul quantique (sauf si nous avons quelque chose de fou comme ).P=BQP
Pour être universel pour le calcul quantique (selon la définition habituelle), le groupe généré par vos portes doit être dense dans les unitaires. En d' autres termes, étant donné un arbitraire et cible unitaire U il y a un moyen d'appliquer un nombre fini de vous quantiques portes pour obtenir un unitaire U ' tel que | | U - U ′ | | < ϵ .ϵ U U′ ||U−U′||<ϵ
Toffoli en soi n'est clairement pas universel selon cette définition car il prend toujours des états de base en états de base, et ne peut donc pas implémenter quelque chose qui prend par exemple. En d'autres termes, il ne peut pas créer de superposition.|0⟩→12√(|0⟩+|1⟩)
la source
De l' article de wikipedia que vous avez cité :
Ce qui signifie en termes simples que toute fonction booléenne ne peut être construite qu'avec des portes Toffoli.
Les fonctions booléennes sont généralement construites à partir de portes OU, ET et NON, qui peuvent être combinées pour former n'importe quelle fonction booléenne. Il est largement connu que la même chose n'est possible qu'avec des portes NOR ou uniquement avec des portes NAND.
La porte de Toffoli peut être résumée comme suit:
Étant donné que les première et deuxième sorties sont toujours égales aux première et deuxième entrées, nous pouvons les ignorer. Nous avons donc:
Avec cela, il est possible de définir la porte NAND comme:
Puisque la porte NAND est universelle et que la porte NAND peut être définie comme une porte Toffoli, alors la porte Toffoli est universelle.
Il existe une autre façon de prouver que Toffoli est universel, en construisant directement les portes ET et NON:
Ensuite, nous pouvons construire la porte OU en utilisant les lois de De Morgan :
EDIT, car la question a été modifiée et son champ d'application a changé:
Tout d'abord, je ne comprends pas l'informatique quantique, donc s'il y a quelque chose qui ne va pas, veuillez ajouter un commentaire. J'ai fait un peu de recherche pour essayer de compléter cette réponse et j'ai terminé avec ceci:
La porte Toffoli est réversible (mais pas celle utilisée ci-dessus). Cela signifie que tout calcul effectué avec lui peut être annulé. C'est:
Ce qui signifie que pour tout triple (a, b, c) si le Toffoli est appliqué deux fois, l'entrée d'origine est obtenue comme sortie.
La réversibilité est importante car les portes quantiques doivent être réversibles, de sorte que la porte (classique) de Toffoli peut être utilisée comme porte quantique pour cette raison.
Comme démontré ici , la porte Deutsch est définie de la même manière que la porte Toffoli, mais au lieu d'une porte classique, elle est quantique:
De cette façon, la porte Toffoli est un cas particulier de la porte Deutsch où:
Un ensemble quantique universel de Tgate peut être obtenu, si nous combinons la porte Toffoli avec la porte Hadamard. C'est exactement ce que fait la porte Deutsch.
Des références intéressantes peuvent être trouvées ici , ici et ici . Une référence précieuse possible, montrant les fondements de la transformation Deutsch devrait être ici , mais le lien est protégé par mot de passe.
la source