Jaka jest architektura „Pegasus” D-Wave?

Czym różni się architektura Pegaza od D-Wave od architektury Chimera?

Odpowiedzi:

Pegasus to pierwsza fundamentalna zmiana w architekturze D-Wave od czasu D-Wave One.

Wszystkie D-Wave Two, 2X i 2000Q wykorzystywały architekturę „Chimera”, która składała się z komórek elementarnych $K_{4,4}$ wykresy. Cztery generacje maszyn D-Wave właśnie dodały więcej kubitów, dodając coraz więcej komórek jednostkowych, które były takie same.

W Pegasusie faktyczna struktura komórek elementarnych po raz pierwszy uległa zasadniczej zmianie. Zamiast wykresu Chimera, gdzie każdy kubit może mieć maksymalnie 6 kubitów, wykres Pegaza pozwala każdemu kubitowi połączyć się z 15 innymi kubitami.

Maszyna została już wykonana z 680 kubitami Pegasus (porównaj to z kubitami Chimera 2048 w D-Wave 2000Q).

Praca została zaprezentowana przez Trevora Lantinga z D-Wave cztery dni temu:

— użytkownik1271772
źródło

Możesz teraz generować wykresy Pegaza za pomocą wersji Networkx D-Wave. W połączeniu z ich minorminer algorytm można sprawdzić, czy problemy będą osadzać się na ich nowej architektury: github.com/dwavesystems/dwave_networkx/commit/...

— Mark Fingerhuth

PDF prezentacji ze zduplikowanymi slajdami.

— Indolering,

Film z rozmowy na AQC youtube.com/watch?v=05ovPNxmfjE&feature=youtu.be

— Davide Venturelli

Mam nadzieję, że ten spóźniony wkład nie będzie bez znaczenia, ale jak wspomniano w jednym z powyższych komentarzy, używając wersji NetworkX w wersji D-Waves, można zwizualizować sieć Pegasus. Dołączyłem tutaj kilka zdjęć architektury Pegasus 2 (P2) i Pegasus 6 (P6) przy użyciu D-Wave NetworkX.

Powodem, dla którego uważam Pegaza za interesujący, jest to, że architektura pozwala na cykle nieparzyste i oczywiście oczywistą skalę w maksymalnym stopniu. Teoretyczna niezdolność Chimery do posiadania nieparzystych cykli jest ograniczona, ale praktycznie można ją oszacować za pomocą niewielkich technik osadzania i być może niedoskonałej chimery, ale oczywiście Pegasus całkowicie to pokonuje.

— Dtoc
źródło

To są ładne ilustracje! Ale to, czego nie mogę łatwo ustalić na podstawie tych obrazów lub prezentacji DWAVE połączonej w komentarzach z inną odpowiedzią, to: --- czy istnieje ładny matematyczny opis struktury graficznej architektury Pegaza? Z twoich komentarzy jasno wynika, że nie jest to dwustronny wykres (dobre miejsce na początek), a diagramy sugerują, że coś w rodzaju struktury najbliższego sąsiada na kwadratowej sieci odgrywa pewną rolę. Czy można jednak mniej więcej precyzyjnie opisać, czym są zestawy wierzchołków i krawędzi?

— Niel de Beaudrap

@NieldeBeaudrap Czy pytasz o kod, który generuje listę par wierzchołków?

— Andrew O

@AndrewO: To by wystarczyło; chociaż miałem na myśli prostą specyfikację matematyczną, jeśli jest dostępna, podobnie jak

V = Z_{k} \times Z_{n}

$V = \mathbb Z_k \times \mathbb Z_n$ ,

E = {{(a, b), (a^{'}, b^{'})} : a, a^{'} \in Z_{k}, b, b^{'} \in Z_{n}, a^{'} \in {a - 1, a, a + 1}, b^{'} \in {b - 1, b, b + 1}}

$E = \{ \, \{(a, \! b), (a'\!, \! b') \} \, : \, a, a' \in \mathbb Z_k, \; b, b'\in \mathbb Z_n, \; a' \in \{a{-}1,a,a{+}1 \},\; b' \in \{b{-} 1,b,b{+}1\} \, \}$ określa wykres sparametryzowany przez

n

$n$ i

k

$k$ .

— Niel de Beaudrap,

@NieldeBeaudrap Wysłałem Ci kilka plików. Ponadto, jeśli przyjrzysz się uważnie, nadal ma dwustronną komórkę K44. Każdy kształt „L” jest jedną komórką jednostkową K44. Jeśli masz zainstalowane oprogramowanie D-Wave, możesz wyszukać pegasus.py, aby zobaczyć, jak generują wykres. Mam swoją własną zhackowaną wersję z pierwszego zdjęcia w październiku 2017 r.

— Andrew O

@AndrewO: Dzięki za pliki. Miło wiedzieć, że „komórki L” to K44. Widzę również powtarzający się wzór K42s --- między „kolumnami” każdego L i lewą połową „rzędu” L bezpośrednio na wschód-południowy-wschód od niego; a także między „rzędami” każdego L i dolną połową kolumny L bezpośrednio na północ-północny zachód - ułożone w trójkątną strukturę kratową, a także niektóre łańcuchy kubitów w długich rzędach i kolumnach . Spróbuję sprawdzić, czy uda mi się znaleźć pegasus.py gdzieś, aby przeanalizować kod, lub sformalizować te obserwacje.

