У меня есть приемный сын. Из своих 17 лет 4 он прожил со мной. 6 лет я был скаутмастером, а теперь хожу в методистскую церковь. Иногда по воскресеньям я даже встаю за кафедру. Я одинаково люблю работать и с человеческими, и с инженерными ценностями.

Аудиоверсия: Apple Podcasts Яндекс.Музыка PodFM Google Podcasts YouTube.

Пара слов о специфике отрасли

Возможности для ученых из смежных областей

Какие задачи стоят перед сообществом

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

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

Краткое знакомство с квантовым хакингом

Нельзя так просто взять и не помешать коллегам

Почему важно не торопиться с публикацией методов защиты

Немного о взаимодействии с контролирующими организациями

О разграничении на фундаментальную и прикладную науку

• Как подойти к синхронизации AR-контента с шоу в масштабе целого стадиона
• Что общего у научной визуализации данных и геймдева
• Что ждет начинающих ученых в сфере МО

Введение

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

Устройство блокчейна

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

Такой вычислительно сложной задачей может быть, например, поиск коллизий хеша: нахождение некоего числа, proof-of-work (англ.: доказательство работы), при добавлении которого хеш от блока начинается с нескольких нулей. Данная задача с помощью классического компьютера может решаться лишь перебором, из-за чего среднее время нахождение такого числа экспоненциально растет с ростом требуемого количества нулей. Более подробно об этом можно прочитать в оригинальной статье С. Накамото, предложившего данную идею.

Блоки состоят из сформированных пользователями транзакций, которые подписываются ими с использованием асимметричной криптографии. Каждый пользователь имеет два ключа: приватный, известный только этому пользователю, с помощью которого он подписывает транзакции, и публичный, известный всем пользователям, с помощью которого кто угодно может проверить подпись. Например, биткоин использует для подписи транзакций алгоритм ECDSA (англ.: Elliptic Curve Digital Signature Algorithm), схожий с алгоритмом DSA (англ.: Digital Signature Algorithm), но определенный в группе точек эллиптической кривой. Криптографическая стойкость данного логарифма основывается на сложности задачи дискретного логарифмирования, которая на классическом компьютере решается за экспоненциальное время относительно размера ключа. Другой вычислительно сложной задачей является задача факторизации больших чисел, на которой, например, основан алгоритм RSA (англ.: Rivest Shamir Adleman), также обеспечивающий криптографическую стойкость цифровой подписи, поскольку лежащая в основе него задача решается за время, которое экспоненциально зависит от размера ключа. Таким образом, пока эта криптографическая стойкость существует, пользователям гарантируется, что никто другой не сможет сгенерировать транзакции от их имени.

Уязвимость перед квантовым компьютером

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

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

Алгоритм Гровера

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

Суть алгоритма Гровера заключается в следующем. Допустим, мы имеем некую функцию $inline$f(x)$inline$, корень которой мы собираемся найти. Пусть эта функция реализуема на классическом компьютере, тогда в теории представляется возможным реализовать обратимую функцию $inline$U_f(x)$inline$, которая равняется $inline$0$inline$, если $inline$x$inline$ является корнем функции $inline$f$inline$, и $inline$1$inline$ в противном случае. Такая функция называется оракулом, а её обратимость обеспечивает то, что её можно реализовать на квантовом компьютере, например, при помощи вентилей Тоффоли. В таком случае на вход этой функции можно подавать не одно значение $inline$x$inline$, как в классическом переборе, а суперпозицию всех возможных значений $inline$x$inline$, а значит, получать на выходе суперпозицию всех возможных выходных значений оракула. Далее с помощью элементарных квантовых вентилей можно усилить амплитуду вероятности состояния, соответствующего корню оракула. После определенного количества таких итераций в результате измерения будет получен корень исходной функции $inline$f$inline$ с вероятностью, практически равной $inline$1$inline$. Ситуация несколько осложняется в случае, когда у функции $inline$f$inline$ имеется несколько корней, что соответствует задаче поиска коллизий хеша, однако и в таком случае алгоритм Гровера показывает значительное ускорение по сравнению с простым перебором.

Атака на proof-of-work

Несмотря на то, что алгоритм Гровера способен обеспечить квадратичное ускорение при подсчете блоков, атака с его помощью не является для блокчейна критической, что утверждается в недавнем отчете группы канадских и австралийских ученых. Дело в том, вычислительная мощность интегральных схем специального назначения (англ.: ASIC), находящаяся в настоящий момент в руках майнеров, способна свести на нет практически любые попытки получить ускорение майнинга при помощи квантового компьютера. Допускается, однако, что дальнейшее развитие квантовых технологий может способствовать тому, что квантовые компьютеры получат серьезное преимущество над существующими вычислительными мощностями, но это, по оценкам авторов работы, наступит лишь после повсеместного распространения квантовых компьютеров. Когда же это настанет, майнеры также получат возможность использовать их, тем самым возможность доминирования с помощью квантового компьютера снизойдет на нет.

Кроме того, существуют и другие подходы к генерации блоков, в основе которых не лежат вычислительно сложные задачи, а значит, блокчейны на их основе могут рассматриваться как устойчивые к атакам на proof-of-work. Наиболее популярным таким подходом, который в настоящий момент уже используется, например, в BlackCoin, является proof-of-stake (англ.: доказательство доли владения), заключающийся в том, что блоки с большей вероятностью генерируются теми пользователями, которые владеют большей частью средств в блокчейне. Proof-of-stake не требует поиска коллизий хеша, поэтому с этой точки зрения является устойчивой к атакам с помощью квантового компьютера.

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

Алгоритм Шора

Теперь перейдем к краткому рассмотрению Алгоритма Шора, который способен разлагать большие числа на простые множители и производить дискретное логарифмирование, причем делать всё это за полиномиальное время, сводя обе эти задачи к поиску периода функции. Из-за этого вычислительно сложные задачи, лежащие в основе криптографической стойкости алгоритмов создания цифровой подписи, таких как RSA, ECDSA, ECDH, DSA, оказываются решаемыми за вменяемое время с помощью квантового компьютера, обладающего достаточной мощностью. Наличие такого квантового компьютера позволит злоумышленнику создавать ложные транзакции, тем самым получая доступ ко всем средствам, хранящимся в блокчейне, поэтому в настоящее время именно атаки с помощью алгоритма Шора считаются наиболее опасными для безопасного функционирования блокчейна.

Постквантовый блокчейн

Требования, предъявляемые к постквантовому блокчейну

Прежде чем перейти к обозрению различных подходов к созданию цифровой подписи, устойчивой к квантовым атакам, рассмотрим, какие требования предъявляются к постквантовому блокчейну в целом, чтобы в дальнейшем иметь представление, какие методы могут быть использованы, а какие нет. С одной стороны, кажется, что можно лишь увеличивать размеры ключей и хеша, чтобы отсрочить момент когда квантовые компьютеры смогут окончательно взломать блокчейн, однако такой подход имеет ряд недостатков. Во-первых, это будет требовать от устройств большого количества памяти и вычислительных ресурсов, что неприемлемо в случаях, когда с блокчейном необходимо взаимодействовать устройствам Интернета вещей, поскольку зачастую они не обладают большой памятью и мощностью, а наоборот, должны работать несколько лет от одной батарейки. Во-вторых, увеличение размера хешей и подписей влечет за собой увеличение размера блокчейна, который необходимо хранить всем пользователям, что может занимать довольно много памяти. Такая проблема уже сейчас возникла в Bitcoinе, размер блокчейна которого увеличился на целых 60Гб за один год и на момент написания статьи составил 310Гб, причем его рост лишь продолжает увеличиваться и, можно предположить, примерно к 2030 году он превысит 1Тб. Конечно, существует вариант использовать так называемые легкие кошельки, позволяющие не хранить весь блокчейн, но это уменьшает надежность системы. Таким образом, основные требования к постквантовому блокчейну касаются размеров подписей, ключей и хешей: они не должны быть слишком большими. Кроме того, постквантовый блокчейн должен иметь достаточно большую скорость исполнения операций, чтобы обеспечивать стабильное функционирование системы с огромным количеством транзакций в секунду.

