ZX-исчисление - ZX-calculus

В ZX-исчисление это строгий графический язык для рассуждений о линейных картах между кубиты, которые представлены как ZX-диаграммы. ZX-диаграмма состоит из набора генераторов, называемых пауки которые представляют собой конкретные тензоры. Они соединены вместе, чтобы сформировать тензорная сеть похожий на Графическое обозначение Пенроуза. Благодаря симметрии пауков и свойств нижележащего категория, топологически деформируя ZX-диаграмму (т.е. перемещая генераторы без изменения их соединений), не влияет на линейную карту, которую она представляет. В дополнение к равенствам между ZX-диаграммами, которые порождаются топологическими деформациями, ZX-исчисление также имеет набор правила графической перезаписи для преобразования ZX-диаграмм друг в друга. ZX-исчисление универсальный в том смысле, что любую линейную карту между кубитами можно представить в виде ZX-диаграммы, а различные наборы графических правил перезаписи полный для разных семейств линейных отображений. ZX-диаграммы можно рассматривать как обобщение обозначение квантовой схемы.

История

ZX-исчисление было впервые введено Боб Кук и Росс Дункан в 2008 году как продолжение Категориальная квантовая механика школа рассуждений. Они представили основные понятия о пауках, сильная взаимодополняемость и большинство стандартных правил перезаписи.[1][2]

В 2009 году Дункан и Пердрикс обнаружили дополнительную Разложение Эйлера правило для Ворота Адамара[3], который был использован Бакенсом в 2013 году для получения первого результата полноты для ZX-исчисления.[4]. А именно, что существует набор правил перезаписи, достаточный для доказательства всех равенств между стабилизатор ZX-диаграммы, где фазы кратны , с точностью до глобальных скаляров. Позднее этот результат был уточнен для полноты с учетом скалярных множителей.[5].

В 2017 году завершение ZX-исчисления для примерно универсального фрагмент был найден[6], в дополнение к двум различным результатам полноты для универсального ZX-исчисления (где фазам разрешено принимать любое действительное значение)[7][8].

Также в 2017 году книга Изображение квантовых процессов был выпущен, который строит квантовую теорию с нуля, используя ZX-исчисление[9]. См. Также книгу 2019 г. Категории квантовой теории[10].

Неформальное введение

Пример ZX-диаграммы. У этого есть два входа (провода, идущие слева) и три выхода (провода, идущие вправо), и, следовательно, он представляет собой линейную карту из к .

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

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

Генераторы

Строительные блоки или генераторы ZX-исчисления являются графическими представлениями конкретных состояния, унитарные операторы, линейные изометрии, и прогнозы в вычислительной базе и Базис с преобразованием Адамара и . Зеленый цвет (или иногда белый) используется для представления вычислительной основы, а красный цвет (или иногда серый) используется для представления преобразованного Адамара базиса. Кроме того, каждый из этих генераторов может быть обозначен фазой, которая является действительным числом из интервала . Если фаза равна нулю, это обычно не записывается.

Генераторы:

Генераторы ZX-исчисления, неформально
ТипГенераторСоответствующая линейная картаЗамечания
штатЗа и , это отображение соответствует ненормализованным версиям преобразованных по Адамару базисных состояний и , соответственно. За , это ненормализованная версия T магическое состояние[11] .
штатЗа и , это отображение соответствует ненормализованным версиям вычислительных базисных состояний и , соответственно.
унитарная картаЭта карта представляет собой вращение вокруг оси Z Сфера Блоха под углом . За , это Z Матрица Паули.
унитарная картаЭта карта представляет собой поворот вокруг оси X сферы Блоха на угол . За , это X Матрица Паули.
унитарная карта
Эта карта Ворота Адамара часто используется в квантовых схемах.
изометрияЗа , эта карта представляет операцию копирования в вычислительной базе. При той же стоимости , он также соответствует гладкий раскол операция по решетчатая хирургия.[12]
изометрияЗа , эта карта представляет собой операцию копирования в базисе с преобразованием Адамара. При той же стоимости , он также соответствует грубый раскол операция по решетчатая хирургия.[12]
частичная изометрияЗа , эта карта представляет операцию управляемого НЕ, за которой следует деструктивное измерение Z на целевом кубите. пост-выбранный государству . При той же стоимости , он также соответствует плавное слияние (без операторов побочных продуктов) решетчатая хирургия.[12]
частичная изометрияЗа , эта карта представляет операцию управляемого НЕ, за которой следует деструктивное измерение X на контрольном кубите, выбранном после перехода в состояние . При той же стоимости , он также соответствует грубое слияние (без операторов побочных продуктов) решетчатая хирургия.[12]
проекцияЗа или , эта карта соответствует деструктивному измерению X пост-выбранный государству или , соответственно.
проекцияЗа или , эта карта соответствует деструктивному измерению Z пост-выбранный государству или , соответственно.