— Niel de Beaudrap,

Czym różni się architektura Pegaza od D-Wave od architektury Chimera?

Zobacz: „ Pegasus: Drugi wykres łączności dla wielkoskalowego sprzętu do wyżarzania kwantowego ” (22 stycznia 2019 r.), Autor: Nike Dattani (Harvard), Szilard Szalay (Wigner Research Center) i Nick Chancellor (Durham). Dane zostały wykonane przy użyciu oprogramowania PegasusDraw typu open source .

„128 kubitów pierwszego komercyjnego annealera kwantowego (D-Wave One, wydanego w 2011 r.) Połączono [za pomocą wykresu o nazwie Chimera (po raz pierwszy zdefiniowanego publicznie w 2009 r. [1]), który dość łatwo jest opisać: tablica 2D $K_{4,4}$ wykresy, z których każda ma jedną „stronę” $K_{4,4}$ połączony z tą samą odpowiednią stroną na $K_{4,4}$ komórki bezpośrednio nad i pod nim, a druga strona jest połączona z tą samą odpowiednią stroną na $K_{4,4}$ komórki po prawej i lewej stronie (patrz ryc. 1). Kubity mogą łączyć się z maksymalnie 6 innymi kubitami, ponieważ każdy kubit łączy się z 4 kubitami w ramach swojego kubita $K_{4,4}$ komórka elementarna i do 2 kubitów w $K_{4,4}$ komórki powyżej i poniżej lub po lewej i prawej stronie. Wszystkie komercyjne annealery kwantowe zbudowane do tej pory stosują ten wykres połączeń, z tylko coraz większą liczbą $K_{4,4}$ komórki (patrz Tabela 1).
$\begin{array}{lc} Tablica {K.}_{4, 4} komórki & Łączna liczba kubitów \\ D-Wave One & 4 \times 4 & 128 \\ D-Wave Two & 8 \times 8 & 512 \\ D-Wave 2X & 12 \times 12 & 1152 \\ D-Wave 2000Q & 16 \times 16 & 2048 \end{array}$ $\begin{array}{lc} &\text{Array of }K_{4,4}\text{ cells} & \text{Total # of qubits} \\ \text{D-Wave One} & 4 \times 4 & 128 \\ \text{D-Wave Two} & 8 \times 8 & 512 \\ \text{D-Wave 2X} & 12 \times 12 & 1152 \\ \text{D-Wave 2000Q} & 16 \times 16 & 2048 \end{array}$ $Tabela I: Dotychczasowe wykresy chimery we wszystkich komercyjnych sprzedawcach kwantowych.$ $\text{Table I: Chimera graphs in all commercial quantum annealers to date.}$

W 2018 roku D-Wave ogłosił budowę (jeszcze nie komercyjnej) kwantowej annealer o większej łączności niż oferuje Chimera oraz program (NetworkX), który pozwala użytkownikom generować pewne wykresy Pegasus. Jednak nie opublikowano jeszcze wyraźnego opisu połączeń grafowych w Pegasusie, więc musieliśmy zastosować proces inżynierii odwrotnej, aby go określić, a następna sekcja opisuje algorytm, który ustaliliśmy dla generowania Pegasusa.

[1]H. Neven, VS Denchev, M. Drew-Brook, J. Zhang, WG Macready i G. Rose, NIPS 2009 Demonstracja: Klasyfikacja binarna z wykorzystaniem sprzętowej implementacji kwantowego wyżarzania, Tech. Rep. (2009).

W tym artykule jest kilkadziesiąt ilustracji, zweryfikowanych przez Kelly Boothby z D-Wave, nie chcę przeceniać; Myślę, że opisałem sedno tego.

Kilka punktów:

Każdy kubit jest powiązany z 6 indeksami: (x, y, z, i, j, k).
Stopień wierzchołków (który wynosi 15) wzrósł 2,5-krotnie w porównaniu do stopnia Chimery (który wynosi 6), z wyjątkiem komórek na granicy.
Nieplanarność Pegaza zwiększa liczbę problemów optymalizacji binarnej, których nie można jeszcze rozwiązać w czasie wielomianowym na fali D-wave.
Wszystkie gadżety kwadratowe dla pojedynczych wyrażeń sześciennych, które wymagają jednego pomocniczego kubita, mogą być osadzone w Pegasusie bez dalszych pomocniczych kubitów, ponieważ Pegasus zawiera $K_4$ , co oznacza, że wszystkie trzy logiczne kubity i pomocniczy kubit można połączyć w dowolny sposób, bez jakiegokolwiek drobnego osadzania.

Zobacz także: „ Kwadratizacja w dyskretnej optymalizacji i mechanice kwantowej ”, (14 stycznia 2019 r.), Autor: Nike Dattani. Kod źródłowy GitHub .

— Obrabować
źródło