Схемная модель языка Quipper

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

Использование схемной модели приводит к трём различным этапам выполнения программы: компиляция, время генерации схемы и время исполнения схемы. Это, в свою очередь, приводит к дополнительному различию между входными данными. Входные данные, значение которых известно на стадии генерации схемы, называются параметрами, тогда как входные данные, значение которых известно только во время исполнения схемы, будут так и называться входными данными. Чтобы сохранить это различие явным, в языке Quipper вводится три основных типа для битов и кубитов. Мы используем тип Bool для логического параметра, значение которого известно на стадии генерации схемы, тип Bit для классических булевских входных данных, а также тип Qubit для квантовых входных данных схемы. Параметр типа Bool может быть легко преобразован к входному значению типа Bit, но не наоборот. Кроме того, поскольку измерения могут происходить только во время исполнения схем, типом результата измерения является Bit, а не Bool.

2. Язык Quipper в примерах

Квантовая телепортация

Примитивные операции языка Quipper. Несмотря на то, что при помощи языка Quipper можно описывать квантовые схемы, на практике часто удобнее размышлять о квантовых программах в терминах применения гейтов к кубитам (или битам), которые содержатся в переменных. Эта процедурная парадигма лежит в основе разработки квантовых алгоритмов на языке Quipper, и на ней строятся все остальные высокоуровневые операции.

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

plus_minus :: Bool -> Circ Qubit

plus_minus b = do

q <- qinit b

r <- hadamard q

return r

Первая строка определяет тип функции. Мы видим, что эта функция принимает на вход булевский параметр. Тип выходного значения этой функции — Circ Qubit. Часть типа Circ является, на самом деле, типовым оператором, который обозначает, что определяемая функция может иметь физические сторонние эффекты в то время, когда она будет исполняться (программисты на языке Haskell распознают в этом монаду). Часть типа Qubit говорит нам о том, что функция возвращает кубит. Тело функции обычно начинается с ключевого слова do, за которым следует блок квантовых операций, которые должны быть исполнены в заданном порядке. Тело функции plus_minus использует три операции. Оператор qinit инициализирует новый кубит в состоянии, соответствующем параметру b. Здесь значение False соответствует кубиту |0>, а значение True — |1>. Запись говорит нам, что этот новый проинициализированный кубит сохраняется в переменной q. Оператор hadamard применяет гейт Адамара к кубиту q и сохраняет новое состояние кубита в переменной r. В последней строке кубит r возвращается в качестве результата работы функции. Общим итогом — эта функция возвращает проинициализированный кубит |+> или |-> в зависимости от значения входного булевского параметра. Мы также заметили, что все переменные в теле функции использованы линейно, то есть каждое состояние кубита записано только один раз и прочитано только один раз. Это ограничение обусловлено законами квантовой физики. Однако синтаксисом языка Quipper не запрещается использовать один и тот же идентификатор переменной для обозначения состояний q и r, и мы часто будем пользоваться этим в будущем.

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

Полезной операцией, которая имеется в языке Quipper, является функция экспорта квантовой схемы в различные форматы. Например, для того чтобы создать документ в формате PDF из функции plus_minus, которая была определена выше, мы можем использовать определённый в языке Quipper оператор print_simple. Необходимо отметить, что параметры (но не входные значения) должны получить конкретные значения во время генерации схемы. Здесь мы устанавливаем в параметр b значение False:

print_plus_minus :: IO ()

print_plus_minus = print_simple PDF (plus_minus False)

Диаграммы квантовых схем, которые приводятся далее на всём протяжении этой статьи, сгенерированы на основе здешнего исходного кода. Следующий пример показывает то, как можно контролировать квантовый гейт. Эта функция получает на вход кубит, а возвращает пару кубитов. Операция qnot применяет гейт НЕ к кубиту b. Более того, инфиксный оператор `controlled` обеспечивает то, что эта операция контрлируется значением кубита a. Общий эффект функции share заключается в том, что она получает кубит в состоянии , связывает его с вновь проинициализированным кубитом для создания квантового состояния .