Постквантовые алгоритмы цифровой подписи

В настоящее время ведутся активные работы по разработке алгоритмов шифрования, в том числе и алгоритмов создания цифровой подписи, которые будут устойчивы к атакам с помощью квантового компьютера. Интерес исследователей подогревается тем, что в 2016 году NIST (англ.: Национальный институт стандартов и технологий) запустил конкурс таких алгоритмов, результаты которого будут объявлены к 2022 году. Приведем далее наиболее известные из предложенных алгоритмов, устойчивых к квантовым атакам.

Начнем рассмотрение с механизмов цифровой подписи на основе кода (англ.: code based), примером которой является система McEliece, предложенная примерно в то же время, что и повсеместно используемый алгоритм RSA, однако не получившая тогда широкого распространения. В настоящее время данная система, а также ряд её улучшений, таких как система Niederreiterа, обретают всё большую популярность, поскольку они являются устойчивыми к атакам с помощью алгоритма Шора. В их основе лежит задача декодирования линейных кодов, что является NP-полной задачей, при этом пока что нерешаемой на квантовом компьютере. Несмотря на то, что подписи, сгенерированные по данным методам, обладают относительно маленьким размером и могут быть проверены достаточно быстро, они требуют хранения огромных матриц, которые выступают в роли ключей, что в свою очередь также увеличивает время генерации подписи, затрудняя её использование в блокчейне. В связи с этим исследуются различные методы сжатия матриц или использования других кодов, например, LDPC кодов (англ.: Low Density Parity Check), особенностью которых является малая плотность проверочной матрицы.

Другим механизмом создания цифровой подписи является так называемый механизм на основе решеток (англ.: lattice based), который был отдельно выделен в недавнем отчете NIST как наиболее перспективный. Так называемую решетку можно представить себе как набор точек в n-мерном пространстве с периодической структурой. В данном случае математической задачей, на которой основана криптографическая стойкость, является, например, задача нахождения в этой решетке кратчайшего вектора (Shortest Vector Problem) или же схожая с ней задача нахождения ближайшего вектора (Closest Vector Problem), причём обе эти задачи обладают огромной вычислительной сложностью. Однако недостатком таких систем является тот факт, что необходимо хранить ключи большого размера, что приводит к значительным накладным расходам шифротекста и делает практически невозможным использование подобных систем в блокчейне. Существуют, однако, системы на основе решеток, основанные на задаче краткого целочисленного решения (англ.: Short Integer Solution), благодаря чему удается уменьшить размер ключа, позволяя тем самым использовать такие системы в блокчейне.

Последним механизмом создания цифровой подписи, рассматриваемым в данной статье, является механизм на основе хеша (англ.: hash based), безопасность которого основывается не на сложности некоей математической задачи, а на лежащей в его основе криптографической хеш-функции. Подобный подход был предложен ещё в 70-х годах прошлого века как альтернатива алгоритмам RSA и DSA, однако он не пользовался большим интересом, поскольку накладывает ограничение на количество повторных использований подписей. Однако сейчас этот подход обретает всё большую популярность, поскольку он является устойчивым к квантовым атакам. Недостатком же такого подхода является тот факт, что генерация ключа занимает достаточно длительное время, что делает его неприменимым для использования в блокчейне.

Заключение

В рамках данной статьи были рассмотрены атаки с помощью квантового компьютера, к которым блокчейн оказывается уязвимым. Было выяснено, что хоть алгоритм Гровера и показывает квадратичное ускорение по сравнению с классическими подходами, атака с его помощью не несет практически никакой угрозы для существующих систем на основе proof-of-work, не говоря уже о других методах генерации блоков, таких как proof-of-stack. В то же время главной угрозой, способной свести на нет безопасное функционирование не только блокчейна, но и практически всех цифровых финансовых операций, является атака с помощью алгоритма Шора, методы борьбы с которой были также освещены в данной статье. Кроме того, были рассмотрены требования, предъявляемые к квантовому блокчейну, которые определяют, какие методы борьбы с данной атакой являются приемлемыми, а какие нет.

-Прикольные диалоги генерирует Алиса, когда говорит сама с собой, - сказал DS Петренко.-Ага, - согласился DevOps Колосов. - В разговорах с людьми такого не увидишь. Надо будет запостить на какой-нибудь гиковский портал.

• github.com/quantumlib/Cirq
• github.com/artiste-qb-net/qubiter
• code.google.com/archive/p/pyqu
• qiskit.org

• Большой учебник, с которого лучше начать: Michael A.Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information. Книга очень толстая, есть на русском языке. Там вы точно найдете ответы на все вопросы.
• IBM Q: quantumexperience.ng.bluemix.net
• IBM Q User Guide: quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/introduction.html
• Qiskit: qiskit.org
• Немного научпопа:
  nplus1.ru/material/2017/06/07/quantumcomputers
  nplus1.ru/news/2017/05/26/quantum-blockchain

Продолжаем рубрику тем для первого свидания. На сегодняшней повестке дня упрощение схем для квантовых программ методами ZX-исчисления.

Далее от имени автора

Прежде всего, я хотел бы поблагодарить моих наставников Роджера Ло и Цзиньго Лю за то, что они курировали меня во время Google Summer of Code 2020. В этом проекте GSoC я разрабатываю новый пакет Julia ZXCalculus.jl, который реализует ZX-исчисление, и интегрирую его в качестве инструмента упрощения схем и квантовых программ в YaoLang.jl DSL (предметно-ориентированный язык) для Yao.jl. Yao.jl современный квантовый симулятор со множеством продвинутых функций, такими как автоматическое дифференцирование и символьные вычисления. Как пользователь "Yao.jl", я рад возможности внести свой вклад в его развитие. В этом блоге я подытожу результаты проделанной работы.

Квантовые схемы и ZX-исчисление

Квантовое программирование использует принципы квантовой механики для вычислений. Для описания квантовых алгоритмов мы часто используем модель квантовой схемы, которая является аналогом модели классической логической схемы. Квантовые схемы состоят из набора основных квантовых элементов, таких как вентили Паули, Адамара, T, CNOT.

В общем, будет много эквивалентных квантовых схем, представляющих одну и ту же операцию. С точки зрения квантового оборудования, нужно найти схему, которая минимизирует использование аппаратных ресурсов. К сожалению, поиск наиболее желаемой схемы является очень сложной задачей в плане вычислительной сложности, так как проверка эквивалентности между двумя квантовыми схемами является coQMA-трудной (квантовый аналог coNP) [1], [2]. Несмотря на это, у нас все еще есть некоторые эвристические эффективные алгоритмы для упрощения квантовых схем. В этом блоге я представлю мощный инструмент для этой проблемы ZX-исчисление.

Квантовая схема это граф, представляющий тензорные и матричные произведения. Например

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

Более того, по определению Z-пауков и X-пауков, существуют основные эквивалентные правила, с помощью которых можно упростить ZX-диаграммы.

После упрощения ZX-диаграмм мы должны преобразовать их обратно в схемы. В работе [3] разработаны алгоритмы для приведенной выше схемы.

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

Цель GSoC проекта

