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

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.

Je suppose que ce que vous recherchez est le circuit suivant. Ici, $b_1,b_2,b_3,b_4 \in \{0,1\}$ , et $\oplus$ est l'addition modulo $2$ .

Ici, le cinquième qubit est utilisé comme auxiliaire ou ancilla qubit . Cela commence à $|0\rangle$ et se termine à $|0\rangle$ 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\rangle$ . 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\rangle$ . 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\rangle$ 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 $\mathrm{CCCNOT}$ , qui agit sur quatre qubits. Nous pouvons définir la matrice suivante (la représentation matricielle du Pauli- $X$ -gate):

$$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ Par ailleurs, on note la $N$ matrice d'identité par -dimensionnelle $I_N$ . Maintenant, nous observons que la représentation matricielle de la porte $\mathrm{CCCNOT}$ , agissant sur quatre qubits, est donnée par la matrice $16 \times 16$ : $$\mathrm{CCCNOT} = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix}$$ Par conséquent, nous pouvons déterminer son déterminant: $$\det(\mathrm{CCCNOT}) = -1$$ Considérons maintenant la représentation matricielle de la porte de Toffoli, agissant sur les trois premiers qubits d'un$4$ -qubit system. Sa représentation matricielle s'écrit (où nous avons utilisé le produit Kronecker des matrices): $$\mathrm{Toffoli} \otimes I_2 = \begin{bmatrix} I_6 & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{12} & 0 \\ 0 & X \otimes I_2 \end{bmatrix} = \begin{bmatrix} I_{12} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ Calcul de ses rendements déterminants: $$\det(\mathrm{Toffoli} \otimes I_2) = 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\rangle$ avec $|0010\rangle$ , $|0101\rangle$ avec $|0110\rangle$ , 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 seulement$2$ qubits (c'est-à-dire que$S_4$ est généré par les transpositions de$S_4$ ), 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éterminant$1$ .

La dernière chose à noter est que le déterminant commute avec la multiplication matricielle, c'est-à-dire $\det(AB) = \det(A)\det(B)$ , pour deux matrices $A$ 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 $\mathrm{CCCNOT}$ ne peut pas être implémentée en utilisant uniquement des portes Toffoli sur $4$ qubits.

$\mathrm{CCCNOT}$$5$

$$\mathrm{CCCNOT} \otimes I_2 = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{28} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ $$\det(\mathrm{CCCNOT} \otimes I_2) = 1$$ $\mathrm{CCCNOT}$$5$$1$$-1$$5$