Calculs classiques sur des ordinateurs quantiques

Nous allons maintenant nous pencher sur la mise en œuvre d'algorithmes classiques sur des ordinateurs quantiques. Nous verrons que tout calcul réalisable avec un circuit booléen classique peut également être effectué par un circuit quantique avec un coût computationnel asymptotique similaire. De plus, cela peut être fait de manière « propre », comme décrit prochainement, ce qui est une exigence importante pour utiliser ces calculs comme sous-routines dans des calculs quantiques plus larges.

Simulation de circuits booléens avec des circuits quantiques

Les circuits booléens sont composés de portes ET, OU, NON et FANOUT. Pour simuler les circuits booléens avec des circuits quantiques, nous commencerons par montrer comment chacune de ces quatre portes peut être simulée par des portes quantiques. Une fois cela fait, convertir un circuit booléen donné en circuit quantique est une simple question de simulation porte par porte. Nous aurons seulement besoin de portes NON, de portes NON contrôlées et de portes Toffoli pour ce faire, qui sont toutes des opérations déterministes en plus d'être unitaires.

Portes Toffoli

Les portes Toffoli peuvent aussi être décrites comme des portes NON contrôlées-contrôlées, dont l'action sur les états de la base standard est représentée dans la figure suivante.

En gardant à l'esprit que nous utilisons la convention d'ordre de Qiskit, où les qubits sont ordonnés par signification croissante de haut en bas, la représentation matricielle de cette porte est la suivante.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Une autre façon de considérer les portes Toffoli est qu'elles sont essentiellement des portes de requête pour la fonction ET, dans le sens où elles suivent le schéma que nous avons vu dans la leçon précédente pour les implémentations de portes de requête unitaires de fonctions arbitraires à entrées et sorties binaires.

Les portes Toffoli ne sont pas incluses dans l'ensemble de portes par défaut discuté plus tôt dans la leçon, mais il est possible de construire une porte Toffoli à partir de portes $H,$ $T,$ $T^{\dagger}$ et CNOT comme suit.

Simulation de portes booléennes avec des portes Toffoli, NON contrôlées et NON

Une seule porte Toffoli, utilisée conjointement avec quelques portes NON, peut implémenter une porte ET et une porte OU, et les portes FANOUT peuvent facilement être implémentées en utilisant des portes NON contrôlées, comme le suggèrent les diagrammes suivants.

Dans les trois cas, les qubits sur lesquels les portes ET, OU et FANOUT agissent arrivent de la gauche comme entrées, et on a également besoin d'un qubit d'espace de travail initialisé à l'état zéro pour chacun. Ces qubits d'espace de travail apparaissent à l'intérieur des boîtes représentant les implémentations de portes pour suggérer qu'ils sont nouveaux, et donc font partie du coût de ces implémentations.

Pour les portes ET et OU, on a également deux qubits en surplus, en plus du qubit de sortie. Par exemple, à l'intérieur de la boîte dans le diagramme représentant la simulation d'une porte ET, les deux qubits du haut restent dans les états $\vert a\rangle$ et $\vert b\rangle.$ Ces qubits sont illustrés comme restant à l'intérieur des boîtes car ils ne sont plus nécessaires et ne font pas partie de la sortie. Ils peuvent être ignorés pour l'instant, bien qu'on y revienne prochainement.

La porte booléenne restante, la porte NON, est incluse dans notre ensemble de portes quantiques par défaut, donc on n'a pas besoin de simulation pour celle-ci.

Simulation porte par porte de circuits booléens

Supposons maintenant qu'on ait un circuit booléen ordinaire nommé $C,$ composé de portes ET, OU, NON et FANOUT, et ayant $n$ bits d'entrée et $m$ bits de sortie. Soit $t = \operatorname{size}(C)$ le nombre de portes dans $C,$ et donnons le nom $f$ à la fonction que $C$ calcule, qui prend la forme