Основная цель этого проекта заключается в реализации ZX-исчисления и связанного с ним алгоритма на языке Julia. И мы выпустим пакет Julia ZXCalculus.jl. Существует Python-реализация ZX-исчисления, PyZX. Как и PyZX, ZXCalculus.jl должна предоставлять API для перевода на ZX-диаграммы, извлечения схем из ZX-диаграмм, упрощения и визуализации. Большинство функций PyZX будут реализованы в ZXCalculus.jl. Кроме того, мы интегрируем ZXCalculus.jl в квантовый компилятор YaoLang.jl и реализуем механизм упрощения схем на уровне компиляции.

В YaoLang.jl можно определить гибридные квантовые программы с классической информацией (например, классические параметры, классические потоки управления). Эти квантовые программы будут преобразованы в промежуточное представление (Yao IR), которое содержит квантовые схемы наряду с формой SSA (Статическая форма единого назначения) классической программы. Эти схемы будут упрощены с помощью ZXCalculus.jl. Затем YaoIR будет скомпилирован в бэкенд-инструкции, такие как QASM или инструкции симулятора Yao.

Для достижения наилучшей производительности при компиляции и обеспечения возможности дальнейшей настройки процедуры упрощения необходима чистая реализация ZX-исчисления на языке Julia.

Методы

Метод извлечения схем является каноническим методом алгоритмов упрощения схем на основе ZX-исчисления. Я тут буду в основном обсуждать его реализую.

Структуры данных

Для реализации этих алгоритмов нам необходимо реализовать структуры данных для хранения ZX-диаграмм и правила изменения ZX-диаграмм. ZX-диаграмму можно рассматривать как мультиграф с дополнительной информацией о его вершинах. Каждая вершина может быть представлена чем-то из Z-пауков, X-пауков или H-коробок. В исходных ZX-диаграммах допускаются открытые ребра. Для простоты мы добавили 2 специальных вида вершин, входную границу и выходную границу для записи этих ребер. Мы используем представление списка смежности для хранения мультиграфов. Список смежности хранится в виде "Dict", ключами которого являются идентификаторы вершин.

struct Multigraph{T<:Integer} <: AbstractMultigraph{T}    adjlist::Dict{T, Vector{T}}end

Поскольку нам нужно переписать мультиграфы с помощью правил ZX-исчисления, будет удобнее фиксировать идентификаторы вершин. Поэтому мы используем Dict вместо Array. Еще бывают фазы для Z- и X-пауков. Нам нужен еще один словарь для хранения этих фаз. Структура данных ZX-диаграммы аналогична следующей:

struct ZXDiagram{T<:Integer, P} <: AbstractZXDiagram{T, P}    mg::Multigraph{T}    st::Dict{T, SpiderType.SType}    ps::Dict{T, P}    ...end

В статье предложены графоподобные ZX-диаграммы. Они включают в себя только Z-пауков и имеют разные типы граней: адамаровские и неадамаровские. Мы также можем использовать мультиграфы для представления графоподобных ZX-диаграмм и различные кратности ребер для представления различных типов ребер. Мы определяем ZXGraph для графоподобных ZX-диаграмм так:

struct ZXGraph{T<:Integer, P} <: AbstractZXDiagram{T, P}    mg::Multigraph{T}    st::Dict{T, SpiderType.SType}    ps::Dict{T, P}    ...end

С этого момента мы создали структуры данных, которые нам нужны.

Правила преобразований

Чтобы упростить ZX-диаграммы, нам нужно реализовать правила перезаписи в ZX-исчислении. Существует два шага: сопоставление правил и переписывание ZX-диаграмм с соответствующими правилами. Мы использовали для этого благословенную джулианскую множественную диспетчеризацию. API-интерфейсы выглядят как-то так:

match(r::AbstractRule, zxd::AbstractZXDiagram)rewrite!(r::AbstractRule, zxd::AbstractZXDiagram{T, P}, matches::Vector{Match{T}}) where {T, P}

Здесь match вернет все совпадающие вершины, которые будут сохранены в структуре

struct Match{T<:Integer}    vertices::Vector{T}end

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

check_rule(r::AbstractRule, zxd::AbstractZXDiagram{T, P}, vs::Vector{T}) where {T, P}

Для упрощения ZX-диаграммы с помощью правила мы определили simplify! так:

function simplify!(r::AbstractRule, zxd::ZXDiagram)    matches = match(r, zxd)    while length(matches) > 0        rewrite!(r, zxd, matches)        matches = match(r, zxd)    end    return zxdend

На этапе упрощения [3], мы должны конвертировать ZX-диаграмму в графоподобный вариант с правилами i1, i2, h, и f. После, упрощаем графоподобную ZX-диаграмму локальным дополнительным правилом и правилом замещения. Мы можем выполнить эти шаги с помощью вышеуказанных функций. Упрощенные графоподобные ZX-диаграммы будут просто маленькими скелетами по сравнению с первоначально большой схемой. Единственное, что остается это извлечение схем из ZX-диаграмм.

Извлечение схем

Это самая сложная часть схемы упрощения. Для получения более подробной информации можно прочитать оригинал статьи. Я только кратко объясню алгоритм извлечения схемы.

Существует особенность для любой ZX-диаграммы квантовой схемы. Мы можем определить на ней g-поток. С помощью g-потока мы можем узнать порядок всех пауков. Правила, которые мы использовали для упрощения ZX-диаграммы, сохранят это хорошее свойство. Это дает нам возможность извлекать схемы из упрощенных ZX-диаграмм.

Кроме того, любая графоподобная ZX-диаграмма локально представима по CNOT + H. Мы можем извлечь эти схемы CNOT с гауссовским устранением над $F_2$. Вместе с остальными H-, CZ-гейтами и Z-вращениями мы получаем схему, эквивалентную исходной.

Demo

Демонстрационная схема взята из приложения к статье [3]. Все коды можно найти в разделе examples\ex1.jl у ZXCalculus.jl.

# this is the original circuit.zxd = generate_example()ZXplot(zxd)

# convert a ZX-diagram to a graph-like ZXdiagramzxg = ZXGraph(zxd)ZXplot(zxg, linetype = "curve")

# simplify with local complementary rule simplify!(Rule{:lc}(), zxg)ZXplot(zxg, linetype = "curve")

# simplify with pivoting rulesimplify!(Rule{:p1}(), zxg)ZXplot(zxg, linetype = "curve")

# removing all Paulis adjancent to boundariesreplace!(Rule{:pab}(), zxg)ZXplot(zxg, linetype = "curve")

# extract circuitcir = circuit_extraction(zxg)ZXplot(cir)

Наконец, мы получили упрощенную схему.

• [1]: "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• [2]: Exact Non-identity check is NQP-complete
• [3]: Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• [4]: Reducing T-count with the ZX-calculus

Метапрограммирование, квантовая компиляция и оптимизация схем при квантовой компиляции

В прошлом месяце я в основном работал над интеграцией с YaoLang.jl для ZXCalculus.jl. Это был мой первый опыт работы с метапрограммированием Джулии на практике. Я хочу поблагодарить своего наставника Роджера Ло за то, что он научил меня основным понятиям и полезным методам метапрограммирования.

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

Как Julia работает

Все коды Джулии по сути строки (Strings), которые хранятся на диске. Когда мы запускаем коды Julia, Джулия сначала разбирает этот код на AST (абстрактные синтаксические деревья). AST будет храниться в виде выражений в структуре данных Expr в Julia. На этом уровне синтаксического анализа мы называем эти выражения IR (промежуточные представления) поверхностного уровня.

julia> s = "1 + 1 * 2""1 + 1 * 2"julia> ex = Meta.parse(s):(1 + 1 * 2)julia> dump(ex)Expr  head: Symbol call  args: Array{Any}((3,))    1: Symbol +    2: Int64 1    3: Expr      head: Symbol call      args: Array{Any}((3,))        1: Symbol *        2: Int64 1        3: Int64 2

