Языки программирования для квантового компьютера

Прототип ядра ионного квантового компьютера. Ion Quantum Technology Group, Сассекский университет

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

К счастью, для решения этой проблемы появляются отличные проекты, привлекающие внимание широкой аудитории. Например, несколько лет назад IBM дала возможность любому подключиться к 5-кубитному компьютеру. В проекте зарегистрировались 70 000 человек.

Однако индустрия квантовых вычислений по-прежнему остается в зачаточном состоянии. Хотя уже создано немало прототипов, они не могут сделать то, с чем не справится обычный ноутбук. Необходимое аппаратное обеспечение еще не существует, но для изучения у нас есть кое-что еще — языки квантового программирования.

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

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

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

Прежде чем заняться программами, давайте вспомним базовые вещи о квантовых вычислениях. И здесь нам поможет статья Брайана Хейса «Programming Your Quantum Computer».

Обычный компьютер основан на битах: речь идет переменных, которые имеют только два возможных значения. Мы часто называем их 0 и 1, хотя в контексте булевой алгебры мы можем назвать их «Истинные» и «Ложные».

С битами можно выполнять простые булевы операции, такие как NOT, AND и OR. Любая переменная, более сложная, чем бит (например, int или float), представляет собой просто набор из множества бит.

Квантовые компьютеры основаны на квантовых битах или кубитах. Они также имеют два возможных значения, которые мы можем назвать 0 и 1. Но законы квантовой механики также допускают другие значения, которые мы называем состояниями суперпозиций.

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

Дело не в том, что кубит может иметь промежуточное значение, например 0,63; когда измеряется состояние кубита, результат всегда равен 0 или 1. Но в ходе вычисления кубит может действовать так, как если бы он представлял собой смесь состояний — например, 63% нуля и 37% единицы.

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

Подобно волнам, состояния 0 и 1 кубита имеют амплитуды, которые могут быть либо положительными, либо отрицательными. В зависимости от знаков амплитуд квантовая интерференция может либо увеличивать, либо уменьшать вероятность того, что определенное состояние будет наблюдаться, когда мы измеряем состояние кубита.

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

Одним из последних аспектов квантовой странности является запутанность. Вы не можете изменить один кубит внутри квантового регистра, оставив остальное без изменений. Для начала каждая функция, вычисленная квантовой системой, должна быть полностью обратимой. Если машина получает на вход A для вывода результата B, то должна быть возможность восстановить A при наличии B.

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

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

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

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

Open Quantum Assembly Language (OpenQASM)

Исходный код OpenQASM был выпущен как часть программного обеспечения IBM Quantum Information Software Kit (QISKit) для использования с квантовой вычислительной платформой Quantum Experience. OpenQASM имеет общие черты со специализированными языками программирования (такими, как Verilog), используемыми для описания структуры и поведения электронных схем.

Программы QASM фактически всегда начинаются одинаково: мы определяем все биты, которые нам понадобятся — как квантовые, так и нормальные. Ниже приведен пример исходного кода OpenQASM. Программа добавляет два четырехбитовых номера.

OPENQASM 2.0; include "qelib1.inc"; gate majority a,b,c  {    cx c,b;    cx c,a;    ccx a,b,c;  } gate unmaj a,b,c  {    ccx a,b,c;    cx c,a;    cx a,b;  } qreg cin[1]; qreg a[4]; qreg b[4]; qreg cout[1]; creg ans[5]; // устанавливаем входящие значения x a[0]; // a = 0001 x b;    // b = 1111 // добавляем a к b, сохраняем результаты в b majority cin[0],b[0],a[0]; majority a[0],b[1],a[1]; majority a[1],b[2],a[2]; majority a[2],b[3],a[3]; cx a[3],cout[0]; unmaj a[2],b[3],a[3]; unmaj a[1],b[2],a[2]; unmaj a[0],b[1],a[1]; unmaj cin[0],b[0],a[0]; measure b[0] -> ans[0]; measure b[1] -> ans[1]; measure b[2] -> ans[2]; measure b[3] -> ans[3]; measure cout[0] -> ans[4];

Q#

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

operation Teleport(msg : Qubit, there : Qubit) : () {     body {         using (register = Qubit[1]) {             let here = register[0];             H(here);             CNOT(here, there);             CNOT(msg, here);             H(msg);            if (M(msg) == One) { Z(there); }             if (M(here) == One) { X(there); }             }        }     }

Скрипт Teleportation.qs из учебника по Q#. Учебник доступен здесь

Q# выглядит не так, как большинство других языков программирования, и несколько похож на C#.

Quantum Development Kit предоставляется бесплатно с подробными инструкциями по его установке и вводным учебным программам. Q# компилируется на квантовом симуляторе Visual Studio, имитируя квантовый процессор на 32 кубита. Симулятор может имитировать до 40 кубитов.

Если следовать туториалу от Microsoft, то процесс обучения пойдет от наблюдения запутанных состояний из двух кубитов к моделированию квантовой телепортации.

LIQUi (Language-Integrated Quantum Operations)

Платформа LIQUi, созданная командой Quantum Architectures and Computation Group в Microsoft Research, включает язык программирования, алгоритмы оптимизации и планирования, а также несколько квантовых симуляторов. LIQUi может использоваться для перевода квантового алгоритма, написанного в виде программы высокого уровня на языке F# из семейства .NET Framework, в низкоуровневые команды для квантового компьютера.

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

