Квантовые алгоритмы

Продолжаем рубрику тем для первого свидания. На сегодняшней повестке дня упрощение схем для квантовых программ методами 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

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

Фрактальная геометрия природы Бенуа Мандельброт

1. Введение: Демон Лапласа и Бог Эйнштейна
2. Принцип неопределенности, татуировка и каллиграфия
3. Волны материи и их амплитуды
4. Комплексные числа и фаза вероятности
5. Реальный мир и мнимые единицы
6. Волновая функция и плотность вероятности
7. Квантовый шлагбаум декогеренции
8. Немного квантовой криптографии
9. Заключение

Введение: Демон Лапласа или Бог Эйнштейна

Принцип неопределенности, татуировка и каллиграфия

Слева: мастер каллиграфии рисует символ Энсо (яп. ,), источник. Справа: процесс нанесения татуировки на кожу человека, источник.

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

Вверху, слева на право: интерференционные картины получаемые при последовательном уменьшении щели, источник. Внизу: схема экспериментальной установки, источник.

Волны материи и их амплитуды

Дифракция прямого волнового фронта, проходящего через отверстие, источник.

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

Комплексные числа и фаза вероятности

Демонстрация принципа интерференции волн. Слева: конструктивная интерференция встреча пиков волн совпадающей фазе даёт более высокую результирующую амплитуду. Справа: деструктивная интерференция при встрече пиков волн в противоположной фазе. Источник.

Анимация последовательных преобразований, которые позволяют получить волновую функцию как сумму амплитуд вероятности в точках на пути частицы (зеленая линия), сначала задается вещественная часть амплитуды, а затем фаза (угол поворота) в комплексной плоскости. Источник.

Где: комплексно сопряженное число

Реальный мир из мнимых единиц

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

Код Python:

from numpy import *from matplotlib.pyplot import *from mpl_toolkits.axes_grid.axislines import SubplotZeromu, sigma = 0, 0.1x = np.arange(-1,1,0.02)y = 1/(sigma * np.sqrt(2 * np.pi))*np.exp( - (x - mu)**2 / (2 * sigma**2) )y1 = poly1d(polyfit(x,y,1))# lineary2 = poly1d(polyfit(x,y,2))# quadraticy3 = poly1d(polyfit(x,y,3))# cubicy4 = poly1d(polyfit(x,y,4))# 4th degreey5 = poly1d(polyfit(x,y,10))# 10th degreey6 = poly1d(polyfit(x,y,18))# 18th degreefig = figure(figsize=(20,8), facecolor='#f4efcb', edgecolor='#f4efcb')ax = SubplotZero(fig,111)fig.add_subplot(ax)ax.plot(x,y1(x),'r',label=u'линейный')ax.plot(x,y2(x),'g',label=u'квадратичный')ax.plot(x,y3(x),'orange',label=u'кубический')ax.plot(x,y4(x),'b',label=u'$4$ степени')ax.plot(x,y5(x),'c',label=u'$10$ степени')ax.plot(x,y6(x),'m',label=u'$18$ степени')ax.plot(x,y,'k.',label=u'данные')ax.set_xlabel(u'x')ax.set_ylabel(u'y')ax.set_facecolor('#f4efcb')ax.minorticks_on()ax.legend(frameon=False,loc=8,labelspacing=.2)ax.annotate('коэффициенты полинома 18 степени:'+'\n'+str(y6.coeffs), xy = (-1,1.2))setp(ax.get_legend().get_texts(), fontsize='large')fig.savefig("Curve fitting.svg",bbox_inches="tight",pad_inches=.15)

Комикс с шуткой на тему действительных чисел (англ. real numbers) и умножения волновой функции на собственное комплексное сопряжение. Источник

Волновая функция и плотность вероятности

Слева: кривые плотности вероятности нахождения электрона вокруг единичного протона, для трёх энергетических уровней . Справа: показан пример как выглядели бы распределения точек при проведении измерения координаты электрона. Источник.

