3.6. Предлагаемые языки

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

Quantum Flow Charts, QPL (Selinger). Язык программирования, описанный в [Sel04], представляет программы в виде потоковых схем. Такие схемы состоят из элементарных строительных блоков, таких как унитарные операции, измерения и т. д. Потоковая схема может иметь несколько входных и выходных сторон, которые представляют поток управления программой; каждая сторона может быть проинтерпретирована как различный классический выбор. Например, двоичное измерение может иметь две выходные стороны, по одной для каждого результата измерения.

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

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

Семантика этого языка описана в терминах операторов плотности и супероператоров, так что две неразличимые программы имеют одну семантику.

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

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

Лямбда-исчисление (van Tonder). В работе [vT04] описано лямбда-исчисление. Для обеспечения обратимости (то есть унитарной эволюции) после каждого шага вычислений записывается некоторая информация, которая позволяет восстановить предыдущее состояние. Также добавлена система типизации, которая накладывает ограничения на допустимые операции и допускает осуществление формального вывода относительно программ.

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

qGCL (Zuliani, Sanders). Язык программирования qGCL [SZ00, Zul04] основан на классическом вероятностном языке pGCL [MM99], который в свою очередь основан на языке GCL Э. Дейсктры [Dij76]. В язык pGCL добавлен новый тип данных, представляющий собой квантовый регистр, то есть вектор в конечномерном гильбертовом пространстве. Далее в виде подпрограмм pGCL определены такие операции, как инициализация, унитарное преобразование и измерение. Это автоматически дало ясную семантику языка qGCL, которая наследует законы семантики языка pGCL, так что также поддерживается формальный вывод относительно программ. Далее, язык qGCL содержит возможность недетерминированного выбора, что позволяет создать усовершенствованное исчисление.

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

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

QPAlg (Lalire, Jorrand). В работе [LJ04] описан язык программирования QPAlg. Этот язык основан на классическом исчислении процессом, схожем с CCL [Mil89] и Lotos [BB87]. Далее это исчисление процессов дополнено вероятностями и квантовыми типами данных (при помощи метода, напоминающего гибридный подход, кратко обрисованный в разделе 3.4). К сожалению, из-за недетерминизма в рамках управления приоритетами, возникают проблемы, описанные в разделе 3.2.

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