Automatyczna kompilacja obwodów kwantowych

Niedawne pytanie dotyczyło sposobu skompilowania 4-kubitowej bramki CCCZ (kontrolowany-kontrolowany-kontrolowany-Z) w proste bramki 1-kubitowe i 2-kubitowe, a jedyna dotychczasowa odpowiedź wymaga 63 bram !

Pierwszym krokiem było użycie konstrukcji C n U podanej przez Nielsen & Chuang:$^n$

Przy $n=3$ oznacza to 4 bramki CCNOT i 3 proste bramki (1 CNOT i 2 Hadamardy wystarczą do wykonania ostatniego CZ na docelowym kubicie i ostatnim kubicie roboczym).

Twierdzenie 1 tego artykułu mówi, że ogólnie CCNOT wymaga 9 bramek z jednym kubitem i 6 bramek z dwoma kubitami (łącznie 15):

To znaczy:

(4 CCNOT) x (15 bramek na CCNOT) + (1 CNOT) + (2 Hadamards) = 63 bramek ogółem .

W komentarzu zasugerowano, że 63 bramki można następnie skompilować przy użyciu „automatycznej procedury”, na przykład z teorii grup automatycznych .

Jak można wykonać tę „automatyczną kompilację” i jak bardzo zmniejszyłby liczbę bramek 1-kubitowych i 2-kubitowych w tym przypadku?

Niech $g_1 \cdots g_M$ będzie podstawową bramą, z której wolno korzystać. Do celów niniejszego $\operatorname{CNOT}_{12}$ i $\operatorname{CNOT}_{13}$ itd. Są traktowane jako osobne. Zatem $M$ jest wielomianowo zależne od $n$ , liczby kubitów. Dokładna zależność polega szczegóły dotyczące rodzaju bram użyć i jak $k$ -local są. Na przykład, jeśli istnieje $x$ pojedynczych bramek kubitowych i $y$ 2-kubitowych bramek, które nie zależą od kolejności jak $CZ$ to .$M = xn+\binom{n}{2}y$

Obwód jest więc produktem tych generatorów w określonej kolejności. Ale istnieje wiele obwodów, które nic nie robią. Jak . Więc dają relacje w grupie. To jest prezentacja grupowa gdzie istnieje wiele relacji, których nie znamy.$\operatorname{CNOT}_{12} \operatorname{CNOT}_{12} = \mathrm{Id}$ $\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

Problem, który chcemy rozwiązać, zawiera słowo w tej grupie, które jest najkrótszym słowem reprezentującym ten sam element. W przypadku ogólnych prezentacji grupowych jest to beznadziejne. Rodzaj prezentacji grupowej, w której dostępny jest ten problem, nazywa się automatyczny.

Ale możemy rozważyć prostszy problem. Jeśli wyrzucimy część , wówczas słowa z poprzedniej postaci będą postać gdzie każde z jest słowem tylko w pozostałych literach. Jeśli uda nam się je skrócić za pomocą relacji, które nie dotyczą , wówczas cały obwód. Jest to podobne do optymalizacji CNOT samodzielnie w drugiej odpowiedzi.$g_i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$g_i$

Na przykład, jeśli są trzy generatory, a słowo to , ale nie chcemy zajmować się , zamiast tego skrócimy i do i . Następnie składamy je z powrotem jako i jest to skrót od oryginalnego słowa.$aababbacbbaba$$c$$w_1=aababba$$w_2=bbaba$$\hat{w}_1$$\hat{w}_2$$\hat{w}_1 c \hat{w}_2$

Więc WLOG (bez utraty ogólności), załóżmy, że już mamy ten problem gdzie teraz używamy wszystkich określonych bramek. Ponownie prawdopodobnie nie jest to automatyczna grupa. Ale co jeśli wyrzucimy niektóre relacje. Wtedy będziemy mieli inną grupę, która ma mapę ilorazową do tej, której naprawdę chcemy.$\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

Grupa brak relacji jest wolną grupą , ale jeśli umieścisz jako relację, otrzymasz darmowy produkt i istnieje mapa ilorazowa od pierwszej do późniejszej, zmniejszająca liczbę w każdym segmencie modulo .$\langle g_1 g_2 \mid - \rangle$$g_1^2=\mathrm{id}$ $\mathbb{Z}_2 \star \mathbb{Z}$$g_1$$2$

Relacje, które wyrzucamy, będą takie, że ta na górze (źródło mapy ilorazów) będzie z założenia automatyczna. Jeśli użyjemy tylko relacji, które pozostają i skracają słowo, to nadal będzie ono krótszym słowem dla grupy ilorazowej. Po prostu nie będzie optymalny dla grupy ilorazów (cel mapy ilorazów), ale będzie miał długość do długości, od której zaczął.$\leq$

To był ogólny pomysł, jak możemy to zmienić w konkretny algorytm?

Jak wybrać i relacje, które należy wyrzucić, aby uzyskać automatyczną grupę? W tym miejscu pojawia się wiedza na temat bramek elementarnych, których zwykle używamy. Jest wiele zaangażowań, więc zachowaj tylko te. Zwróć szczególną uwagę na fakt, że są to tylko elementarne inwolucje, więc jeśli twój sprzęt ma trudności z wymianą kubitów, które są bardzo oddzielone na twoim chipie, oznacza to, że zapisujesz je tylko w tych, które możesz łatwo zrobić i redukuje to słowo do być jak najkrótszym.$g_i$

Załóżmy na przykład, że masz konfigurację IBM . Następnie są dozwolonymi bramami. Jeśli chcesz wykonać ogólną permutację, rozłóż ją na czynniki . To słowo w grupie , które chcemy skrócić .$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$

