Synthèse adaptée au matériel dans la plate-forme Classiq

Introduction

Dans l'informatique classique, les aspects physiques de la gestion de la mémoire sont essentiels pour la performance des logiciels. La plupart des développeurs d'algorithmes ne s'embarrassent cependant pas de ces considérations et se concentrent sur une programmation simple. Cette simplicité est possible parce que les bibliothèques optimisées et les outils automatisés standard de l'industrie supportent suffisamment le fardeau pour la plupart des cas d'utilisation. Il est donc souhaitable que le développement d'algorithmes quantiques bénéficie de la même chose. Bien que les ordinateurs quantiques n'en soient qu'à leurs débuts, nous pouvons commencer à appliquer un raisonnement analogue. Comment ? En considérant les deux ingrédients suivants : les qubits auxiliaires quantiques (ancilla), qui stockent temporairement les calculs intermédiaires, et la connectivité entre les qubits, une propriété physique de la mémoire. Ce billet de blog explique comment ils sont liés et explore cette relation en utilisant la plateforme Classiq pour automatiser l'optimisation.

Vue d'ensemble 

Lorsque Dmitri Maslov a proposé d'utiliser des portes de Toffoli à phase relative pour construire une nouvelle implémentation de portes quantiques multicontrôlées, il a démontré les avantages de sa méthode en comparant les métriques de niveau logique à d'autres implémentations. L'article précise toutefois que ces mesures ne prennent pas en compte "le modèle de connectivité des qubits". En effet, l'espace physique ne s'étend que sur trois dimensions, et chaque qubit ne peut pas être connecté à tous les autres qubits de manière évolutive dans un espace à dimension finie". Maslov, expert en conception d'algorithmes quantiques, reconnaît certainement les exigences imposées par le matériel. Ici, nous utiliserons la plateforme Classiq pour explorer la remarque de Maslov et présenter un exemple de l'effet de la connectivité des qubits sur les portes multi-contrôlées.

Nous expliquerons brièvement les opérations multicontrôlées et discuterons des implémentations de la bibliothèque Classiq. Ensuite, nous nous pencherons sur la connectivité matérielle et ses contraintes pour la conception de circuits quantiques au niveau des portes. Enfin, nous démontrons les capacités du moteur de synthèse de Classiq à sélectionner différentes implémentations en fonction de la connectivité matérielle. Cet ajustement est un exemple de co-conception de circuits quantiques, où les informations de bas niveau provenant du matériel déterminent la conception du circuit au niveau logique.

Opérations quantiques multicontrôlées

Les opérations quantiques multi-contrôlées servent de base aux algorithmes quantiques canoniques, tels que les opérations de Grover et les opérations arithmétiques. Par souci de simplicité, nous nous concentrerons sur les opérations NOT multicontrôlées (MCX). Toute opération quantique arbitraire multi-contrôlée peut en effet être écrite en utilisant des portes MCX et une opération quantique mono-contrôlée (essayez ceci comme un simple exercice).

En dehors de l'implémentation de Maslov, différentes portes MCX ont été proposées au fil des ans et peuvent être trouvées dans la littérature et les bibliothèques open-source comme Qiskit et TKet. Le point commun entre ces propositions est le compromis entre le nombre de qubits auxiliaires et la profondeur du circuit et le nombre de portes non contrôlées (CX) (de rares exemples nécessitent des portes exponentiellement précises (voir ici), mais nous les éviterons ici pour des raisons de simplicité). 

Que sont les qubits auxiliaires ? Ils servent de mémoire temporaire dans le calcul quantique - ils sont alloués au début et ramenés à leur état initial (non calculé) à la fin. Les qubits auxiliaires peuvent être nécessaires s'ils réduisent d'autres ressources de calcul. Par exemple, la profondeur du circuit et le nombre de portes CX affectent la qualité du programme en raison de la perte de fidélité qui en résulte, en particulier dans les dispositifs quantiques bruyants.

La bibliothèque de Classiq combine différentes implémentations (ce qui mériterait un billet de blog séparé) pour construire une série qui joue sur ce compromis. Le moteur de synthèse sélectionne l'implémentation en fonction des contraintes fournies par l'utilisateur. 

Connectivité matérielle

Lors de la conception d'un programme classique, nous ne tenons généralement pas compte de l'appareil physique sur lequel le logiciel s'exécute. Cette partie est prise en charge en coulisses par des optimisations intermédiaires et de bas niveau automatisées et n'est réglée que par des experts. Un aspect important est la surcharge due à la communication physique entre le processeur (CPU) et les différents dispositifs de mémoire : la mémoire sur puce (cache) est plus petite mais plus proche du CPU, tandis que la mémoire principale, la mémoire vive (RAM), est plus éloignée. Par conséquent, l'utilisation de la mémoire cache est essentielle pour déterminer les performances du programme et a parfois plus de poids que la minimisation du nombre d'opérations de calcul. Les exemples qui abordent ce problème sont les implémentations algorithmiques pour les opérations matricielles, les passes de compilation comme le blocage et le déroulement des boucles, et les considérations sur l'allocation de la mémoire sur la pile ou sur le tas.

Peut-on trouver un analogue quantique ? Alors que les ordinateurs quantiques sont prématurés pour les architectures de mémoire complexes, nous pouvons considérer les qubits auxiliaires comme de la mémoire. Pour expliquer cette analogie plus en détail, nous devons discuter du concept de routage dans le cadre du processus de compilation.