$$f:\Sigma^n\rightarrow\Sigma^m$$

pour $\Sigma = \{0,1\}.$

Considérons maintenant ce qui se passe lorsqu'on parcourt une à une les portes ET, OU et FANOUT de $C,$ en remplaçant chacune par la simulation correspondante décrite ci-dessus, y compris l'ajout des qubits d'espace de travail requis. Nommons le circuit résultant $R,$ et ordonnons les qubits de $R$ de sorte que les $n$ bits d'entrée de $C$ correspondent aux $n$ qubits du haut de $R$ et les qubits d'espace de travail se trouvent en bas.

Ici, $k$ est le nombre de qubits d'espace de travail requis — un pour chaque porte ET, OU et FANOUT de $C$ — et $g$ est une fonction de la forme $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ qui décrit les états des qubits en surplus créés par les simulations de portes après l'exécution de $R$. Dans la figure, les qubits correspondant à la sortie $f(x)$ sont en haut et les qubits restants en surplus stockant $g(x)$ sont en bas. On peut forcer cela en réarrangeant les qubits à l'aide de portes SWAP, qui peuvent être implémentées avec trois portes NON contrôlées comme ceci :

Comme nous le verrons dans la prochaine section, il n'est pas vraiment essentiel de réarranger les qubits de sortie de cette façon, mais c'est facile à faire si on le choisit.

La fonction $g$ qui décrit les états classiques des qubits en surplus est déterminée par le circuit $C,$ mais on n'a pas vraiment besoin de s'en préoccuper ; on ne se soucie pas spécifiquement de l'état dans lequel se trouvent ces qubits lorsque le calcul se termine. La lettre $g$ vient après $f,$ donc c'est un nom raisonnable pour cette fonction à cet égard, mais il y a une meilleure raison de choisir le nom $g$ — c'est l'abréviation de garbage (déchet).

Nettoyer les déchets

Si notre seul intérêt est d'évaluer la fonction $f$ calculée par un circuit booléen $C$ avec un circuit quantique, on n'a pas besoin d'aller plus loin que la simulation porte par porte venant d'être décrite. Cela signifie qu'en plus de la sortie de la fonction, on aura un tas de déchets en surplus.

Cependant, cela n'est pas suffisant si on veut effectuer des calculs classiques comme sous-routines dans des calculs quantiques plus larges, car ces qubits de déchets vont causer des problèmes. Le phénomène d'interférence est d'une importance cruciale pour les algorithmes quantiques, et les qubits de déchets peuvent ruiner les schémas d'interférence nécessaires au bon fonctionnement des algorithmes quantiques.

Heureusement, il n'est pas difficile de nettoyer les déchets, pour ainsi dire. La clé est d'utiliser le fait que, puisque $R$ est un circuit quantique, on peut l'exécuter à rebours, en remplaçant simplement chaque porte par son inverse et en les appliquant dans l'ordre inverse, obtenant ainsi un circuit quantique pour l'opération $R^{\dagger}.$ Les portes Toffoli, les portes CNOT et les portes NON sont en réalité leurs propres inverses, donc exécuter $R$ à rebours revient vraiment juste à appliquer les portes dans l'ordre inverse — mais plus généralement, tout circuit quantique peut être inversé comme décrit.

Concrètement, ce qu'on peut faire est d'ajouter $m$ qubits supplémentaires (en rappelant que la fonction $f$ a $m$ bits de sortie), d'utiliser des portes CNOT pour copier la sortie de $R$ sur ces qubits, et d'inverser $R$ pour nettoyer les déchets. La figure suivante illustre le circuit résultant et décrit son action sur les états de la base standard.

Si on met une boîte autour de l'ensemble du circuit et qu'on l'appelle $Q,$ ça ressemble à ceci :

Étant donné que $C$ a $t$ portes, le circuit $Q$ aura $O(t)$ portes.

