Automatyczna kompilacja obwodów kwantowych

12

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):

wprowadź opis zdjęcia tutaj


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?

użytkownik1271772
źródło
1
Jestem w trakcie kilku rzeczy, ale zauważyłem twoje pytanie. Globalne bramki Mølmer – Sørensen są 2 bramkami kubitowymi , a artykuł Zastosowanie globalnych interakcji w wydajnych konstrukcjach obwodów kwantowych opisuje: „Zoptymalizowane wdrożenie bramki CCCZ za pomocą trzech bram GMS”, patrz rysunek 9. Jeśli tak, to proszę napisać odpowiedź pomocny.
Rob
Reprezentacja na obrazie wymaga tylko 4 CCNOT, a zatem 63 bramek zamiast 93.
Dyon J Don Kiwi van Vreumingen
@DonKiwi, odnotowano! 4 CCNOT zamiast 6. Aktualizuję go teraz.
user1271772,
1
@Rob: Wygląda na to, że sugerujesz sprzężenie X w CCCX za pomocą dwóch Hadamardów. Następnie CCCX można rozłożyć tak, jak w powyższym obwodzie Nielsen & Chaung. Czy to jest poprawne? W mojej drugiej odpowiedzi na pytanie DonKiwi zrobiłem coś takiego. Wygląda na to, że twój komentarz pojawił się w momencie, gdy wpisywałem tę odpowiedź, ponieważ dzieli je 5 minut (i napisanie go zajęło mi więcej niż 5 minut). To pytanie dotyczące „automatycznej kompilacji” wciąż jednak pozostaje aktualne, ponieważ byłoby fajnie móc zbudować obwód w „oczywisty sposób”, a następnie automatycznie skompilować w coś bardziej wydajnego.
user1271772,
1
@ user1271772 - Każdy (qu) bit pomaga.
Rob

Odpowiedzi:

6

Niech g1gM będzie podstawową bramą, z której wolno korzystać. Do celów niniejszego CNOT12 i CNOT13 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+(n2)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.CNOT12CNOT12=Id g1gMR1

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.giw1gi1w2gi2wkwigi

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.aababbacbbabacw1=aababbaw2=bbabaw^1w^2w^1cw^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.g1gMR1

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 .g1g2g12=id Z2Zg12

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ął.

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.gi

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ć .s01,s02,s12,s23,s24,s34si,i+1s01,s02,s12,s23,s24,s34R1

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(θ)XR(θ)1X

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ć.(gigj)mij=1mij

mij 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śćkmij22k1mij=2mij=2gigjmij1(gigi)1=1(CNOT12H1) , znasz kolejność bez obliczania.CNOT37H3

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 .NKm

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ęść).TiTin=1Tiiw1gi1w2gi2wkwiX1T2X1T2X1T2X1

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 .HiHimij1,2

AHusain
źródło
+1 !!! Dużo szczegółów! Czytam to :)
user1271772
1
@AHussain, czy można przejść przez przykład, w którym stosuje się to do „naiwnej” konstrukcji CCCZ w moim pytaniu, i otrzymać mniejszą liczbę bram? Oryginalne pytanie o CCCZ ma teraz 6 odpowiedzi, a wiele z nich ma znacznie mniejszą liczbę bramek. Zastanawiam się, co przyniesie twoje podejście do liczenia bram.
user1271772,
4

Stosując procedurę opisaną w https://arxiv.org/abs/quant-ph/0303063 1 , 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.iIxiI{1,2,3,4}

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


1 Uwaga: Jestem autorem

Norbert Schuch
źródło
Ciekawy. Nadal muszę przeczytać artykuł, aby zobaczyć, jaka jest procedura. Czekam też, aż @AHussain powie nam, jak to zrobić, używając teorii automatycznych grup.
user1271772,