Что такое архитектура Pegasus от D-Wave?

Ответы:

5

Pegasus - это первое фундаментальное изменение в архитектуре D-Wave со времен D-Wave One.

D-Wave Two, 2X и 2000Q все использовали архитектуру "Химера", которая состояла из элементарных ячеек K4,4графики. Четыре поколения машин D-Wave просто добавили больше кубитов, добавляя все больше и больше одинаковых элементарных ячеек.

В Пегасе фактическая структура элементарных ячеек в корне изменилась впервые. Вместо графа химер, где каждый кубит может иметь не более 6 кубитов, граф Пегаса позволяет каждому кубиту соединяться с 15 другими кубитами.

Машина уже была сделана с 680 кубитами Пегаса (сравните это с 2048 кубитами Химеры в D-Wave 2000Q).

Работа была представлена ​​Тревором Лантингом из D-Wave, четыре дня назад:

введите описание изображения здесь введите описание изображения здесь

user1271772
источник
5
Вы можете создавать графики Pegasus с помощью версии networkx от D-Wave. В сочетании с их минорным алгоритмом вы можете проверить, будут ли ваши проблемы встраиваться в их новую архитектуру: github.com/dwavesystems/dwave_networkx/commit/…
Марк Фингхут,
1
PDF презентации с дублирующими слайдами.
Выезд
1
Видеозапись выступления на AQC youtube.com/watch?v=05ovPNxmfjE&feature=youtu.be
Давиде Вентурелли
2

Надеюсь, что этот поздний вклад не будет бессмысленным, но, как упоминалось в одном из комментариев выше, с помощью версии NetworkX D-Waves вы можете визуализировать сеть Pegasus. Я приложил несколько изображений архитектур Pegasus 2 (P2) и Pegasus 6 (P6) с использованием D-Wave NetworkX.

P2

P6

Причина, по которой я нахожу Pegasus интересной, заключается в том, что архитектура допускает циклы нечетных чисел и, конечно, очевидное увеличение в максимальной степени. Теоретическая неспособность химеры иметь нечетные циклы ограничивает, но практически она может быть аппроксимирована с использованием незначительных методов встраивания и, возможно, несовершенной химеры, но, конечно, Пегас полностью преодолевает это.

DTOC
источник
Это хорошие иллюстрации! Но что я не могу легко определить по этим изображениям или по представлению DWAVE, связанному в комментариях к другому ответу, таково следующее: есть ли хорошее математическое описание структуры графа архитектуры Pegasus? Из ваших комментариев ясно, что это не двудольный граф (хорошее место для начала), и диаграммы показывают, что что-то вроде структуры ближайшего соседа на квадратной решетке играет некоторую роль. Но возможно ли более или менее точно описать, что такое множество вершин и ребер?
Ниль де Бодрап
@NieldeBeaudrap Вы спрашиваете код, который генерирует список пар вершин?
Андрей О
@AndrewO: Это будет делать; хотя я имел в виду простую математическую спецификацию, если таковая имеется, так же, какV=Zk×Zn, E={{(a,b),(a,b)}:a,aZk,b,bZn,a{a1,a,a+1},b{b1,b,b+1}} определяет график, параметризованный n а также k,
Ниль де Бодрап
@NieldeBeaudrap Я отправил тебе несколько файлов по электронной почте. Кроме того, у него все еще есть двухчастная ячейка K44, если вы посмотрите внимательно. Каждая "L" форма представляет собой одну элементарную ячейку K44. Если у вас установлены компоненты D-Wave, вы можете выполнить поиск pegasus.py, чтобы увидеть, как они генерируют график. У меня есть своя собственная взломанная версия с момента, когда картина впервые вышла в октябре 2017 года.
Andrew O
@AndrewO: Спасибо за файлы. Приятно знать, что «L-клетки» - это K44. Я также вижу повторяющуюся схему K42s - между «столбцами» каждого L и левой половиной «ряда» L непосредственно к востоку-юго-востоку от него; а также между «рядами» каждого L и нижней половиной столбца L непосредственно к северу-северо-западу - в виде треугольной решетчатой ​​структуры, а также с некоторыми цепочками кубитов в длинных рядах и столбцах , Я постараюсь посмотреть, смогу ли я найти pegasus.py где-нибудь, чтобы проанализировать код, или формализовать эти наблюдения.
Ниль де Бодрап
1