В этом примере ex это AST. Его head это :call, что означает, что это вызов функции. Он вызывает функцию + с аргументами 1 и еще одним Expr.

Затем опускаемся на уровень. На этом уровне макросы будут расширены, а "синтаксический сахар" Джулии будет преобразован в вызовы функций. Например, a[i] будет заменено на getindex(a, i). После серии преобразований, IR поверхностного уровня будет преобразован в SSA (Статическая форма единого назначения). IR также называется "пониженным" IR. В SSA IR каждая переменная может быть назначена только один раз. В Julia мы можем использовать макрос @code_lowed, чтобы увидеть SSA IR объекта Expr:

julia> @code_lowered 2 + 3CodeInfo(1  %1 = Base.add_int(x, y)      return %1)

Джулия сделает вывод типа на SSA IR и оптимизирует его. А затем преобразует его в LLVM коды. Мы можем использовать макросы @code_typed и @code_llvm, чтобы увидеть эти IRs.

julia> @code_typed 2 + 3CodeInfo(1  %1 = Base.add_int(x, y)::Int64      return %1) => Int64julia> @code_llvm 2 + 3;  @ int.jl:53 within '+'; Function Attrs: uwtabledefine i64 @"julia_+_15307"(i64, i64) #0 {top:  %2 = add i64 %1, %0  ret i64 %2}

Наконец, LLVM преобразует эти коды в собственные машинные коды.

julia> @code_native 2 + 3        .text;  @ int.jl:53 within '+'        pushq   %rbp        movq    %rsp, %rbp        leaq    (%rcx,%rdx), %rax        popq    %rbp        retq        nopw    (%rax,%rax); 

Вот пикча из JuliaCon 2018, которая демонстрирует, как работает компилятор Julia.

Как работает YaoLang.jl

Цель YaoLang.jl построить удобный квантовый компилятор для гибридных квантово-классических программ в Julia. То есть, используя только несколько макросов и добавляя их к собственным функциям Julia, можно определить квантовые программы. В YaoLang.jl функция, украшенная макросом device, будет рассматриваться как функция с квантовыми операциями. В этих функциях макросы @ctrl, @measure, @expect и "синтаксический сахар" locs => gate доступны для определения квантовых операций. Например, представим схему для квантового преобразования Фурье n кубитов:

@device function qft(n::Int)    1 => H    for k in 2:n        @ctrl k 1 => shift(2 / 2^k)    end    if n > 1        2:n => qft(n - 1)    endend

Подобно процедурам компиляции Julia, макрос device будет анализировать функцию в IR поверхностного уровня в YaoLang.jl. Затем все макросы и синтаксический сахар для квантовых операторов будут заменены вызовами функций. Эти вызовы функций будут помечены меткой :quantum. Теперь IR поверхностного уровня будет преобразован в пониженный SSA IR. В YaoLang.jl SSA IR будет храниться в структуре данных YaoIR.

Остальные части это оптимизация YaoIR и преобразование из него в коды аппаратного уровня. ZXCalculus.jl предназначен для оптимизации квантовых схем и должен быть интегрирован на уровне оптимизации.

Интеграция ZXCalculus.jl

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

1. преобразовать его в ZX-диаграмму
2. Упростить ZX-диаграмму
3. Перевести упрощенную ZX-диаграмму обратно в YaoIR

Второй шаг уже реализован в ZXCalculus.jl. Нам нужно только реализовать преобразование между ZXDiagram и YaoIR.

YaoIR в ZXDiagram

Поскольку каждый YaoIR является SSA, мы можем просмотреть все утверждения, чтобы получить информацию о вентилях и их местоположениях. Для этого окинем взором самую обширную локацию по числу кубитов. Чтобы построить соответствующую ZX-диаграмму, построим пустую схему и последовательно протолкнем в нее гейты при обходе YaoIR. А код такой:

function ZXDiagram(ir::YaoIR)    if ir.pure_quantum        n = count_nqubits(ir)        circ = ZXDiagram(n)        stmts = ir.body.blocks[].stmts        for stmt in stmts            # push gates        end        return circ    endend

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

ZXDiagram в YaoIR

Мы предполагаем, что получаем ZXDiagram, представляющую квантовую схему. Чтобы преобразовать ее в YaoIR, нам нужно извлечь последовательность квантовых вентилей в ZXDiagram.

Их можно выудить из информации о расположении ZXDiagram. Так мы узнаем, как пауки сортируются от входа к выходу и высмотрим расположение кубитов для каждого паука. Если паук имеет степень 2, он представляет собой однокубитовый гейт. В противном случае он представляет собой вентиль с несколькими кубитами. Пройдя всех пауков от входа к выходу, мы можем получить последовательность квантовых вентилей. И тогда мы сможем построить новый YaoIR с этой последовательностью.

Параметры оптимизации

В "ZXCalculus.jl" существует несколько методов упрощения схем. И мы предлагаем реализовать другие методы упрощения, которые не основаны на ZX-исчислении. Необходимо предоставить пользователю возможность выбирать, какие методы оптимизации будут применяться.

Мы добавили эти параметры в макрос @device. Параметры оптимизации можно задать следующим образом

@device optimizer = [opt...] function my_circuit(args...)    ...end

Так optimizer вполне представим как подмножество [:zx_clifford, zx_teleport]. И мы добавим больше методов в будущем.

Примеры

К настоящему времени, ZXCalculus.jl была интегрирована с YaoLang.jl. Мы можем использовать YaoLang.jl для проверки правильности алгоритмов в ZXCalculus.jl. Данный пример представляет собой арифметическую схему.

Сначала мы определим два контура. Один оригинальная схема, другой оптимизированная.

using YaoLang@device function test_cir()    5 => H    5 => shift(0.0)    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    5 => shift($(1/4*))    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    4 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 1 4 => X    4 => shift($(7/4*))    1 => shift($(1/4*))    @ctrl 1 4 => X    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 3 5 => X    5 => shift($(1/4*))    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 3 5 => X    4 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 3 4 => X    4 => shift($(7/4*))    5 => H    3 => shift($(1/4*))    @ctrl 3 4 => X    5 => shift(0.0)    @ctrl 4 5 => X    5 => H    5 => shift(0.0)    @ctrl 3 5 => X    5 => shift($(7/4*))    @ctrl 2 5 => X    5 => shift($(1/4*))    @ctrl 3 5 => X    5 => shift($(7/4*))    @ctrl 2 5 => X    3 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 2 3 => X    3 => shift($(7/4*))    5 => H    2 => shift($(1/4*))    @ctrl 2 3 => X    5 => shift(0.0)    @ctrl 3 5 => X    5 => H    5 => shift(0.0)    @ctrl 2 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    5 => shift($(1/4*))    @ctrl 2 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    2 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 1 2 => X    2 => shift($(7/4*))    5 => H    1 => shift($(1/4*))    @ctrl 1 2 => X    5 => shift(0.0)    @ctrl 2 5 => X    @ctrl 1 5 => Xendcir = test_cir()@device optimizer = [:zx_teleport] function teleport_cir()    5 => H    5 => shift(0.0)    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    5 => shift($(1/4*))    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    4 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 1 4 => X    4 => shift($(7/4*))    1 => shift($(1/4*))    @ctrl 1 4 => X    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 3 5 => X    5 => shift($(1/4*))    @ctrl 4 5 => X    5 => shift($(7/4*))    @ctrl 3 5 => X    4 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 3 4 => X    4 => shift($(7/4*))    5 => H    3 => shift($(1/4*))    @ctrl 3 4 => X    5 => shift(0.0)    @ctrl 4 5 => X    5 => H    5 => shift(0.0)    @ctrl 3 5 => X    5 => shift($(7/4*))    @ctrl 2 5 => X    5 => shift($(1/4*))    @ctrl 3 5 => X    5 => shift($(7/4*))    @ctrl 2 5 => X    3 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 2 3 => X    3 => shift($(7/4*))    5 => H    2 => shift($(1/4*))    @ctrl 2 3 => X    5 => shift(0.0)    @ctrl 3 5 => X    5 => H    5 => shift(0.0)    @ctrl 2 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    5 => shift($(1/4*))    @ctrl 2 5 => X    5 => shift($(7/4*))    @ctrl 1 5 => X    2 => shift($(1/4*))    5 => shift($(1/4*))    @ctrl 1 2 => X    2 => shift($(7/4*))    5 => H    1 => shift($(1/4*))    @ctrl 1 2 => X    5 => shift(0.0)    @ctrl 2 5 => X    @ctrl 1 5 => Xendtp_cir = teleport_cir()