Сочинение

Генераторы могут быть составлены двумя способами:

  • последовательно, соединив выходные провода одного генератора с входными проводами другого;
  • параллельно, устанавливая два генератора вертикально.

Эти законы соответствуют композиции и тензорному произведению линейных отображений.

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

Только топология имеет значение

Две диаграммы представляют один и тот же линейный оператор, если они состоят из одних и тех же генераторов, соединенных одинаковым образом. Другими словами, всякий раз, когда две ZX-диаграммы могут быть преобразованы друг в друга топологической деформацией, они представляют собой одно и то же линейное отображение. Таким образом ворота с управляемым НЕ можно представить следующим образом:

ZX-исчисление cNOT-example.svg

Переписывание схемы

В следующем примере квантовой схемы создается GHZ-состояние. Путем перевода его в ZX-диаграмму с использованием правил, согласно которым «смежные пауки одного цвета сливаются», «Адамар меняет цвет пауков» и «пауки arity-2 являются идентичностями», можно графически уменьшить до GHZ -государственный:

Схема GHZ как ZX-diagram.svg

Любую линейную карту между кубитами можно представить в виде ZX-диаграммы, т.е.ZX-диаграммы являются универсальный. Данная ZX-диаграмма может быть преобразована в другую ZX-диаграмму с использованием правил перезаписи ZX-исчисления тогда и только тогда, когда две диаграммы представляют одну и ту же линейную карту, то есть ZX-исчисление звук и полный.

Формальное определение

В категория ZX-диаграмм является кинжал компактная категория, что означает, что он симметричный моноидальный структура (тензорное произведение), является компактный закрытый (она имеет чашки и шапки) и оснащен кинжал, так что все эти структуры должным образом взаимодействуют. Объектами категории являются натуральные числа, а тензорное произведение задается сложением (категория - это PROP ). Морфизмы этой категории являются ZX-диаграммами. Две ZX-диаграммы составляются путем сопоставления их по горизонтали и соединения выходов левой диаграммы с входами правой диаграммы. Моноидальное произведение двух диаграмм можно представить, поместив одну диаграмму над другой.

Действительно, все ZX-диаграммы построены свободно из набора генераторов через композицию и моноидальное произведение по модулю равенств, индуцированных компактной структурой и правилами ZX-исчисления, приведенными ниже. Например, идентичность объекта изображается как параллельные провода слева направо, в особом случае это пустая диаграмма.

В следующей таблице представлены генераторы вместе с их стандартными интерпретациями как линейные карты, выраженные в Обозначение Дирака. Вычислительные базисные состояния обозначены и Адамар -трансформированные базисные состояния . В -кратное тензорное произведение вектора обозначается .

Генераторы ZX-диаграмм[13]
имяДиаграммаТипЛинейная карта, которую он представляет
пустая диаграмма
Это обычное представление пустой диаграммы в категориальной квантовой механике.
1
провод / личность
Состояние колокола
Это обычное представление чашечной диаграммы в категориальной квантовой механике.
Эффект колокола
Это обычное представление кепки в категориальной квантовой механике.
замена
Это обычное представление морфизма перестановки на графическом языке симметричных моноидальных категорий.
Z паук
Это зеленый Z-паук из ZX-исчисления, с фазой альфа и n входов и m выходов.
X паук
Это красный X-паук из ZX-исчисления, с фазой альфа и n входов и m выходов.
Адамар

Существует множество различных версий ZX-исчисления, в которых в качестве аксиом используются разные системы правил перезаписи. Все используют метаправило «имеет значение только топология», что означает, что две диаграммы равны, если они состоят из одних и тех же генераторов, соединенных одинаковым образом, независимо от того, как эти генераторы расположены на диаграмме. Ниже приведены некоторые из основных набор правил перезаписи, здесь заданный «с точностью до скалярного фактора»: т.е. две диаграммы считаются равными, если их интерпретация как линейные карты отличается на ненулевой комплексный коэффициент.

