Автоматическая компиляция квантовых цепей

Недавно был задан вопрос о том, как скомпилировать 4-кубитный вентиль CCCZ (Control-Control-Control-Z-Z) в простые 1-кубитные и 2-кубитные вентили, и единственный ответ, который был дан до сих пор, требует 63 вентилей !

Первым шагом было использование конструкции C n U, предоставленной Nielsen & Chuang:$^n$

При $n=3$ это означает 4 шлюза CCNOT и 3 простых шлюза (1 CNOT и 2 Адамара достаточно для выполнения окончательной CZ на целевом кубите и последнем рабочем кубите).

Теорема 1 этой статьи гласит, что в общем случае CCNOT требует 9 однокубитных и 6 двухкбитных вентилей (всего 15):

Это означает:

(4 CCNOT) x (15 ворот на CCNOT) + (1 CNOT) + (2 Адамара) = 63 всего ворот .

В комментарии было высказано предположение, что 63 шлюза могут быть затем скомпилированы с использованием «автоматической процедуры», например, из теории автоматических групп .

Как можно выполнить эту «автоматическую компиляцию», и насколько это уменьшило бы число вентилей с 1 и 2 кубитами в этом случае?

Пусть $g_1 \cdots g_M$ - основные ворота, которые вам разрешено использовать. Для целей настоящего $\operatorname{CNOT}_{12}$ и $\operatorname{CNOT}_{13}$ т. Д. Рассматриваются как отдельные. Таким образом, $M$ полиномиально зависит от $n$ , число кубитов. Точная зависимость включает в себя детали того, какие типы ворот вы используете, и насколько они $k$ локальны. Например, если есть $x$ однобитовых ворот и $y$ 2-кубитных ворот, которые не зависят от порядка, такого как $CZ$ то .$M = xn+\binom{n}{2}y$

Схема тогда является произведением этих генераторов в некотором порядке. Но есть несколько схем, которые ничего не делают. Как . Так что те дают отношения по группе. То есть это групповое представление где есть много отношений, которые мы не знаем.$\operatorname{CNOT}_{12} \operatorname{CNOT}_{12} = \mathrm{Id}$ $\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

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

Но мы можем рассмотреть более простую проблему. Если мы выбрасываем некоторые из , то слова до этого становятся в форме где каждый из является словами только в оставшихся буквах. Если нам удалось сделать их короче, используя отношения, которые не включают , то мы сделаем всю схему короче. Это похоже на самостоятельную оптимизацию CNOT, сделанную в другом ответе.$g_i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$g_i$

Например, если есть три генератора и слово , но мы не хотим иметь дело с , вместо этого мы сократим и до и , Затем мы складываем их обратно как и это сокращение исходного слова.$aababbacbbaba$$c$$w_1=aababba$$w_2=bbaba$$\hat{w}_1$$\hat{w}_2$$\hat{w}_1 c \hat{w}_2$

Итак, WLOG (без потери общности), давайте предположим, что мы уже в этой задаче где мы теперь используем все указанные ворота. Опять же, это, вероятно, не автоматическая группа. Но что, если мы выбрасываем некоторые отношения? Тогда у нас будет другая группа, у которой есть фактор-карта до той, которую мы действительно хотим.$\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

Группа no - это свободная группа , но если вы положите в качестве отношения, вы получите бесплатный продукт и существует частное отображение от первого к последующему, уменьшающее число в каждом сегменте по модулю .$\langle g_1 g_2 \mid - \rangle$$g_1^2=\mathrm{id}$ $\mathbb{Z}_2 \star \mathbb{Z}$$g_1$$2$

Отношения, которые мы выбрасываем, будут такими, что одно наверху (источник фактор-карты) будет автоматическим по замыслу. Если мы используем только те отношения, которые остаются и сокращают слово, то оно все равно будет более коротким словом для фактор-группы. Это просто не будет оптимальным для фактор-группы (цели для фактор-карты), но она будет иметь длину до длины, с которой она началась.$\leq$

Это была общая идея, как мы можем превратить это в конкретный алгоритм?

Как мы выбираем и отношения, которые нужно выбросить, чтобы получить автоматическую группу? Именно здесь приходит знание о типах элементарных врат, которые мы обычно используем. Инволюций много, поэтому оставляйте только те. Обратите пристальное внимание на тот факт, что это только элементарные инволюции, поэтому, если вашему оборудованию трудно поменять кубиты, которые сильно разделены на вашем чипе, это записывает их только в те, которые вы можете легко сделать, и сокращая это слово до быть как можно короче.$g_i$

Например, предположим, у вас есть конфигурация IBM . Тогда являются разрешенными воротами. Если вы хотите сделать общую перестановку, разложите ее на факторов. Это слово из группы которое мы хотим сократить ,$s_{01},s_{02},s_{12},s_{23},s_{24},s_{34}$$s_{i,i+1}$$\langle s_{01},s_{02},s_{12},s_{23},s_{24},s_{34} \mid R_1 \cdots \rangle$