share :: Qubit -> Circ (Qubit, Qubit)

share a = do

b <- qinit False

b <- qnot b `controlled` a

return (a, b)

Определённые ранее квантовые функции могут быть использованы в качестве строительных блоков в других квантовых функциях. Фактически, они могут использоваться абсолютно так же, как и предопределённые операторы языка Quipper. В следующем примере мы используем определённые ранее функции plus_minus и share для создания пары кубитов в состоянии Белла .

bell00 :: Circ (Qubit, Qubit)

bell00 = do

a <- plus_minus False

(a, b) <- share a

return (a, b)

Схема квантовой телепортации. Давайте обратимся к квантовой телепортации (введение в предмет можно обнаружить в [15]). Этот процесс вовлекает в себя две стороны — Алису и Боба. Целью Алисы является телепортация кубита q Бобу. Алиса и Боб должны иметь доступ к одному кубиту из сцеплённой пары (a, b), которая может быть получена при помощи функции bell00, определённой выше. Мы можем размышлять о роли Алисы в терминах функции, которая получает пару кубитов — q и a. На выходе эта функция выдаёт пару классических битов, которые получаются при помощи применения двух унитарных гейтов с последующим измерением обоих кубитов.

alice :: Qubit -> Qubit -> Circ (Bit, Bit)

alice q a = do

a <- qnot a `controlled` q

q <- hadamard q

(x, y) <- measure (q, a)

return (x, y)

Необходимо отметить, что функция measure применяется к паре кубитов. Синтаксис языка Quipper предполагает, что это просто сокращённая запись для измерения двух кубитов в паре. Сокращённая запись возможна потому, что оператор языка Quipper measure является обобщённым оператором: он может быть применён к любой структуре данных, которая содержит кубиты, а возвращает соответствующую структуру данных, содержащую биты. Другим примером обобщённого оператора в языке Quipper является оператор cdiscard, который может быть применён к любой структуре данных, содержащих классические биты. Этот оператор используется в части протокола телепортации на стороне Боба:

bob :: Qubit -> (Bit, Bit) -> Circ Qubit

bob b (x, y) = do

b <- gate_X b `controlled` y

b <- gate_Z b `controlled` x

cdiscard (x, y)

return b

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

teleport :: Qubit -> Circ Qubit

teleport q = do

(a, b) <- bell00

(x, y) <- alice q a

b <- bob b (x, y)

return b

Квантовые типы данных и обобщённые функции. Квантовые типы данных построены на основе типа Qubit при помощи использования различных конструкторов данных, таких как кортежи или списки. Например, тип (Qubit, [Qubit]) — это тип-пара, первым элементом которой является кубит, а вторым — список кубитов переменной, но конечной длины. Каждый квантовый тип данных, такой как qa = (Qubit, [Qubit]), имеет соответствующий классический тип данных, такой как ca = (Bit, [Bit]), а также булевый тип данных, такой как ba = (Bool, [Bool]). Мы говорим, что такие типы qa, ca и ba имеют одну и ту же форму, но разные листьевые типы. Функция в языке Quipper называется обобщённой, если она может оперировать значениями типов данных любой формы.

Мы уже видели примеры некоторых встроенных обобщённых функций языка Quipper, таких как measure, cdiscard и print_simple. Однако тот факт, что программист сам сожет создавать обобщённые функции делает их особенно полезными в языке Quipper. Сейчас мы продемонстрируем эту возможность при помощи определения обобщённого варианта схемы квантовой телепортации.

В языке Quipper ключевое слово QShape указывает на то, что три типа qa, ca и ba являются квантовой, классической и булевой версиями некоторого типа данных. Для определения обобщённого варианта функции plus_minus нам заменить типы Bool и Qubit соответствующей парой типов qa и ca:

plus_minus_generic :: (QShape ba qa ca) => ba -> Circ qa

plus_minus_generic a = do

qs <- qinit a

qs <- mapUnary hadamard qs

return qs