Правила ZX-исчисления[14]
Название правилаПравилоОписание
Z-паук слияниеZX-исчисление зеленый паук fusion rule.svgКогда два Z-паука соприкасаются, они могут сливаться вместе, и их фазы складываются. Это правило соответствует тому, что Z-паук представляет собой ортонормированный базис - вычислительный базис.
Икс-паук фьюжнZX-Calculus Red Spider Fusion rule.svgСм. Слияние Z-паука.
Правило идентичности
ZX-исчисление red and green identity rules.svg
Бесфазный 2 Z- или X-паук арности равен тождеству. Это правило гласит, что Белл-состояние является одним и тем же независимо от того, выражается ли он в вычислительном базисе или в базисе с преобразованием Адамара. В терминах теории категорий он говорит, что компактная структура, индуцированная Z- и X-пауками, совпадает.
Изменение цвета
Правило изменения цвета ZX-исчисления.svg
Ворота Адамара меняют цвет пауков. Это выражает свойство, которое вентиль Адамара отображает между вычислительным базисом и базисом, преобразованным Адамара.
Копировать правило
ZX-Calculus 2 выводит красно-зеленый copy rule.svg
Z-паук копирует X-пауков arity-1. Это выражает тот факт, что X-паук arity-1 пропорционален вычислительному базисному состоянию (в данном случае ).
Правило биалгебрыZX-исчисление 2 вход 2 выход биалгебра rule.svgДва цикла Z- и X-пауков упрощают. Это выражает то свойство, что вычислительный базис и преобразованный по Адамару базис являются сильно дополняющий.
-скопировать правилоZX-исчисление красный пи корыто зеленый фазовый паук copy rule.svgНЕ-гейт (X-паук arity-2 с phase) копирует через Z-паук и переворачивает фазу этого паука. В этом правиле указываются сразу два свойства. Во-первых, это НЕ карта функций вычислительного базиса (он отображает базовые состояния в базовые состояния), и, во-вторых, когда НЕ коммутируется через вентиль Z-вращения, это вращение переворачивается.
Разложение ЭйлераZX-исчисление скалярно-свободное правило разложения Эйлера по Адамару. SvgВорота Адамара можно развернуть на три вращения вокруг сферы Блоха (соответствующие ее Углы Эйлера ). Иногда это правило принимают за определение генератора Адамара, и в этом случае единственными генераторами ZX-диаграмм являются Z- и X-паук.

Приложения

ZX-исчисление использовалось во множестве квантовая информация и вычисление задачи.

инструменты

Правила перезаписи ZX-исчисления могут быть формально реализованы как экземпляр перезапись с двойным выталкиванием. Это было использовано в программном обеспечении Quantomatic чтобы позволить автоматическое переписывание ZX-диаграмм (или более общих строковые диаграммы )[23]. Чтобы формализовать использование «точек» для обозначения любого количества проводов, например, используемых в правиле слияния пауков, это программное обеспечение использует ударная коробка обозначение[24] реализовать правила перезаписи, в которых пауки могут иметь любое количество входов или выходов.

Более свежий проект по работе с ZX-диаграммами - PyZX, который в первую очередь ориентирован на оптимизацию схем[14].

Связанные графические языки

ZX-исчисление - только один из нескольких графических языков для описания линейных отображений между кубитами. В ZW-исчисление был разработан вместе с ZX-исчислением и может естественным образом описывать W-состояние и фермионные квантовые вычисления[25][26]. Это был первый графический язык, который имел полный набор правил для приблизительно универсального набора линейных отображений между кубитами.[7], и первые результаты полноты ZX-исчисления используют редукцию к ZW-исчислению.

Более новый язык - это ZH-исчисление. Это добавляет H-бокс как генератор, который обобщает вентиль Адамара из ZX-исчисления. Он может естественным образом описывать квантовые схемы, включающие вентили Тоффоли.[27].

Связанные алгебраические концепции

Бесфазные пауки в исчислении ZX удовлетворяют аксиомам Алгебра Хопфа с тривиальным отображением в качестве антипода. В этом можно убедиться, заметив, что он изоморфен групповой алгебре .

Смотрите также