Обратите внимание, что они не должны быть стандартными инволюциями. Например, вы можете добавить в дополнение кПодумайте о теореме Готтесмана-Найла , но абстрактно это означает, что ее будет легче обобщить. Например, используя свойство, которое при коротких точных последовательностях, если у вас есть конечные полные системы переписывания для двух сторон, то вы получаете одну для средней группы. Этот комментарий не нужен для остальной части ответа, но показывает, как вы можете собрать более общие примеры из приведенных в этом ответе.$R(\theta) X R(\theta)^{-1}$$X$

только отношения вида . Это дает группу Кокстера, и это автоматически. На самом деле, нам даже не нужно начинать с нуля, чтобы кодировать алгоритм для этой автоматической структуры. Он уже реализован в Sage (на основе Python) общего назначения. Все, что вам нужно сделать, это указать а оставшаяся реализация уже выполнена. Вы могли бы сделать некоторые ускорения в дополнение к этому.$(g_i g_j)^{m_{ij}} = 1$$m_{ij}$

$m_{ij}$ действительно легко вычислить из-за локальных свойств ворот. Если вентили не более чем локально, то вычисление может быть выполнено в мерном гильбертовом пространстве. Это потому, что если индексы не перекрываются, то вы знаете, что . для когда и коммутируют. Вам также нужно только вычислить менее половины записей. Это потому, что матрица симметрична, имеет на диагонали ( ). Также большинство записей просто переименовывают вовлеченные кубиты, так что если вы знаете порядок$k$$m_{ij}$$2^{2k-1}$$m_{ij}=2$$m_{ij}=2$$g_i$$g_j$$m_{ij}$$1$$(g_i g_i)^1 = 1$$(\operatorname{CNOT}_{12} H_1)$ , вы знаете порядок без повторного вычисления.$\operatorname{CNOT}_{37} H_3$

Это позаботилось обо всех отношениях, которые включали не более двух разных ворот (доказательство: упражнение). Отношения, в которых участвовало или более, были выброшены. Теперь вернем их обратно. Допустим, у нас это есть, тогда можно выполнить жадный алгоритм Дена, используя новые отношения. Если произошли изменения, мы подбрасываем их обратно, чтобы снова пройти через группу Коксетера. Это повторяется, пока нет никаких изменений.$3$

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

Если вы хотите проверить это самостоятельно, укажите число генераторов как , длину случайного слова, которое вы пробуете, и матрицу Кокстера как .$N$$K$$m$

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)

Пример с N=28и K=20, первые две строки - это входное невосстановленное слово, следующие две - сокращенное слово. Я надеюсь, что я не сделал опечатку при вводе матрицы .$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']

Отбрасывая те генераторы, как мы возвращаем только отношения, подобные и коммутирует с вентилями, которые не включают кубит . Это позволяет нам сделать декомпозицию до того, как как можно дольше. Мы хотим избежать таких ситуаций, как . (В Cliff + T часто стараются минимизировать T-count). Для этой части решающее значение имеет направленный ациклический граф, показывающий зависимость. Это проблема поиска хорошего топологического вида DAG. Это делается путем изменения приоритета, когда у вас есть выбор, какую вершину использовать дальше. (Я бы не стал тратить время на оптимизацию этой части слишком сильно.)$T_i$$T_i^n = 1$$T_i$$i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$X_1 T_2 X_1 T_2 X_1 T_2 X_1$

Если слово уже близко к оптимальной длине, делать нечего, и эта процедура не поможет. Но как самый простой пример того , что он находит, если у вас есть несколько единиц , и вы забыли там был в конце одного и в начале следующего, это позволит избавиться от этой пары. Это означает, что вы можете с уверенностью сказать, что при выполнении общих процедур «черного ящика» все эти очевидные отмены будут учтены. Это делает другие, которые не так очевидны; те используют когда .$H_i$$H_i$$m_{ij} \neq 1,2$

Используя процедуру, описанную в https://arxiv.org/abs/quant-ph/0303063 ¹ , любой диагональный вентиль - любой, таким образом, в частности вентиль CCCZ - может быть разложен в терминах, например, CNOT и однобитовых диагональных вентилей, где CNOT могут быть оптимизированы самостоятельно, следуя классической процедуре оптимизации.

Ссылка обеспечивает схему, использующую 16 CNOT для произвольных диагональных 4-кубитных вентилей (рис. 4).

Примечание. Хотя в принципе может существовать более простая схема (упомянутая схема была оптимизирована с учетом более ограниченной архитектуры схемы), она должна быть близка к оптимальной - схема должна создавать все состояния в форме для любого нетривиального подмножества , а для 4 кубитов их 15.$\bigoplus_{i\in I}x_i$$I\subset\{1,2,3,4\}$

Отметим также, что эта конструкция ни в коем случае не должна быть оптимальной.

^{1 Примечание: я автор}