Язык Quipper как встроенный язык программирования

Аннотация

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

Ключевые слова: квантовые вычисления, языки программирования, Quipper.

Введение

Обзор

Язык программирования Quipper [10] является встроенным языком программирования для квантовых вычислений. Он был разработан как часть проекта QCS [13] агенства IARPA. Задекларированной целью проекта QCS является «аккуратно оценить и сократить вычислительные ресурсы, которые требуются для реализации квантовых алгоритмов на реалистичном квантовом компьютере» с акцентом на использовании техник, разработанных в рамках компьютерных наук (CS).

В этой статье мы покажем, как язык Quipper может быть использован для реализации существующих квантовых алгоритмов при помощивнимательного рассмотрения некоторых из возможностей языка, которые были специально добавлены для выполнения этой задачи. Развитие языка Quipper руководствовалось целью реализации семи нетривиальных квантовых алгоритмов, которые можно найти в литературе [3, 5, 11, 12, 14, 17, 18]. Эти алгоритмы были выбраны в рамках проекта QCS и предоставлены ​​нам в модифицированной форме. Они охватывают широкий спектр методов, используемых в рамках квантовых вычислений. Каждый алгоритм имеет свои собственные особенности, которые помогли разработать возможности языка Quipper, которые теперь в нём доступны.

Чтобы попытаться продемонстрировать использование языка Quipper и дать представление о тех типах задач, в рамках решения которых полезны различные языковые особенности, мы будем использовать простые примеры. Далее мы рассмотрим три основных независимых друг от друга примеров:

● Квантовая телепортация покажет нам: модель квантовых схем в основе языка Quipper, примитивные операции языка Quipper, квантовые типы данных, обобщённые функции, комментарии и метки.

● Квантовое преобразование Фурье и квантовое сложение поможет нам увидеть: рекурсию, операторы на уровне схем, схемы в виде процедур и симуляцию.

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

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

В другой недавней работе [10] мы более подробно описали обоснование различных вариантов проектирования возможностей языка, в том числе высокоуровневый обзор его особенностей. Также мы дали больше общих сведений по имеющимся квантовым языкам программирования, и о создании самого языка Quipper. С другой стороны, целью настоящей работы является предоставить введение в язык 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].

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

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

Where

s = bool_xor (bool_xor a b) carry_in

carry_out = (a && b) || (a && carry_in) || (b && carry_in)

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

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

adder_circ = unpack template_adder

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

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

adder_reversible :: ((Qubit, Qubit, Qubit), (Qubit, Qubit))

-> Circ ((Qubit, Qubit, Qubit), (Qubit, Qubit))

adder_reversible = classical_to_reversible adder_circ

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

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

adder_circ_b = decompose_generic Binary adder_circ

Окончательные замечания

Искусство

В литературе (см. [8]) было описано некоторое количество квантовых языков программирования. Несмотря на это, были реализованы только C-подобный язык QCL [16] с оптимизацией квантовой симуляции; квантовая монада IO [2], которая также является квантовым языком программирования, встроенным в язык Haskell; язык LQPL [9], являющийся функциональным квантовым языком программирования с линейными типами. Однако большиинство языков программирования, описанных в литературе, не могут быть смасштабированы на задачи огромных размеров.

Проблема генерации описания схем на основе функциональных программ также изучалась вне контекста квантовых вычислений; см., например, [4, 6].

Заключение

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

Список источников

1. Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Physical Review A 70(5), 052328 (Nov 2004), arXiv:quant-ph/0406196.