operation TeleportClassicalMessage(message : Bool) : Bool {             body {                 mutable measurement = false;                  using (register = Qubit[2]) {                     // Запросим несколько кубитов, которые можно использовать для телепортации.                     let msg = register[0];                     let there = register[1];                      // Кодируем сообщение, которое мы хотим отправить.                     if (message) { X(msg); }                     Teleport(msg, there);                      // Проверяем сообщение.                     if (M(there) == One) { set measurement = true; }                      ResetAll(register);                 }                  return measurement;             }         }

Как можно заметить по примеру выше, LIQUi очень похож на Q#.

Quantum Computation Language (QCL)

QCL, или Quantum Computation Language создан Бернхардом Омером в 1998 году. Развитие языка продолжается и сейчас: существует эмулятор, который позволяет запускать квантовые программы на классическом компьютере. Конечно, эмулятор не может обеспечить ускорение квантового параллелизма; с другой стороны, он предлагает программисту некоторые полезные функции, такие как команды для проверки внутреннего состояния кубитов (что крайне трудно сделать на реальном квантовом оборудовании).

QCL заимствует синтаксис C и Java, которые иногда описываются как «императивные» языки, потому что они полагаются на прямые команды для установки и сброса значений переменных. Такие команды обычно запрещены в квантовом вычислении, поэтому основные части программы QCL работают только на классическом оборудовании. Квантовая система служит «оракулом», отвечающим на вопросы, которые могут быть заданы в формате, подходящем для вычислений кубитов. Каждый запрос к оракулу должен иметь требуемую архитектуру дымоходной трубы, но он может быть встроен в цикл во внешнем классическом контексте.

Фрагмент кода, созданного в QCL (дискретное преобразование Фурье):

operator dft(qureg q) {           const n=#q;      int i; int j;  for i=1 to n {  for j=1 to i-1 {   V(pi/2^(i-j),q[n-i] & q[n-j]);  }  H(q[n-i]);  }  flip(q);  }

Дискретное преобразование Фурье является решающим шагом в алгоритме факторизации Шора. В алгоритме Шора число, подлежащее факторизации, рассматривается как волнообразный, периодический сигнал. Если N имеет коэффициенты u и v, то N состоит из u повторений v или v повторений u. Алгоритм Шора использует квантовый параллелизм для поиска периода таких повторений, хотя процесс не такой простой и прямой, как может показаться в примере выше.

Quipper

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

Рассмотрим классическую квантовую телепортацию. Она включает в себя две стороны — Алису и Боба. Целью Алисы является телепортация кубита q к Бобу. У Алисы и Боба должен быть доступ к кубитам из запутанной пары (a, b). Мы можем думать о роли Алисы в терминах функции, которая вводит два кубита 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) 

Более подробно можно познакомиться в документе «An Introduction to Quantum Programming in Quipper».

А вот интересный пример возведения в 17 степень, путем возведения x в 16 степень встроенной процедурой возведения в квадрат и перемножением x и x^16:

o4_POW17 :: QIntTF -> Circ (QIntTF,QIntTF)  o4_POW17 = box "o4" $ x -> do  comment_with_label "ENTER: o4_POW17" x "x"   (x, x17) <- with_computed_fun x  (x -> do  (x,x2) <- square x  (x2,x4) <- square x2  (x4,x8) <- square x4  (x8,x16) <- square x8  return (x,x2,x4,x8,x16))  ((x,x2,x4,x8,x16) -> do  (x,x16,x17) <- o8_MUL x x16  return ((x,x2,x4,x8,x16),x17))  comment_with_label "EXIT: o4_POW17" (x,x17) ("x","x17")  return (x, x17)

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

Quipper, как и QCL, автоматически генерирует схемы из высокоуровневых исходных смысловых конструкций.

Другие подходы

Разноцветные квадраты говорят пяти квантовым битам IBM, что нужно делать. Перетаскиванием вы можете создавать свои собственные квантовые вычисления

Проект IBM Quantum Experience предоставляет возможность каждому запустить экспериментальную программу на реальном квантовом компьютере. Работа с языком программирования IBM похожа на процесс написания музыки с помощью приложения. Программист может просто перетащить квантовые объекты в определенную область, чтобы написать программу.

Quantum Computing Playground — эксперимент WebGL Chrome, позволяющий смоделировать работу с квантовым компьютером в окошке браузера. Имеется собственный язык сценариев Qscript с функциями отладки и 3D-квантовой визуализации. Квантовая вычислительная площадка может эффективно имитировать квантовые регистры до 22 кубитов.

Python QISKit SDK включает в себя несколько инструментов, которые инженеры IBM Q предоставили для иллюстрации целей квантового программирования. В частности, SDK показывает, как вы можете выполнить несколько заданий для сложных экспериментов. Как ясно из названия, QISKit позволяет разработчикам исследовать квантовый компьютер с помощью Python.

Qbsolv — open source проект для работы с кубитами квантового процессора D-Wave (подходит только для компьютеров этой компании).

Языков квантового программирования (и симуляторов) уже десятки, но все они работают на виртуальной машине. Вероятно, IBM Q — это единственный проект, который предлагает доступ к реальному квантовому компьютеру. Однако для того, чтобы начать заниматься «квантовым программированием», вовсе не обязательно иметь доступ к реальному передовому устройству. Уже сейчас можно не только изучать работу перспективных квантовых алгоритмов, но и создавать работающие приложения, например игры. Но это уже совсем другая история.

Источники:

Even You Can Help Build a Quantum Computer
Quipper: The First High-Level Scalable Programming Language for Quantum Computers
Quantum Programming Language
How to program a quantum computer
Structured Quantum Programming
QCL — A Programming Language for Quantum Computers