Чем архитектура D-Wave Pegasus отличается от архитектуры Chimera?

См. « Пегас: второй граф связности для крупномасштабного аппаратного обеспечения квантового отжига » (22 января 2019 г.). Авторы: Найк Даттани (Гарвард), Сцилард Сзалай (Центр исследования Вигнера) и Ник Канцлер (Дарем). Рисунки были сделаны с помощью их открытого программного обеспечения PegasusDraw .

«128 кубитов первого коммерческого квантового отжига (D-Wave One, выпущенного в 2011 году) были связаны [графиком под названием« Химера »(впервые определенным публично в 2009 году [1]), который довольно легко описать: двумерный массив K4,4 графики, с одной «стороной» каждого K4,4 будучи подключенным к той же соответствующей стороне на K4,4 ячейки непосредственно над и под ним, а другая сторона подключена к той же соответствующей стороне на K4,4клетки справа и слева от него (см. рисунок 1). Кубиты могут соединяться до 6 других кубитов, так как каждый кубит связан с 4 кубитами в пределах егоK4,4 элементарная ячейка, и до 2 кубитов в K4,4клетки выше и ниже или слева и справа от него. Все коммерческие квантовые отжигы, построенные на сегодняшний день, следуют этому графическому соединению, только с большим и большим количествомK4,4 клетки (см. таблицу 1).

Array of K4,4 cellsTotal # of qubitsD-Wave One4×4128D-Wave Two8×8512D-Wave 2X12×121152D-Wave 2000Q16×162048
Table I: Chimera graphs in all commercial quantumannealers to date.

В 2018 году D-Wave объявил о создании (еще не коммерческого) квантового отжига с большей связью, чем предлагает Chimera, и программы (NetworkX), которая позволяет пользователям генерировать определенные графики Пегаса. Однако явного описания связности графов в Pegasus еще не было опубликовано, поэтому нам пришлось применить процесс обратного инжиниринга для его определения, и в следующем разделе описан алгоритм, который мы установили для генерации Pegasus.

[1]Х. Невен, В. С. Денчев, М. Дрю-Брук, Дж. Чжан, В. Г. Макриди и Г. Роуз, демонстрация NIPS 2009: двоичная классификация с использованием аппаратной реализации квантового отжига, Tech. Отчет (2009).

Химера против Пегаса

В этой газете есть несколько десятков иллюстраций, проверенных Келли Бутби из D-Wave, я не хочу приводить цитаты; Я верю, что раскрыл суть этого.

Несколько моментов:

  • Каждый кубит связан с 6 индексами: (x, y, z, i, j, k).

  • Степень вершин (которая равна 15) увеличилась в 2,5 раза по сравнению со степенью химеры (которая равна 6), за исключением клеток на границе.

  • Непланарность Пегаса расширяет число проблем бинарной оптимизации, которые еще не могут быть решены за полиномиальное время на D-волне.

  • Все гаджеты квадратизации для единичных кубических членов, для которых требуется один вспомогательный кубит, могут быть встроены в Pegasus без дополнительных вспомогательных кубитов, потому что Pegasus содержит K4, что означает, что все три логических кубита и вспомогательный кубит могут быть связаны любым способом, без какого-либо второстепенного вложения.

См. Также: « Квадратизация в дискретной оптимизации и квантовой механике » (14 января 2019 г.), автор Nike Dattani. Исходный код GitHub .

обкрадывать
источник