Dans de nombreuses architectures de calcul quantique (comme les qubits supraconducteurs), les qubits ne sont pas directement connectés. Par exemple, le diagramme de connectivité d'un processeur IBM Eagle extrait de la plateforme Classiq est présenté ci-dessous. Ce diagramme est formé par l'empilement vertical de lignes de 14-15 qubits et leur connexion par des couches alternées de 4 qubits.

Supposons maintenant que les portes du circuit logique (par exemple, CX) se trouvent entre deux qubits non voisins, comme les deux marqués en bleu. Pour effectuer l'opération de porte, nous introduisons des portes SWAP le long d'un chemin sélectionné qui relie ces qubits afin d'acheminer l'information vers le qubit cible. 

L'opération de la porte SWAP est coûteuse : chaque porte SWAP représente trois portes CX ! Par conséquent, l'optimisation de l'étape de routage pour un circuit logique donné est extrêmement importante pour les performances. Malheureusement, l'optimisation du routage est un problème NP-hard, et nous ne pouvons donc pas calculer à l'avance le nombre de portes CX dans le circuit compilé. Certains algorithmes de routage heuristiques ont été développés et sont disponibles dans la littérature et les bibliothèques open-source.

Synthèse adaptée au matériel avec Classiq

Nous pouvons maintenant poser la question suivante : en raison du routage, l'utilisation de qubits auxiliaires peut-elle avoir des rendements décroissants ? Plus précisément, étant donné une implémentation d'une porte MCX avec des auxiliaires qui vise à réduire le nombre de portes CX autant que possible, cette implémentation sera-t-elle toujours considérée comme la plus optimale pour le matériel qui n'est pas entièrement connecté, ou le surcoût de routage rendra-t-il l'utilisation des auxiliaires redondante ?

Demandons au moteur de synthèse de Classiq de construire une porte MCX à 30 qubits de contrôle pour répondre à cette question. Nous accordons les portes de base à CX et U et optimisons le nombre de portes CX. Vous pouvez essayer vous-même :

• Tout d'abord, nous synthétisons pour une connectivité "tout-à-tout".
  Comme prévu, le moteur a choisi une implémentation de type Maslov avec le nombre maximal de qubits auxiliaires. Le circuit résultant nécessite 45 qubits : 31 qubits fonctionnels, répartis en 30 qubits de contrôle et un seul qubit cible, et 14 qubits auxiliaires. 
• Ensuite, nous générons la même porte MCX pour un circuit avec un schéma de connectivité 1-D du plus proche voisin de 50 qubits.
  Le circuit de niveau logique qui en résulte n'utilise plus que 42 qubits. En effet, l'utilisation d'un trop grand nombre d'auxiliaires entraîne un surcoût de routage supérieur au gain obtenu par le stockage temporaire des calculs quantiques.

Note 1 : dans le second cas, les 42 qubits représentent le circuit de niveau logique. Le nombre de qubits peut augmenter après l'application de l'algorithme de routage. La distinction essentielle ici est que l'implémentation au niveau logique est modifiée, ce qui donne un meilleur circuit lorsque l'on utilise Classiq.
Note 2 : Ce n'est pas le dernier mot, et nous pourrions trouver de meilleures implémentations à l'avenir. En outre, d'autres considérations, telles que les optimisations au niveau de la grille appliquées au cours du processus, peuvent également affecter le circuit final. Néanmoins, cet exemple met en évidence le comportement de rendement décroissant de l'ajout d'un trop grand nombre d'auxiliaires, qui est pris en compte par le moteur de synthèse automatisé de Classiq et qui est difficile à suivre naïvement. 

En guise de défi, vous pouvez essayer de reproduire ce comportement en utilisant une connectivité matérielle réelle au lieu du plus proche voisin 1-D. Il n'est pas facile de trouver un tel exemple pour les architectures actuellement disponibles. Néanmoins, il sera probablement de plus en plus pertinent au fur et à mesure que ces architectures deviendront plus complexes, en particulier lorsqu'il s'agira d'architectures multicœurs. Pouvez-vous imaginer d'autres blocs quantiques présentant un compromis entre le nombre de qubits et le nombre de CX ?

Conclusion

Lors de la conception d'algorithmes quantiques, il est important d'inclure les propriétés matérielles dans les considérations de performance. L'utilisation du moteur de synthèse de Classiq permet aux développeurs de concentrer leurs efforts sur la structure algorithmique du modèle plutôt que de s'attaquer aux complexités des optimisations au niveau des portes. Le besoin d'outils automatisés tels que Classiq ne fera qu'augmenter à mesure que les circuits quantiques évolueront vers une complexité de niveau commercial et comprendront de nombreux blocs de construction, chacun d'entre eux présentant des compromis dépendant du matériel. Pour un aperçu du moteur de synthèse de Classiq, voir les parties I et II.

Enfin, la connectivité des qubits n'est qu'une des nombreuses contraintes possibles qui peuvent inspirer l'utilisation du codesign pour l'amélioration des performances. Par exemple, on peut ajuster les couches CX dans un circuit pour mieux atténuer les erreurs (voir ici). D'autres cas d'utilisation pourraient prendre en compte les limites du contrôle classique des qubits.