Мы отметили, что функция qinit уже является обобщённой. Оператор mapUnary применяет функцию типа Qubit Circ Qubit к каждому кубиту внутри квантовой структуры данных. Для того чтобы обобщить функцию share, мы используем функцию qc_false, которая генерирует булеву структуру данных корректной формы, в которой каждое булево значение установлено в False. Функция mapBinary аналогична функции mapUnary, но применяет функцию типа Qubit Qubit Circ (Qubit, Qubit) к каждой соответствующей паре кубитов в двух квантовых структурах данных одинаковой формы. Мы также используем встроенный оператор controlled_not.

share_generic :: (QShape ba qa ca) => qa -> Circ (qa, qa)

share_generic qa = do

qb <- qinit (qc_false qa)

(qb, qa) <- mapBinary controlled_not qb qa

return (qa, qb)

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

bell00_generic :: (QShape ba qa ca) => ba -> Circ (qa, qa)

bell00_generic shape = do

qa <- plus_minus_generic shape

(qa, qb) <- share_generic qa

return (qa, qb)

Изменения в функции Алисы почти такие же, какие мы уже видели.

alice_generic :: (QShape ba qa ca) => qa -> qa -> Circ (ca, ca)

alice_generic q a = do

(a, q) <- mapBinary controlled_not a q

q <- mapUnary hadamard q

(x, y) <- measure (q, a)

return (x, y)

Для функции Боба нам необходим способ отображения классически контролируемых X- и Z-вращений над входными битами и кубитами. Функция mapBinary_c похожа на функцию mapBinary, но принимает на вход функцию типа Qubit Bit Circ (Qubit, Bit). Также, несмотря на то, что оператор controlled_not является встроенным, контролируемые X- и Z-вращения таковыми не являются, поэтому мы используем секцию where для локального определения обобщённой функции controlled_gate.

bob_generic :: (QShape ba qa ca) => qa -> (ca, ca) -> Circ qa

bob_generic b (x, y) = do

(b, y) <- mapBinary_c (controlled_gate gate_X) b y

(b, x) <- mapBinary_c (controlled_gate gate_Z) b x

cdiscard (x, y)

return b

Where

controlled_gate gate b x = do

gate b `controlled` x

return (b, x)

Различные части обобщённой функции квантовой телепортации теперь могут быть соединены вместе.

teleport_generic :: (QData qa) => qa -> Circ qa

teleport_generic q = do

(a, b) <- bell00_generic (qc_false q)

(x, y) <- alice_generic q a

b <- bob_generic b (x, y)

return b

Необходимо отметить, что обобщённые функции языка Quipper генерируют семейства квантовых схем, по одной на каждый тип данных. Для того чтобы иметь возможность напечатать какую-либо схему из такого семейства, нам надо заменить функцию print_simple на обобщённый вариант print_generic. Разница заключается в том, что вторая функция принимает дополнительный аргумент, который определяет, какой экземпляр из семейства квантовых схем напечатать. Мы покажем пример печати схем телепортации пары кубитов и списка из трёх кубитов.

print_generic PDF teleport_generic (qubit, qubit)

print_generic PDF teleport_generic [qubit, qubit, qubit]

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

teleport_generic_labeled :: (QData qa) => qa -> Circ qa

teleport_generic_labeled q = do

comment_with_label "ENTER: bell00" q "q"

(a, b) <- bell00_generic (qc_false q)

comment_with_label "ENTER: alice" (a, b) ("a", "b")

(x, y) <- alice_generic q a

comment_with_label "ENTER: bob" (x, y) ("x", "y")

b <- bob_generic b (x, y)

return b

2.2. Квантовое преобразование Фурье и квантовое сложение