Zauważ, że nie muszą to być standardowe inwolucje. Możesz dodać oprócz na przykład. Pomyśl o twierdzeniu Gottesmana-Knilla , ale w abstrakcyjny sposób oznacza to, że łatwiej będzie je uogólnić. Na przykład przy użyciu właściwości, która w krótkich, dokładnych sekwencjach, jeśli masz skończone kompletne systemy przepisywania dla dwóch stron, to dostajesz jeden dla grupy środkowej. Ten komentarz jest niepotrzebny w pozostałej części odpowiedzi, ale pokazuje, jak można zbudować większe, bardziej ogólne przykłady z tych w tej odpowiedzi.$R(\theta) X R(\theta)^{-1}$$X$

Zachowywane są tylko relacje formy . Daje to grupę Coxeter i jest automatyczne. W rzeczywistości nie musimy nawet zaczynać od zera, aby kodować algorytm dla tej automatycznej struktury. Jest już zaimplementowany w Sage (oparty na Pythonie) w ogólnym celu. Wystarczy, że podasz a pozostała implementacja została już wykonana. Oprócz tego możesz przyspieszyć.$(g_i g_j)^{m_{ij}} = 1$$m_{ij}$

$m_{ij}$ jest naprawdę łatwy do obliczenia ze względu na właściwości położenia bram. Jeśli bramki są co najwyżej -lokalne, to obliczenia można wykonać na przestrzennej przestrzeni Hilberta . Jest tak, ponieważ jeśli indeksy się nie pokrywają, to wiesz, że . dotyczy sytuacji, gdy i dojazdy. Musisz także obliczyć mniej niż połowę wpisów. To dlatego, że matryca jest symetryczna, zawiera „S na przekątnej ( ). Również większość wpisów zmienia nazwę tylko zaangażowanych kubitów, więc jeśli znasz kolejność$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)$ , znasz kolejność bez obliczania.$\operatorname{CNOT}_{37} H_3$

Zajęło się to wszystkimi relacjami, które dotyczyły tylko dwóch odrębnych bram (dowód: ćwiczenie). Relacje obejmujące lub więcej osób zostały wyrzucone. Teraz je ponownie wprowadzamy. Załóżmy, że mamy, a następnie można wykonać chciwy algorytm Dehna przy użyciu nowych relacji. Jeśli nastąpiła zmiana, podrzucamy ją z powrotem, aby ponownie przejść przez grupę Coxeter. Powtarza się, dopóki nie zostaną wprowadzone żadne zmiany.$3$

Za każdym razem, gdy słowo się skraca lub pozostaje na tej samej długości, używamy tylko algorytmów, które zachowują się liniowo lub kwadratowo. Jest to dość tania procedura, więc równie dobrze możesz to zrobić i upewnić się, że nie zrobiłeś nic głupiego.

Jeśli chcesz to przetestować sam, podaj liczbę generatorów jako , długość losowego słowa, które wypróbowujesz, a macierz Coxetera jako .$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)

Przykład z N=28i K=20, pierwsze dwa wiersze to wejściowe słowo nieredukowane, następne dwa to słowo zredukowane. Mam nadzieję, że nie popełniłem literówki, wchodząc w matrycę .$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']

Odkładając z powrotem te generatory, takie jak , odkładamy tylko relacje takie jak a dojeżdża do bram, które nie obejmują qubit . Dzięki temu możemy dokonać dekompozycji z poprzedniej, aby mieć tak długo, jak to możliwe. Chcemy unikać sytuacji takich jak . (W Cliff + T często dąży się do zminimalizowania liczby T). W tej części kluczowy jest ukierunkowany wykres acykliczny pokazujący zależność. Jest to problem znalezienia dobrego topologicznego rodzaju DAG. Dokonuje się tego poprzez zmianę pierwszeństwa, gdy można wybrać, którego wierzchołka użyć następnie. (Nie marnowałbym czasu zbyt mocno optymalizując tę ​​część).$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$

Jeśli słowo jest już blisko optymalnej długości, nie ma wiele do zrobienia i ta procedura nie pomoże. Ale ponieważ najbardziej podstawowym przykładem tego, co znajduje, jest to, że jeśli masz wiele jednostek i zapomniałeś, że na końcu jednego, a na początku następnego, pozbędzie się tej pary. Oznacza to, że możesz umieścić w czarnej skrzynce popularne procedury z większą pewnością, że po ich złożeniu wszystkie oczywiste odwołania zostaną załatwione. Robi inne, które nie są tak oczywiste; te używają, gdy .$H_i$$H_i$$m_{ij} \neq 1,2$

Stosując procedurę opisaną w https://arxiv.org/abs/quant-ph/0303063 ¹ , każdą bramę diagonalną - a tym samym w szczególności bramę CCCZ - można rozłożyć pod względem np. CNOT i bramek ukośnych o jednym kubicie, gdzie CNOT można optymalizować samodzielnie, stosując klasyczną procedurę optymalizacji.

Odnośnik zapewnia obwód wykorzystujący 16 CNOT dla dowolnych ukośnych bramek 4-kubitowych (ryc. 4).

Uwaga: Chociaż w zasadzie może istnieć prostszy obwód (wspomniany obwód został zoptymalizowany z myślą o bardziej ograniczonej architekturze obwodu), powinien być bliski optymalnego - obwód musi utworzyć wszystkie stany w postaci dla dowolnego nietrywialnego podzbioru , a jest 15 takich dla 4 kubitów.$\bigoplus_{i\in I}x_i$$I\subset\{1,2,3,4\}$

Należy również pamiętać, że ta konstrukcja w żadnym wypadku nie musi być optymalna.

^{1 Uwaga: Jestem autorem}