2. Altenkirch, T., Green, A.S.: The Quantum IO Monad. In: Gay, S., Mackie, I. (eds.) Semantic Techniques in Quantum Computation, pp. 173{205. Cambridge University Press (2009).

3. Ambainis, A., Childs, A.M., Reichardt, B.W., Spalek, R., Zhang, S.: Any AND-OR formula of size n can be evaluated in time n^1/2+o(1) on a quantum computer. SIAM J. Comput. 39, 2513{2530 (2010).

4. Bjesse, P., Claessen, K., Sheeran, M., Singh, S.: Lava: hardware design in Haskell. In: Proceedings of the third ACM SIGPLAN international conference on Functional programming. pp. 174{184. ICFP '98, ACM, New York, NY, USA (1998), doi:10.1145/289423.289440.

5. Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing. pp. 59{68 (2003).

6. Claessen, K.: Embedded Languages for Describing and Verifying Hardware. Ph.D. thesis, Chalmers University of Technology and Goteborg University (2001).

7. Draper, T.G.: Addition on a Quantum Computer (Aug 2000), arXiv:quant-ph/0008033.

8. Gay, S.J.: Quantum programming languages: Survey and bibliography. Mathematical Structures in Computer Science 16(4) (2006), http://www.dcs.gla.ac.uk/~simon/publications/QPLsurvey.pdf.

9. Giles, B.: Programming with a Quantum Stack. Master's thesis, Department of Computer Science, University of Calgary (Apr 2007), http://pages.cpsc.ucalgary.ca/~gilesb/research/lqpl.html.

10. Green, A.S., Lumsdaine, P.L., Ross, N.J., Selinger, P., Valiron, B.: Quipper: A scalable quantum programming language (2012), to appear in PLDI 2013, arXiv:1304.3390.

11. Hallgren, S.: Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J. ACM 54(1), 4:1{4:19 (Mar 2007), doi:10.1145/1206035.1206039.

12. Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009).

13. IARPA Quantum Computer Science Program: Broad Agency Announcement IARPA-BAA-10-02 (April 2010), https://www.fbo.gov/notices/637e87ac1274d030ce2ab69339ccf93c.

14. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem (Nov 2003), arXiv:quant-ph/0310134.

15. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2002).

16. Omer, B.: A Procedural Formalism for Quantum Computing. Master's thesis, Dept. of Theoretical Physics, Tech. Univ. Vienna (Jul 1998), http://tph.tuwien.ac.at/~oemer/qcl.html.

17. Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738{760 (2004).

18. Whiteld, J.D., Biamonte, J., Aspuru-Guzik, A.: Simulation of electronic structure hamiltonians using quantum computers. Molecular Physics 109(5), 735{750 (2011).

Аннотация

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

Ключевые слова: квантовые вычисления, языки программирования, Quipper.

Введение

Обзор

Язык программирования Quipper [10] является встроенным языком программирования для квантовых вычислений. Он был разработан как часть проекта QCS [13] агенства IARPA. Задекларированной целью проекта QCS является «аккуратно оценить и сократить вычислительные ресурсы, которые требуются для реализации квантовых алгоритмов на реалистичном квантовом компьютере» с акцентом на использовании техник, разработанных в рамках компьютерных наук (CS).

В этой статье мы покажем, как язык Quipper может быть использован для реализации существующих квантовых алгоритмов при помощивнимательного рассмотрения некоторых из возможностей языка, которые были специально добавлены для выполнения этой задачи. Развитие языка Quipper руководствовалось целью реализации семи нетривиальных квантовых алгоритмов, которые можно найти в литературе [3, 5, 11, 12, 14, 17, 18]. Эти алгоритмы были выбраны в рамках проекта QCS и предоставлены ​​нам в модифицированной форме. Они охватывают широкий спектр методов, используемых в рамках квантовых вычислений. Каждый алгоритм имеет свои собственные особенности, которые помогли разработать возможности языка Quipper, которые теперь в нём доступны.

Чтобы попытаться продемонстрировать использование языка Quipper и дать представление о тех типах задач, в рамках решения которых полезны различные языковые особенности, мы будем использовать простые примеры. Далее мы рассмотрим три основных независимых друг от друга примеров:

● Квантовая телепортация покажет нам: модель квантовых схем в основе языка Quipper, примитивные операции языка Quipper, квантовые типы данных, обобщённые функции, комментарии и метки.

● Квантовое преобразование Фурье и квантовое сложение поможет нам увидеть: рекурсию, операторы на уровне схем, схемы в виде процедур и симуляцию.

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

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

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

Язык Quipper как встроенный язык программирования

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

В то время как подход с построением встроенного языка программирования имеет много преимуществ (см. [6, гл. 1.3], где представлено общее обсуждение вопроса), есть и определённые потенциальные ловушки, о которых должны знать программисты. Одной из них является искушение использовать основной языке, то есть в данном случае написание программ на языке Haskell, а не следование идиоме языка Quipper. Это может нарушить используемые абстракции и сделать программу менее переносимой в случае изменения реализации. Другой недостаток подхода встраиваемого языка заключается в том, что часто ошибки компиляции сложно расшифровать, потому что компилятор представляет их в терминах базового, а не встроенного языка. Наконец, в то время как язык Haskell во всех отношениях является прекрасным базовым языком программирования, в частности для модели квантовых вычислений есть действительно два важных недостатка: отсутствие линейных типов и отсутствие зависимых типов, поэтому мы должны проверять некоторые свойства программ во время выполнения, хотя они в принципе могли бы быть проверены системой типизации во время компиляции.