https://arxiv.org/pdf/1304.3390.pdf
Quipper: A Scalable Quantum Programming Language

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

Поэтому посмотрим на сам Quipper как язык: в чём его особенности и трудности, и как они решаются.

Технически, Quipper реализован в виде eDSL на Haskell. Вполне ожидаемо, монадический eDSL. Впрочем, лично мне кажется, для описания квантовых алгоритмов в виде circuits (схем) могли бы больше подойти Arrows (стрелки) — если на самом деле они не подходят, то интересно почему?

Помимо монад, Quipper полагается и на более продвинутые фичи Haskell и GHC, в частности, творчески использует Template Haskell чтобы автоматически преобразовывать "классические" функции подходящего вида в соответствующие квантовые схемы, получая оракулов для квантовых алгоритмов.

И тем не менее, кое-чего авторам не хватило:

> In particular, Haskell lacks two features that would be useful for Quipper: linear types and dependent types.

По такому поводу авторы выдвинули идею переделать Quipper в самостоятельный язык со своим собственным компилятором и системой типов. Но можно просто подождать ещё пару лет. А вы говорите, что зависимые типы никому не нужны. 😊

Так или иначе, Quipper разрабатывался как язык, не зависящий от конкретной реализации квантового компьютера, позволяя как тестировать полученные программы на симуляторе (или рисовать в виде диаграмм), так и переносить между разными физическими квантовыми компьютерами. Это достигается использованием общепринятой абстрактной модели QRAM machine, подразумевающей наличие квантового вычислительного устройства в виде сопроцессора, управляемого классическим компьютером. Что определяет следующую особенность программ на Quipper — в их жизненном цикле 3 стадии: 1. компиляция из исходного текста (Haskell) в программу, запускаемую на классической части квантового компьютера; 2. запуск этой программы для подготовки квантовой схемы и её запуска на квантовом сопроцессоре; 3. выполнение квантовой схемы на квантовом сопроцессоре. И на разных стадиях доступны совершенно разные языковые возможности и типы данных.

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

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

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

При этом, квантовые схемы, производимые Quipper — первого порядка, т.е. сами не могут оперировать квантовыми схемами как значениями (не могут создавать и применять замыкания, говоря "классическим" языком). Так что несмотря на то, что Quipper является функциональным языком с поддержкой функций высшего порядка ("наследуя" эти возможности из Haskell), к моменту формирования конечного квантового контура все структуры высшего порядка "схлопываются".

Вся эта схема работы здорово напоминает про staged metaprogramming и модальные системы типов — возможно, это могло бы стать ещё одной фичей квантового языка программирования. 😊

#dsl #haskell #quipper #quantumcomputing