Знаете ли вы, что знаменитый квантовый отжиг D-Wave не может изначально запускать даже базовые логические элементы? Квантовая технология — это следующее большое достижение в мире компьютеров. Они настолько продвинуты, что могут решать математические уравнения намного быстрее, чем даже наши лучшие суперкомпьютеры. Но без поддержки они не могут запускать даже простые логические элементы, такие как вентиль И. Но, применив немного магии кодирования, мы можем это сделать.
В классических вычислениях есть несколько логических вентилей, таких как вентили AND, XOR, OR и NAND. Существуют цифровые схемы, такие как полные и половинные сумматоры. В этой статье мы покажем, как закодировать логический элемент И, схему полусумматора и схему полного сумматора в квантовом отжиге D-Wave.
И Ворота
Начнем с самого простого: вентиля И. Логический элемент И возвращает истину, если оба входа одинаковы, и ложь, если они не совпадают. В следующей таблице истинности переменные «a» и «b» представляют наши два входа, а переменная «p» представляет выходные данные. У нас будет еще одна переменная, называемая «v1», дополнительная переменная, необходимая для вычислений.
В статье D-Wave «Повышение производительности целочисленного факторинга с помощью смещений квантового отжига» автор описывает базовую схему значений вентиля И в квантовом компьютере. Мы будем использовать диаграммы из этой статьи в качестве эталона для нашего кода.
На изображении выше (рис. 4) показана таблица истинности вентиля И, а также диаграмма, показывающая значения кубитов (кружки) и связи между ними (линии) на основе показанного цветового кода. Чтобы создать BQM, мы создаем словарь, заполненный значениями кубитов, и еще один словарь со значениями соединений. Мы называем эти термины линейными и квадратичными соответственно.
Мы будем использовать бинарную квадратичную модель (BQM) для представления нашего вентиля И, структуры данных, созданной специально для квантового компьютера. Мы будем добавлять значения для наших кубитов, а также значения связей между ними. Эти значения можно сформулировать двумя разными способами: QUBO или Ising. В упомянутом выше документе «Повышение» используется модель Изинга, поэтому мы будем использовать модель Изинга в BQM.
Примечание. Модель Изинга представляет двоичные числа, такие как 0 и 1, как -1 и 1 соответственно.
Сначала мы импортируем библиотеку dimod. Эта библиотека позволит нам кодировать на отжиге D-Wave. Убедитесь, что у вас установлен D-Wave Ocean SDK, иначе это не сработает. Обратитесь к связанным видеороликам для получения руководства по установке для вашей ОС: Mac OS, Windows или Linux.
import dimod
Затем мы можем создать функцию для представления вентиля И. Нашими параметрами будут два входа (a, b), выход (p) и наша дополнительная переменная v1.
def and_gate(a, b, p, v1):
linear = {a: -0.5, b: -0.5, p: 1.0, v1: 0}
quadratic = {(a, b): 0.5, (a, v1): 1, (b, p): -1, (p, v1): 1}
return dimod.BinaryQuadraticModel(linear, quadratic, dimod.SPIN)
Используя цветовой код (рис. 3) и диаграмму (рис. 4), мы можем присвоить значения наших кубитов в «линейном» словаре, а значения связей кубитов в «квадратичном» словаре. Затем мы возвращаем BQM, используя эти линейные и квадратичные члены. Параметр dimod.SPIN указывает, что наш BQM будет использовать модель Изинга вместо модели QUBO. Мы используем Ising здесь, потому что все значения в D-Wave представлены в формате Ising.
Наконец, мы можем добавить код драйвера для проверки нашей функции.
and_bqm = and_gate('a', 'b', 'p', 'v1')
sampler = dimod.ExactSolver()
print(sampler.sample(and_bqm))
Здесь мы вызываем нашу функцию, а затем запускаем ее через ExactSolver, квантовый отжиг. ExactSolver распечатает все комбинации просмотренных входных данных (a, b) и выходных данных, отсортированные в порядке возрастания энергии.
a b p v1 energy num_oc. 1 +1 -1 -1 -1 -2.5 1 5 +1 +1 +1 -1 -2.5 1 12 -1 +1 -1 +1 -2.5 1 14 +1 -1 -1 +1 -2.5 1 15 -1 -1 -1 +1 -2.5 1 2 +1 +1 -1 -1 -0.5 1 4 -1 +1 +1 -1 -0.5 1 6 +1 -1 +1 -1 -0.5 1 11 -1 +1 +1 +1 -0.5 1 13 +1 +1 -1 +1 -0.5 1 0 -1 -1 -1 -1 1.5 1 3 -1 +1 -1 -1 1.5 1 10 +1 +1 +1 +1 1.5 1 7 -1 -1 +1 -1 3.5 1 8 -1 -1 +1 +1 3.5 1 9 +1 -1 +1 +1 3.5 1 ['SPIN', 16 rows, 16 samples, 4 variables]
Как только мы запустим код, ваш вывод должен выглядеть так, как показано на изображении выше. Первый столбец представляет собой номер теста. Второй и третий столбцы (a, b) — это первый и второй входы соответственно. Столбец «p» — это выходные данные, а «v1» — дополнительная переменная.
Когда система D-Wave запущена, она ищет ответы, представленные здесь в виде BQM, с наименьшим значением энергии. Здесь самое низкое значение энергии, которое находится в столбце под названием «энергия», равно -2,5. Все BQM со значением -2,5 показывают правильные входы в паре со своими выходами. Столбец «num_oc» представляет количество раз, когда ExactSolver проверял комбинацию.
В результатах мы видим, что значения Изинга отображаются в столбцах a, b и p по сравнению со столбцами из предыдущей таблицы истинности.
На этом изображении мы видим, как наши значения Изинга правильно соотносятся с соответствующими двоичными значениями в таблице истинности. Однако прогоны 1 и 14 имеют одинаковые значения a, b и p, и оба имеют наименьшую энергию. Это связано с наличием дополнительной переменной v1, и это появление будет отображаться в других воротах, когда мы также включим дополнительные переменные, такие как v1. Это не влияет на точность нашей модели; это всего лишь побочный продукт наличия переменной v1.
Полу- и полные сумматоры
Мы можем использовать тот же метод, что и для логического элемента И, для кодирования двух других полезных схем: полусумматоров и полных сумматоров. Полусумматор принимает два двоичных числа и возвращает сумму и перенос. Полный сумматор принимает три двоичных числа, возвращает сумму и выполняет перенос на основе этих трех чисел. Вот таблицы:
В этих таблицах показано основное поведение этих цепей, реагирующих на различные входные данные. Если мы вернемся к статье D-Wave, которую мы рассмотрели для вентиля И, показана модель Изинга для полусумматора.
Используя тот же цветовой код, что и вентиль И (рис. 3), мы можем легко написать функцию для полусумматора. На этот раз нам нужны две дополнительные переменные. Мы также меняем наши переменные на t1 и t2 для входов, для паритета с бумагой.
def half_adder(t1, t2, s, c, v1, v2):
linear = {c: 1, v1: 0, v2: 1, t1: 0, t2: 0, s: 1}
quadratic = {(c, t1): -1, (c, t2): -1, (c, s): 1, (v1, t1): -1,
(v1, t2): 1, (v2, t1): 1, (v2, t2): 1, (v2, s): 1}
return dimod.BinaryQuadraticModel(linear, quadratic, dimod.SPIN)
С точками данных из диаграммы полусумматора (рис. 7) мы можем подставить значения для наших линейных членов и квадратичных членов. Затем мы можем вернуть нашу BQM как модель Изинга для значений. Структура кода практически не изменилась по сравнению с вентилем И, единственное отличие заключается в значениях в словарях. Затем мы можем запустить функцию со следующим кодом драйвера.
half_adder_bqm = half_adder('t1', 't2', 's', 'c', 'v1', 'v2')
sampler = dimod.ExactSolver()
print(sampler.sample(half_adder_bqm))
Функция должна дать следующий вывод.
c s t1 t2 v1 v2 energy num_oc. 4 -1 -1 -1 -1 +1 +1 -5.0 1 7 -1 -1 -1 -1 -1 +1 -5.0 1 17 +1 -1 +1 +1 -1 -1 -5.0 1 18 +1 -1 +1 +1 +1 -1 -5.0 1 32 -1 +1 -1 +1 -1 -1 -5.0 1 51 -1 +1 +1 -1 +1 -1 -5.0 1 10 +1 -1 +1 -1 +1 +1 -3.0 1 11 -1 -1 +1 -1 +1 +1 -3.0 1 12 -1 -1 +1 -1 +1 -1 -3.0 1 13 +1 -1 +1 -1 +1 -1 -3.0 1
На самом деле вывод должен состоять из 64 строк, но я показываю только первые 10 выводов, которые являются наиболее важными. Здесь столбец «c» — перенос, «s» — сумма, «t1» и «t2» — входные данные, а «v1» и «v2» — дополнительные переменные. Мы видим, что наименьшая энергия равна -5,0, поэтому первые шесть БКМ с этой энергией являются правильными решениями, соответствующими таблице истинности на рис. 7. Мы можем подтвердить это, сравнив с таблицей истинности:
Результаты правильно соответствуют таблице истинности, но, как и в случае с логическим элементом И, мы получаем повторяющиеся значения. Вышеупомянутое, это связано с нашими дополнительными переменными, на этот раз v1 и v2. Как и в прошлый раз, проблем с точностью этой модели не возникнет.
Полный сумматор, который может складывать три двоичных числа, по своей реализации очень похож на полусумматор. Вот схема полного сумматора из статьи D-Wave.
Полному сумматору требуются три дополнительные переменные для обработки всех трех входных данных, поэтому мы примем это во внимание, когда будем использовать эту диаграмму для написания функции для нашего кода.
def full_adder(t1, t2, t3, s, c, v1, v2, v3):\n",
linear = {t1: 0, t2: 0, t3: 0, s: 0, c: 0, v1: 0, v2: 0, v3: 0}
quadratic = {(t3, v3): 1, (c, t1): -1, (c, t2): -1, (c, s): 1, (c, v3): 1, (v1, t1): 1,(v1, t2): -1, (v1, s): 1, (v1, v3): -1, (v2, t1): -1, (v2, t2): 1,(v2, s): 1, (v2, v3): -1}
return dimod.BinaryQuadraticModel(linear, quadratic, dimod.SPIN
Единственное, что мы меняем из функции полусумматора, — это имена переменных, а также значения этих переменных.
Запустив его с тем же кодом драйвера, мы получим следующий вывод:
c s t1 t2 t3 v1 v2 v3 energy num_oc. 8 -1 +1 -1 -1 +1 -1 -1 -1 -7.0 1 21 +1 +1 +1 +1 +1 -1 -1 -1 -7.0 1 36 +1 -1 -1 +1 +1 +1 -1 -1 -7.0 1 102 +1 -1 +1 -1 +1 -1 +1 -1 -7.0 1 142 -1 +1 +1 -1 -1 -1 +1 +1 -7.0 1 162 +1 -1 +1 +1 -1 +1 +1 +1 -7.0 1 191 -1 -1 -1 -1 -1 +1 +1 +1 -7.0 1 204 -1 +1 -1 +1 -1 +1 -1 +1 -7.0 1 9 -1 +1 +1 -1 +1 -1 -1 -1 -5.0 1 11 -1 +1 -1 +1 +1 -1 -1 -1 -5.0 1
На выходе должно быть 256 строк, но опять же, я показываю только первые 10, так как они наиболее важны для нас. Мы видим, что функция дала нам правильные входные и выходные значения и показывает, что первые восемь имеют наименьшее значение энергии, равное -7,0. Это можно подтвердить сравнением с таблицей истинности полного сумматора:
Все выходные данные с наименьшим значением энергии (-7,0) соответствуют строке в таблице истинности, а это означает, что теперь модель ведет себя как полный сумматор.
Поздравляем! Вам удалось создать и выполнить логические вентили — задачу, которую большинство квантовых компьютеров не могут выполнить изначально. Эти вентили и сумматоры могут показаться простыми на первый взгляд, но это фундаментальные строительные блоки, необходимые для создания почти всего в мире компьютеров. Используя это как основу, вы можете создавать большие и лучшие программы для решения более сложных задач. Удачи!
Примечание. Особая благодарность Алексу Хану и Терриллу Францу из Гаррисбергского университета за помощь в написании этой статьи.
Источники:
1. https://www.dwavesys.com/media/l0tjzis2/14-1002a_b_tr_boosting_integer_factorization_via_quantum_annealing_offsets.pdf
