Compilation automatique de circuits quantiques

Une question récente a demandé ici comment compiler la porte CCCZ à 4 qubits (contrôlé-contrôlé-contrôlé-Z) en portes simples à 1 qubit et 2 qubits, et la seule réponse donnée jusqu'à présent nécessite 63 portes !

La première étape a été d'utiliser la construction C n U donnée par Nielsen & Chuang:$^n$

Avec $n=3$ cela signifie 4 portes CCNOT et 3 portes simples (1 CNOT et 2 Hadamards suffisent pour faire le CZ final sur le qubit cible et le dernier qubit de travail).

Le théorème 1 de cet article dit qu'en général le CCNOT nécessite 9 portes à un qubit et 6 portes à deux qubits (15 au total):

Ça signifie:

(4 CCNOT) x (15 portes par CCNOT) + (1 CNOT) + (2 Hadamards) = 63 portes au total .

Dans un commentaire , il a été suggéré que les 63 portes puissent ensuite être compilées en utilisant une "procédure automatique", par exemple à partir de la théorie des groupes automatiques .

Comment cette "compilation automatique" peut-elle se faire, et dans quelle mesure cela réduirait-il le nombre de portes à 1 qubit et 2 qubit dans ce cas?

Soit $g_1 \cdots g_M$ les portes de base que vous êtes autorisé à utiliser. Aux fins du présent $\operatorname{CNOT}_{12}$ et $\operatorname{CNOT}_{13}$ etc., sont traités séparément. Donc $M$ est polynomialement dépendant de $n$ , le nombre de qubits. La dépendance précise implique des détails sur les types de portes que vous utilisez et la façon dont elles sont $k$ locales. Par exemple, s'il y a $x$ portes à qubit unique et $y$ portes à 2 qubits qui ne dépendent pas d'un ordre comme $CZ$ alors .$M = xn+\binom{n}{2}y$

Un circuit est alors un produit de ces générateurs dans un certain ordre. Mais il existe plusieurs circuits qui ne font rien. Comme . Donc ça donne des relations sur le groupe. C'est-à-dire qu'il s'agit d'une présentation de groupe où il existe de nombreuses relations que nous ne connaissons pas.$\operatorname{CNOT}_{12} \operatorname{CNOT}_{12} = \mathrm{Id}$ $\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

Le problème que nous voulons résoudre se voit attribuer un mot dans ce groupe, quel est le mot le plus court qui représente le même élément. Pour les présentations générales de groupe, c'est sans espoir. Le type de présentation de groupe où ce problème est accessible est appelé automatique.

Mais nous pouvons considérer un problème plus simple. Si nous jetons certains des , alors les mots d'avant deviennent de la forme où chacun des sont des mots uniquement dans les lettres restantes. Si nous avons réussi à les raccourcir en utilisant les relations qui n'impliquent pas le , alors nous aurons raccourci tout le circuit. Cela s'apparente à l'optimisation des CNOT par eux-mêmes dans l'autre réponse.$g_i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$g_i$

Par exemple, s'il y a trois générateurs et que le mot est , mais que nous ne voulons pas traiter , nous raccourcirons plutôt et en et . Nous les avons ensuite remis ensemble sous la et c'est un raccourcissement du mot d'origine.$aababbacbbaba$$c$$w_1=aababba$$w_2=bbaba$$\hat{w}_1$$\hat{w}_2$$\hat{w}_1 c \hat{w}_2$

Donc WLOG (sans perte de généralité), supposons que nous sommes déjà dans ce problème où nous utilisons maintenant toutes les portes spécifiées. Encore une fois, ce n'est probablement pas un groupe automatique. Mais que se passe-t-il si nous jetons certaines des relations. Ensuite, nous aurons un autre groupe qui a une carte de quotient jusqu'à celle que nous voulons vraiment.$\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

Le groupe no relations est un groupe libre , mais si vous mettez comme relation, vous obtenez le produit gratuit et il existe une carte de quotient de la première à la dernière réduisant le nombre de dans chaque segment modulo .$\langle g_1 g_2 \mid - \rangle$$g_1^2=\mathrm{id}$ $\mathbb{Z}_2 \star \mathbb{Z}$$g_1$$2$