Si on fait abstraction des $k$ qubits d'espace de travail supplémentaires, ce qu'on a est un circuit $Q$ qui fonctionne exactement comme une porte de requête pour la fonction $f.$ Si on veut simplement calculer la fonction $f$ sur une chaîne $x,$ on peut poser $y = 0^m$ et la valeur résultante $f(x)$ apparaîtra sur les $m$ qubits du bas — ou on peut fournir un état différent aux $m$ qubits du bas si on le souhaite (peut-être pour faire usage d'un retour de phase, comme dans l'algorithme de Deutsch ou l'algorithme de Deutsch-Jozsa).

Cela signifie que, pour tout algorithme par requêtes, si on dispose d'un circuit booléen qui calcule la fonction d'entrée, on peut remplacer chaque porte de requête par une implémentation en circuit de celle-ci, et l'algorithme par requêtes fonctionnera correctement.

Notons que les qubits d'espace de travail sont nécessaires pour que ce processus fonctionne, mais ils sont ramenés à leurs états initiaux une fois que le circuit combiné est exécuté. Cela permet que ces qubits soient réutilisés comme qubits d'espace de travail à d'autres fins. Il existe également des stratégies connues pour réduire le nombre de qubits d'espace de travail requis (au prix de rendre les circuits plus grands), mais nous ne discuterons pas de ces stratégies ici.

Implémentation de fonctions inversibles

La construction décrite ci-dessus nous permet de simuler n'importe quel circuit booléen avec un circuit quantique sans déchets. Si $C$ est un circuit booléen implémentant une fonction $f:\Sigma^n \rightarrow \Sigma^m,$ alors on obtient un circuit quantique $Q$ qui opère comme suit sur les états de la base standard.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Le nombre $k$ indique combien de qubits d'espace de travail sont requis au total. C'est suffisant pour les besoins de ce cours, mais il est possible de pousser cette méthodologie un peu plus loin lorsque la fonction $f$ elle-même est inversible.

Pour être précis, supposons que la fonction $f$ prenne la forme $f:\Sigma^n \rightarrow \Sigma^n,$ et supposons également qu'il existe une fonction $f^{-1}$ telle que $f^{-1}(f(x)) = x$ pour tout $x\in\Sigma^n$ (qui est nécessairement unique lorsqu'elle existe). Cela signifie que l'opération qui transforme $\vert x \rangle$ en $\vert f(x) \rangle$ pour tout $x\in\Sigma^n$ est unitaire, donc on pourrait espérer construire un circuit quantique qui implémente l'opération unitaire définie par

$$U \vert x \rangle = \vert f(x) \rangle$$

pour tout $x\in\Sigma^n.$

Pour être clair, le fait que ce soit une opération unitaire repose sur le fait que $f$ est inversible — ce n'est pas unitaire quand $f$ ne l'est pas. En faisant abstraction des qubits d'espace de travail, $U$ est différent de l'opération que le circuit $Q$ implémente car on ne conserve pas une copie de l'entrée et ne lui applique pas un XOR vers une chaîne arbitraire, on remplace $x$ par $f(x).$

La question est : quand $f$ est inversible, peut-on faire cela ?

La réponse est oui, à condition qu'on soit autorisé à utiliser des qubits d'espace de travail et, en plus d'avoir un circuit booléen qui calcule $f,$ on en ait également un qui calcule $f^{-1}.$ Ce n'est donc pas un raccourci pour inverser computationnellement des fonctions quand on ne sait pas déjà comment faire ! Le diagramme suivant illustre comment cela peut être fait en composant deux circuits quantiques, $Q_f$ et $Q_{f^{-1}},$ qui sont obtenus individuellement pour les fonctions $f$ et $f^{-1}$ via la méthode décrite ci-dessus, ainsi que $n$ portes de permutation, en prenant $k$ comme le maximum du nombre de qubits d'espace de travail requis par $Q_f$ et $Q_{f^{-1}}.$