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