Implémentation d'une porte CCCNOT utilisant uniquement des portes Toffoli

10

Une porte CCCNOT est une porte réversible à quatre bits qui retourne son quatrième bit si et seulement si les trois premiers bits sont tous à l'état 1 .

Comment pourrais-je implémenter une porte CCCNOT en utilisant les portes Toffoli? Supposons que les bits de l'espace de travail commencent par une valeur particulière, soit 0 ou 1, à condition que vous les renvoyiez à cette valeur.

chuster
la source
Utiliser uniquement des portes Toffoli, ou Toffoli et CNOT sont-ils un jeu équitable?
user1271772
Seules les portes de Toffoli sont autorisées.
chuster
1
Quelle partie de cette question est quantique? Il semble que vous souhaitiez décomposer une porte réversible classique (CCCNOT) en plus petites portes réversibles classiques (CCNOT).
user1271772
1
La question elle-même ne concerne pas l'informatique quantique, mais les portes sont importantes pour les circuits quantiques.
chuster

Réponses:

8

Je suppose que ce que vous recherchez est le circuit suivant. Ici, b1,b2,b3,b4{0,1} , et est l'addition modulo 2 .

entrez la description de l'image ici

Ici, le cinquième qubit est utilisé comme auxiliaire ou ancilla qubit . Cela commence à |0 et se termine à |0 lorsque le circuit est appliqué.

Permettez-moi de vous expliquer comment ce circuit fonctionne. L'idée est tout d'abord de vérifier si les deux premiers qubits sont en état |1 . Cela peut être fait en utilisant une seule porte Toffoli, et le résultat est stocké dans le qubit auxiliaire. Maintenant, le problème se réduit à retourner le qubit 4 , chaque fois que qubits 3 et le qubit auxiliaire sont dans |1 . Ceci peut également être réalisé en utilisant une application d'une porte Toffoli, à savoir celle du milieu dans le circuit illustré ci-dessus. Enfin, la dernière porte de Toffoli sert à non- calculer le résultat temporaire que nous avons stocké dans le qubit auxiliaire, de sorte que l'état de ce qubit retourne à |0 après l'application du circuit.


Dans la section des commentaires, la question s'est posée de savoir s'il est possible de mettre en œuvre un tel circuit en utilisant uniquement des portes Toffoli, sans utiliser de qubits auxiliaires. On peut répondre à cette question par la négative, comme je vais le montrer ici.

Nous voulons implémenter la porte CCCNOT , qui agit sur quatre qubits. Nous pouvons définir la matrice suivante (la représentation matricielle du Pauli- X -gate):

X=[0110]
Par ailleurs, on note la N matrice d'identité par -dimensionnelle jeN . Maintenant, nous observons que la représentation matricielle de la porte CCCNOT , agissant sur quatre qubits, est donnée par la matrice 16×16 :
CCCNOT=[je1400X]
Par conséquent, nous pouvons déterminer son déterminant:
det(CCCNOT)=-1
Considérons maintenant la représentation matricielle de la porte de Toffoli, agissant sur les trois premiers qubits d'un4 -qubit system. Sa représentation matricielle s'écrit (où nous avons utilisé le produit Kronecker des matrices):
ToFFoljeje2=[je600X]je2=[je1200Xje2]=[je120000je20je20]
Calcul de ses rendements déterminants:
det(ToFFoljeje2)=1
Les portes Toffoli peuvent également agir sur différents qubits bien sûr. Supposons que nous laissions la porte de Toffoli agir sur le premier, le deuxième et le quatrième qubit, où le quatrième qubit est le qubit cible. Ensuite, nous obtenons la nouvelle représentation matricielle de celle affichée ci-dessus en échangeant les colonnes correspondant aux états qui ne diffèrent que dans le troisième et le quatrième qubit, c'est-à-dire |0001 avec |0010 , |0101 avec |0110 , etc. La chose importante à noter ici, est que le nombre de swaps de colonnes est même, et par conséquent que le déterminant reste inchangé. Comme nous pouvons écrire chaque permutation de qubits comme une séquence de permutations consécutives de seulement2 qubits (c'est-à-dire queS4 est généré par les transpositions deS4 ), nous constatons que pour toutes les portes de Toffoli, appliquées à toute combinaison de qubits de contrôle et de cible, sa représentation matricielle a le déterminant1 .

La dernière chose à noter est que le déterminant commute avec la multiplication matricielle, c'est-à-dire det(UNEB)=det(UNE)det(B) , pour deux matrices UNE et B compatibles avec la multiplication matricielle. Par conséquent, il devient maintenant évident que l'application de plusieurs portes Toffoli en séquence ne crée jamais un circuit dont la représentation matricielle a un déterminant différent de 1 , ce qui implique en particulier que la porte CCCNOT ne peut pas être implémentée en utilisant uniquement des portes Toffoli sur 4 qubits.

CCCNOT5

CCCNOTje2=[je1400X]je2=[je280000je20je20]
det(CCCNOTje2)=1
CCCNOT51-15

arriopolis
la source
1
une source, ou une méthode utilisée pour dériver le circuit, serait utile!
glS
1
Je ne connais aucune source expliquant comment concevoir de tels circuits de manière globale. Les sources que j'ai utilisées pour apprendre l'informatique quantique étaient le livre de Nielsen et Chuang, et les notes de cours qui peuvent être trouvées ici: homepages.cwi.nl/~rdewolf/qcnotes.pdf , mais ces sources ne se concentrent pas spécifiquement sur la conception des circuits quantiques.
arriopolis
2
J'ai essayé de développer un peu plus le fonctionnement du circuit. J'espère que cela vous aidera à concevoir des circuits similaires à celui-ci! :)
arriopolis
Est-ce possible sans auxiliaires?
user1271772
1
+1CCCNOT4-1CCCNOT+1