Les relations que nous jetons seront telles que celle à l'étage (la source de la carte des quotients) sera automatique par conception. Si nous utilisons uniquement les relations qui restent et raccourcissons le mot, alors ce sera toujours un mot plus court pour le groupe de quotients. Il ne sera tout simplement pas optimal pour le groupe de quotients (la cible de la carte de quotients), mais il aura la longueur à la longueur avec laquelle il a commencé.$\leq$

C'était l'idée générale, comment pouvons-nous transformer cela en un algorithme spécifique?

Comment choisissons-nous le et les relations à jeter afin d'obtenir un groupe automatique? C'est là que la connaissance des types de portes élémentaires que nous utilisons généralement entre en jeu. Il y a beaucoup d'involutions, alors ne gardez que celles-ci. Gardez une attention particulière au fait que ce ne sont que les involutions élémentaires, donc si votre matériel a du mal à échanger des qubits qui sont largement séparés sur votre puce, cela les écrit uniquement dans ceux que vous pouvez faire facilement et réduit ce mot à être aussi court que possible.$g_i$

Par exemple, supposons que vous ayez la configuration IBM . Alors sont les portes autorisées. Si vous souhaitez faire une permutation générale, décomposez-la en facteurs. C'est un mot du groupe que nous souhaitons raccourcir .$s_{01},s_{02},s_{12},s_{23},s_{24},s_{34}$$s_{i,i+1}$$\langle s_{01},s_{02},s_{12},s_{23},s_{24},s_{34} \mid R_1 \cdots \rangle$

Notez que celles-ci ne doivent pas nécessairement être les involutions standard. Vous pouvez ajouter en plus de par exemple. Pensez au théorème de Gottesman-Knill , mais d'une manière abstraite, cela signifie qu'il sera plus facile de généraliser. Telles que l'utilisation de la propriété que sous de courtes séquences exactes, si vous avez des systèmes de réécriture complets finis pour les deux côtés, vous obtenez un pour le groupe du milieu. Ce commentaire n'est pas nécessaire pour le reste de la réponse, mais montre comment vous pouvez construire de plus grands exemples plus généraux à partir de ceux de cette réponse.$R(\theta) X R(\theta)^{-1}$$X$

Les relations conservées ne sont que celles de la forme . Cela donne un groupe Coxeter et c'est automatique. En fait, nous n'avons même pas besoin de recommencer à zéro pour coder l'algorithme de cette structure automatique. Il est déjà implémenté dans Sage (basé sur Python) dans un but général. Tout ce que vous avez à faire est de spécifier le et le reste de l'implémentation est déjà fait. Vous pourriez faire quelques accélérations en plus de cela.$(g_i g_j)^{m_{ij}} = 1$m i j$m_{ij}$

$m_{ij}$ est vraiment facile à calculer en raison des propriétés de localisation des portes. Si les portes sont au plus locales, alors le calcul de peut être fait sur un espace de Hilbert dimensionnel . En effet, si les indices ne se chevauchent pas, vous savez que . est pour quand et navette. Vous ne devez également calculer que moins de la moitié des entrées. En effet, la matrice est symétrique, a sur la diagonale ( ). De plus, la plupart des entrées ne font que renommer les qubits impliqués, donc si vous connaissez l'ordre des$k$$m_{ij}$$2^{2k-1}$$m_{ij}=2$$m_{ij}=2$$g_i$$g_j$$m_{ij}$$1$$(g_i g_i)^1 = 1$$(\operatorname{CNOT}_{12} H_1)$ , vous connaissez l'ordre de sans le calcul.$\operatorname{CNOT}_{37} H_3$

Cela a pris en charge toutes les relations qui n'impliquaient au plus que deux portes distinctes (preuve: exercice). Les relations qui impliquaient ou plus ont toutes été rejetées. Nous les remettons maintenant. Disons que nous avons cela, alors on peut exécuter l'algorithme gourmand de Dehn en utilisant de nouvelles relations. S'il y avait un changement, nous le repoussons pour parcourir à nouveau le groupe Coxeter. Cela se répète jusqu'à ce qu'il n'y ait aucun changement.$3$

Chaque fois que le mot raccourcit ou reste de la même longueur et nous utilisons uniquement des algorithmes qui ont un comportement linéaire ou quadratique. Il s'agit d'une procédure plutôt bon marché, alors faites-le et assurez-vous de ne rien faire de stupide.