Рекомендации

  1. ^ Кок, Боб; Дункан, Росс (2008), "Взаимодействующие квантовые наблюдаемые", Автоматы, языки и программирование, Конспект лекций по информатике, 5126, Springer Berlin Heidelberg, стр. 298–310, CiteSeerX  10.1.1.381.2573, Дои:10.1007/978-3-540-70583-3_25, ISBN  9783540705826
  2. ^ Кок, Боб; Дункан, Росс (2011-04-14). «Взаимодействующие квантовые наблюдаемые: категориальная алгебра и диаграмматика». Новый журнал физики. 13 (4): 043016. arXiv:0906.4725. Bibcode:2011NJPh ... 13d3016C. Дои:10.1088/1367-2630/13/4/043016. ISSN  1367-2630.
  3. ^ а б Дункан, Росс; Пердрикс, Саймон (2009), "Состояния графа и необходимость разложения Эйлера", Математическая теория и вычислительная практика, Springer Berlin Heidelberg, стр. 167–177, Дои:10.1007/978-3-642-03073-4_18, ISBN  9783642030727
  4. ^ Бакенс, Мириам (17 сентября 2014 г.). «ZX-исчисление является полным для квантовой механики стабилизаторов». Новый журнал физики. 16 (9): 093021. arXiv:1307.7025. Bibcode:2014NJPh ... 16i3021B. Дои:10.1088/1367-2630/16/9/093021. ISSN  1367-2630.
  5. ^ Бакенс, Мириам (4 ноября 2015 г.). «Завершение ZX-исчисления стабилизатора для скаляров». Электронные материалы по теоретической информатике. 195: 17–32. arXiv:1507.03854. Bibcode:2015arXiv150703854B. Дои:10.4204 / eptcs.195.2. ISSN  2075-2180.
  6. ^ Джендель, Эммануэль; Пердрикс, Саймон; Вильмарт, Рено (2018). «Полная аксиоматизация ZX-исчисления для квантовой механики Clifford + T». Материалы 33-го ежегодного симпозиума ACM / IEEE по логике в компьютерных науках - LICS '18. Нью-Йорк, Нью-Йорк, США: ACM Press: 559–568. arXiv:1705.11151. Дои:10.1145/3209108.3209131. ISBN  9781450355834.
  7. ^ а б Хаджихасанович, Амар; Нг, Кан Фенг; Ван, Цюаньлун (2018). «Две полные аксиоматизации чистых кубитных квантовых вычислений». Материалы 33-го ежегодного симпозиума ACM / IEEE по логике в компьютерных науках. ACM: 502–511. Дои:10.1145/3209108.3209128. ISBN  9781450355834. Получено 21 мая 2019.
  8. ^ Джендель, Эммануэль; Пердрикс, Саймон; Вильмарт, Рено (2018). "Диаграммное мышление за пределами квантовой механики Clifford + T". Материалы 33-го ежегодного симпозиума ACM / IEEE по логике в компьютерных науках - LICS '18. Нью-Йорк, Нью-Йорк, США: ACM Press: 569–578. arXiv:1801.10142. Bibcode:2018arXiv180110142J. Дои:10.1145/3209108.3209139. ISBN  9781450355834.
  9. ^ Кок, Боб; Киссинджер, Алекс (2017). Изображение квантовых процессов. Кембридж: Издательство Кембриджского университета. Дои:10.1017/9781316219317. ISBN  9781316219317.
  10. ^ Хойнен, Крис; Викари, Джейми (2019). Категории квантовой теории. Издательство Оксфордского университета. Дои:10.1093 / oso / 9780198739623.001.0001. ISBN  9780198739616.
  11. ^ Бравый, Сергей; Хаа, Чонван (27.11.2012). «Магическая дистилляция с низкими накладными расходами». Физический обзор A. 86 (5): 052329. arXiv:1209.2426. Bibcode:2012PhRvA..86e2329B. Дои:10.1103 / Physreva.86.052329. ISSN  1050-2947.
  12. ^ а б c d Хорсман, Доминик; де Бодрап, Ниль (27 апреля 2017 г.). «Исчисление ZX - это язык для хирургии решетки поверхностного кода». arXiv:1704.08670v2 [Quant-ph ].
  13. ^ Бакенс, Мириам; Пердрикс, Саймон; Ван, Цюаньлун (2017-01-01). «Упрощенный ZX-расчет стабилизатора». Электронные материалы по теоретической информатике. 236: 1–20. Дои:10.4204 / eptcs.236.1. ISSN  2075-2180.
  14. ^ а б ван де Ветеринг, Джон; Киссинджер, Алекс (2019-04-09). «PyZX: крупномасштабные автоматизированные схематические рассуждения». arXiv:1904.04735v1 [Quant-ph ].
  15. ^ Дункан, Росс; Пердрикс, Саймон (2010), "Переписывание основанных на измерениях квантовых вычислений с обобщенным потоком", Автоматы, языки и программирование, Springer Berlin Heidelberg, стр. 285–296, Дои:10.1007/978-3-642-14162-1_24, ISBN  9783642141614, S2CID  34644953
  16. ^ Киссинджер, Алекс; ван де Ветеринг, Джон (2019-04-26). «Универсальный MBQC с обобщенными четно-фазовыми взаимодействиями и измерениями Паули». Квантовая. 3: 134. Дои:10.22331 / кв-2019-04-26-134. ISSN  2521-327X.
  17. ^ Хорсман, Доминик; де Бодрап, Ниль (2017-04-27). «Исчисление ZX - это язык для хирургии решетки поверхностного кода». arXiv:1704.08670v1 [Quant-ph ].
  18. ^ Пердрикс, Саймон; Хорсман, Доминик; Дункан, Росс; де Бодрап, Ниль (2019-04-29). «Pauli Fusion: вычислительная модель для реализации квантовых преобразований из терминов ZX». arXiv:1904.12817v1 [Quant-ph ].
  19. ^ Хорсман, Доминик; Зохрен, Стефан; Роффе, Йошка; Киссинджер, Алекс; Канцлер Николай (23.11.2016). «Графические структуры для проектирования и проверки квантовой коррекции ошибок». arXiv:1611.08012v3 [Quant-ph ].
  20. ^ Дункан, Росс; Лукас, Максим (27 декабря 2014). «Проверка кода Steane с помощью Quantomatic». Электронные материалы по теоретической информатике. 171: 33–49. Дои:10.4204 / eptcs.171.4. ISSN  2075-2180.
  21. ^ Гарви, Лиам; Дункан, Росс (27.02.2018). «Проверка самого маленького интересного цветового кода с помощью Quantomatic». Электронные материалы по теоретической информатике. 266: 147–163. Дои:10.4204 / eptcs.266.10. ISSN  2075-2180.
  22. ^ Фэган, Эндрю; Дункан, Росс (31.01.2019). «Оптимизация схем Клиффорда с помощью Quantomatic». Электронные материалы по теоретической информатике. 287: 85–105. arXiv:1901.10114. Bibcode:2019arXiv190110114F. Дои:10.4204 / eptcs.287.5. ISSN  2075-2180.
  23. ^ Киссинджер, Алекс; Замджиев, Владимир (2015), "Квантовая математика: помощник по доказательству схематического мышления", Автоматическое удержание - CADE-25, Springer International Publishing, стр. 326–336, arXiv:1503.01034, Bibcode:2015arXiv150301034K, Дои:10.1007/978-3-319-21401-6_22, ISBN  9783319214009
  24. ^ Быстрее, Дэвид; Киссинджер, Алекс (2015-05-02). «Логика первого порядка для строковых диаграмм». arXiv:1505.00343v1 [math.CT ].
  25. ^ Кок, Боб; Киссинджер, Алекс (2010), "Композиционная структура многоканальной квантовой запутанности", Автоматы, языки и программирование, Springer Berlin Heidelberg, стр. 297–308, arXiv:1002.2540, Bibcode:2010arXiv1002.2540C, Дои:10.1007/978-3-642-14162-1_25, ISBN  9783642141614
  26. ^ Хаджихасанович, Амар; Дункан, Росс (2015). «Диаграмматическая аксиоматизация кубитовой запутанности». 2015 30-й ежегодный симпозиум ACM / IEEE по логике в компьютерных науках. С. 573–584. arXiv:1501.07082. Дои:10.1109 / lics.2015.59. ISBN  9781479988754.
  27. ^ Бакенс, Мириам; Киссинджер, Алекс (31.01.2019). "ZH: Полное графическое исчисление для квантовых вычислений с использованием классической нелинейности". Электронные материалы по теоретической информатике. 287: 23–42. Дои:10.4204 / eptcs.287.2. ISSN  2075-2180.

внешняя ссылка