Jaka jest architektura „Pegasus” D-Wave?

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

architecture physical-realization d-wave chimera pegasus użytkownik1271772
źródło

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