Si vous voulez le tester vous-même, donnez le nombre de générateurs comme , la longueur du mot aléatoire que vous essayez et la matrice de Coxeter comme .$N$$K$$m$

edge_list=[]
for i1 in range(N):
    for j1 in range(i):
        edge_list.append((j1+1,i1+1,m[i1,j1]))
G3 = Graph(edge_list)
W3 = CoxeterGroup(G3)
s3 = W3.simple_reflections()
word=[choice(list([1,..,N])) for k in range(K)]
print(word)
wTesting=s3[word[0]]
for o in word[1:]:
    wTesting=wTesting*s3[o]
word=wTesting.coset_representative([]).reduced_word()
print(word)

Un exemple avec N=28et K=20, les deux premières lignes sont le mot d'entrée non réduit, les deux suivantes sont le mot réduit. J'espère que je n'ai pas fait de faute de frappe en entrant dans la matrice .$m$

[26, 10, 13, 16, 15, 16, 20, 22, 21, 25, 11, 22, 25, 13, 8, 20, 19, 19, 14, 28]

['CNOT_23', 'Y_1', 'Y_4', 'Z_2', 'Z_1', 'Z_2', 'H_1', 'H_3', 'H_2', 'CNOT_12', 'Y_2', 'H_3', 'CNOT_12', 'Y_4', 'X_4', 'H_1', 'Z_5', 'Z_5', 'Y_5', 'CNOT_45']

[14, 8, 28, 26, 21, 10, 15, 20, 25, 11, 25, 20]

['Y_5', 'X_4', 'CNOT_45', 'CNOT_23', 'H_2', 'Y_1', 'Z_1', 'H_1', 'CNOT_12', 'Y_2', 'CNOT_12', 'H_1']

En remettant ces générateurs comme nous seulement les relations comme et que commute avec des portes qui n'impliquent pas qubit . Cela nous permet de faire la décomposition d'avant avoir le plus longtemps possible. Nous voulons éviter des situations comme . (Dans Cliff + T, on cherche souvent à minimiser le compte T). Pour cette partie, le graphique acyclique orienté montrant la dépendance est crucial. C'est un problème de trouver une bonne sorte topologique du DAG. Cela se fait en modifiant la priorité lorsque l'on a le choix du sommet à utiliser ensuite. (Je ne perdrais pas de temps à optimiser trop durement cette partie.)$T_i$$T_i^n = 1$$T_i$$i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$X_1 T_2 X_1 T_2 X_1 T_2 X_1$

Si le mot est déjà proche de la longueur optimale, il n'y a pas grand-chose à faire et cette procédure n'aidera pas. Mais comme l'exemple le plus élémentaire de ce qu'il trouve est que si vous avez plusieurs unités et que vous avez oublié qu'il y avait un à la fin de l'un et un au début du suivant, il se débarrassera de cette paire. Cela signifie que vous pouvez mettre en boîte noire les routines courantes avec une plus grande confiance que lorsque vous les assemblerez, ces annulations évidentes seront toutes prises en charge. Il en fait d'autres qui ne sont pas aussi évidents; ceux-ci utilisent lorsque .$H_i$$H_i$$m_{ij} \neq 1,2$

En utilisant la procédure décrite dans https://arxiv.org/abs/quant-ph/0303063 ¹ , toute porte diagonale - toute donc en particulier la porte CCCZ - peut être décomposée en termes par exemple de CNOT et de portes diagonales à un qubit, où les CNOT peuvent être optimisés par eux-mêmes en suivant une procédure d'optimisation classique.

La référence fournit un circuit utilisant 16 CNOT pour des portes arbitraires diagonales à 4 qubits (Fig. 4).

Remarque: Bien qu'il puisse en principe y avoir un circuit plus simple (ledit circuit a été optimisé avec une architecture de circuit plus contrainte à l'esprit), il devrait être proche de l'optimal - le circuit doit créer tous les états de la forme pour tout sous-ensemble non trivial , et il y en a 15 pour 4 qubits.$\bigoplus_{i\in I}x_i$$I\subset\{1,2,3,4\}$

Notez également que cette construction ne doit en aucun cas être optimale.

^{1 Remarque: je suis un auteur}