С помощью пакета YaoArrayRegister.jl, мы можем вычислить матрицу для каждой схемы.

using YaoArrayRegistermat = zeros(ComplexF64, 32, 32)for i = 1:32    st = zeros(ComplexF64, 32)    st[i] = 1    r0 = ArrayReg(st)    r0 |> cir    mat[:,i] = r0.stateendtp_mat = zeros(ComplexF64, 32, 32)for i = 1:32    st = zeros(ComplexF64, 32)    st[i] = 1    r1 = ArrayReg(st)    r1 |> tp_cir    tp_mat[:,i] = r1.stateend

Сравнивая эти две матрицы, мы видим, что они идентичны. Следовательно, алгоритм возвращает эквивалентную упрощенную схему.

sum(abs.(mat - tp_mat) .> 1e-14) == 0

Итого

Во время второго этапа кодирования я реализовал преобразование между "ZXDiagram" и "YaoIR", что обеспечивает интеграцию ZXCalculus".jl с YaoLang.jl. Кроме того, документация теперь доступна здесь. И во время испытания ZXCalculus".jl с помощью YaoLang.jl и YaoArrayRegister.jl я нашел несколько ошибок в реализации извлечения контуров и фазовой телепортации. Эти ошибки уже исправлены.

На следующем этапе я буду работать над компиляцией кодов OpenQASM в коды YaoIR. Это позволит нам читать схемы из кода OpenQASM. А также протестирую результативность ZXCalculus.jl на некоторых эталонных схемах и сравню его с PyZX.

Упрощение квантовой схемы

Предположим, что у нас есть квантовая схема с 24 гейтами, как описано выше. Мы можем определить эту схему с помощью YaoLang.jl используя макрос @device. YaoLang.jl это компилятор для гибридных квантово-классических программ, которые очень практичны в нынешнюю эпоху NISQ (noisy intermediate-scale quantum). Кроме того, YaoLang.jl интегрирован с ZXCalculus.jl.

julia> using YaoLang;julia> @device optimizer = [:zx_teleport] function demo_circ_simp()           1 => shift($(7/4))           1 => H           1 => Rx($(/4))           4 => H           @ctrl 1 4 => Z           @ctrl 4 1 => X           1 => H           4 => H           1 => T           4 => shift($(3/2))           4 => X           1 => H           4 => S           4 => X           2 => S           @ctrl 2 3 => X           2 => H           @ctrl 2 3 => X           2 => T           3 => S           2 => H           3 => H           3 => S           @ctrl 2 3 => X       enddemo_circ_simp (generic circuit with 1 methods)

Можно добавить аргумент optimizer = [opts...] в макрос @device, чтобы упростить эту схему во время компиляции. В настоящее время существует только два этапа оптимизации: :zx_clifford для упрощения Клиффорда [1] и :zx_teleport для фазовой телепортации [2]. Например, с помощью optimizer = [:zx_teleport] компилятор вызовет алгоритм фазовой телепортации в ZXCalculus.jl для упрощения схемы.

Мы можем использовать макрос @code_yao, чтобы увидеть, какая схема у нас есть. В этом примере количество гейтов схемы было уменьшено с 24 до 20.

julia> using YaoLang.Compilerjulia> gate_count(demo_circ_simp)Dict{Any,Any} with 8 entries:  "YaoLang.Rx(3.141592653589793)"     => 2  "YaoLang.H"                         => 6  "YaoLang.Rx(0.7853981633974483)"    => 1  "YaoLang.shift(4.71238898038469)"   => 1  "YaoLang.shift(1.5707963267948966)" => 4  "YaoLang.shift(0.7853981633974483)" => 1  "@ctrl YaoLang.Z"                   => 1  "@ctrl YaoLang.X"                   => 4

Мы можем использовать YaoArrayRegister.jl чтобы применить эту упрощенную схему к квантовому состоянию:

julia> using YaoArrayRegister;julia> circ_teleport = demo_circ_simp()demo_circ_simp (quantum circuit)julia> r = rand_state(4);julia> r |> circ_teleportArrayReg{1, Complex{Float64}, Array...}    active qubits: 4/4

Можно также загрузить схемы из OpenQASM. OpenQASM это квантовая инструкция. Коды OpenQASM можно запускать на квантовых устройствах IBM. А квантовые схемы могут храниться в виде кодов OpenQASM. Я использовал пакет Джулии RBNF.jl (парсит код в ограниченную форму Бэкуса-Наура) для перевода OpenQASM кодов в AST, с последующим преобразованием его в YaoIR, промежуточное представление для смешанной квантово-классической программы YaoLang.jl. Это делает возможным чтение схем из OpenQASM в ZXCalculus.jl через YaoLang.jl.

using YaoLang: YaoIR, is_pure_quantumusing ZXCalculuslines = readlines("gf2^8_mult.qasm")src = prod([lines[1]; lines[3:end]])ir = YaoIR(@__MODULE__, src, :qasm_circ)ir.pure_quantum = is_pure_quantum(ir)circ = ZXDiagram(ir)pt_circ = phase_teleportation(circ)

Здесь мы загрузили схему в виде ZXDiagram из файла .qasm, который можно найти тут. И мы использовали алгоритм фазовой телепортации, чтобы упростить его. Мы видим, что Т-число в цепи уменьшилось с 448 до 264.

julia> tcount(circ)448julia> tcount(pt_circ)264

Приведенные выше примеры показали, как ZXCalculus.jl работает в качестве механизма упрощения схем в YaoLang.jl. А теперь давайте посмотрим, что скрывается за сценой.

Низкоуровневые интерфейсы ZXCalculus

В ZX-исчислении мы будем иметь дело с ZX-диаграммами и мультиграфами с некоторой дополнительной информацией. Каждая вершина ZX-диаграммы называется пауком. Есть два типа пауков, Z-паук и X-паук. Каждый паук связан с числом, называемым фазой. По нотации Дирака Z-паук и X-паук представляют собой следующие матрицы ранга 2.

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

Желтая коробка, H-box, это простая нотация следующих пауков в ZX-исчислении

Для представления общих ZX-диаграмм мы определили структуру ZXDiagram в ZXCalculus.jl. Мы можем построить ZX-диаграмму, которая представляет собой пустую квантовую схему с n кубитами с помощью ZXDiagram(n). Например, если мы хотим упростить приведенную выше схему с помощью ZXCalculus.jl вручную, то сначала мы построим ZX-диаграмму схемы из 4 кубитов.

using ZXCalculuszxd = ZXDiagram(4)

Затем мы добавляем некоторые элементы к ZX-диаграмме, которую мы только что построили. Просто используем push_gate! и push_ctrl_gate!