Квантовый шлагбаум декогеренции

Вы правда считаете, что Луна существует только тогда, когда вы на неё смотрите? (Rev. Mod. Phys. 51, 863914 (1979), p. 907).

Тогда какова размерность клубка ниток? С большого расстояния клубок представляет собой не более чем точку с нулевыми размерами. Приближаясь, можно увидеть, что это шар, который заполняет пространство в трех измерениях. Еще ближе можно увидеть саму нить, и объект становится фактически одномерным Мандельброт без математики апеллировал к теории относительности: Представление о том, что числовой результат должен зависеть от отношения объекта к наблюдателю, в духе физики нашего столетия и даже является образцовой её иллюстрацией.

Хаос. Создание новой науки Джеймс Глейк

Слева: анимация интерференционной картины от прохождения волны через двойную щель, источник. Справа: результаты эксперимента по регистрации одиночных электронов после прохождения двойной щели. Источник: New Journal of Physics, Volume 15, March 2013.

Карикатура, высмеивающая разделение явлений на квантовые и классические. Источник (http://personeltest.ru/away/www.bourbaphy.fr/zurek.pdf)

$inline$z1z2=|z1||z2|[cos(1+2)+isin(1+2)]$inline$

Черной стрелкой показано сравнение скорости вращения фаз двух волновых пакетов с разной частотой источник.

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

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

Немного квантовой криптографии

Схема конструкции квантового компьютера D-Wave 2000Q, источник.

• вертикальная поляризация, горизонтальная;
• диагональная поляризация, антидиагональная.

Слева: вертикально ориентированный фотон блокируется линейным поляризационным фильтром. Справа: при повороте поляризационного фильтра на вертикально поляризационный фотон проходит свободно. Источник.

В левой части: диагональный фотон (красная стрелка) представленный в виде композиции горизонтальной и вертикальной компоненты (розовая и фиолетовая стрелка) электромагнитного поля. В правой части: линейный поляризационный фильтр блокирует вертикальную компоненту диагонального фотона и на выходе получается горизонтально поляризованный фотон. Источник

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

Логическая схема алгоритма шифрования . Источник.

Заключение

• Физика и философия Вернер Гейзенберг, осмысление квантовой теории, как её видел один из наиболее видных её основоположников.
• КЭД странная теория света и вещества классическая книга гениального Ричарда Фейнмана, которая написана по мотивам научно-популярных лекций, прочитанных им в 60-е годы в калифорнийском технологическом институте (Caltech).
• Как понимать квантовую механику более современная и содержащая чуть больше формул, но также изложенная понятным, человеческим языком книга, за авторством доцента кафедры теоретической физики МФТИ Иванова Михаил Геннадьевича.
• Квантовые вычисления со времен Демокрита книга написанная профессором компьютерных наук Скоттом Ааронсоном и которая является чем-то средним между учебником и популярной книгой, для получения наибольшей пользы от чтения которой, рекомендуется выполнять самостоятельные упражнения.
• Physics Videos by Eugene Khutoryansky YouTube канал инженера микроэлектроники, живущего в США, в своих роликах Евгений наглядно демонстрирует сложные физические концепции, благодаря чему многие из его видео набирают больше миллиона просмотров.
• Minute phisics еще один отличный канал по физике, на котором отдельный плэйлист посвящен квантовой механике, не смотря на название, видео достаточно подробно и с нуля разбирают такие сложные темы как: теорему о запрете клонирования, парадокс Харди и даже квантовый алгоритм Шора, позволящий находить простые множители числа за полиномиальное время.
• 3Blue1Brown канал выпускника Оксфорда Гранта Сандерсона, отлично сочетания понятного изложения и уникальной визуализации концепций из: квантовой физики, линейной алгебры, нейронных сетей. Также Грант является автором курса по многопараметрическому исчислению, доступному на площадке некоммерческого проекта Khan Academy.