Рекурсия. На языке Quipper можно писать функции, генерирующие квантовые схемы, которые рекурсивны по любому из параметров, значение которого известно на стадии генерации. Что замечательно, мы можем определять функции, которые рекурсивны над формой входных данных, такой как список кубитов. Например, представьте себе квантовое преобразование Фурье (КПФ), которое может быть оформлено в виде рекурсивного определения. Функция qft’ определена над списком кубитов. Для рекурсии мы предоставляем два базовых варианта. Если входной список пуст, то и квантовая схема пуста. Если входной список содержит только один кубит, то квантовая схема состоит из одного гейта Адамара. Для рекурсивного случая квантовая схема КПФ для (n + 1) кубита представляет собой квантовую схему КПФ для n кубитов, за которой следует набор вращений всех (n + 1) кубитов. Этот набор вращений также может быть определён при помощи рекурсивной функции, которую мы назовём rotations. Ну и функция rGate m представляет собой встроенный оператор языка Quipper, который представляет вращение вокруг оси z на .

qft' :: [Qubit] -> Circ [Qubit]

qft' [ ] = return []

qft' [x] = do

hadamard x

return [x]

qft' (x:xs) = do

xs' <- qft' xs

xs'' <- rotations x xs' (length xs')

x' <- hadamard x

return (x':xs'')

Where

rotations :: Qubit -> [Qubit] -> Int -> Circ [Qubit]

rotations _ [] _ = return []

rotations c (q:qs) n = do

qs' <- rotations c qs n

letm = ((n + 1) - length qs)

q' <- rGate m q `controlled` c

return (q':qs')

Функция qft’ получает на вход список, в котором кубиты расположены от младшего к старшему (little-endian), а возвращает список с кубитами от старшего к младшему (big-endian). Поскольку это является сбивающим с толку, мы обернули эту функцию в другую — qft_big_endian, которая просто обращает порядок кубитов во входном списке. В языке Quipper это достигается не тем, что меняются местами провода на схеме, но тем, что меняется порядок ссылок на провода; и язык Quipper остаток квантовой цепи присоединит соответствующим образом.

qft_big_endian :: [Qubit] -> Circ [Qubit]

qft_big_endian qs = do

comment_with_label "ENTER: qft_big_endian" qs "qs"

qs <- qft' (reverse qs)

comment_with_label "EXIT: qft_big_endian" qs "qs"

return qs

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

inverse_qft_big_endian :: [Qubit] -> Circ [Qubit]

inverse_qft_big_endian = reverse_generic_endo qft_big_endian

Квантовый сумматор. В качестве применения схемы КПФ мы рассмотрим квантовую схему, которая производит сложение [7] без привлечения вспомогательных кубитов. Эта схема использует КПФ в качестве метода для изменения базиса. В конце вычислений применяется обращённое КПФ для возвращения базиса к исходному состоянию. Часть схемы, находящаяся между двумя КПФ, и которая, собственно, осуществляет сложение, также определена в виде рекурсивной функции.

qft_adder :: [Qubit] -> [Qubit] -> Circ ()

qft_adder _ [] = return ()

qft_adder as (b:bs) = do

qft_adder' as b 1

qft_adder (tail as) bs

Where

qft_adder' :: [Qubit] -> Qubit -> Int -> Circ [Qubit]

qft_adder' [] _ _ = return []

qft_adder' (a:as) b n = do

b <- rGate n b `controlled` a

qft_adder' as b (n + 1)

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

qft_add_in_place :: [Qubit] -> [Qubit] -> Circ ([Qubit], [Qubit])

qft_add_in_place a b = do

label (a, b) ("a", "b")

with_computed (qft_big_endian b) $ \b' -> do

qft_adder a (reverse b')

label (a, b) ("a", "b")

return (a, b)

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

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

qft_add_in_place_boxed :: [Qubit] -> [Qubit] -> Circ ([Qubit], [Qubit])

qft_add_in_place_boxed a b = do

label (a, b) ("a", "b")

with_computed (box "QFT" qft_big_endian b) $ \b' -> do

qft_adder a (reverse b')

label (a, b) ("a", "b")

return (a, b)

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

● Классический симулятор — эффективно симулирует классические схемы.

● Стабилизированный симулятор — эффективно симулирует схемы из группы Клиффорда [1].

● Квантовый симулятор — симулирует произвольную схему (с экспоненциальным ростом затрат).

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