push_gate!(zxd, Val(:Z), 1, 7//4)push_gate!(zxd, Val(:H), 1)push_gate!(zxd, Val(:X), 1, 1//4)push_gate!(zxd, Val(:H), 4)push_ctrl_gate!(zxd, Val(:CZ), 4, 1)push_ctrl_gate!(zxd, Val(:CNOT), 1, 4)push_gate!(zxd, Val(:H), 1)push_gate!(zxd, Val(:H), 4)push_gate!(zxd, Val(:Z), 1, 1//4)push_gate!(zxd, Val(:Z), 4, 3//2)push_gate!(zxd, Val(:X), 4, 1//1)push_gate!(zxd, Val(:H), 1)push_gate!(zxd, Val(:Z), 4, 1//2)push_gate!(zxd, Val(:X), 4, 1//1)push_gate!(zxd, Val(:Z), 2, 1//2)push_ctrl_gate!(zxd, Val(:CNOT), 3, 2)push_gate!(zxd, Val(:H), 2)push_ctrl_gate!(zxd, Val(:CNOT), 3, 2)push_gate!(zxd, Val(:Z), 2, 1//4)push_gate!(zxd, Val(:Z), 3, 1//2)push_gate!(zxd, Val(:H), 2)push_gate!(zxd, Val(:H), 3)push_gate!(zxd, Val(:Z), 3, 1//2)push_ctrl_gate!(zxd, Val(:CNOT), 3, 2)

Теперь давайте нарисуем ZX-диаграмму, которую мы построили. Инструмент визуализации ZXCalculus.jl в настоящее время предоставляется в YaoPlots.jl.

using YaoPlotsplot(zxd)

Заодно поднимем алгоритмы упрощения clifford_simplification [1] и phase_teleportation [2]

ex_zxd = clifford_simplification(zxd);pt_zxd = phase_teleportation(zxd);plot(ex_zxd)plot(pt_zxd)

Схема после упрощения Клиффорда

Схема после фазовой телепортации

Алгоритм фазовой телепортации может уменьшить число Т-вентилей квантовой схемы. Воспользуемся tcount чтобы показать количество Т-вентилей. В этом примере число Т уменьшилось с 4 до 2.

julia> tcount(zxd)4julia> tcount(pt_zxd)2

Эти алгоритмы используют правила ZX-исчисления для упрощения ZX-диаграмм. Эти правила определяют, как ZX-диаграммы могут быть преобразованы. Вот некоторые основные правила для ZXDiagram.

В работе [1] определен особый тип ZX-диаграммы графоподобная ZX-диаграмма. Мы используем ZXGraph, чтобы представить ее в ZXCalculus.jl. И вот некоторые правила для ZXGraph

Можно применить правила на ZX-диаграмме вручную. Для этого мы предоставляем различные API.

Функция match найдет все вершины соответствующие заданному правилу. Применение rewrite! переписывает ZX-диаграмму на некоторых совпадающих вершинах. replace! функция просто сопоставляет и переписывает все совпадающие вершины один раз. simplify! функция будет сопоставлять и переписывать ZX-диаграмму с правилом до тех пор, пока не останется сопоставимых вершин.

В clifford_simplification, мы сначала преобразуем заданную ZX-диаграмму в графоподобную ZX-диаграмму

zxg = ZXGraph(zxd)plot(zxg)

Затем, мы упрощаем ее с помощью правил :lc, :p1, и :pab

simplify!(Rule{:lc}(), zxg)simplify!(Rule{:p1}(), zxg)replace!(Rule{:pab}(), zxg)plot(zxg)

Наконец, мы извлекаем новую схему из упрощенной графоподобной ZX-диаграммы

ex_circ = circuit_extraction(zxg)plot(ex_circ)

Почему именно ZXCalculus.jl?

Вышеприведенные алгоритмы уже реализованы в пакете Python PyZX. PyZX это полнофункциональная библиотека для манипулирования крупномасштабными квантовыми схемами и ZX-диаграммами. Он предоставляет множество удивительных возможностей визуализации и поддерживает различные формы квантовых схем, включая QASM, Quipper и Quantomatic.

Так почему же мы разработали ZXCalculus.jl? Это связано с тем, что ZXCalculus.jl является не только полнофункциональной библиотекой для ZX-исчисления, но и одним из механизмов упрощения схем для YaoLang.jl. Легкая нативная реализация ZX-исчисления необходима, так как зависимость от пакета Python сделает работу компилятора медленнее и сложнее.

Benchmarks

Мы провели сравнительный анализ алгоритма фазовой телепортации на 40 схемах с различным числом вентилей (от 57 до 91642). ZXCalculus.jl имеет ускорение от 6 до 50 раз в этих примерах (время выполнения ZXCalculus.jl масштабируется до 1 для каждой схемы на этом рисунке). Эти тесты выполняются на ноутбуке с процессором Intel i7-10710U и 16 ГБ оперативной памяти. Код для бенчмарков можно найти здесь.

В большинстве примеров T-число оптимизированных схем, производимых ZXCalculus.jl, совпадает с PyZX. Однако в 2 примерах ZXCalculus.jl имеет больше T-count, чем PyZX. Это может быть вызвано различными стратегиями упрощения между ZXCalculus.jl и PyZX. Мы продолжим исследовать это в будущем.

Кроме того, YaoLang.jl поддерживает гибридные квантово-классические программы. Можно оптимизировать гибридные квантово-классические программы с помощью ZXCalculus.jl.

Резюме и дальнейшей работы

В течение GSoC 2020 я в основном выполнил следующие работы.

• Представление и манипулирование ZX-диаграммами с высокой производительностью.
• Реализация двух алгоритмов упрощения на основе ZX-исчисления.
• Добавление визуализации в ZX-схемы в YaoPlots.jl.
• Интеграция ZXCalculus.jl с YaoLang.jl.
• Добавление поддержки OpenQASM в YaoLang.jl.

Есть еще кое-что, что нужно отполировать.

• Поиск лучшей стратегии упрощения, чтобы получить более низкие значения T.
• Полная поддержка визуализации "ZXGraph" (сценарий построения графика может потерпеть неудачу на некоторых "ZXGraph" с фазовыми гаджетами).
• Преобразование на ZX-схемы для тензорных сетей без YaoLang.jl.
• Преобразование между "YaoIR" и "ZXDiagram" может привести к тому, что схема отличается от глобальной фазы. Мы должны записать эту глобальную фазу в более поздней версии.

Кроме того, я буду продолжать работать над YaoLang.jl с Роджером Ло, Чтобы поддерживать больше методов упрощения схем (методы сопоставления шаблонов, методы на основе Quon и т.д.).

Благодарности

Я хочу поблагодарить своих наставников, Роджера Ло и Цзиньго Лю. Без их помощи я не смог бы осуществить этот проект. ZXCalculus.jl очень вдохновлен PyZX. Спасибо Алекс Киссинджер и Джон ван де Ветеринг, авторам PyZX. Они дали мне полезные советы по алгоритму фазовой телепортации и рассмотрели бенчмарки между PyZX и ZXCalculus.jl. Благодарю Google за проведение Google Summer of Code, которое способствует развитию сообщества с открытым исходным кодом.

[1]: Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
[2]: Reducing T-count with the ZX-calculus

Квантовые вычисления

Основы квантовых вычислений

Квантовые первопроходцы

IBM

Google

Alibaba

Microsoft

Intel

D-Wave Systems

Rigetti

Quantum Circuits

IonQ

Xanadu

Honeywell

Amazon

Разработчики программного обеспечения для квантовых компьютеров

1QBit

CQC

QC Ware

QSimulate

Rahko

Zapata

Пользователи приложений квантовых компьютеров

Квантовое будущее

• Кевин Хартнет Рассвет квантовых вычислений, Quanta Magazine, 18 июня 2019 г.
• Статья Масуд Мохсени 2017 года Коммерциализация ранних квантовых технологий
• Статья Джона Прескилла Квантовые вычисления в эпоху NISQ и за её пределами от 2018 года
• Сайт IonQ Technology
• Видео D-Wave Systems, объясняющее квантовый отжиг
• Сайт IBM-Q
• Сайт квантовых вычислений Microsoft
• Сайт Google Quantum AI
• Новостной блог Intel Quantum Computing
• Сайт D-Wave Systems
• Сайт Quantum Circuits
• Сайт HQS Quantum Simulations

Познакомьтесь с квантовым пьяницей

Начните программировать квантовые компьютеры

На Хабре практически нет информации про квантовое машинное обучение (Quantum Machine Learning), и в этой статье я постараюсь подробнее раскрыть тему. Сразу скажу, что промышленных квантовых компьютеров сегодня не существует, все основные разработки в этой области носят теоретический характер, а задачу, которую мы будем разбирать в статье можно решить по классике за доли секунд. Но ведь еще 30 лет назад была так называемая зима искусственного интеллекта, а сегодня нейронные сети буквально окружают нас. Кто знает, может быть вскоре и квантовые компьютеры станут неотъемлемой частью нашей жизни? К тому же область квантовых вычислений, а тем более область QML, обладает особой притягательностью и таинственностью и, как минимум, стоит быть замеченной.

В статье я постарался рассказать о QML в целом, а также об основном строительном блоке QML Variational Quantum Circuit. Большую часть статьи я постарался сделать практической, c примерами кода на Cirq, а в конце добавил реализацию одного из базовых алгоритмов QML на Tensorflow Quantum.

Введение

Гипотетически QML имеет ряд существенных преимуществ, по сравнению с классическим машинным обучением. Variational Quantum Circuit, или VQC, которые можно назвать аналогом классических полносвязных слоев в обычных нейронных сетях, являются более выразительными и при этом содержат меньше обучаемых параметров. Ряд квантовых алгоритмов потенциально также дает существенное ускорение по сравнению с обычными аналогами:

Метод	Ускорение
Bayesian Inference
Online Perceptron
Least Square Fitting
Classical Boltzman Machine
Quantum Boltzman Machine
Quantum PCA
Quantum SVM
Quantum RL

Для наиболее полного ознакомления с темой я рекомендую обзор 2017-го года в журнале Nature или препринт той же работы в arXiv. Именно из этой работы я взял данную таблицу. В ней указано ускорение по сравнению с классическим аналогом. Так, подразумевает, что квантовый алгоритм квадратично быстрее, чем его классический аналог, а означает экспоненциальное ускорение.

Основа QML

Как я уже говорил, основной строительный блок в QML это Variational Quantum Circuit. Их мы детально рассмотрим чуть позже, но в целом любая статья или любой новый алгоритм по QML будет так или иначе содержать набор VQC или их вариаций. Такие блоки не являются чисто квантовыми схемами, и в этом они сильно отличаются, например, от широко известных квантовых алгоритмов Шора или Гровера. В основном QML строится по гибридной схеме, когда у нас есть параметризованные квантовые схемы, такие как VQC, и они составляют собой квантовую часть. Классическая часть обычно отвечает за оптимизацию параметров квантовых схем, например, градиентными методами, так, чтобы VQC, подобно слоям нейронных сетей, выучивали нужные нам преобразования входных данных. Именно так построена библиотека Tensorflow Quantum, где квантовые слои сочетаются с классическими, а обучение происходит как в обычных нейронных сетях.

Variational Quantum Circuit

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

Вот так выглядит простейшая VQS, где вектор кодируется через вращения кубитов вокруг оси , а параметры кодируют вращения вокруг оси :

Разберем этот момент подробнее. Мы хотим закодировать входной вектор данных в состояние , по сути своей, выполнить операцию перевода классических входных данных в квантовые. Для этого мы берем кубитов, каждый из которых исходно находится в состоянии . Состояние каждого отдельного кубита мы можем представить как точку на поверхности сферы Блоха:

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

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

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

В библиотеке для квантовых вычислений Cirq от компании Google, которой мы будем активно пользоваться, это можно реализовать, например, так:

import cirqimport sympyqubits = cirq.LineQubit.range(10)x = sympy.symbols("x0:10")thetas = sympy.symbols("t0:10")circuit = cirq.Circuit()for i in range(10):    circuit.append(cirq.rx(x[i])(qubits[i]))    circuit.append(cirq.ry(thetas[i])(qubits[i]))

Таким образом, мы получаем квантовую ячейку circuit, которая параметризируется классическими параметрами и применяет преобразование к классическому входному вектору. Именно на таких блоках и строятся алгоритмы квантово-классического обучения. Мы будем применять преобразования к классическим данным на квантовом компьютере (или симуляторе), измерять выход нашей VQC и далее использовать классические градиентные методы для обновления параметров VQC.

Variational Quantum Eigensolver

Основой многих алгоритмов квантового машинного обучения является Harrow-Hasssidim-Loloyd алгоритм (есть препринт в arXiv) для поиска решения систем линейных уравнений. Именно на основе этого алгоритма построен, например, квантовый SVM наиболее известный и многообещающий алгоритм QML. Однако HHL достаточно сложный и начинать рассказ с него было бы странно. Вместо этого, далее, мы посмотрим как устроен другой алгоритм Variational Quantum Eigensolver, алгоритм поиска минимальных собственных значений эрмитовых матриц, который лежит в основе HHL.

Почему именно проблема собственных значений? Ответ прост:

• поиск минимальных собственных значений эрмитовых операторов важная задача физики, именно для нее Р. Фейнман впервые предложил модель квантового компьютера;
• Variational Quantum Eigensolver является ключевой частью HHL-алгоритма, итерация HHL сводится к задаче о собственных значениях;
• Сам алгоритм достаточно прост как для понимания, так и для реализации.

Опишем задачу формально.

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

Для решения этой задачи мы воспользуемся так называемой Вариационной теоремой (Variational theorem), которая для оператора дает нам следующее:

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

1. Готовим состояние , параметризованное вектором параметров
2. Измеряем ожидаемое значение оператора в этом состоянии
3. Оцениваем градиент , ожидаемого значения по весам
4. Обновляем вектор :

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

Надеюсь, больше понимания станет, когда мы посмотрим, как это выглядит в коде.

Реализация на Tensorflow Quantum

Для начала краткие обозначения импортов:

import tensorflow as tfimport tensorflow-quantum as tfq

Tensorflow Quantum специальная библиотека, которая позволяет использовать схемы Cirq как тензоры Tensorflow, а также содержит специализированные варианты tf.keras.Layers для квантово-классического обучения. Библиотека совместима со стилем и другими слоями tf и позволяет задействовать систему автоматического диффиренцирования Tensorflow. Одним из таких tfq.layers мы и воспользуемся это tfq.layers.SampledExpectation.

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

Сигнатура и описание слоя tfq.layers.SampledExpectation

layer = tfq.layers.SampledExpectation()res = layer(    circuit,    symbol_names,    symbol_values,    operators,    repetitions,)

• cicuit схема (cirq.Circuit), параметризирующая состояние
• symbol_names символы sympy, которые параметризируют состояние
• symbol_values значения символов-параметров (обычно tf.Variable)
• operators операторы (например, cirq.PauliSum)
• repetitions число измерений, по которым оценивается значение оператора

Этот слой явно реализует нам для оператора оценку значения оператора в конкретном состоянии по определенному числу измерений:

А параметры в формуле связаны с сигнатурой метода call следующим образом:

Формула	Сигнатура tfq.layers.SampledExpectation.call
	symbol_values значения параметров
	circuit квантовая схема готовит нам состояние
	symbol_names связь параметры схемы с symbol_values
	operators оператор, например cirq.PauliSum

Параметр repetition не имеет прямой связи с математическим формализмом, но именно он показывает нам насколько хорошо мы оцениваем значение оператора.

Но перед началом всего обучения необходимо решить, как именно мы будем параметризовать состояние. В вышеописанных терминах нам надо определить , который мы будем передавать в качестве параметра circuit в tfq.layers.SampledExpectation. В данном случае воспользуемся более сложной параметризацией, где на каждый спин у нас будет три параметра: , а не один:

qubits = cirq.GridQubit.rect(dim, 1)params_x = sympy.symbols(f"x0:{dim}")params_y = sympy.symbols(f"y0:{dim}")params_z = sympy.symbols(f"z0:{dim}")cirquit = cirq.Circuit()for i in range(dim):    cirquit.append(cirq.rx(params_x[i])(qubits[i]))    cirquit.append(cirq.ry(params_y[i])(qubits[i]))    cirquit.append(cirq.rz(params_z[i])(qubits[i]))

Выглядит наша схема так:

Для примера, найдем минимальное собственное значение оператора Transverse-field Ising, так называемой квантовой модели Изинга. Этот оператор строится применением операторов Паули (в нашем варианте это будут и ) и имеет два классических параметра . Параметры на самом деле имеют физический смысл, а сам оператор часто применяют для описания Гамильтонианов реальных физических систем, то есть это не просто абстрактная задача. Но сейчас аспекты физики нас интересуют в меньшей степени. На самом деле любой эрмитов оператор можно определить в терминах матриц Паули, так что выбрав Изинга мы не теряем общности рассуждений.

Это оператор размерности , где это число кубитов, на которое он действует. Так как квантовые симуляторы достаточно прожорливы, а доступ к реальным кубитам в Google Cloud Platform стоит денег, то не будем брать большую размерность . Сейчас нам интересно просто посмотреть, как оно работает, о каком-то превосходстве квантовых алгоритмов на реальных задачах речи не идет. Запишем реализацию этого оператора в коде Cirq.

def get_ising_operator(    qubits: List[cirq.GridQubit], j: float, h: float) -> cirq.PauliSum:    op = h * cirq.X(qubits[-1])    for i, _ in enumerate(qubits[:-1]):        op -= j * cirq.Z(qubits[i]) * cirq.Z(qubits[i + 1])        op += h * cirq.X(qubits[i])    return op

Хотелось бы еще раз обратить внимание на тот факт, что для кубитов оператор TFI это матрица размера (а не , как можно было бы подумать!) Чтобы убедится в этом, ниже, под спойлером, будет код определения такого же оператора на чистом NumPy в виде разреженной комплексной матрицы:

import numpy as npfrom scipy import sparsedef sigmaz_k(k, N) -> sparse.csr_matrix:    res = 1    for i in range(N):        if i == k:            res = sparse.kron(                res,                sparse.csr_matrix(                    np.array([[1, 0], [0, -1]], dtype=np.complex)                )            )        else:            res = sparse.kron(res, sparse.eye(2, dtype=np.complex))    return resdef sigmax_k(k, N) -> sparse.csr_matrix:    res = 1    for i in range(N):        if i == k:            res = sparse.kron(                res,                sparse.csr_matrix(                    np.array([[0, 1], [1, 0]], dtype=np.complex)                )            )        else:            res = sparse.kron(res, sparse.eye(2, dtype=np.complex))    return resdef tfi_op(N, j, h) -> sparse.csr_matrix:    res = sparse.csr_matrix((2 ** N, 2 ** N), dtype=np.complex)    for i in range(N - 1):        res += -j * sigmaz_k(i, N) * sigmaz_k(i + 1, N)        res += h * sigmax_k(i, N)    res += h * sigmax_k(N - 1, N)    return res

Как я уже писал, минимальное собственное значение этого оператора мы легко найдем классическими методами (например, алгоритм Арнольди) в пару строчек кода, используя готовые рутины:

from scipy import sparsefrom scipy.sparse import linalgexact_sol = linalg.eigs(    sparse.csc_matrix(op.matrix()), k=1, which="SR", return_eigenvectors=False)[0]print(f"Exact solution: {np.real(exact_sol):.4f}")

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

Ну и наконец самое интересное, код для обучения нашей VQC на Tensorflow Quantum.

# Операторop = get_ising_operator(qubits, j, h)# Модельmodel = tfq.layers.SampledExpectation()# Вектор обучаемых параметровthetas = tf.Variable(np.random.random((1, 3 * dim)), dtype=tf.float32)log_writer = tf.summary.create_file_writer("train")for epoch in tqdm(range(epochs)):    with tf.GradientTape() as gt:        out = model(            cirquit,            symbol_names=params_x + params_y + params_z,            symbol_values=thetas,            operators=op,            repetitions=5000,        )    grad = gt.gradient(out, thetas)    thetas.assign_sub(lr * grad)    with log_writer.as_default():        tf.summary.scalar("Eigen Val", out[0, 0], step=epoch)        tf.summary.histogram("Gradients", grad, step=epoch)

Это простейший стандартный цикл обучения в Tensorflow, а model это объект класса tf.keras.layers.Layer, для которого можно применять все наши привычные оптимизаторы, логгеры и приемы из классического глубокого обучения. Параметры VQC хранятся в переменной типа tf.Variable и обновляются по простому правилу , это минимальная реализация градиентного спуска со скоростью . Каждый раз мы используем 5000 измерений для максимально точной оценки ожидаемого значения нашего оператора в состояниии . Все это в течение 350 эпох. На моем ноутбуке для , и процесс занял порядка 40 секунд.

Визуализируем графики обучения (scipy дал точное решение ): tensoboard --logdir train/

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

Еще пара слов о потенциале такого Eigensolver-а

Несмотря на игрушечность примера с 5-ю кубитами, я бы хотел еще раз напомнить, что мы работаем с матрицей . Более того, в сравнении с классическими методами глубокого обучения, сама идея о том, что мы параметризуем преобразование при помощи всего лишь параметров (в нашем случае ровно ) выглядит очень перспективно. Для сравнения в классическом глубоком обучении такое преобразование кодировалось бы квадратной матрицей весов , то есть экспоненциально большим числом параметров. При этом в ряде работ было показано, что в сравнении с обычными полносвязными слоями нейронных сетей VQC даже более выразительны при столь меньшем числе параметров! Именно этим, как мне кажется, обусловлен такой живой интерес к этой области: если бы имели бы реальный квантовый компьютер, QML на основе таких VQC, вероятно, были бы гораздо круче классических нейронных сетей во многих задачах.

Заключение

Несомненно, сейчас не идет речи о каком-то реальном применении QML. Для сравнения наша VQC обучалась около 45 секунд на моем ноутбуке, а scipy.sparse.eigs потребовались доли секунд, чтобы найти минимальное собственное значение. К тому же, даже на симуляторе, где нет шума, оценка tfq.layers.SampledExpectation явно хромает, что уж говорить о реальных квантовых компьютерах. Но сейчас очень многие частные компании, такие как Google, IBM, Microsoft и другие, а также правительства и институты тратят огромные ресурсы на исследования в данном направлении. Квантовые компьютеры уже сегодня доступны для тестирования в облачных серверах IBM и AWS. Многие ученые высказывают уверенность в скором достижении квантового превосходства на практических задачах (напомню, превосходство на специально выбранной удобной для квантового компьютера задаче было достигнуто Google в прошлом году). Все это, а также таинственность и красота квантового мира, делает эту область такой привлекательной. Надеюсь, эта статья поможет и вам погрузиться в дивный квантовый мир!

Весь используемый код можно посмотреть в моем GitHub.

Проклятие детерминизма

Безвременный уход в миры Эверетта

Квантовый пулемет оружие смелых

Хрупкие шестеренки вселенной

Власть сознания над материей

Финал, которого не было

Концепция квантового объёма от IBM предлагает вынести измерение прогресса в квантовых вычислениях за пределы простого подсчёта кубитов