Процедурный формализм для квантовых вычислений
Бернхард Омер
23 июля 1998 года
Факультет теоретической физики
Венский технический университет
Электронная почта: oemer@tph.tuwien.ac.at
Домашняя страница: http://tph.tuwien.ac.at/~oemer
Абстрактный
Несмотря на множество общих концепций с классической информатикой, квантовые вычисления по-прежнему широко рассматриваются как особая дисциплина в широкой области теоретической физики. Одной из причин медленного внедрения КВ в сообществе компьютерной науки является запутанное разнообразие формализмов (обозначения Дирака, матрицы, вентили-ворота, операторы и т.д.), ни один из которых не имеет никакого аналога знакомого с классическими языками программирования, а также довольно “физическая” терминология в большей части доступной литературы.
QCL (Quantum Computation Language) пытается восполнить этот пробел: QCL - это
высокоуровневый, архитектурно независимый язык программирования для квантовых компьютеров, синтаксис которого заимствован из классических процедурных языков, таких как C или Pascal. Это позволяет полностью реализовать и смоделировать квантовые алгоритмы (включая классические компоненты) в едином последовательном формализме.
Глава 1 представляет собой введение в основные концепции квантового программирования- кроме того, полный языковой справочник по QCL можно найти в главе 2, а в главе 3 приведены некоторые примеры, включая реализацию алгоритма факторизации Шора на QCL. Исходный код интерпретатора QCL доступен
по адресу http://tph.tuwien.ac.at/~oemer/qcl.html.
Содержание
1 Введение 4
1.1 Модели квантовых вычислений . . . . . . . . . . . . . . . . 4
1.1.1 Математическая модель квантовых вычислений. . . . . . . . . . . . . 4
1.1.2 Модель машины для квантовых вычислений . . . . . . . . . . . . . . . . 5
1.1.3 Модель ворот для квантовых вычислений . . . . . . . . . . . . . . . . . . 6
1.1.4 Языки программирования . . . . . . . . . . . . . . . . . 7
1.2 Принципы квантовых вычислений . . . . . . . . . . . . . . . 7
1.2.1 Кубиты . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Запутанность состояний . . . . . . . . . . . . . . . . . . 8
1.2.3 Обратимость . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Инициализация . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Измерение состояний . . . . . . . . . . . . . . . . . . . . . 9
1.3 Квантовое программирование . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Квантовый параллелизм . . . . . . . . . . . . . . . . . . . 10
1.3.2 Квантовые регистры . . . . . . . . . . . . . . . . . . . . 10
1.3.3 Функции . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Управление свободным пространством . . . . . . . . . . . . . . . 13
1.3.5 Условные операторы . . . . . . . . . . . . . . . . . . 14
2 Язык квантовых вычислений QCL 16
2.1 Введение QCL . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 Особенности . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Пример: Дискретное преобразование Фурье в QCL . . . . . 17
2.1.3 Интерпретатор QCL . . . . . . . . . . . . . . . . . . . 18
2.1.4 Структура программы на QCL . . . . . . . . . . . . . . . 20
2.2 Классические выражения и переменные . . . . . . . . . . . . . . . . 22
2.2.1 Постоянные выражения . . . . . . . . . . . . . . . . . . . 22
2.2.2 Операторы . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3 Функции . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.4 Символы . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Квантовые регистры и выражения . . . . . . . . . . . . . . . 30
1
СОДЕРЖАНИЕ 2
2.3.1 Регистры и состояния . . . . . . . . . . . . . . . . . . . 30
2.3.2 Квантовые переменные . . . . . . . . . . . . . . . . . . . . 31
2.3.3 Квантовые выражения . . . . . . . . . . . . . . . . . . 35
2.4 Утверждения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4.1 Элементарные команды . . . . . . . . . . . . . . . . . . 36
2.4.2 Квантовые утверждения . . . . . . . . . . . . . . . . . . . 39
2.4.3 Управление потоком . . . . . . . . . . . . . . . . . . . . . . . 41
2.5 Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5.2 Функции . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5.3 Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5.4 Общие операторы . . . . . . . . . . . . . . . . . . . . 46
2.5.5 Псевдо-классические операторы . . . . . . . . . . . . . . . . . 49
2.5.6 Квантовые функции . . . . . . . . . . . . . . . . . . . . 50
3 Операторы и алгоритмы 56
3.1 Элементарные операторы . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Общие унитарные операторы . . . . . . . . . . . . . . . . 56
3.1.2 Псевдоклассические операторы . . . . . . . . . . . . . . . . . 58
3.2 Составные операторы . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.1 Псевдоклассические операторы . . . . . . . . . . . . . . . . . 60
3.2.2 Модульная арифметика . . . . . . . . . . . . . . . . . . . 62
3.2.3 Квантовое преобразование Фурье . . . . . . . . . . . . . . . 64
3.3 Алгоритм Шора для квантовой факторизации . . . . . . . . . . 65
3.3.1 Мотивация . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.3.2 Алгоритм . . . . . . . . . . . . . . . . . . . . . . 66
3.3.3 Реализация QCL . . . . . . . . . . . . . . . . . . . 69
A QCL- программы и включаемые файлы 75
A.1 по умолчанию.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
A.2 функции.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
A.3 функция qufunct.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
A.4 модарит.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
A.5 dft.qcl в расширенном виде . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
A.6 сокращенный qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
B Графики QCL 85
B.1 Синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
B.1.1 Выражения . . . . . . . . . . . . . . . . . . . . . . . . 85
B.1.2 Заявления . . . . . . . . . . . . . . . . . . . . . . . . 86
B.1.3 Определения . . . . . . . . . . . . . . . . . . . . . . . . . 86
СОДЕРЖАНИЕ 3
B.2 Сообщения об ошибках . . . . . . . . . . . . . . . . . . . . . . . . . . 87
B.2.1 Ошибки при проверке типов . . . . . . . . . . . . . . . . . . . . . 87
B.2.2 Ошибки при оценке . . . . . . . . . . . . . . . . . . . . . 89
B.2.3 Ошибки при выполнении . . . . . . . . . . . . . . . . . . . . . 90
Глава 1
Вступление
1.1 Модели квантовых вычислений
В классической теории информации концепция универсального компьютера может быть представлена несколькими эквивалентными моделями, соответствующими различным научным подходам. С математической точки зрения универсальный компьютер — это машина, способная вычислять частично рекурсивные функции, специалисты по информатике
часто используют машину Тьюринга в качестве своей любимой модели, инженер-электрик, возможно, будет говорить о логических схемах, в то время как программист, безусловно, предпочтет универсальный язык программирования.
Что касается квантовых вычислений, то у каждой из этих классических концепций есть квантовый аналог:
Модель классическая квантовая
Математическии частично рекурсивные функции унитарные операторы
Машина Машина Тьюринга QTM квантовая машина Тьюринга
Схема логическая схема квантовые вентили
Алгоритмический универсальный язык программирования QCL-квантовый язык (библиотека С)
Таблица 1.1: классическая и квантовая вычислительные модели
1.1.1 Математическая модель QC
Моральным эквивалентом частично рекурсивных функций в QC являются унитарные операторы. Поскольку каждая классически вычислимая задача может быть переформулирована как вычисление значения частично рекурсивной функции, каждое квантовое вычисление должно иметь соответствующий унитарный оператор.
4
ГЛАВА 1. ВВЕДЕНИЕ 5
1.1.1.1 Унитарные операторы
Унитарный оператор U в гильбертовом пространстве H является линейным оператором, который соответствует следующим условиям:
U (; |;; + ; |;;) = ; U |;; + ;U |;;
и U † = U -1 c |;;, ; ; H (1.1)
Хотя унитарные операторы полностью описывают само квантовое вычисление, это было бы бесполезно, поскольку квантовые состояния невозможно наблюдать непосредственно.
Согласно копенгагенской интерпретации квантовой физики, установка и результат любого квантово-механического эксперимента должны быть сформулированы в классических терминах. Таким образом, нам потребуются 2 дополнительные операции для установки определенного начального состояния |;0; и для измерения выходного сигнала.
1.1.1.2 Инициализация
Оператор сбросить (ресет) R является постоянной оператора H, который сбрасывает общее
|;; в |;0;. Обычно выбирают основании H таким образом, чтобы |;0; = |0;.
1.1.1.3 Измерение
Оператор измерения M (O) наблюдаемой величины O = {;0, ;0, . . . ;0}, где ;i - взаимно ортогональное разложение H, случайным образом применяет проекционный оператор P (;i) к измеряемому состоянию |;;, смещенному на вероятность pm = ;P (;m); и перенормирует результат.
Классическим результатом измерения является ;(m), где ; — отображение {0, 1, . . . k} ; R ; {physical unit физическая единица измерения O}. 1
Поскольку математическая модель трактует унитарные операторы как черные ящики, мера сложности не предусмотрена.
1.1.2 Машинная модель квантовых вычислений QC
По аналогии с классической машиной Тьюринга (ТМ) было сделано несколько предположений о квантовых машинах Тьюринга (QTM) как модели универсального квантового компьютера [3, 1].
Таким образом, полное состояние машины |; задается суперпозицией базовых состояний |l, j, s›, где l - внутреннее состояние головки, j - положение головки, а s - двоичное представление содержимого ленты. Чтобы сохранить возможность разделения H,1
1 Поскольку нас не интересуют физические величины, а O обычно соответствует регистру
кубитов, мы можем использовать стандартную наблюдаемую величину, таким образом, ;(i) = i.
ГЛАВА 1. ВВЕДЕНИЕ 6
(бесконечная) битовая строка s должна удовлетворять условию нулевого конца-хвоста состояния, т.е. допускается только конечное число битов с sm ; 0.
Квантовый аналог функции перехода классического вероятностного TM - это шаговый оператор T, который должен быть унитарным, чтобы допускать существование соответствующего гамильтониана2 и удовлетворять условиям локализации для задействованного ленточного кубита, а также для перемещения головки.
QTMs обеспечивают измерение времени выполнения, но, как и в случае с классическим TM, поиск подходящего оператора шага может быть очень сложным, а сложность во время выполнения (т.е. количество применений T по отношению к проблеме размера) остается проблемой. За пределами теории квантовой сложности квантовые машины Тьюринга QTM имеют второстепенное значение.
1.1.3 Модель Gate в QC
Квантовые схемы являются квантовых вычислений (квантуум компьюташионс) эквивалентом классических булевых сетей с прямым заполнением (фид-форвард), с одним существенным отличием: поскольку все квантовые вычисления должны быть унитарными, все квантовые схемы могут быть вычислены, оценены в обоих направлениях (как с классической обратимой логикой). Квантовые схемы состоят из элементарных элементов и работают с кубитами, таким образом, dim(H) = 2n, где n - (фиксированное) количество кубитов.
Фактическое унитарное преобразование, выполняемое m-кубитным вентилем, зависит
от 2m-мерного подпространства H' ; H, соответствующего конкретным позициям входных кубитов. Пусть G - двумерный оператор (m = 1) для вентиля, работающего на k-м кубите состояния
, и I(l) - оператора идентификации l-кубита, тогда результирующий оператор Gk(n) равен
Gk(n) = I(k - 1) ; G ; I(n - k ; 1) с I(l) |; = |;, |;C2l (1.2)
Таким образом, квантовый m-кубитный вентиль в n-кубитном гильбертовом пространстве представляет собой класс из n!/(n;m)! унитарных операторов.
Чтобы обеспечить возможность реализации всех возможных унитарных преобразований, должен быть доступен универсальный набор элементарных вентилей управления, из которых могут быть построены составные вентили. Одним из возможных наборов (предложенных Дойчем) [4] является , например, {; ; [0, 2;) /D(;)} с
D(;) : |i, j, k; ;{ i cos ; |i, j, k; + sin ; |i, j, 1 ; k; для i = j = 1
|i, j, k; в противном случае (1.3)
2 В квантовой механике с непрерывным временем оператор U распространения во времени задается через U (t) = e;iH(t;t0)/h.
Поскольку H имеет только действительные собственные значения, U должен быть единым -унитарным.
ГЛАВА 1. ВВЕДЕНИЕ 7
Однако даже одного D(;) с иррациональным ;/; достаточно, чтобы аппроксимировать любой
унитарный оператор с произвольной точностью.3
В отличие от операторного формализма, вентильная запись (гейт-нотация) является по своей сути конструктивным методом, и, -в отличие от QTMs-, сложность задачи напрямую отражается на количестве вентилей, необходимых для ее реализации.
1.1.4 Языки программирования
Когда дело доходит до программирования и разработки неклассических алгоритмов, мы можно рассматривать операторную алгебру как спецификацию, а квантовые вентили - как
язык сборки QC.
Отсутствие типичных методов программирования в виде локальных квантовых переменных, управления пространством с нуля (скратч-царапины) и динамической длины регистров в качестве общих свойств в обоих формализмах делает фактическую реализацию4 нетривиальных квантовых алгоритмов очень сложной (см. пример в [13]), поскольку классический подход “разделяй и властвуй” является только для ограниченного использования.
Другой проблемой является классическая структура управления: из-за их вероятностной природы, оценка результатов измерений и условные попытки являются частью практически любого квантового алгоритма, однако они не могут быть описаны в рамках традиционного формализма.
Цель QCL - заполнить этот пробел и служить языком программирования высокого уровня для квантовых вычислений.
1.2 Принципы квантовых вычислений
1.2.1 Кубиты
Для реализации вычислительной модели в качестве физического устройства компьютер должен быть способен адаптировать различные внутренние состояния, предоставлять средства-значения для выполнения необходимых преобразований с ними и извлечения выходной информации. Корреляция между физическим и логическим состоянием машины
произвольна (при условии, что она согласуется с требуемыми преобразованиями) и требует интерпретации.
В обычном модуле оперативной памяти общее квантовое состояние тысяч электронов интерпретируется только как один бит. Логическое состояние определяется ожидаемым значением содержимого его регистра (например, напряжением конденсатора)
3 Обратите внимание, что D(;/2) определяет логический элемент-вентиль Тоффоли, который является универсальным для классической обратимой логики.
4 Это означает конструктивную спецификацию последовательности элементарных элементов, а не ее экспериментальная реализация.
ГЛАВА 1. ВВЕДЕНИЕ 8
Интерпретация в виде (классических) битов выполняется путем сравнения измеренного значения с определенным пороговым значением, в то время как большое количество частиц гарантирует , что неопределенность измерения достаточно мала (O(1/;n)), чтобы сделать ошибки практически невозможными.
В квантовом компьютере информация представляется непосредственно в виде общего квантового состояния многих подсистем. Каждая подсистема описывается комбинацией двух “чистых” состояний, интерпретируемых как |0; и |1; (квантовый бит, кубит). Это может быть реализовано, например, за счет вращения частицы, поляризации фотона или за счет основного и возбужденного состояний иона.
1.2.2 Запутанность состояний
Из-за взаимно однозначной связи между логическим и физическим состоянием в квантовом компьютере квантовый регистр, содержащий более одного кубита, не может быть описан простым перечислением, перелистыванием состояний каждого кубита. Фактически, “состояние кубита” становится бессмысленным термином 5
Для изолированной системы из двух кубитов ее состояние может быть описано четырьмя комплексными амплитудами a|0, 0; + b|1, 0; + c|0, 1; + d|1, 1;. Вы можете определить математическое ожидание для первого кубита, которое равно
;bb; + dd;, но для первого кубита больше нет изолированного состояния, например, (a + c)|0; + (b + d)|1;, поскольку |a|2 + |b|2 + |c|2 + |d|2 = 1 не означает, что |a + c|2 + |b + d|2 = 1.
Следовательно, манипуляции с отдельным кубитом влияют на комплексные амплитуды всеобщего состояния и носят глобальный характер. Чтобы описать объединенное
состояние |;; n запутанных кубитов, необходимо 2n комплексных чисел.
|;; = 2n;1;i=0 ci |i; с 2n;1;i=0 c;i ci = 1 и ci ; C (1.4)
1.2.3 Обратимость
Чтобы обеспечить согласованность вычислений, квантовые регистры должны быть изолированы, чтобы избежать взаимодействия с окружающей средой. Энтропия такой системы должна оставаться постоянной, поскольку рассеивание тепла невозможно, поэтому изменения состояния должны быть адиабатическими, что требует, чтобы все вычисления были обратимыми.
Каждая обратимая операция может быть описана унитарным оператором U, который
соответствует условию U -1 = U†. Композиции унитарных операторов также являются
унитарными, поскольку (UV )-1 = V †U †. Ограничение на унитарные операторы также может
5 Иногда встречающееся обозначение |;;|;; для множественных квантовых регистров вместо простых состояний произведения несколько вводит в заблуждение в этом отношении. В этой статье |;;|;; всегда обозначает векторное произведение, а регистры при необходимости помечаются индексами типа |·;s.
ГЛАВА 1. ВВЕДЕНИЕ 9
может быть непосредственно получено для оператора временного распространения U = e-iHt/h.
Поскольку оператор Гамильтона H является наблюдаемым, он имеет только действительные собственные значения
и († U ) = U -1 = eiHt/h.
Общее унитарное преобразование в двумерном гильбертовом пространстве
C2 может быть определено следующим образом:
U (;, ;, ;, ; ) =(ei(;+;+; ) cos ; /2 e;i(;+;;; ) sin ;/2
;ei(;;;+; ) sin ;/2 -ei(;;;;; ) cos ;/2)
где ;, ;, ;, ; ; R
(1.5)
Если этот оператор может быть применен к произвольным двумерным подпространствам H, то любое унитарное преобразование может быть построено с помощью композиции. Если разрешены только подпространства, соответствующие подмножеству кубитов, что имеет место для многих предлагаемых архитектур, среди которых также линейная ионная ловушка (Кирак- Золлера вентиля [2]), то для получения смешивания между отдельными кубитами требуется дополнительный 4-мерный 2-кубитный оператор [6].
Одной из возможностей для этого оператора является 2-кубитное исключающее ИЛИ значение, которое определяется как
XOR : |x, y; ; |x, x ; y; или в матричной записи:
XOR =
;1 0 0 0;
;0 1 0 0;
;0 0 0 1;
;0 0 1 0;
; ; (1.6)
Квантовый компьютер, который способен выполнять главные операции с одним кубитом и
операции исключения (XOR), может выполнять любые возможные операции и в этом смысле является универсальным.
1.2.4 Инициализация
Чтобы перевести квантовый компьютер в желаемое входное состояние |;;, достаточно обеспечить значения для первоначального “охлаждения” всех кубитов до |0;, а затем применить унитарное преобразование U, которое соответствует условию U |0; = |;;. Можно представить U как базовое преобразование, которое тривиально существует для любого желаемого |;;.
1.2.5 Измерение состояний
Измерение n кубитов уменьшает размерность H в 2n раз. Результат измерения зависит от амплитуды вероятности для определенной конфигурации битов.
Рассмотрим два квантовых регистра с n и m кубитами в состоянии
|;; =2n;1;i=0 2m;1; j=0 ci,j |i, j > с ;i,jc;i,j ci,j = 1 (1.7)
ГЛАВА 1. ВВЕДЕНИЕ 10
Базовые векторы |i, j; интерпретируются как пара двоичных чисел с i < 2n и j < 2m. Вероятность p(I) для измерения числа I в первом регистре и соответствующее состояние после измерения |;' I ; задаются через
p(I) = 2m;1;j=0 c;I,j cI,j и |;' I ; = 1/;p(I) 2м;1; j=0 cI,j |I, j> (1.8)
Измерение кубитов - единственная неунитарная операция, которую квантовый компьютер должен уметь выполнять во время вычислений.
1.3 Квантовое программирование
1.3.1 Квантовый параллелизм
Поскольку все унитарные преобразования являются линейными операторами, любая операция в- сформированное на основе квантового состояния, одновременно применяется ко всем его базовым векторам, таким образом
U ;ici|i; = ;iciU |i; (1.9)
Эта уникальная особенность квантовых компьютеров называется квантовым параллелизмом.
Поскольку число базовых векторов экспоненциально увеличивается с увеличением числа кубитов, можно решить определенные задачи (например, задачу Дойча-Йожсы [4]) за полиномиальное время (т.е. количество элементарных операций является полиномиальным значением длины входных данных), в то время как классическому компьютеру потребовалось
бы экспоненциальное число шагов.
1.3.2 Квантовые регистры
1.3.2.1 2-регистровые состояния
Поскольку кубиты квантового компьютера представляют собой возможное запутанное всеобщее состояние, строго говоря, не существует такого понятия, как подсостояние для конкретных кубитов, поскольку состояние n + m кубитов имеет вид
|;; = 2n;1; i=0 2m;1; j=0 aij |i, j; (1.10)
обычно не может быть записано как состояние произведения |;;|;; состояний n и m кубитов, поскольку обычно
|;; ; |;; ; |;; =2n;1;i=02m;1;j=0bicj |i, j; (1.11)
ГЛАВА 1. ВВЕДЕНИЕ 11
Однако, по аналогии с моделью вентиля- гейт (см. раздел 1.1.3), мы можем легко расширить понятие унитарных операторов n кубитов (см. раздел 1.3.3.1) для работы с состояниями n + m кубитов, используя расширенный оператор U1 (индекс указывает что это влияет на первый регистр):
U1 = U ; I(m) = 2n;1; i,j=0 2m;1; k=0 uij |i, k;j, k/ |1.12)
Первые n кубитов состояния n + m кубитов |; называются квантовым регистром n кубитов относительно оператора U .
U1 | ;> =2n-1;i,j=0 2m-1; k=0 2n;1;i'=0 2m;1; j'=0 uij ai'j' |i, k;;j, k|i', j'; =
2n;1; i,j,i'=0 2m;1; k,j'=0 uij ai'j' ;ji' ;k,j' |i, k; = 2n;1; i,j=0 2m;1; k=0 uij ajk |i, k; (1.13)
1.3.2.2 Изменение порядка регистров
Концепция квантовых регистров может быть расширена на произвольные последовательности кубитов.
Определение 1 (Квантовый регистр) Квантовый регистр s из n кубитов представляет собой
последовательность взаимно отличающихся нуль - основанных позиций кубита ;s0, s1 . . . sn-1; некоторого состояния |;; ; с N ; n.
Пусть s - n кубитный регистр n + m кубитного состояния /;;. Используя произвольную
перестановку ; над n + m элементами с ;i = si для i < n, мы можем построить оператор переупорядочивания ;s путем перестановки кубитов.
;s |b0, b1 . . . bl; = | ; при l = n + m (1.14)
Используя любые ;s и U1, мы можем определить применение U к регистру s в |;; как
U (s) |;; = ;†s U1 ;s /;; |1.15)
Обратите внимание, что, несмотря на то, что здесь представлено m! возможных реализаций ;s, определение U (s) уникально:
Определение 2 (Регистра операторы) Регистровый оператор для n-кубитного квантового регистра s с состоянием |;; ; C2N и унитарный оператор U : ; - это унитарный оператор N кубитов U (s) = ;†s (U ; I(m)) ;s.
ГЛАВА 1. ВВЕДЕНИЕ 12
1.3.3 Функции
1.3.3.1 Псевдоклассические операторы
Общий вид унитарного оператора U над n кубитами имеет вид
U =2n;1;i=0 2n;1;j=0|i> uij <j| при 2n;1;k=0u;kiukj = ;ij (1.16)
Если элементы матрицы uij имеют вид с некоторой перестановкой ;, то их влияние на чистые состояния (базовые векторы) можно описать в терминах классической обратимой булевой логики.
Определение 3 (Псевдоклассический оператор) Псевдоклассическим оператором является
унитарный оператор вида U : |i; ; |;i;.
Пусть f : - биективная функция, тогда соответствующий
псевдоклассический оператор F задается как
F =2n;1;i=0|f (i);;i/ и F -1 = F † =2n-1;i=0/i;;f (i)/ (1.17)
1.3.3.2 Манипуляции необратимыми функциями
Одной из очевидных проблем квантовых вычислений являются их ограничения к обратимым вычислениям. Рассмотрим простую арифметическую операцию типа целого деления на 2 (DIV2 ' |i; = |i/2; для четного i и |(i ; 1)/2; для нечетного i). Очевидно, что эта операция необратима, поскольку DIV2 '|0; = DIV2 ' / 1;, поэтому соответствующего псевдоклассического оператора не существует.
Однако, если мы используем второй регистр с начальным значением |0;, то мы можем
определить оператор DIV2 колдовски соответствует условию DIV2 / x, 0; = / x, x / 2;или
|x, (x-1) / 2; соответственно. Поведение DIV2 / x, y; 0; не определено и может быть задан произвольно при условии, что DIV2 является унитарным 6.
Определение 4 (Квантовые функции) Для любой функции f:Bn; Bm(или равно f: ) существует псевдоклассический оператор F : , работающие с входным регистром из n кубитов и выходным регистром из m кубитов с F |x, 0; = |x, f (x);. Операторы такого рода следует называть квантовыми функциями.
6 В данном конкретном случае всего один дополнительный кубит для хранения младшего бита аргумента достаточно чтобы расширить "DIV2" до унитарного оператора.
ГЛАВА 1. ВВЕДЕНИЕ 13
1.3.4 Управление промежуточным-скратч пространством
1.3.4.1 Повторное использование регистров
Покуда хранение копии аргумента будет позволять нам вычислять необратимые функции, оно же также вынуждает нас предоставлять дополнительную память для промежуточных результатов. При более длительных вычислениях это привело бы к постоянно растущему количеству "ненужных" битов, которые не имеют отношения к конечному результату. Простое и элегантное решение этой проблемы было предложено Беннетом [8, 9]: если функция f (x) = f (g(x)), то промежуточный результат может быть “переработан” (G и H - квантовые функции для g и h, индексы указывают на используемые регистры):
|x, 0, 0; G12 - </x, g(x), 0; H23 ; < / x, g(x), h(g(x)); G†12- x, 0, f (x); (1.18)
Последний шаг просто является инверсией первого шага и вычисляет средний результат. Затем можно повторно использовать второй регистр для дальнейших вычислений.
Без (с нуля ) скратч управления. оценка композиции по глубине требует d операций и используется d ; 1 ненужных джанк регистров. Вычисление по методу Беннета может быть использовано для сопоставления пространства и времени: Полное вычисление всех промежуточных результатов требует 2d-1 операций и d-1 скретч регистров, которые полезны, если скретч-данные могут быть повторно использованы при дальнейших вычислениях.
Комбинированное использование r регистров в качестве скретч-промежуточного и джанк- ненужного пространства , композиция глубины d = (r + 2)(r + 1)/2 может быть оценена с помощью 2d ; r-1 = (r +1)2 операций. Вычисление f (x) = l(k(j(i(h(g (x))))) для 4-регистровой машины (1 входной, 1 выходной и 2 скретч/джанк регистров) будет выполняться следующим образом (значения функций указаны в префиксной записи):
|x, 0, 0, 0; I34H23G12- </x, gx, hgx, ihgx; G†12 ЧАСОВ†23- </x, 0, 0, ihgx; J†
42K23J42;; (1.19)
|x, 0, kihgx, ihgx; L32
Используя этот метод мы можем уменьшить требуемое пространство O (1/;d) с вычислением расходов над O(2).
1.3.4.2 Ненужные-джанк регистры
Если вычисление функции f (x) заполняет скретч регистр с джанк битами j(x) (т.е. |x, 0, 0; ; / x, f(x), j (x);), аналогичная процедура может освободить
ГЛАВУ 1. ВВЕДЕНИЕ 14
регистр еще раз:
|x, 0, 0, 0; F123- 0; РАЗВЕТВЛЕНИЕ 24; f(x), f (x), f (x); F †123; < / x, 0, 0, f (x);(1.20)
И снова, последний шаг является инверсией первого. Промежуточный шаг операция РАЗВЕТВЛЕНИЯ, которая копирует результат функции в дополнительный пустой регистр (т.е. находящийся в подсостоянии |0;). Возможными реализациями являются, например , РАЗВЕТВЛЕНИЕ: (x + y) mod 2N; (1.21)
1.3.4.3 Перезапись обратимых функций
Как указывалось в разделе 1.3.3.1, каждой обратимой функции f: соответствует псевдослучайный классический оператор f : |i> |f (i)>. В то время как прямое осуществление F возможно с любым целостным набором псевдоклассических операторов7, реализация квантовой функции солидно более эффективна.
Если у нас есть эффективные реализации квантовых функций Uf :| i, 0;;
|i, f (i); и Uf -1 : |i, 0;; |i, f -1 (i);, то оператор перезаписи F' создается с использованием n кубитного скретч-регистра.
F ' : / i, 0;Uf- <|i, f (i); ПОМЕНЯТЬ МЕСТАМИ- f (i), i; U †;1;; |f (i), 0; (1.22)
1.3.5 Условные операторы
Классические программы допускают условное выполнение кода в зависимости от содержимого логической переменной (условное ветвление).
Унитарный оператор, с другой стороны, статичен и не имеет внутреннего управления потоком.8 Тем не менее, мы можем условно применить n-кубитный оператор U к квантовому регистру, используя разрешающий кубит и определяя n + 1 кубитный оператор U '
U ' = (I(n) 0
0 U)(1.23)
Таким образом, U применяется только к базовым векторам, для которых установлен разрешающий бит. Это может быть легко расширено до разрешающих регистров произвольной длины.
7 Одним из примеров может служить элемент Тоффоли T : |x, y, z; ; |x ; (y ; z), y, z;, который может быть использован для реализации любого псевдоклассического оператора для 3 или более кубитов
8 Можно возразить, что QTM на самом деле имеет внутреннее управление потоком, поскольку состояние и положение головки являются квантовыми регистрами. Однако здесь управление потоком относится к динамической генерации последовательности элементов-вентилей (гейтс), см. раздел 1.1.3
ГЛАВА 1. ВВЕДЕНИЕ 15
Определение 5 (Условный оператор) Условный оператор U[[e]] с разрешающим регистром e является унитарным оператором вида
U[[e]] : |i, ;; = |i;|;;e ;
{(U |i;) |;;e , если ; = 111 . . .
|i;|;;e в противном случае (1.24)
Условные операторы часто используются в арифметических квантовых функциях
и других псевдоклассических операторах.
Если архитектура позволяет эффективно реализовать элемент управления-"не" C : |x, y1, y2 . . .; ; |(x ; ;i yi), y1, y2 . . .;, тогда условные псевдоклассические операторы могут быть реализованы простым добавлением строки предоставить (enable) в регистр управления для всех операций управления- «не» (controlled-not).
Глава 2
QCL – квантовый Язык Расчета
2.1 Знакомство с QCL
2.1.1 Возможности
Как указывалось в разделе 1.1.4, QCL - это язык высокого уровня для квантового программирования. Его основными особенностями являются:
• классический язык управления с функциями, потоковым управлением, интерактивным вводом-выводом и различными классическими типами данных (int, real, complex, boolean, string).
• 2 типа квантовых операторов: общие унитарные (operator -операторы) и обратимые
псевдоклассические вентили (qufunct-куфунк)
• обратное выполнение, позволяющее на лету определять обратный оператор посредством кэширования вызовов операторов
• различные типы квантовых данных (кубитные регистры) для получения информации о режимах доступа во время компиляции (qureg-курег, quconst-куконст, quvoid-кувойд, quscratch-кускретч)
• удобные функции для управления квантовыми регистрами (q[n] - кубит,
q[n:m] - подстрока, q&p - комбинированный регистр)
• Управление квантовой памятью (quheap-кухип), позволяющее использовать локальные квантовые
переменные
• Прозрачная интеграция управления пространством scratch-скретч в стиле Bennet
16
ГЛАВА 2. QCL 17
• Простая адаптация к отдельным наборам элементарных операторов
Интерпретатор qcl дополнительно интегрирует числовой симулятор и оболочечную среду для интерактивного использования.
2.1.2 Пример: Дискретное преобразование Фурье в QCL
В таблице 2.1 показана QCL-реализация алгоритма Копперсмита [7] из быстрого квантового дискретного преобразования Фурье для квантовых регистров произвольной длины (подробнее см. раздел 3.2.3).
оператор dft(qureg q) _BOS_ // основной оператор
const n=#q; // присваивает n длине входных данных
int i; int j; // объявляет счетчики циклов
для значений от i=0 до n-1 {
для j=0 до i-1 { // применяет условные фазовые вентили
Фаза(2*pi/2^(i-j+1),q[n-i-1] и q[n-j-1]);
}
Смешивание(q[n-i-1]); // вращение кубита
}
flip(q); // поменять местами порядок битов выходных данных
}
Таблица 2.1: Дискретное преобразование Фурье dft.qcl в QCL
По сути, dft.qcl содержит два цикла: Внешний цикл выполняет Преобразования Адамара (см. раздел 3.1.1.3) от старшего кубита к младшему (Mix), в то время как внутренний контур выполняет условные фазовые сдвиги (Cphase) между кубитами.
Оператор dft принимает квантовый регистр (qureg) q в качестве аргумента. Как указывалось в разделе 1.3.2, квантовый регистр - это не квантовое состояние само по себе, а указатель, указывающий целевые кубиты в общем состоянии машины, точно так же, как входные и выходные линии в модели вентиля (gate). Чтобы разрешить определение оператора, не зависящего от размера регистра, количество кубитов в регистре может быть определено во время выполнения с помощью оператора # размера.
Внутри определения оператора вложенные операторы могут вызываться так же, как и подпроцедуры в классических процедурных языках. Это означает, что фактическая последовательность операторов (как встроенных, так и определенных пользователем) может быть полностью определена во время выполнения, включая использование циклов (в данном случае «для-цикл»( for-loops)), условных операторов и т.д.
В отличие от большинства классических языков, QCL имеет строгую математическую последовательность функций и операторов, что означает, что два последующих вызова с использованием
ГЛАВА 2. QCL 18
одних и тех же параметров должны приводить к точно такой же операции. Это относится-
требует, чтобы операторы были свободны от побочных эффектов, и запрещает использование глобальных переменных.
Это обеспечивает выполнение в зависимости от контекста: DFT(q), вызываемый с верхнего ур вня, работает ожидаемо, однако, если вызывается как !DFT(q) (присоединение, таким образом, инверсия для унитарных операторов), все операторы в DFT также инвертируются и применяются в обратном порядке. Обратное выполнение также может выполняться неявно, когда используются локальные квантовые регистры и управление пространством с нуля в стиле Беннета.
Чтобы продемонстрировать использование нового оператора, давайте запустим интерпретатор QCL и подготовим тестовое состояние:
$ qcl -b5 -i dft.qcl
[0/5] 1 |00000>
qcl> создать q[5]; // выделить регистр из 5 кубитов
qcl> Смешать(q[3:4]); // повернуть кубиты 3 и 4
[5/5] 0.5 |00000> + 0.5 |10000> + 0.5 |01000> + 0.5 |11000>
qcl> Not(q[0]); // инвертировать первый кубит
[5/5] 0.5 |00001> + 0.5 |10001> + 0.5 |01001> + 0.5 |11001>
Теперь у нас есть периодическое состояние с периодом 23 = 8 и смещением 1, состоящее
из 4 базовых векторов, к которым мы можем применить DFT.
qcl> dft(q);
[5/5] 0.353553 |00000> + -0.353553 |10000> + 0.353553 i |01000> +
-0.353553я |11000> + (0.25,0.25) |00100> + (-0.25,-0.25) |10100> +
(-0.25,0.25) |01100> + (0.25,-0.25) |11100>
Дискретное преобразование Фурье “инвертирует” период до 25/8 = 4 и приводит к периодическому распределению со смещением 0. Информация об исходном смещении содержится в фазовых коэффициентах и не влияет на распределение вероятностей:
qcl> dump q;
: СПЕКТР q: |43210>
0.125 |00000> + 0.125 |00100> + 0.125 |01000> + 0.125 |01100> +
0.125 |10000> + 0.125 |10100> + 0.125 |11000> + 0.125 |11100>
“Вычисление” DFT возвращает исходную конфигурацию:
qcl> !dft(q);
[5/5] 0.5 |00001> + 0.5 |10001> + 0.5 |01001> + 0.5 |11001>
qcl> выход;
2.1.3 Интерпретатор QCL
Интерпретатор qcl имитирует квантовый компьютер с произвольным числом кубитов (по умолчанию используется системная длина слова) и вызывается со следующим интаксисом:
qcl [параметры] [QCL-файл] . . .
ГЛАВА 2. QCL 19
2.1.3.1 Параметры
qcl принимает следующие параметры командной строки (значения по умолчанию приведены в параграфах):
Параметры запуска:
-h, --помощь выводит это сообщение в справке
-V, --версия отображает информацию о версии
-i, --интерактивный режим принудительного взаимодействия
-n, --no-default-include не читает значение по умолчанию.qcl при запуске
(--нет значений по умолчанию)
-o, --logfile укажите файл журнала
(-- файл колода)
-b, --bits=n: заданное количество кубитов (32)
Динамические параметры (могут быть изменены с помощью инструкции set):
-s, --seed=<начальное значение> задает случайное начальное значение (системное время)
-I, --include-path=<путь> QCL включает путь (.)
-p, --dump-prefix=<префикс файла> задает префикс файла дампа
-f, --dump-format=b,a,x выводят базовые векторы в шестнадцатеричном, автоматическом или двоичном виде (a)
-d, --debug=<y|n> открывать отладочную оболочку при ошибке (n)
-a, --auto-dump=<y|n> всегда сбрасывать квантовое состояние в режиме оболочки (n)
-l, --log==<y|n> регистрировать вызовы внешних операторов (n)
-L, --логарифмическое состояние==<y|n> логарифмическое состояние после каждого преобразования (n)
-T, --трассировка==<y|n> режим трассировки (очень подробный) (n)
-S, --синтаксис=<y|n> проверяйте только синтаксис, без интерпретации (n)
-E, --echo=<y|n> эхо-анализ входных данных (n)
-t, --test=<y|n> тестируем программу, игнорируем квантовые операции (n)
-e, --shell-escape=<y|n> выполняем экранирование оболочки (y)
-r, --allow-redefines=<y|n> игнорировать переопределения вместо ошибки (n)
Логические значения могут быть заданы в любом распространенном формате, включая y[es]/n[o], 0/1 и t[rue]/f[alse]. Динамические параметры также могут быть вызваны из
командной строки или QCL-программами с помощью команды set.
2.1.3.2 По умолчанию они включают
Если параметр --no-default-include не отключен, qcl интерпретирует включенный по умолчанию файл по умолчанию default.qcl при запуске. Если в командной строке не указаны файлы, qcl запускается в интерактивном режиме, в противном случае файлы выполняются в заданном порядке, и qcl завершает работу.
2.1.3.3 Интерактивное использование
При запуске в интерактивном режиме (без указания файлов или опции -i) qcl переходит в командную строку верхнего уровня и запрашивает ввод данных пользователем (qcl>). Вложенные оболочки с закрытой областью действия (см. раздел 2.2.4.4) могут быть открыты командной оболочкой; в этом случае запрос будет qcln>, где n указывает на нулевую основанную на нуле) глубину вложенности. Вложенные оболочки также открываются в случае ошибок, когда --debug=yes и запрашивается qcln$.
ГЛАВА 2. QCL 20
qcl> установить значение debug true; // включить отладку.
qcl> real inv(реальный x) { возвращает 1/x; }
qcl> print inv(0.0); // вызывает ошибку
! в функции inv: математическая ошибка: деление на ноль
qcl1$ list x; // это аргумент для fac
: локальный символ x = 0.000000:
real x
qcl1$ exit; // закрыть отладочную оболочку
qcl> список x; // глобальный x не определен
: символ x не определен.
Оболочка закрывается с помощью EOF (обычно Ctrl-d) или командой exit.
Закрытие оболочки верхнего уровня завершает работу программы.
2.1.4 Структура программы QCL
2.1.4.1 Нотация (обозначения)
Синтаксическая структура программы на QCL описывается контекстно-свободной грамматикой LALR(1) (см. приложение B.1). Для формального определения синтаксических
выражений используется следующая нотация:
название выражения ; определение выражения 1
; определение выражения 2
· · · · · ·
В определениях выражений применяются следующие условные обозначения
Ключевые слова и другой текстовый текст задаются в courier
Подвыражения выделяются курсивом
Необязательные выражения заключаются в [ квадратные скобки ] Необязательные выражения могут повторяться 0 или 1 раз.
Несколько выражений заключаются в { фигурные скобки }. Несколько выражений могут быть повторяется 0, 1 или n раз.
Варианты записываются в виде alt 1| alt 2| . . .
Необходимо выбрать только один вариант.
Группировка выражений может быть принудительной (круглые скобки).
Для упрощения обозначения литералов определены следующие классы символов
:
ГЛАВА 2. QCL 21
• цифра - десятичная цифра от 0 до 9.
• буква - буква алфавита от а до я или от А до Я. Важен регистр.
• символ - печатаемый символ, за исключением ‘".
Программа QCL - это, по сути, последовательность инструкций и определений , считываемых либо из файла, либо непосредственно из командной строки. (В последнем случае ввод ограничивается одной строкой, которая неявно завершается символом ‘;’.)
qcl-input ; { stmt | def }
2.1.4.2 Инструкции
Инструкции варьируются от простых команд, от вызовов процедур до сложных структур управления и выполняются при их обнаружении.
qcl> if random()>=0.5 { выводится "красный"; } else { выводится "черный"; }
: красный
2.1.4.3 Определения
Определения не выполняются, но привязывают значение (определение переменной или константы) или блок кода (определение процедуры) в символ (идентификатор).
qcl> int counter=5;
qcl> int fac(int n) { если n<=0 {возвращает 1;} else {возвращает n*fac(n-1);} }
Следовательно, каждый символ имеет связанный с ним тип, который может быть либо типом данных, либо типом процедуры и определяет, осуществляется ли доступ к символу посредством ссылки или вызова.
2.1.4.4 Выражения
Многие операторы и процедуры принимают аргументы определенных типов данных. Эти
выражения могут состоять из литералов, ссылок на переменные и подвыражений
, объединенных операторами и вызовами функций.
qcl> выведите "5 из 10:",fac(10)/fac(5)^2,"комбинации".
: 5 из 10: 252 комбинаций.
ГЛАВА 2. QCL 22
Комментарии 2.1.4.5
Как и в C++, QCL поддерживает два способа комментирования кода. Все комментарии
просто отбрасываются сканером.
Комментарии к строке начинаются с // и продолжаются до конца текущей строки
Комментарии в стиле C начинаются с /* и заканчиваются на */ и могут продолжаться на протяжении нескольких строк. Комментарии в стиле C могут не быть вложенными.
2.1.4.6 Включаемые файлы
Команда include "filename" указывает интерпретатору обработать файл filename.qcl, прежде чем продолжить работу с текущим входным файлом или командной строкой. qcl ищет файл в текущем каталоге и в каталоге include по умолчанию, который можно изменить с помощью параметра include-path.
При интерактивном использовании include "имя файла" может быть сокращено до <<имя файла.
2.2 Классические выражения и переменные
2.2.1 Константные выражения
Классическими типами данных QCL являются арифметические типы int, вещественные и
комплексные, а также общие типы boolean и string.
Типов Описания Примеры
int integer 1234, -1
real действительное число 3.14, -0.001
complex сложное комплексное число (0,-1), (0.5, 0.866)
boolean логическое значение true, false
string строка символов "hello world", ""
Таблица 2.2: классические типы и литералы
2.2.1.1 Целое число
Тип QCL int основан на типе данных C, обозначаемом как long. На 32;разрядныхкомпьютерах это обычно позволяет использовать значения от -231 до 231 - 1. Хотя этого более чем достаточно для любой стандартной задачи программирования, реализация некоторых комбинаторных функций может потребовать некоторого внимания.
ГЛАВА 2. QCL 23
Однако ограничение длины слова никак не влияет на количество кубитов которые могут быть смоделированы на основе максимального размера квантовых регистров. 1
2.2.1.2 Действительные числа
Тип QCL real основан на типе данных C double, который обычно является 64-разрядным. Чтобы улучшить читаемость, вывод действительных чисел сокращен до разумного количества цифр.
Действительные числа записываются в десятичной системе счисления и должны
содержать десятичную точку.
2.2.1.3 Комплексные (сложные)
Комплексные числа QCL внутренне представлены в виде двух двойных чисел с плавающей точкой. Это справедливо для переменных типа complex, а также для внутреннего представления состояния машины. Комплексные числа представлены в виде (действительных,воображаемых) пар:
const ; ( комплексная координата , complex-coord )
комплексная координата ; [ + | - ] цифра { digit } [ . { digit }]
2.2.1.4 Логическое значение
В отличие от C, логические значения в QCL имеют свой собственный тип данных. Литералами для логических значений являются значения true и false:
2.2.1.5 Строки
Строковые литералы заключаются в кавычки "символьная строка" и могут содержать любой печатаемый символ, кроме "".
2.2.2 Операторы
2.2.2.1 Арифметические операторы
Арифметические операторы обычно работают со всеми арифметическими типами данных и возвращают наиболее общий тип (перегрузка оператора), например
. qcl> print 2+2; // возвращает значение int
: 4
qcl> вывести 2+2.0; // вычисляется как реальный
: 4.000000
qcl> вывести 2+(2,0); // вычисляется как сложный
: (4.000000,0.000000)
1 Поскольку квантовые измерения также возвращают целые числа, измерения должны быть разделены для больших регистров
ГЛАВА 2. QCL 24
Чтобы обеспечить чистую целочисленную арифметику, существуют некоторые исключения, позволяющие избежать
приведения типов:
• Оператор деления / выполняет целочисленное деление, если оба аргумента являются
целыми числами.
• Оператор модуля mod определен только для целочисленных аргументов.
• Оператор степени ^ для целых оснований определен только для неотрицательных целых показателей. Для действительных показателей основание должно быть неотрицательным.
В таблице 2.3 приведены все арифметические операторы, упорядоченные по старшинству. Все бинарные операторы являются левоассоциативными, таким образом, a ; b ; c = (a ; b) ; c. Явная группировка может быть достигнута с помощью круглых скобок.
Операция Описание Пример Тип Значение
^ степень (0,1)^-1,5 комплексная ; 1;2 (1 + i)
целочисленная степень (-2)^11 int -2048
- унарный минус -1 целое 1
* умножение (0,1)*(0,1) комплексное -1
/ деление 3./2 действительное 3/2
целочисленное деление 3/2 целое 1
по модулю целое число по модулю 100 по модулю 16 целое 4
+ сложение 1,5+1,5 действительное 3
- вычитание (1,2)-(0,2) комплексное 1
Таблица 2.3: арифметические операторы
2.2.2.2 Операторы сравнения и логические операторы
В таблице 2.4 приведены все операторы сравнения и логические операторы с их типами аргументов.
Возвращаемый тип всех операторов - boolean.
2.2.2.3 Другие операторы
QCL определяет еще два оператора, которые в основном используются с квантовыми
выражениями. Они описаны в разделе 2.3.3 и упомянуты только для полноты картины.
Конкатенация Оператор конкатенации & объединяет два квантовых регистра или две строки. Его приоритет равен арифметическим операторам + и -.
ГЛАВА 2. QCL 25
Операции Описания Тип аргумента
== равны все арифметические значения, строка
!= неравны все арифметические значения, строка
< меньшее целое число, действительное
<= меньшее или равное целое число, действительное
> большее целое число, действительное
>= большее или равное целое число, действительное
или логическое включающее или логическое
исключающее или логическое исключающее или логическое значение
Таблица 2.4: сравнение и логические операторы
Размер Оператор размера # определяет длину (т.е. количество кубитов) любого квантового выражения. Это оператор с наивысшим приоритетом.
2.2.3 Функции
В отличие от пользовательских функций (см. раздел 2.5.2), большинство встроенных функций QCL перегружены. Как и арифметические операторы, они часто принимают более
одного типа аргументов и возвращают значения разных типов.
2.2.3.1 Тригонометрические функции
Тригонометрические функции (таблица 2.5) определены для аргументов int, вещественных и комплексных значений. Возвращаемый тип - вещественный или комплексный, в зависимости от типа аргумента.
qcl> print sin(0); // целочисленные или вещественные аргументы
: 0.000000 // вычисляются как действительные, даже если
qcl> print sin(pi); // результатом является целое число
: 0.000000
qcl> вывести tanh((0,1)*pi); // комплексные аргументы вычисляются
: (0,000000,-0,000000) // в комплексные
2.2.3.2 Экспоненты и логарифмы
exp, log и sqrt также работают со всеми типами арифметики (таблица 2.6). Квадратные корни
из отрицательных действительных чисел вызывают ошибку, как и неположительные действительные логарифмы.
ГЛАВА 2. QCL 26
Функция. Описание функции. Описание
sin(x) синус x sinh(x) гиперболический синус x
cos(x) косинус x cosh(x) гиперболический косинус x
tan(x) тангенс x, tanh(x) гиперболический тангенс x
, cot(x) котангенс x, coth(x) гиперболический котангенс x
Таблица 2.5: тригонометрические и гиперболические функции
qcl> вывести sqrt(-1);
! математическая ошибка: действительный квадратный корень из отрицательного числа
qcl> вывести log(-1.0);
! математическая ошибка: действительный логарифм неположительного числа
qcl> напечатать sqrt((-1,0)),log((-1,0));
: (0.000000,1.000000) (0.000000,3.141593)
Функция. Описание
exp(x) e, возведенный в степень x
log(x) натуральный логарифм x
log(x,n) по основанию-n логарифм x
sqrt(x) квадратный корень из x
Таблица 2.6: Экспоненциальные и связанные с ними функции
2.2.3.3 Комплексные числа
Для обработки и преобразования сложных выражений определены функции Re, Im, abs
и conj (таблица 2.7). abs также работает с аргументами real и int.
Функция. Описание
Re(z) действительная часть z
Im(z) мнимая часть z
abs(z) величина z
conj(z) комплексно сопряженная с z
Таблица 2.7: функции для комплексных чисел
2.2.3.4 Округление
Для значений ceil(x) и floor(x) действительное значение x округляется в большую или меньшую сторону до ближайшего целого числа. Округленное значение возвращается в виде int.
ГЛАВА 2. QCL 27
2.2.3.5 Максимум и минимум
Функции max и min принимают произвольное количество значений int или вещественных аргументов- определяет и возвращает максимальное или минимальное значение. Тип возвращаемого значения — int, если все аргументы являются целыми, и вещественными в противном случае.
qcl> вывести max(3,pi,4);
: 4.000000
2.2.3.6 GCD и LCM
Наибольший общий делитель и наименьшее общее кратное из списка целых чисел могут быть определены с помощью gcd и lcm.
qcl> печать в формате gcd(48,72,180),lcm(48,72,180);
: 12 720
2.2.3.7 Случайные числа
Псевдофункция random() возвращает случайное значение из интервала [0, 1). Генерацию случайных чисел можно определить, указав начальное значение с помощью опции --seed. Случайные числа не могут использоваться в определение функций и квантовых операторов.
Функция. Описание
ceil(x) - ближайшее целое число к x (округлено в большую сторону)
floor(x) - ближайшее целое число к x (округлено в меньшую сторону)
max(x,...) максимальное
min(x,...) минимальное
gcd(n,...) наибольший общий делитель
lcm(n,…) наименьшее общее кратное
random() случайное значение из [0, 1)
Таблица 2.8: другие функции QCL
2.2.4 Символы
2.2.4.1 Идентификаторы
Идентификаторы могут содержать только буквенно-цифровые символы (без подчеркивания) и должны начинаться с буквы. Как и в C, здесь нет ограничений по длине и важен регистр. Имена не должны совпадать с внутренними ключевыми словами.
ГЛАВА 2. QCL 28
2.2.4.2 Константы
Часто используемые значения могут быть определены как символьные константы. Синтаксис
объявления константы -
const-def ; const identifier = expr ;
Определение pi в стандартном включаемом файле таково, например
, const pi=3.141592653589793238462643383279502884197;
Определения констант не ограничиваются константными выражениями, но сохраняют свое
значение после определения:
qcl> начальное значение const=random();
qcl> начальное значение print;
: 0.378990
qcl> начальная версия печати;
: 0.378990
2.2.4.3 Переменные
Определение переменных в QCL аналогично C:
var-def ; идентификатор типа [ = expr ] ;
Классическими типами данных являются int, real, complex, boolean и string (см. раздел 2.2.1). Если начальное значение не задано, новая переменная инициализируется нулем, false или "" соответственно.
Значение переменной может быть изменено с помощью присваивания (assignment), а также нескольких других инструкций (см. раздел 2.4):
qcl> complex z; // объявляем комплексную переменную z
qcl> вывести z; // значение z было инициализировано значением 0
: (0,000000,0,000000)
qcl> z=(0,1); // значение z равно i
qcl> вывести z;
: (0.000000,1.000000)
qcl> z=exp(z*pi); // присвоение z может содержать z
qcl> вывести z;
: (-1.000000,0.000000)
qcl> ввести z; // запросить ввод данных пользователем
? сложный z [(Re,Im)]? (0.8,0.6)
qcl> вывести z;
: (0.800000,0.600000)
Поскольку значения переменных по определению не уникальны, доступ к глобальным переменным невозможен в подпрограммах с математической семантикой, а именно в функциях и (псевдоклассических) операторах.
ГЛАВА 2. QCL 29
2.2.4.4 Области и пространства имен
Все символы используют одно и то же пространство имен, поэтому все глобальные идентификаторы должны быть уникальными, даже если они обозначают разные объекты. Чтобы гарантировать согласованное поведение определенных функций и операторов, невозможно отменить определение после объявления глобального символа.
qcl> int f;
qcl> int f(int n) { возвращает f^2; }
! недопустимая область применения: глобальный символ f уже определен
Параметр --allow-redefines может использоваться для устранения ошибок при повторном объявлении символа. В этом случае переопределения автоматически игнорируются, и обработка входного файла или строки продолжается. Это может быть полезно для безопасного включения файлов или скрытия определений частными версиями:
qufunct flip(qureg q) { /* определяю свою собственную версию flip */ }
set allow-переопределяет значение true;
включает "dft"; // перевернутая версия в dft.qcl игнорируется
, set allow-переопределяет значение false;
Определение символа можно отобразить с помощью команды list (пример приведен ниже
).
При интерактивном использовании qcl (см. раздел 2.1.3.3) команда shell может использоваться для открытия подоболочки с временной областью действия. Это означает, что новые определения действительны только в текущей подоболочке.2 Все временные символы
снова уничтожаются, когда в подоболочке остается значение exit.
qcl> список x;
: символ x не определен.
qcl> оболочка;
: экранирование оболочки
qcl1> int x;
qcl1> список x;
: глобальный символ x = 0:
int x;
qcl1> выход
qcl> список x;
: символ x не определен.
2 Обратите внимание, что это не ставит под угрозу математическую семантику функций и операторов, поскольку наличие используемых глобальных символов проверяется уже при определении процедуры , а не только во время выполнения.
ГЛАВА 2. QCL 30
2.3 Квантовые регистры и выражения
2.3.1 Регистры и состояния
2.3.1.1 Состояние компьютера и состояние программы
Память квантового компьютера обычно представляет собой комбинацию подсистем с двумя состояниями, называемых квантовыми битами (кубитами). Как указывалось в разделе 1.2.2 , “содержимое памяти” - это объединенное состояние всех кубитов. Это состояние повторно-
понимается как (квантовое) состояние машины в отличие от состояния программы, которое является текущим состоянием управляющего (классического) алгоритма (например, содержимое переменной, стек выполнения и т.д.) 3.
Машинное состояние |;> n–кубитного квантового компьютера представляет собой вектор в гильбертовом пространстве , однако из–за разрушительного характера
измерений (см. раздел 1.2.5) |;> невозможно непосредственно наблюдать.
2.3.1.2 Квантовые регистры
QCL использует концепцию квантовых регистров (см. раздел 1.3.2) в качестве интерфейса между состоянием машины и управляющим алгоритмом. Квантовый регистр является указателем на последовательность (взаимно отличающихся) кубитов, и все операции с состоянием машины (за исключением команды сброса, см. раздел 2.4.2.2) принимают квантовые регистры в качестве аргументов.
Поскольку квантовый компьютер с n кубитами допускает n!/(n;m)! различные m кубитных регистров, любая унитарная операция или операция измерения в m кубитном регистре могут привести к n!/(n;m)! различным операциям с состоянием машины:
Пусть s - это m кубитных регистров, охватывающих кубиты в нулевых позициях ;s0, s1 . . . sm;1; (с si6 = sj для всех i, j < m) состояния n кубитного автомата |;; и Op являются операторами объединения кубита или измерения, тогда операция Op(s) регистра соответствует следующей операции состояния машины (см. раздел 1.3.2.2):
Op(s) : |;; ; R†s (Op ; I(n - m)) Rs /;; (2.1)
Оператор переупорядочивания Rs и оператор идентификации k-кубита I(k) определены
в (1.15) и (1.2) соответственно.
2.3.1.3 Управление памятью
В QCL связь между регистрами и кубитами обрабатывается прозрачно путем выделения и разгрузки кубитов квантовой кучи, что позволяет
3Отметим, что QTM в этом смысле не имеет программного состояния, поскольку не подчиняется никаким классическим мета-алгоритмам
ГЛАВА 2. QCL 31
использование локальных квантовых переменных. Вся свободная (т.е. нераспределенная) квантовая память должна быть пустой.
Определение 6 (Пустые регистры) Квантовый регистр s считается пустым, если
P0(s) |;; = |;; с P0 = |0;;0| (2.2)
При запуске или после команды сброса все состояние машины пустое, таким образом /;; | /0;.
Псевдоклассические операторы (qufunct) позволяют использовать локальные квантовые переменные в качестве промежуточного скретч пространства (см. раздел 1.3.4). Когда выделяются временные промежуточные регистры (quscratch), управление памятью должно отслеживать все точки доступа.- выполняйте операции до тех пор, пока локальный регистр снова не будет освобожден. Затем регистры результатов сохраняются с помощью разветвления, и вычисление выполняется в обратном порядке.
Пользователь может переопределить управление памятью по умолчанию, явно исключив локальные переменные из вычисления, объявив их общими регистрами qureg (см. раздел 2.3.2.1). В этом случае ответственность за надлежащую очистку лежит на
программисте.
2.3.1.4 Моделирование
В то время как QCL – как язык программирования – предназначен для работы с любой архитектурой квантового компьютера на основе кубитов, разработка необходимых аппаратных средств, скорее всего, потребуется еще несколько десятилетий. Вот почему QCL также поддерживает моделирование квантовых компьютеров и предоставляет специальные команды для доступа к (моделируемому) состоянию машины.
Интерпретатор qcl может моделировать квантовые компьютеры с произвольным количеством кубитов (опция --bits). Фактически сохраняются только базовые векторы с ненулевой амплитудой, поэтому использование начальных регистров не требует дополнительной памяти.
Все численные расчеты выполняются библиотекой квантовых вычислений. Пожалуйста, обратитесь к [17] для получения более подробного описания.
2.3.2 Квантовые переменные
Квантовые регистры, связанные с символическим именем, называются квантовыми
переменными.
2.3.2.1 Общие регистры
Общий квантовый регистр с n = expr кубитами может быть объявлен с
помощью идентификатора
var-def ; qureg indentifier [ expr ] ;
ГЛАВА 2. QCL 32
Пустая квантовая память выделяется из кучи и привязывается к символьному идентификатору.
Объявление в глобальной области видимости определяет постоянный квантовый регистр, который не подвержен искажениям при управлении промежуточным пространством. Это означает, что, как и в случае с классическими глобальными переменными, нет способа вернуть выделенные кубиты в пределах одной оболочки.
Если глобальный регистр определен в подоболочке (см. раздел 2.2.4.4) и подоболочка закрывается, символ уничтожается, а выделенные кубиты снова помечаются как свободные. Программист должен гарантировать, что освобожденные кубиты на самом деле пусты.
qcl> qureg q[1]; // выделяем кубит
qcl> Rot(-pi/2,q); // выполняем вращение одного бита
[1/4] 0.707107 |0000> + 0.707107 |0001>
qcl> оболочка; // открыть подоболочку
: shell escape
qcl1> qureg p[1]; // выделить другой кубит
qcl1> Rot(-pi/2,p); // также повернуть регистр p
[2/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl1> exit; // покинуть подоболочку
qcl> dump; // прежний регистр p не пуст
: СОСТОЯНИЕ: 1/4 кубита выделено, 3/4 кубита свободны.
0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> список p; // однако символ p не определен
: символ p не определен.
Сброс состояния компьютера с помощью команды reset не влияет на привязку регистров.
[0/4] 1 |0000>
qcl> qureg q[1]; // выделяем кубит
qcl> сброс; // сброс: |Psi> -> |0>
[1/4] 1 |0000>
qcl> список q; // регистр q все еще существует
: глобальный символ q = |...0>:
qureg q[1];
Квантовые типы quvoid и quscratch ограничены псевдоклассическими операторами (qufunct) и эквивалентны qureg, за исключением того, что они обрабатываются по-другому с помощью управления памятью (подробности см. в разделе 2.5.6.3).
2.3.2.2 Квантовые константы
Регистры можно объявить постоянными, используя регистровый тип quconst. Квантовая константа должна быть инвариантной ко всем применяемым операторам.
4 Обратите внимание, что правильное вычисление возможно только в том случае, если с момента выделения памяти не выполнялись необратимые операции типа измерений.
ГЛАВА 2. QCL 33
Определение 7 (Инвариантность регистров) Квантовый регистр c считается инвариантным к регистровому оператору U (s, c), если U удовлетворяет условию
U : |i, j> = |i>s|j>c ; (Uj |i>s) |j>c (2.3)
Квантовой константы имеют фиксированный спектр вероятности: пусть |;; = ; аіј |i, j;
такой конечный автомат и |;'; = U (s, c) |;; и P(J) и Р'(К) вероятности измерения J в регистр C до и после применения оператора, тогда
Хотя глобальные регистры могут быть объявлены как квантовые константы, это не так.-
особенно полезно, поскольку нет возможности изменить спектр регистра, и , следовательно, регистр всегда будет пустым.
qcl> quconst c[1];
qcl> Mix(c);
! несоответствие параметров: quconst используется в качестве неконстантного аргумента для смешивания
Если аргумент оператора объявлен как quconst, регистр должен быть инвариантным ко всем последующим вызовам оператора в пределах определения оператора.
qcl> operator foo(quconst c) { Rot(pi,c); }
! в operator foo: несоответствие параметров: quconst используется в качестве неконстантного
аргумента для Rot
При использовании в качестве типа аргумента квантовой функции константы регистры
не заменяются при вычислении локальных промежуточных регистров (см. раздел 2.5.5).
2.3.2.3 Пустые регистры
Если аргумент v для оператора объявлен quvoid, ожидается, что квантовый реестр будет пустым при обычном вызове оператора (см. раздел 2.4.1.2) или будет вычислен, если оператор вызывается инвертированным. Таким образом, в зависимости от флага присоединения оператора, состояние машины |;; должно соответствовать либо
U (v, . . .) : |;; = |0;v|;; ; |;'; или U †(v, . . .) : |;; ; |0;v|;'; (2.6)
Это можно проверить во время выполнения с помощью опции --check.
ГЛАВА 2. QCL 34
qcl> qureg q[4];
qcl> настроить p[4];
qcl> установить проверку 1; // включить проверку согласованности
qcl> Rot(pi/100,p[2]); // слегка повернуть один целевой кубит
[8/8] 0.999877 |00000000> + -0.0157073 |01000000>
qcl> Разветвление(q,p); // p считается пустым
! в qufunct Разветвление: ошибка памяти: void или пустой регистр не пуст
При использовании в качестве типа аргумента квантовой функции регистры void заменяются на временный регистр, если вычисляются локальные промежуточные регистры.
2.3.2.4. Регистры промежуточные
В качестве аргументов оператора рассматриваются регистры типа quscratch это должны быть явные начальные регистры, которые должны быть пустыми при вызове оператора и должны быть вычислены до завершения работы оператора, поэтому оператор и состояние машины должны удовлетворять условию
U (s, . . .) : |;; = |0;s|;; ; |0;s|;'; = |;'; (2.7)
Как с quvoid, это проверено во время выполнения, если параметр —check проверить имеет значение.
Если в теле квантовой функции определен нулевой регистр, для повторного заполнения регистра используется вычисление в стиле Беннета, описанное в разделе 1.3.4.2
(подробное объяснение приведено в разделе 2.5.5).
Квантовые функции, использующие локальные начальные регистры, могут не принимать общие регистры (qureg) в качестве аргументов.
qcl> qufunct nop(qureg q) { quscratch s[1]; }
! недопустимый тип: локальные регистры scratch не могут использоваться с
аргументами qureg
2.3.2.5 Ссылки регистра
Для удобства обращения к подрегистрам или комбинированным регистрам (см. ниже)
квантовым выражениям можно присвоить имена, объявив ссылку на регистр.
def ; идентификатор типа [ = expr ] ;
Квантовое выражение expr привязано к регистра идентификатору типа quantum type, который может быть qureg или quuconst.
qcl> qureg q[8];
qcl> количество странных битов=q[1]&q[3]&q[5]&q[7];
qcl> количество слабых битов=q[0:3];
qcl> список q,странные символы,младшие символы;
: глобальный символ q = |........76543210>:
qureg q[8];
: странные символы глобального символа = |........3.2.1.0.>:
курег случайных чисел;
: младшие значения глобальных символов = |............3210>:
курег случайных чисел;
ГЛАВА 2. QCL 35
Ссылки также могут быть использованы для переопределения проверки типов путем повторного объявления quconst как qureg, что может быть полезно, если постоянный аргумент должен временно использоваться в качестве пробела, но позже восстанавливается. Смотрите пример реализации модульного добавления (addn) в разделе 3.2.2.1 (стр. 62).
2.3.3 Квантовые выражения
Квантовое выражение - это анонимная ссылка на регистр, которая может использоваться
в качестве аргумента оператора или для объявления именованных ссылок (см. выше).
Выражение. Описание Регистр
a ссылку ;a0, a1 . . . an;
a[i] кубит ;ai;
а[i:j] подстроки ;ai, ai+1 . . . aj ;
а[i\j] подстроки ;ai, ai+1 . . . aj+l-1 ;
a&b конкатенации ;a0, a1 . . . an, ;b0, ba1 . . . bm ;
Таблица 2.9: квантовые выражения
2.3.3.1 Подрегистры
К подрегистрам можно обращаться с помощью оператора подстрочного индекса [. . .]. В зависимости от синтаксиса (см. таблицу 2.9) отдельные кубиты задаются их нуля основанным смещением и подстроки задаются смещением первого кубита и либо смещением последнего кубита (синтаксис [. . .:. . .]) ), либо общей длиной подрегистра (синтаксис [. . .\. . .]).
qcl> создать q[8];
qcl> вывести q[3],q[3:4],q[3\4];
: |....0...> |...10...> |.3210...>
Индексы могут быть произвольными выражениями типа int. Недопустимые индексы приводят ошибке.
qcl> int i=255;
qcl> print q[этаж(журнал(i,2))];
: |0.......>
qcl> вывести q[floor(log(i,2))\2];
! ошибка диапазона: недопустимый квантовый подрегистр
ГЛАВА 2. QCL 36
2.3.3.2 Комбинированные регистры
Регистры можно объединить с помощью оператора конкатенации &. Если регистры
перекрываются, возникает ошибка.
qcl> вывести q[4:7]&q[0:3];
: |32107654>
qcl> вывести q[2]&q[0:3];
! ошибка диапазона: квантовые регистры перекрываются
2.4 Инструкции
2.4.1 Элементарные команды
2.4.1.1 Назначение
Значение любой классической переменной может быть задано оператором присваивания =.
Правое значение должно быть того же типа, что и переменная. В отличие от арифметических операторов и встроенных функций, неявное приведение типов не выполняется.
qcl> сложный z;
qcl> z=pi; // нет приведения
к типу! несоответствие типов: недопустимое присвоение
qcl> z=conj(pi); // неявное приведение типов
Поскольку квантовые переменные потенциально подвержены управлению памятью, ни квантовые регистры, ни ссылки на регистры не могут быть переназначены.
qcl> qureg q[2];
qcl> quref p=q[0];
qcl> p=q[1];
! недопустимый тип: присвоение квантовой переменной
2.4.1.2 Вызов
Могут быть вызваны обычные типы procedure, operator и qufunct.
Stmt ; [ ! ] identifier ( [ expr { , expr }] ) ;
Как и в случае с присваиваниями, для классических типов аргументов не выполняется приведение типов. Квантовые регистры могут быть преобразованы из qureg в quuconst, но не
наоборот.
qcl> list CNot; // Оператор controlled-not принимает
: глобальный символ CNot: // a qureg и quconst в качестве аргументов
extern qufunct CNot(qureg q,quconst c);
qcl> qureg q[2];
qcl> quconst p[2];
qcl> CNot(q[0],q[1]); // приведение из qureg в quconst
qcl> CNot(p[0],p[1]); // нет преобразования из quconst в qureg
! несоответствие параметров: quconst используется как неконстантный аргумент для Cnot
ГЛАВА 2. QCL 37
Тип параметра quvoid и тип локального регистра quscratch просто предоставляют метаинформацию для управления памятью и в противном случае рассматриваются как qureg.
Вызовы типов operator и qufunct могут быть инвертированы с помощью добавочным префиксом ‘!’. Затем оператор выполняется в обычном режиме, за исключением того, что все вспомогательные операции в определении оператора не вводятся немедленно, а сохраняются во внутреннем списке вместе с их оцененными параметрами.
Когда выполнение завершается, субоператоры вызываются в обратном порядке с инвертированными флагами присоединения.
qcl> <<dft
qcl> qureg q[2]; // выделяет 2 кубита.
qcl> установить логарифм 1; // включить ведение журнала операций
qcl> dft(q); // выполнить дискретное преобразование Фурье
@ Rot(действительное значение тета=1,570796,число q=|..0.>)
@ CPhase(реальный phi=1,570796,число q=|..10>)
@ Rot(реальная тета=1,570796,интервал q=|...0>)
@ Swap(интервал a=|...0>,интервал b=|..0.>)
[2/4] 0.5 |0000> + -0.5 |0010> + -0.5 |0001> + 0.5 |0011>
qcl> !dft(q); // обратное преобразование Фурье
@ !Swap(параметр a=|...0>,параметр b=|..0.>)
@ !Rot(реальная тета=1,570796,параметр q=|...0>)
@ !CPhase(реальный phi=1,570796,число q=|..10>)
@ !Rot(реальный theta=1,570796,число q=|..0.>)
[2/4] 1 |0000>
2.4.1.3 Ввод и вывод
stmt ; ввод [ expr ] , идентификатор ;
Команда ввода запрашивает ввод данных пользователем и присваивает значение переменной identifier . При желании вместо этого может быть указана строка запроса expr стандартное приглашение, в котором указываются тип и имя переменной. Перед каждой строкой ввода ставится знак вопроса.
qcl> действительное n;
qcl> введите "Введите количество итераций:",n;
? Введите количество итераций: 1000
повторов запроса на ввод до тех пор, пока не будет введено допустимое входное выражение.
qcl> логическое значение b;
qcl> ввод b;
? логическое значение b [t(rue)/f(alse)] ? да
? логическое значение b [t(rue)/f(alse)]? Истинный
Как и в случае с глобальными переменными, использование инструкций input при определении функций и операторов запрещено.
ГЛАВА 2. QCL 38
Команда print выводит список выражений, разделенных запятыми, и выводит их на консоль. Каждый вывод начинается с двоеточия и заканчивается новой строкой. Несколько выражений разделяются пробелом. В случае квантовых выражений выводится положение соответствующих кубитов в машинном состоянии.
qcl> int i=3; действительный x=pi; комплексный z=(0,1); логическое значение b; число q[8];
qcl> вывести i,x,z,b,q;
: 3 3.141593 (0.000000,1.000000) false |........76543210>
При интерактивном использовании команда печати может быть сокращена до ‘?’.
2.4.1.4 Отладка
Команды shell и exit открывают и закрывают подоболочки при использовании взаимодействия. Пожалуйста, обратитесь к разделам 2.1.3.3 и 2.2.4.4 для получения подробного описания.
stmt ; list [ идентификатор { , identifier }] ;
При вызове без аргументов команда list выводит список всех определенных глобальных и локальных символов. Если задан список символов, выводится их область применения, значение (если правомерно) и их определение.
qcl> <<dft
qcl> переворот списка,pi;
: переворот глобальных символов:
qufunct перевернуть(qureg q) {
int i;
для i = 0 на #q/2-1 {
Поменять местами(q[i],q[(#q-i)-1]);
}
}
: глобальный символ pi = 3,141593:
константа pi = 3,141593;
Команда dump может использоваться для проверки моделируемого состояния машины или спектра квантовых регистров. Пожалуйста, обратитесь к разделу 2.4.2.3 для получения подробного описания.
stmt ; установить параметр [ , expr ] ;
Команда set может использоваться для временного включения опций отладки из командной строки. Полный список опций приведен в разделе 2.1.3.1.
ГЛАВА 2. QCL 39
extern qufunction CNot(qureg q,quconst c).;
qufunct Swap(qureg a,qureg b) {
int i;
если #a != #b { выход из "Swap: изменение размеров регистров"; }
для i=0 на #a-1 {
CNot(a[i],b[i]); // |a,b> -> |a xor b,b>
CNot(b[i],a[i]); // |a xor b,b> -> |a xor b,a>
CNot(a[i],b[i]); //|a xor b,a> -> |b,a>
}
}
Таблица 2.10: Пользовательская реализация Swap.qcl для Swap
2.4.2 Квантовые утверждения
2.4.2.1 Унитарные операции
Операторы Fanout и Swap играют важную роль в QC как моральный эквивалент- аналогично элементарной операции перемещения в обычных микропроцессорах.
РАЗВЕТВЛЕНИЕ: |i, 0; ; |i, i; (2.8)
ЗАМЕНА : |i, j; ; |j, i; (2.9)
Реализация Fanout и Swap по умолчанию, как определено в default.qcl , объявляет их внешними (т.е. элементарными, см. раздел 3.1) операторами:
extern qufunct Fanout(qureg a,qureg b);
extern qufunct Swap(qureg a,qureg b);
Поскольку QCL не требует применения определенного набора элементарных операторов, пользователь волен предоставлять свои собственные реализации. В таблице 2.10 приведен пример пользовательского оператора подкачки, использующего вентили controlled-not. Даже разветвленная операция, которая используется для управления внутренним пространством скретч, может быть заменена при желании (пример приведен в таблице 2.13 на стр. 53).
Для удобства QCL предоставляет некоторый синтаксический сахар для вызовов Fanout
и Swap, который можно использовать вместо стандартного синтаксиса:
stmt ; выражение a( -> | <- | <-> ) выражение b ;
Это ярлыки для разветвления(a,b), !Разветвления(a,b) и подкачки(a,b).
ГЛАВА 2. QCL 40
2.4.2.2 Неунитарные операции
Как указывалось в разделе 1.1.1, любое квантовое вычисление должно состоять из инициализации, унитарных операторов и измерений. Типичный вероятностный квантовый алгоритм обычно запускает цикл оценки следующим образом:
{
reset; // R: |Psi> -> |0>
myoperator(q); // U: |0> -> |Psi’>
измерьте q, m; // M: |Psi’> -> |m>
} до тех пор, пока не будет получено значение ok(m); // выбрано правильное значение m ?
Команда reset сбрасывает машинное состояние |;; на |0;, которое также является начальным состоянием при запуске qcl. Квантовая куча и привязка квантовых переменных остаются неизменными.
stmt ; measure expr [ , identifier ] ;
Команда measure измеряет значение квантового региста expr и присваивает измеренную битовую строку идентификатору переменной int. Если переменная не указана, значение отбрасывается.
Результат измерения определяется генератором случайных чисел, который по умолчанию запускается с использованием текущего системного времени. Для обеспечения воспроизводимости результатов моделирования можно задать начальное значение с помощью опции --seed.
Поскольку операции сброса и измерения необратимы, они не должны выполняться
в рамках определений оператора.
2.4.2.3 Команды симулятора
QCL предоставляет несколько команд для прямого доступа к моделируемому состоянию машины. Поскольку это было бы невозможно при использовании реального квантового компьютера, их следует рассматривать как нестандартное расширение языка QCL.
stmt ; dump [ expr ] ;
; load [ expr ] ;
; save [ expr ] ;
При вызове без аргументов команда dump выводит текущее состояние компьютера в краткой записи. Если задано квантовое выражение, вместо него выводится спектр вероятности.
ГЛАВА 2. QCL 41
qcl> qureg q[2];
qcl> Mix(q);
qcl> dump;
: СОСТОЯНИЕ: 2/4 кубита выделены, 2/4 кубита свободны
0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> сбросить q;
: СПЕКТР q: |..10>
0.25 |00> + 0.25 |01> + 0.25 |10> + 0.25 |11>
Базовые векторы задаются в двоичной системе счисления, если число кубитов равно ; 32
и в шестнадцатеричном формате в противном случае. Можно изменить формат вывода
, используя параметр --dump-format.
qcl> задать формат дампа "x";
qcl> dump;
: СОСТОЯНИЕ: 2/4 кубита выделены, 2/4 кубита свободны
0.5 |0x0> + 0.5 |0x2> + 0.5 |0x1> + 0.5 |0x3>
Если установлена опция --auto-dump, текущее состояние регистрируется в командной строке в интерактивном режиме. По умолчанию --auto-dump активен, если количество кубитов ; 8.
Текущее состояние компьютера можно загрузить и сохранить с помощью команды загрузить и сохранить. Файлы состояния имеют расширение .qst. Если имя файла не указано,
используется файл по умолчанию qclstate.qst.
2.4.3 Управление потоком
2.4.3.1 Блоки
Все операторы управления потоком работают с блоками кода. Блок - это список операторов, заключенных в фигурные скобки:
block ; { stmt { stmt } }
Блоки могут содержать только исполняемые инструкции, без каких-либо определений. В отличие от языка Си, блок не является составным оператором и всегда является частью управляющей структуры. Чтобы избежать двусмысленностей при вложении, фигурные скобки обязательны даже для отдельных команд.
2.4.3.2 Условное ветвление
Операторы if и if-else допускают условное выполнение блоков в зависимости от значения логического выражения.
stmt ; if expr block [ else block ]
Если значение expr равно true, выполняется блок if. Если значение expr равно false,
выполняется блок else, если он определен.
ГЛАВА 2. QCL 42
2.4.3.3 Подсчет циклов
для - циклы принимают идентификатор счетчика типа integer5 , который увеличивается от
expr from до expr to . Тело цикла выполняется для каждого значения идентификатора .
stmt ; для идентификатора = значение expr от к значению expr в блоке [ step expr step ]
Внутри тела счетчик обрабатывается как константа. Приращение равно шагу expr step или 1, если не указано. Если ( expr to ; expr to ) шаг exprstep < 0, цикл вообще не выполняется.
qcl> int i;
qcl> для i=10 - 2 шага -2 { вывести i^2; }
: 100
: 64
: 36
: 16
: 4
qcl> для i=от 1 до 10 { i=i^2; } // i является константой в теле
! неизвестный символ: Неизвестная переменная i
По завершении цикла идентификатору присваивается значение expr to .
2.4.3.4 Условные циклы
QCL поддерживает два типа условных циклов:
stmt ; while expr блокирует
; блокирует до тех пор, пока не будет выполнено expr ;
Цикл while повторяется до тех пор, пока не будет выполнено условие expr. Когда значение expr равно false, цикл завершается.
Цикл until выполняется по крайней мере один раз и повторяется до тех пор, пока не будет выполнено условие expr.
2.4.3.5 Сообщение об ошибке
Определяемые пользователем процедуры часто требуют, чтобы их параметры соответствовали определенным условиям (например, размеру аргументов квантового регистра). Аварийное завершение работы подпрограмм может быть вызвано инструкцией exit.
stmt ; exit [ выражение ] ;
Exit принимает в качестве аргумента сообщение об ошибке типа string. Рассмотрим
пользовательский оператор Swap (таблица 2.10) на стр. 39.
5 Это делается для того, чтобы избежать тонких проблем с арифметикой с плавающей запятой
ГЛАВА 2. QCL 43
$ qcl -n -i swap.qcl
qcl> параметр q[2];
qcl> параметр p[1];
qcl> Своп(q,p);
! в qufunct Swap: ошибка пользователя: Swap: несоответствие размеров регистров
Если exit вызывается без аргументов, текущая подоболочка закрывается, как описано
в разделе 2.1.3.3.
2.5 Подпрограммы
2.5.1 Введение
2.5.1.1 Синтаксис
QCL предоставляет 4 вида подпрограмм: классические функции, псевдоклассические операторы (qufunct), общие унитарные операторы (operator) и процедуры (procedure). Основной синтаксис для всех объявлений подпрограмм - это
def ; ( тип | routine-type ) идентификатор arg-list тело
рутинного типа ; оператор | функция | процедура
arg-list ; ( [ arg-def { , arg-def }] )
arg-def ; идентификатор типа
тело ; _BOS_ { const-def | var-def } { stmt } }
2.5.1.2 Иерархия подпрограмм
Поскольку QCL допускает обратный вызов операторов и может выполнять управление промежуточным скретч пространством для квантовых функций, допустимые побочные эффекты для состояния классической программы, а также для состояния квантовой машины должны быть строго определены.
тип программы - рутина состояние программы- состояние машины
процедуры все все
оператор нет унитарное
куфункция (qufunct) нет псевдоклассическое
функции нет нет
Таблица 2.11: иерархия подпрограмм QCL и допустимые побочные эффекты
4 типа процедур QCL образуют иерархию вызовов, что означает, что процедура может вызывать только подпрограммы того же или более низкого уровня (см. таблицу 2.11).
ГЛАВА 2. QCL 44
Математическая семантика операторов и функций QCL требует, чтобы каждый вызов был воспроизводимым. Это означает, что эти процедуры не только не должны изменять состояние программы, но и что их выполнение никоим образом не должно зависеть от глобального состояния программы, которое включает в себя глобальные переменные, опции и состояние внутреннего генератора случайных чисел.6
2.5.1.3 Внешние процедуры
Хотя QCL включает в себя классический язык программирования, предоставлять все необходимые средства для изменения состояния программы, не существует встроенного аппаратного набора элементарных операторов для управления состоянием квантовой машины, поскольку это потребует предположений об архитектуре моделируемого квантового компьютера.
Элементарный оператор или qufunct можно включить, объявив его к extern.
def ; идентификатор внешнего оператора arg-list ;
; идентификатор внешнего qufunct arg-list ;
Внешние операторы не имеют тела, поскольку они не выполняются в QCL, а просто служат связующим крюком для двоичной функции, которая реализует желаемое деяние непосредственно с помощью цифровой QC-библиотеки [17] и связано с интерпретатором.
QCL интерпретатор включает в себя двоичные версии нескольких распространенных операторов, включая реализацию оператора разветвления (см. раздел 2.5.6.2) который используется QCL управлением скретч промежуточного пространства, и шаблоны общих унитарных матриц для реализации новых элементарных операторов.
Для удобства определения пользовательского набора элементарных операторов внешние объявления могут быть включены во включаемый по умолчанию файл default.qcl. Обратите внимание, что необходимо предоставить определение разветвления для использования локальных промежуточных переменных.
Полный список доступных внешних операторов приведен в разделе 3.1.
2.5.2 Функции
Функции являются наиболее строгим типом рутины и не допускают никаких
взаимодействий с глобальным состоянием.
6 Эти ограничения могут быть частично отменены в целях отладки с помощью команды
shell
ГЛАВА 2. QCL 45
Определяемые пользователем функции могут быть любого классического типа, а именно int, real, complex или string, и могут принимать произвольное количество классических параметров. Значение функции передается вызывающей подпрограмме оператором return.
int digits(int n) { // вычислить количество
возвращаемых 1+этажей(log(n,2)); // двоичные цифры из n
}
Локальные переменные могут быть определены в верхней части тела функции.
int fibonachi(int n) { // вычислить n-е
число int a=0; // число фибоначчи
int b=1; // по итерации
int i;
от i = 1 до n {
b = a+b;
a = b-a;
}
вернуть a;
}
Функции могут вызывать другие функции внутри своего тела. Также разрешены рекурсивные вызовы.
int fac(int n) { // вычислить n!
if n<2 _BOS_ // путем рекурсии
возвращает 1;
} else {
возвращает n*fac(n-1);
}
}
За исключением большинства внутренних функций, неявное приведение типов не выполняется, поэтому аргументы функции должны точно соответствовать указанному типу параметра.
2.5.3 Процедуры
Процедуры являются наиболее общим типом рутины и используются для реализации классических структур управления квантовыми алгоритмами, которые обычно включают вычислительные циклы, выбор применяемых операторов, интерпретация измерений и классические вероятностные элементы.
За исключением обычных объявлений, процедуры допускают те же операции, которые доступны в глобальной области видимости (например, в командной строке), что позволяет произвольно изменять как программу, так и состояние компьютера. Операции, исключительные для процедур, - это
• Доступ к глобальным переменным
ГЛАВА 2. QCL 46
• (Псевдо) случайные числа с использованием псевдофункции random (см. раздел 2.2.3.7)
• Неунитарные операции с состоянием машины с использованием сброса и команды измерения (см. раздел 2.4.2.2)
• Пользовательский ввод с помощью команды ввода (см. раздел 2.4.1.3)
Процедуры могут принимать любое количество классических или квантовых аргументов и вызывать все типы подпрограмм.
процедура prepare(qureg q) {
const l = #q/2; // использует половину регистра
int i; // для
сброса смещения; // инициализирует состояние машины
Смешивать(q[l:#q-1]); // генерировать периодическое распределение
для значений от i = 0 до l-1 { // рандомизировать смещение
, если 0,5<случайное() {
Не(q[i]);
}
}
}
Процедура prepare генерирует периодическое тестовое состояние со случайным смещением,
как мы использовали в примере DFT в разделе 2.1.2.
qcl> запросить q[4];
qcl> подготовить(q);
[4/4] 0.5 |0010> + 0.5 |1010> + 0.5 |0110> + 0.5 |1110>
qcl> подготовить(q);
[4/4] 0.5 |0000> + 0.5 |1000> + 0.5 |0100> + 0.5 |1100>
qcl> подготовить(q);
[4/4] 0.5 |0011> + 0.5 |1011> + 0.5 |0111> + 0.5 |1111>
Процедуры могут объявлять локальные переменные классического и квантового типов. Когда
используются локальные квантовые регистры, программист должен правильно очистить их снова, что может быть достигнуто либо путем вычисления, либо командой сброса. В таблице 2.12 показана простая игра, в которой локальный квантовый регистр используется для генерации “реальных” случайных чисел.
2.5.4 Общие операторы
Оператор рутинного типа используется для общих унитарных операторов. В соответствии с математическим понятием оператора, вызов с одинаковыми параметрами должен приводить к точно такому же преобразованию, поэтому не допускаются ссылки на глобальные переменные, случайные элементы или зависимости от входных данных.
Поскольку оператор ввода ограничен обратимыми преобразованиями состояния машины, команды сброса и измерения также запрещены.
ГЛАВА 2. QCL 47
процедура quRoulette() {
курег q[5];
поле int;
номер int;
введите "Введите номер поля:",поле;
повторить {
Смешать(q);
измерить q,число;
сброс;
} до тех пор, пока число<=36;
поле if==number {
выведите "Число", цифра, "Вы выиграли!";
} поле else {
выведите "Число", цифра, "Вы проиграли".;
}
}
Таблица 2.12: рулетка.qcl quantum roulette
2.5.4.1 Аргументы Оператора
Операторы работают с одним или несколькими квантовыми регистрами (оператор регистра, см. раздел 1.3.2.2), поэтому в зависимости от отображения регистров вызов оператора m кубитов с общей квантовой кучей из n кубитов может привести к n!/(n-m)! различным унитарным преобразованиям.
В QCL этот полиморфизм еще более расширен тем фактом, что квантовые регистры могут быть разного размера, поэтому для каждого квантового параметра s, размер регистра #s = | s / является неявным дополнительным параметром типа int. В дополнение к этому операторы могут принимать произвольное количество явных классических аргументов.
Если задано более одного регистра аргументов, их кубиты могут не перекрываться.
qcl> qreg q[4];
qcl> qreg p=q[2: 3];
qcl> CNot(q[1\2], p);
! ошибка во время выполнения: квантовые аргументы перекрываются
2.5.4.2 Обратные Операторы
Как уже упоминалось в разделе 2.4.1.2, вызовы оператора могут быть инвертированы с помощью префикса присоединения '!’. Оператор, связанный с композицией унитарных Глава2. QCL 48
операторов, равен 7
Поскольку последовательность применяемых вспомогательных операций задается с использованием классического процедурного языка, который не может быть выполнен в обратном порядке, инверсия композиции достигается за счет отложенного выполнения вызовов операторов.
Когда флаг присоединения установлен, выполняется тело оператора и все вызовы вспомогательных операторов помещаются в стек, который затем обрабатывается в обратном порядке с перевернутыми флагами присоединения.
2.5.4.3 Локальные регистры
В отличие от псевдоклассических операторов, в общем случае невозможно разложить унитарный оператор, чтобы снова освободить локальный регистр, не используя также уничтожение предполагаемого результата вычисления-разложения. Это фундаментальное ограничение QC, известное как теорема о неклонировании, вытекающее из того факта, что операция клонирования, т. е. преобразование удовлетворяет условию
для произвольного8 |;> не может быть унитарным, если |;> является составным состоянием, потому что
U может быть унитарным только в том случае, если |;; находится в чистом состоянии, т. е.
|;; = |i;, и в этом случае U = РАЗВЕТВЛЕНИЕ( FANOUT).
Из-за отсутствия операции однократного копирования для квантовых состояний управление скретч промежуточным пространством в стиле Беннета невозможно для обычных операторов, поскольку оно основано на клонировании результирующего регистра.
Несмотря на это ограничение, в QCL возможно выделение временных количественных -квантовых регистров, но программист должен правильно вычислить их снова. Если установлена опция --check, правильность очистки проверяется симулятором.
7 Чтобы избежать двусмысленностей с некоммутативными матричными произведениями, мы используем соглашение ;ni=1 fi = fnfn;1 . . . f1
8 ибо любое конкретное |;; бесконечное количество унитарные “клонирование” операторов тривиально существует, как, например, U; = ;i,j,k |i, j ; k;;k|;;;i, j|
ГЛАВА 2. QCL 49
qcl> установить проверку 1
qcl> оператор foo(параметр q) {параметр p[1]; CNot(p,q); }
qcl> параметр q[1];
qcl> Смешать(q);
[1/4] 0.707107 |0000> + 0.707107 |0001>
qcl> foo(q);
! в операторе foo: ошибка памяти: повреждена квантовая куча
[1/4] 0.707107 |0000> + 0.707107 |0011>
Локальные регистры полезны, если оператор содержит некоторое промежуточные псевдоклассические операции, для которых требуется свободное пространство. Смотрите пример реализации модульного сложения (addn) в разделе 3.2.2.1 (стр. 62).
2.5.5 Псевдоклассические операторы
Рутинный тип qufunct используется для псевдоклассических операторов и квантовых
функций, поэтому все преобразования должны иметь вид
с некоторой перестановкой ;. Таким образом, все n кубитных псевдоклассических операторов F меют общее собственное состояние
2.5.5.1 Биективные функции
Наиболее простым применением псевдоклассических операторов является
прямая реализация биективных функций (см. раздел 1.3.3.1)
qufunct inc(qureg x) {
int i;
for i = #x-от 1 до 1 {
CNot(x[i],x[0:i-1]);
}
Не(x[0]);
}
Оператор inc сдвигает базовые векторы своего аргумента. По аналогии с состояниями бозонов, где приращение собственного состояния соответствует рождению частицы, inc является оператором создания.9
9 На самом деле, это не совсем верно, поскольку, за исключением бозонов, регистр n кубитов ограничен 2n состояниями, так что inc |2n ; 1; = |0;, тогда как a† |2n ; 1; = |2n;
ГЛАВА 2. QCL 50
qcl> qureg q[4];
qcl> inc(q);
[4/4] 1 |0001>
qcl> inc(q);
[4/4] 1 |0010>
qcl> inc(q);
[4/4] 1 |0011>
qcl> inc(q);
[4/4] 1 |0100>
2.5.5.2 Условные операторы
Когда дело доходит до более сложных арифметических операций, часто требуется применить преобразование к регистру a в зависимости от содержимого другого регистра e.
Если для выполнения преобразования требуется задать все кубиты e, то оператор является условным оператором с инвариантом (quconst) предоставляющим регистр e (см. раздел 1.3.5).
Простым примером условного оператора является элемент Тоффоли T : |x, y, z; ;
|x ; (y ^ z), y, z; или его обобщение, управляемый элемент-гейт «не ворота». Условную версию приведенного выше оператора приращения также легко реализовать:
qufunct cinc(qureg x,quconst e) {
int i;
для i = #x-от 1 до 1 шага -1 {
CNot(x[i],x[0:i-1] и e);
}
CNot(x[0],e);
}
Теперь увеличиваются только базовые векторы вида |i;|11 . . .;s:
qcl> qreg q[4]; qreg e[2]; Mix(e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110000>
qcl> cinc(q,e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110001>
qcl> cinc(q,e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110010>
qcl> cinc(q,e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110011>
2.5.6 Квантовые функции
Как определено в разделе 1.3.3.2, квантовая функция F является псевдоклассическим оператором с характеристикой
F : |x;x|0;y ; |x;x|f (x);y с помощью f : Bn ; Bm(2.16)
ГЛАВА 2. QCL 51
Если мы требуем, чтобы регистр аргументов x был инвариантен к F, объявляя x как quconst, это оставляет нам 2 (2n;1) m возможных псевдоклассических реализаций F для любого заданного f . Чтобы отразить тот факт, что F |x, y; 0; не определено, целевой регистр должен быть типа quvoid. (см. раздел 2.3.2.3).
Поскольку, согласно приведенному выше определению, квантовые функции являются просто обычные псевдоклассические операторы, спецификация которых ограничена определенными типами входных состояний, также используют ту же процедуру QCL типа qufunct.
В следующем примере вычисляется четность x и сохраняется в y:
четность qufunction(quconst x,quvoid y) {
int i;
для i = 0 до #x-1 {
CNot(y,x[i]);
}
}
qcl> параметр x[2]; параметр y[1]; Mix(x);
[3/3] 0.5 |000> + 0.5 |010> + 0.5 |001> + 0.5 |011>
qcl> четность(x,y);
[3/3] 0.5 |000> + 0.5 |110> + 0.5 |101> + 0.5 |011>
2.5.6.1 Скретч промежуточные параметры
Мы можем расширить понятие квантовых функций, также разрешив явный скретч регистр s (см. раздел 2.3.2.4) в качестве необязательного параметра для параметра F, так что в итоге мы получим оператор F (x, y, s) с характеристикой
Используя четность и оператор cinc из приведенных выше примеров, мы можем реализовать функцию “добавления четности” f (x) = x + parity (x) четность, предоставив скретч промежуточный кубит:
qufunct добавляет четность(quconst x,quvoid y,quscratch s) {
четность(x,s); // записывает четность с нуля
x -> y; // Разветвление x на y
cinc(y,s); // увеличение y, если четность нечетная
(x,s); // очистка нуля
}
qcl2> параметр x[2]; параметр y[2]; параметр s[1]; Mix(x);
[5/8] 0.5 |00000> + 0.5 |00010> + 0.5 |00001> + 0.5 |00011>
qcl2> добавить соответствие(x,y,s);
[5/8] 0.5 |00000> + 0.5 |01110> + 0.5 |01001> + 0.5 |01111>
Вместо предоставления явного параметра скретч мы, конечно, можем также использовать
локальный регистр типа qureg, который функционально эквивалентен:
ГЛАВА 2. QCL 52
qufunct addparity2(quconst x,quvoid y) {
параметр s[1];
четность(x,s);
x -> y;
cinc(y,s);
четность(x,s);
}
qcl2> параметр x[2]; параметр y[2]; Mix(x);
[4/8] 0.5 |00000> + 0.5 |00010> + 0.5 |00001> + 0.5 |00011>
qcl2> добавить параметр 2(x,y);
[4/8] 0.5 |00000> + 0.5 |01110> + 0.5 |01001> + 0.5 |01111>
Явные скретч-параметры полезны для экономии памяти, если квантовая функция F должна использоваться другим оператором U, у которого в данный момент все еще есть пустые скретч-регистры, вызывается вспомогательный оператор, который, например, имеет место, если U имеет вид
Поскольку как явные начальные параметры типа quscratch, так и локальные регистры
типа qureg должны вычисляться вручную, они особенно полезны для квантовых функций U : |x, 0, 0; ; |x, f (s(x), x), 0; вида
U (x, y, s) = S(x, s)F (x, s, y)S†(x, s) (2.19)
если S инвариантно по отношению к x, а F инвариантно по отношению к x и s, поскольку вычисление s не требует дополнительного регистра для временного сохранения y (см. раздел 1.3.4.2), как это было бы в случае, если бы управляемый локальный резервный регистр вместо этого будет использоваться тип quscratch (см. ниже).
2.5.6.2 Оператор разветвления
Ограничение на перестановки базовых векторов подразумевает, что вычислительный путь чистого состояния также является последовательностью чистых состояний, поэтому в случае
суперпозиций каждый базовый вектор может обрабатываться отдельно.
Как показано в разделе 2.5.4, произвольное чистое состояние |;; = |i; может быть скопировано в пустой регистр с помощью однократной операции разветвления:
Разветвитель : |;;|0; = |i, 0; ; |i, i; = |;;|;; (2.20)
Для непустых целевых регистров, разветвитель |i, j ; 0; остается неопределенным, поэтому для двух n кубитных регистров существует (22n ; 2n)! возможных псевдоклассических реализаций разветвляющего вентиля.10
10 На самом деле, определение разветвления, используемое QCL, несколько более строгое, поскольку оно требует, чтобы первый аргумент был инвариантным (quconst). Это можно переопределить, при необходимости повторно объявив аргумент как qureg (см. раздел 2.3.2.5)
ГЛАВА 2. QCL 53
extern qufunction CNot(qureg q,quconst c);
qufunct разветвление(quconst a,quvoid b) {
int i;
если #a != #b _BOS_ выход "Разветвление: аргументы должны быть одинакового размера"; }
для i=0 до #a-1 {
CNot(b[i],a[i]);
}
}
Таблица 2.13: Пользовательская реализация разветвления в fanout.qcl
В таблице 2.13 показана реализация с использованием вентилей не-управления (контролед-нот), которая математически эквивалентна реализации внешнего оператора по умолчанию Разветвление.
2.5.6.3 Управление скретч промежуточным пространством
Квантовый тип quscratch объявляет локальный регистр как управляемое промежуточное пространство. Регистры управляемого промежуточного пространства (или ненужные регистры) - это временные регистры, которые пусты при выделении и автоматически вычисляются после применения основной части qufunct.
Таким образом, в отличие от локальных регистров qureg или параметров quscratch, локальный регистр quscratch j не должен быть очищен в рамках определения qufunct но может быть оставлено без изменений. Итак, чтобы вычислить некоторую f (x), достаточно,
чтобы тело квантовой функции просто реализовывало некоторый оператор
F : |x, 0, 0; ; |x, f (x), j(x); с произвольной мусорной отбитой джанк строкой j(x) в исходном притертом скретч регистре.
Когда квантовая функция с локальным отбитым джанк регистром j и телом вызывается функция F (x, y, j), выделяется дополнительный оттертый скретч регистр y' того же размера, что и y , и вместо 3-го регистрового оператора F используется 4-ый регистровый оператор F ' применяется, что определяется как
F '(х, У, j, у') = F †(х, У', j) РАЗВЕТВЛЕНИЕ (у', у) F (х, У', j) (2.21)
F 'изначально вызывает F, но вместо y используется временный целевой регистр Y'.
Желаемый результат f (x) затем копируется в исходный целевой регистр y, в то время как нежелательный отбитый джанк результат j(x) остается в регистре джанк. Отменяя начальное вычисление путем применения присоединенного оператора F †, оба, регистр мусора отбитый джанк j и регистр царапины тронутый скретч y', снова становятся об- вычисляемыми, так что вся
Глава 2. QCL 54
процедура :
|х х х|0 0 у|0 дж дж|0 у у'
F (x, Y', j
; ; / x x x / 0 0 у|j (x) j j|f (x) у у '
РАЗВЕТВЛЕНИЕ (у', у
- ;(2.22)
|x;x|f (x) у У|j (x) j j|f (x) у у'
F †(x, Y', j
; ; / x x x|f (x) x y|0 j j / 0 у'
Используя оператор условного приращения со страницы 50, мы можем построить квантовую функцию bitcmp, которая реализует функцию "сравнения битов" f (x1, x2) , которая возвращает 1 если строки битов x1 и x2, содержат один и тот же набор битов либо ноль.
qufunct bitcmp (quconst x1, quconst x2, quvoid y {
const n=ceil (log (max (#x1,#x2)+1,2);
int y;
quscratch j[n]; / / выделяем регистр управляемой царапины
от i=0 до #x1-1 {//j = количество битов в х1
цинке x1 (j, x1[i]); / / приращение j, если установлен бит I или X1 }
Не (j); / / j = 2^n-j-1 = - 1-j по модулю 2^n
от i=0 до #x2-1 {//j = J+количество бит в x2
цинка (j, x2[i]); / / приращение j если установлен бит I O X1
}
CNot (у, j); / / устанавливаем у=1, если j==2^n-1
}
qcl> qreg x1[2]; qreg x2[2]; qreg у [1;
qcl> смесь (x1[1]); смесь (x2[0]); Не (x2[1;
[5/8] 0.5 |00001000> + 0.5 |00001100> + 0.5 |00001010> + 0.5 |00001110>
qcl> bitcmp (x1, x2, y;
[5/8] 0.5 |00001000> + 0.5 |00001100> + 0.5 |00011010> + 0.5 |00001110>
Используя параметр --log, мы можем отследить вызов каждого элементарного оператора:
Глава 2. QCL 55
qcl> набор журналов 1
qcl> bitcmp (х1, х2, у;
@ CNot(qureg q=|0.......>, quconst C= / .0.... 1>)
@ CNot (qureg q=/.0......>, quconst C=|.......0>)
@ CNot(qureg q=|0.......>, qconst C=|.0.... 1.>)
@ CNot(qureg q=|.0......>, quconst C=|......0.>)
@ Not(по буквам q=|10......> )
@ CNot(qureg q=|0.......>, quconst C= / .0...1..>)
@ CNot (qureg q=/.0......>, quconst C=|.....0..>)
@ CNot(qureg q=|0.......>, quconst C= / .0..1...>)
@ CNot (qureg q=/.0......>, quconst C=|....0...>)
@ CNot(qureg q=|..0.....>, quconst c= / 10......> )
@ Fanout (что соответствует=|..0.....>, quvoid B= / ...0....> )
@! CNot (qureg q=|..0.....>, квонст с= / 10......>)
@ !CNot (qureg q=|.0......>, quconst C=|....0...>)
@ !CNot (qureg q= / 0.......>, qconst C=|.0..1...>)
@! CNot (qureg q=/.0......>, quconst C=|.....0..>)
@ !CNot (qureg q= / 0.......>, quconst C= / .0...1..>)
@! Не (qureg q=|10......> )
@! CNot (qureg q=|.0......>, quconst C=|......0.>)
@ !CNot (qureg q= / 0.......>, quconst C=|.0....1.>)
@ !CNot (qureg q= / .0......>, quconst C=|.......0>)
@ !CNot (qureg q= / 0.......>, qconst C=|.0.... 1>)
Первые 10 операций принадлежат оператору тела F ; после подсоединения FANOUT они повторяются в обратном порядке с перевернутыми флагами присоединения (F †).
Дополнительно используя параметр --log-state, мы также можем проследить эволюцию машины состояния.
qcl> bitcmp (x1, x2, у;
@ CNot(qureg q=|0.......>, quconst C=|.0.....1>)
% 0.5 |00001000> + 0.5 |00001100> + 0.5 |00001010> + 0.5 |00001110>
.....
% 0.5 |00001000> + 0.5 |01001100> + 0.5 |11101010> + 0.5 |00001110>
@ Разветвление (что соответствует=|..0.....>, кувоид Б=|...0....>)
% 0.5 |00001000> + 0.5 |01001100> + 0.5 |11111010> + 0.5 |00001110>
.....
@ !CNot (qureg q= / 0.......>, quconst C=|.0.....1>)
% 0.5 |00001000> + 0.5 |00001100> + 0.5 |00011010> + 0.5 |00001110>
Глава 3
Операторы и алгоритмы
3.1 Элементарные Операторы
В этом разделе представлены возможные элементарные операторы, которые могут использоваться при текущей реализации QCL. Поскольку QCL как язык не содержит определенного набора элементарных операторов, они должны быть объявлены как внешние (см. раздел 2.5.1.3), чтобы сделать их доступными для программ.
Обычно это делается в файле по умолчанию, включающем файл default. qcl (см. приложение A1), который загружается при запуске.
3.1.1 Общие Унитарные Операторы
3.1.1.1 Унитарные Матрицы
Наиболее общая форма для указания унитарного оператора (или любого другого линейного
преобразование) для определения матричных элементов: n-кубитный унитарный оператор
, описывающий преобразование U : C2n; C2n и, следовательно, соответствует матрице 2n ; 2n в C
Поскольку для унитарного преобразования U †U = (U ;)TU = I(n), матрица U унитарна тогда и только тогда, когда
QCL предоставляет внешние операторы для общих унитарных матриц 2 ; 2, 4 ; 4 и 8 ; 8, которые программист может использовать для прямой реализации пользовательского набора
из 1, 2 и 3 кубитных вентилей.
56
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 57
Матрица внешних операторов 2x2(
комплекс u00, комплекс u01,
комплекс u10, комплекс u11,
последовательность q);
матрица внешних операторов 4x4(...,последовательность q);
внешний оператор Matrix8x8(...,число q);
Матричные операторы проверяются на унитарность перед их применением:
qcl> const i=(0,1);
qcl> qureg q[1];
qcl> Matrix2x2(i*cos(pi/6),i*sin(pi/6),(0,0),(1,0),q);
! внешняя ошибка: матричный оператор не является унитарным
3.1.1.2 Вращение кубита
Вращение одного кубита определяется матрицей преобразования U (;)
Коэффициент -1/2 до ; задается по аналогии с вращениями спина, которые, как можно показать, имеют вид D = exp(; i/2 ;j ;j )и, следовательно, имеют период 4;.
вращение внешнего оператора (действительная тета, число q);
extern operator Rot(real theta, qureg q);
В отличие от большинства других внешних операторов, Rot не является универсальным для работы с регистрами произвольного размера.
qcl> Rot(pi/2,q);
! внешняя ошибка: можно вращать только отдельные кубиты
! external error: Only single qubits can be rotated
3.1.1.3 Элемент вентиль гейт Адамара
Вентиль Адамара является частным случаем обобщенного Вращения кубита и определяется матрицей преобразования H
H = 1/;2
(
1 1
1 ;1
)
(3.4)
Для случая n кубитных регистров значение H может быть обобщено до
Векторы B' = {i ; Bn | |i'; = H |i;} образуют базу Адамара, или двойную базу, или базу четности для B = {i ; Bn | |i;}.
Преобразование Адамара является самосопряженным (т.е. H† = H), что для унитарных операторов означает, что H2 = I.
Поскольку B' содержит только однородные суперпозиции, которые отличаются только знаками базовых векторов, внешняя реализация H называется Mix.
внешний оператор Mix(qureg q);
external operator Mix (qureg q);
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 58
3.1.1.4 Условный фазовый вентиль гейт
Элемент ворот гейт условной фазы является патологическим случаем условного оператора
(см. раздел 1.3.5) для фазового оператора ei; с нулевым кубитом ei;.
Условный фазовый элемент используется в квантовом преобразовании Фурье (см.
раздел 3.2.3).
внешний оператор CPhase(действительный phi,число q);
extern operator Cphase(real phi,qureg q);
3.1.2 Псевдоклассические операторы
3.1.2.1 Базовая перестановка
Наиболее общей формой задания псевдоклассического оператора U для n кубитов является явное определение базовой перестановки ; базовых векторов:
QCL предоставляет внешние операторы для векторных перестановок для |;| = 2, 4, 8, 16, 32 и 64, которые программист может использовать для прямой реализации пользовательского набора псевдоклассических операторов от 1 до 6 кубитов:
внешний параметр Perm2(int p0 ,int p1 ,последовательность q);
внешний параметр Perm4(int p0 ,int p1 ,int p2 ,int p3 ,последовательность q);
внешний параметр Perm8(...,параметр q);
внешний параметр Perm16(...,параметр q);
внешний параметр Perm32(...,параметр q);
extern qufunct Perm64(...,qureg q);
Базовые перестановки проверяются на унитарность перед их применением (т. е. проверяется, что данная целочисленная последовательность на самом деле является перестановкой)
qcl> qureg q[3];
qcl> Perm8(0,0,1,2,3,4,5,6,q);
! внешняя ошибка: нет перестановки
! external error : no permutation
3.1.2.2 Разветвление
Операция РАЗВЕТВЛЕНИЯ является квантовой функцией (см. раздел 1.3.3.2) и
относится к классу преобразований с характерным РАЗВЕТВЛЕНИЕМ :
|x, 0; ; |x, x; (подробнее см. раздел 2.5.6.2).
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 59
Внешний оператор разветвления QCL определяется как
РАЗВЕТВЛЕНИЕ : |x, y; ; |x, x ; y;, (3.8)
однако полагаться на эту конкретную реализацию считается плохим стилем программирования
.
внешнее функциональное разветвление (quconst a,quvoid b);
3.1.2.3 Мена
Оператор SWAP обменивает кубиты двух регистров одинакового размера (SWAP : |x, y; ; |y, x;). Оператор взаимно однозначной замены кубитов одержит матрицу преобразования
extern qufunction Swap(qureg a,qureg b);
3.1.2.4 Не и управляемый не
Оператор not C инвертирует кубит. Его матрица преобразования равна
C =(0 1
1 0) (3.10)
Оператор C[[e]] управляемый-не, является условным оператором (см. раздел 1.3.5)
в C с помощью разрешающего регистра e:
внешнее значение не соответствует(параметр q);
внешнее значение не соответствует(параметр q,параметр c);
QCL-версии Not и CNot также работают с целевыми регистрами:
qcl> qureg q[4]; qureg p[4];
qcl> Not(q);
[8/8] 1/00001111>
qcl> CNot(p,q);
[8/8] 1 |11111111>
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 60
3.2 Составные операторы
В этом разделе представлены унитарные операторы, необходимые для алгоритма Шор (Shor), представленного в разделе 3.3.
3.2.1 Псевдоклассические операторы
3.2.1.1 Простые манипуляции с битами
Изменение порядка следования регистров Оператор flip изменяет порядок следования битов в регистре.
переверните : |b1, b2 . . . bn; ; |bn, bn;1 . . . b1; (3.12)
qufunct flip(qureg q) { // псевдоклассическая операция для изменения порядка битов
int i; // объявляем счетчик циклов
для i=0 на #q/2-1 { // меняем местами 2 симметричных бита
Меняем местами(q[i],q[#q-i-1]);
}
}
Условное исключение Или оператор cxor обладает функциональностью условной операции разветвления на основе CNot:
cxor : |a;a|b;b|;;e ;{|а;а|а ; б;б|;;е если ; = 111 . . .
| А;А|B;б|;;е иначе (3.13)
qufunct cxor(quconst a,qureg b,quconst enable)
_BOS_ int i;
для i=0 до #a-1 {
CNot(b[i],a[i] и включить);
}
}
3.2.1.2 Сравнения регистры
Сравнение двух классических двоичных чисел a и b может быть просто достигнуто путем сравнения старшего и младшего разрядов и возврата при первом несоответствии.
для i=n-от 1 до 0 _BOS_ // проверьте, является ли b<a
, если бит(b,i)<бит(a,i) { возвращает true; }
}
возвращает значение false;
Однако, если одним из значений является квантовый регистр b, это не так тривиально из-за отсутствия условного ветвления. Итак, поскольку мы не можем просто вернуться из цикла, нам нужно искать другое решение.
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 61
Одна из возможностей состоит в том, чтобы имитировать ранний возврат из цикла с помощью условных операторов (см. раздел 1.3.5): Для каждого сравнения битов мы используем дозволенный бит, который устанавливается равным 1, если биты равны (и цикл должен продолжаться) или до 0, если результат определен и дальнейшие сравнения должны быть отключены.
Чтобы сравнить n кубитный регистр b с классическим целым числом a, мы должны использовать n ; 1 нежелательный отбитый джанк регистр j для хранения разрешенных битов. Затем выполняется следующий основной цикл квантового сравнения b < a.
для i=#b-от 2 до 1 шага -1 _BOS_ // продолжайте для младших битов
, если бит (a,i) _BOS_ // установите новый ненужный бит, если не определились
CNot(j[i-1],j[i] & b[i]);
Не(b[i]); // учитываем последний ненужный бит и
CNot(flag,j[i] & b[i]); // установить флаг результата, если a[i]>b[i]
} еще {
Не(b[i]);
CNot(j[i-1],j[i] & b[i]);
}
Не(b[i]); // восстановить b[i] снова
}
Для полной реализации оператора lt, используемого при модулированном сложении, пожалуйста, обратитесь к приложению 3.2.1.2.
3.2.1.3 Мультиплексированный сумматор .
Мультиплексированный сумматор добавляет один из двух классических битов a0 и a1 к кубиту b в зависимости от содержимого выбранного кубита s. Целевой регистр ysum = (cin, cout) состоит из кубита ввода и кубита вывода, что позволяет выполнять каскадирование. Таблица истинности для операции:
Реализация таблицы истинности с элементами управления-не (muxaddbit) прямо перед вами и может быть найдена в приложении A.3.1 Мультиплексированный сумматор для регистров может быть создан путем каскадирования нескольких однобитовых сумматоров:
1muxaddbit на самом деле является условной версией с дополнительным разрешающим регистром e, поскольку он необходим для модульного умножения
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 62
qufunct muxadd(int a0,int a1,qureg sel,quconst b,quvoid sum,quconst e)
_BOS_ int i;
для i=0 до #b-2 { // полное добавление первых #b-1 битов
mux-adddbit(бит(a0,i),бит(a1,i),sel,b[i],сумма[i:i+1],e);
} // наполовину добавляем последний бит
}
3.2.2 Модулированная арифметика
Многие алгоритмы теории чисел описывают вычисления в классе остатков Zn. Примером квантового алгоритма, использующего модульную арифметику, является Метод Шора квантового разложения на множители за полиномиальное время (см. раздел 3.3).[11].
Для более подробного обсуждения унитарных операторов для модулированной арифметики, пожалуйста, обратитесь к [13].
3.2.2.1 Модулированное сложение
Сложение по модуло n классического целого числа a и квантового регистра b может привести либо к a + b, либо (a ; n) + b), в зависимости от конкретного базового вектора |b;.
В то время как для b < n операция обратима, это не относится к b ; n, поэтому, если n не является степенью 2, помимо целевого сопротивления ys для суммы, нам нужен дополнительный флаг-кубит yy, чтобы разрешить квантовую функцию addn, который есть оба, унитарный и инвариант к b:
При использовании less-than оператора lt и мультиплексирующего сумматора muxadd реализация становится довольно простой в лоб. (Был добавлен допускающий регистр e , позволяющий использовать его для модульного умножения; см. ниже).
qufunct addn(int a,int n,quconst b,qucoid flag,qucoid sum,quconst e) {
число s=сумма[0\#b-1];
qureg f=сумма[#b-1];
qureg bb=b; // "злоупотребляет" суммой и b как нулем
lt(n-a,bb,f,s); // для оператора, который меньше, чем
CNot(flag,f & e); // сохранить результат сравнения
!lt(n-a,bb,f,s); // восстановить сумму и b
-умножение(2^#b+a-n,a,флаг,b,сумма,e); // добавить либо a, либо a-n
}
Единственная хитрость здесь в том, что мы повторно объявляем quconst b как qureg, чтобы мы могли использовать “грязную” реализацию lt, которая не выполняет никакой очистки ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 63
на b или ys (сумма), что в любом случае было бы бессмысленно, поскольку сравнение вычисляется после сохранения результата.
Поскольку addnn;a,n является квантовой функцией для модульного вычитания и, таким образом, реализует функцию, обратную f -1a,n(b) = b ; a mod n (по модулю n) к fa,n = a + b mod n (по модулю n), мы можем построить перезаписывающую версию oaddn модулярного сложения, используя представленный метод в разделе 1.3.4.3:
addnn;a,n не отменяет флаг переполнения yf , поэтому мы должны переключить его вручную
:
U †f -1 = addnn;a,n(b, ys, yf ) (3.16)
Исходные целевые регистры ys и yf теперь могут быть выделены как неуправляемый локальный скретч тронуть.
qufunct oaddn(int a,int n,итоговая сумма,значение e) {
число j[#сумма];
qureg f[1];
addn(a,n,сумма,f,j,e); // мусор -> a+b mod n
Поменять местами(сумма,j); // поменять местами мусор и сумму
CNot(f,e); // переключить флаг
!addn(n-a,n,сумма,f,j,e); // вычислить значение b равным нулю
}
3.2.2.2 Модулярное умножение
Модулярное умножение - это просто совокупность условных прибавлений для каждого кубита в b, поскольку
Первое суммируемое может быть слегка оптимизировано, поскольку накопитель (prod)
по-прежнему пуст.
qufunct muln(int a,int n,quconst b,qureg prod,quconst e)
_BOS_ int i;
для i=0 до #prod-1 {
если бит(a,i) { CNot(prod[i],b[0] & e); }
}
от i=1 до #b-1 {
oaddn(2^i*a mod n,n,prod,b[i] & e);
}
}
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 64
Как указано выше, мы можем создать перезаписывающую версию, если реализация обратной функции существует. Это тот случай, когда gcd(a, n) = 1, поэтому a и n относительно простые, потому что тогда модулярная обратная функция a;1 с a;1a mod n = 1 существует. Поскольку мы намерены использовать оператор для алгоритма Шора, который требует, чтобы gcd(ak, n) = 1, этого для нас достаточно.
Используя два условных элемента исключения (см. раздел 3.2.1.1) для замены регистров2, мы можем реализовать условный omuln[[e]],a,n|b; ; |ab mod n;
функция qufunction(int a,int n,qureg b,quconst e) _BOS_
курег джей[#b];
мульн(a,n,b,j,e);
!muln(invmod(a,n),n,j,b,e);
cxor(j,b,e);
cxor(b,j,e);
}
3.2.2.3 Модулярное возведение в степень
Как и в случае с muln, мы можем построить модулярное возведение в степень, условно
применив omuln с кубитами экспонент в качестве разрешающей строки, согласно
Прежде чем мы сможем начать итерацию, аккумулятор (ex) должен быть инициализирован
значением 1.
qufunct expn(int a,int n,quconst b,quvoid ex)
_BOS_ int i;
Не(например,[0]); // начинаем с 1
для i=0 до #b-1 {
omuln(powmod(a,2^i,n),n,ex,b[i]); // ex -> ex*a^2^i mod n
}
}
3.2.3 Квантовое преобразование Фурье
Для q-мерного вектора |;; дискретное преобразование Фурье определяется как
2 обычно для замены регистра требуется выполнить 3 операции исключения, но поскольку один регистр пуст, достаточно 2 операций исключения.
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 65
Поскольку |; - это объединенное состояние n кубитов, q всегда равно степени 2. Классическое быстрое преобразование Фурье (БПФ ) использует двоичное разложение показателя степени для выполнения преобразования за O(n2n) шагов.
Как предположил Копперсмит [7], тот же принцип можно было бы адаптировать к
квантовым компьютерам, используя комбинацию преобразований Адамара H и условных фазовых вентилей воротов гейтов V (индексы указывают на кубиты, с которыми работают):
DFT ' выполняет итерацию кубитов из MSB в LSB, "разбивает" кубиты с помощью преобразования Адамара, а затем условно применяет фазы в соответствии с их относительным двоичным положением
к каждому уже разделенному кубиту.
Базовые векторы преобразованного состояния | ;'; = DFT ' |;; задаются в обратном порядке битов, поэтому, чтобы получить фактический DFT , биты должны быть перевернуты.
оператор dft(qureg q) _BOS_ // основной оператор
const n=#q; // присваивает n длине входных
данных int i; int j; // объявляет счетчики циклов
для значений от i=0 до n-1 {
для j=0 до i-1 { // применяет условные фазовые вентили
Фаза(2*pi/2^(i-j+1),q[n-i-1] и q[n-j-1]);
}
Смешивание(q[n-i-1]); // вращение кубита
}
flip(q); // поменять местами порядок битов выходных данных
}
3.3 Алгоритм Шора для квантовой факторизации
3.3.1 Мотивация
В отличие от поиска и умножения больших простых чисел, эффективного классического алгоритма факторизации больших чисел не известно. Алгоритм называется эффективным, если время его выполнения, т.е. количество элементарных операций, пропорционально многочлену от длины его входных данных, измеряемой в битах. Наиболее известный (или, по крайней мере, опубликованный) классический алгоритм (квадратичное сито) требует
O(exp ((64.9 )1/3 N 1/3(ln N )2/3)) операций для разложения на множители двоичного числа из N бит [12], т.е. масштабируются экспоненциально в зависимости от размера входных данных.
Таким образом, умножение больших простых чисел является односторонней функцией , т.е. функцией, которая может быть легко вычислена в одном направлении, в то время как ее инверсия практически невозможна. Один-способ функции играют важную роль в
ГЛАВЕ 3. ОПЕРАТОРЫ И АЛГОРИТМЫ используются в
криптографии и необходимы для криптосистем с открытым ключом, где ключ для кодирования является открытым, и только ключ для декодирования остается секретным.
В 1978 году Ривест, Шамир и Адлеман разработали криптографический алгоритм, основанный на одностороннем умножении двух больших (обычно более 100 десятичных знаков) простыми числами. Метод RSA (названный по инициалам его создателей) стал самой популярной системой открытых ключей и реализован во многих коммуникационных программах.
Хотя обычно считается (хотя формально это и не доказано) , что эффективная факторизация простых чисел на классическом компьютере невозможна, в 1994 году П.У. Шор предложил эффективный алгоритм для квантовых компьютеров [11].
3.3.2 Алгоритм
В этом разделе алгоритм Шора описывается с функциональной точки зрения, что означает, что он не имеет отношения к реализации для конкретного аппаратного обеспечения архитектура. Подробная реализация алгоритма Сирака-Цоллера приведена в [13]. Более подробное математическое описание приведено в [14].
3.3.2.1 Модулярное возведение в степень
Пусть N = n1n2 с наибольшим общим делителем gcd(n1, n2) = 1 — это число, подлежащее разложению на множители, x - случайно выбранное число, простое относительно N (т.е. gcd (x, N ) = 1), и вычисляем модульную функцию возведения в степень с периодом r:
expn(k, N ) = xk mod n (по модулю N), expn(k + r, N ) = expn(k, N ), xr ; 1 mod N (по модулю N)
(3.21)
Период r равен порядку x по модулю N . Если r четный, мы можем определить y = xr/2, которая удовлетворяет условию y2 ; 1 mod N (по модулю N) и, следовательно, является решением одной из следующих систем уравнений:
y1 ; 1 по модулю n1 ; 1 по модулю n2 (3.22)
У2 ; -1 мод Н1 ; -1 мод Н2
У3 ; 1 мод Н1 ; -1 мод Н2
У4 ; -1 мод Н1 ; 1 мод Н2
Первые две системы имеют тривиальные решения y1 = 1 и y2 = -1, которые не отличаются от решений квадратного уравнения y2 = 1 в Z или поля Галуа GF (p) (т.е. Zp с простым числом p). Последние две системы имеют нетривиальные решения y3 = a, y4 = -a, как это постулируется китайским остатком
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 67
теоремой, утверждающая, что система из k одновременных соответствий (т.е. система уравнений вида y ; ai mod mi) с взаимно простыми модулями m1, . . . , mk
(т. е. gcd(mi, mj) = 1 для всех i; j) имеет единственное решение y с 0 ; x <m1m2. . . mk.
3.3.2.2 Нахождение множителя
Если r четно и y = ±a при a;1 и a; N ; 1, то (a + 1) или (a ; 1) должен иметь общий делитель с N, потому что a2 ; 1 mod N (по модулю N), что означает , что a2 = cN + 1 при c ; N и, следовательно , a2 ; 1 = (a + 1)(a ; 1) = cN . Можно найти коэффициент N, используя алгоритм Евклида для определения gcd(N, a + 1) и gcd(N, a ; 1), который определяется как
gcd(a, b) =
{
b, если a mod b = 0
gcd(b, a mod b), если a mod b6 = 0 при a > b (3.23)
Можно показать, что случайный x соответствует вышеупомянутым условиям с вероятностью p > 1/2, если N не имеет вида N = p; или N = 2p;. Поскольку существуют эффективные классические алгоритмы для разложения на множители чистых простых степеней (и , конечно, для распознавания коэффициента, равного 2), можно найти эффективный вероятностный алгоритм для разложения на множители, если период r модульного возведения в степень может быть определен за полиномиальное время.
3.3.2.3 Период последовательности
Пусть F - квантовая функция F : |x, 0; ; |x, f (x); от целочисленной функции f : Z ; Z2m с неизвестным периодом r < 2n.
Чтобы определить r, нам нужны два регистра с размерами 2n и m кубитов, которые должны быть сброшены на |0, 0;.
В качестве первого шага мы создаем однородную суперпозицию всех базовых векторов в первом регистре, применяя оператор U с
Это может быть достигнуто, например, с помощью преобразования Адамара H. Применение F к результирующему состоянию дает
Измерение второго регистра с результатом k = f (s) при s < r возвращает состояние к
ГЛАВЕ 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 68
Состояние первого регистра после измерения |;'; состоит только из базовых векторов вида |rj + s;, поскольку f (rj + s) = f (s) для всех j. Таким образом, он имеет дискретный однородный спектр.
Невозможно напрямую извлечь период r или его кратное значение путем измерения первого регистра из-за случайного смещения s. Результат однако коэффициент преобразования Фурье инвариантен (за исключением фазовых коэффициентов, которые
не влияют на спектр вероятности) к смещениям периодического распределения.
Если q = 22n кратно r, то c' i = exp(;i) /;r, если i кратно q/r, и 0 в противном случае. Но даже если r не является степенью 2, спектр | ;'; показывает отчетливые пики с периодом q/r, потому что
Это также является причиной, по которой мы используем первый регистр из 2n кубитов, когда r < 2n , потому что это гарантирует по крайней мере 2n элементов в приведенной выше сумме и, следовательно, ширину пика порядка O(1).
Если мы теперь измерим первый регистр, то получим значение c, близкое к ;q/r , при
; ; Zr. Это можно записать как c/q = c · 2;2n ; ;/r. Мы можем рассматривать это как нахождение рационального приближения a / b с a, b < 2n для двоичного числа с фиксированной точкой c · 2;2n. Эффективный классический алгоритм для решения этой задачи задача с использованием цепных дробей описана в [15] и реализована в функции знаменателя (приложение А.2).
Поскольку форма рационального числа не является однозначной, ; и r определяются как a/b = ;/r только в том случае, если gcd(;, r) = 1. Вероятность того, что ; и r взаимно просты, больше, чем 1/ln r, поэтому для получения постоянной вероятности успеха, максимально приближенной к 1, требуется всего O(n) попыток.3
3 Если предполагаемый период r' = b, полученный из рационального приближения a/b ; c2;2m , нечетный или gcd(xr'/2 ± 1, N ) = 1, то можно попытаться увеличить a/b на некоторый целочисленный коэффициент k для определения фактического периода r = kb.
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 69
3.3.3 Реализация QCL
3.3.3.1 Вспомогательные функции
При реализации алгоритма Шора используются следующие функции:
• логическое значение testprime(int n)
Проверяет, является ли n простым числом 4
• логическое значение testprimepower(int n)
Проверяет, является ли n простой степенью
• int powmod(int x,int a,int n)
Вычисляет xa mod n
• знаменатель int(действительный x,int qmax)
Возвращает знаменатель q наилучшего рационального приближения p/q ; x
с p, q < qmax
Для получения информации о фактической реализации этих функций, пожалуйста, обратитесь к приложению A.2.
3.3.3.2 Процедура shor
Процедура shor проверяет, подходит ли целое число для количественной квантовой факторизации, а затем повторяет алгоритм Шора до тех пор, пока не будет найден множитель.
процедура shor(int number) {
int width=ceil(log(number,2)); // размер числа в битах
параметр reg1[2*ширина]; // первый регистр
qureg reg2[ширина]; // второй регистр
int qmax=2^ширина;
int коэффициент; // найденный коэффициент
int m; реальный c; // измеренное значение
int x; // основание возведения
в степень int p; int q; // рациональная аппроксимация p/q
int a; int b; // возможные множители числа
int e; // e=x^(q/2) номер модуля
if number mod 2 == 0 { выход "число должно быть нечетным"; }
if testprime(число) { выход "простое число"; }
if testprimepower(число) { выход "простая мощность"; };
4 Поскольку обе тестовые функции не являются частью самого алгоритма, были использованы короткие, но неэффективные реализации с O(;n)
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 70
{
{ // генерируем случайную базу
x=этаж(случайный()*(число-3))+2;
} до тех пор, пока gcd(x,число)==1;
выведите "выбранный случайным образом x =",x;
Mix(reg1); // преобразование Адамара
expn(x,число,reg1,reg2); // мера модульного возведения
в степень reg2; // мера 2-го регистра
dft(reg1); // Преобразование Фурье
измерьте reg1,m; // сброс измерения во 2-м регистре
; // очистите локальные регистры
, если m==0 { // ошибка измерения, если 0
, выведите "измеренный ноль в 1-м регистре. повторите попытку...";
} else {
c=m*0,5^(2*ширина); // фиксированная форма точки m
q=знаменатель(c,qmax); // найти рациональное приближение
p=этаж(q*m*c+0,5);
выведите "измеренное",m,", приближение для",c,"равно",p,"/",q;
если q mod 2==1 и 2*q<qmax { // нечетное q ? попробуйте расширить p/q
выведите "нечетный знаменатель, увеличенный на 2".;
p=2*p; q=2*q;
}
if q mod 2==1 _BOS_ // ошибка, если нечетное значение q
выводит "нечетный период. пытаюсь снова...";
} else {
вывести "возможный период равен",q;
e=powmod(x,q/2,число); // вычисляем кандидатов для
a=(e+1) номера модуля; // возможные общие коэффициенты
b=(e+number-1) номер модуля; //
выводим число x,"^",q/2,"+ 1 мод",число,"=",a,",",
x,"^",q/2,"- 1 мод",число,"=",b;
коэффициент=max(gcd(число,a),gcd(число,b));
}
}
} до тех пор, пока коэффициент не будет>1, а затем коэффициент не будет<число;
выведите
}
3.3.3.3 Умножение на 15
15 - это наименьшее число, которое может быть разложено на множители с помощью алгоритма Шора, поскольку оно является произведением наименьших нечетных простых чисел 3 и 5. Для нашей реализации модульного возведения в степень требуется 2l + 1 кубит с нулевым пространством при l = [ld (15 + 1)] = 4. Самому алгоритму требуется 3l кубитов, таким образом, всего 21 кубит необходимо указать.
ГЛАВА 3. ОПЕРАТОРЫ И АЛГОРИТМЫ 71
$ qcl -b21 -i shor.qcl
qcl> shor(15)
: выбран случайный x = 4
: измерен ноль в 1-м регистре. повторите попытку...
: выбрано случайным образом x = 11
: измерено 128 , приближение для 0,500000 равно 1/2
: возможный период равен 2
: 11 ^ 1 + 1 по модулю 15 = 12 , 11 ^ 1 - 1 по модулю 15 = 10
: 15 = 5 * 3
Первая попытка завершилась неудачей, поскольку значение 0 было измерено в первом регистре |;'; и ;/r = 0 не дает никакой информации о периоде r.
Можно возразить, что это маловероятно, поскольку первый регистр имеет 8 кубитов и 256 возможных базовых векторов, однако, если необходимо разложить на множители число n, можно ожидать период около ;n, предполагая, что простые множители числа n имеют одинаковый порядок величины. Это привело бы к периоду q/;n после DFT, и вероятность p = 1/;n случайного выбора базового вектора |0; составила бы p = 25,8%.
В частном случае начального значения x = 4 период модулярного возведения в степень равен 2, поскольку 42 mod 15 (по модулю 15) = 1, следовательно, спектр Фурье
показывает 2 пика при |0; и |128; и p = 1/2.
Вторая попытка также имела такую же вероятность неудачи, начиная со 112( по сравнению с ) mod 15 = 1, но на этот раз измерение зафиксировало второй пик в спектре при |128>. При 128/28 = 1/2 = ;/r период r = 2 был определен правильно, и были найдены коэффициенты gcd(112/2 ± 1 , 15) = {3, 5} до 15.
Библиография
[1] Модели квантовых машин Тьюринга Пола Бениоффа, 1997, архив LANL
quant-ph/9708054
[2] J.I. Cirac, P. Zoller, 1995 Квантовые вычисления с холодными захваченными ионами,
Phys. Rev., Выпуск 74, 1995, 4091
[3] Д. Дойч, 1985 г., Труды Лондонского королевского общества, A 400, 97-117
[4] Дж. Груска, 1998 г., Основы вычислительной техники, глава 12: “Границы" -
Квантовые вычисления”
[5] Р. У. Кейс, 1988, IBM J. Res. Разработка. 32, 24
[6] Д. Дойч, 1989, Квантовые вычислительные сети. Труды Лондонского
королевского общества, A 439, 553-558
[7] Д. Копперсмит, 1994, Приближенное преобразование Фурье, полезное для
квантового разложения на множители, исследовательский отчет IBM № RC19642
[8] К. Х. Беннет, 1973, IBM J. Res. Разработка. 17, 525
[9] К. Х. Беннет, 1989, СИАМ Дж., вычисление. 18, 766
[10] Йоханнес Бухманн, 1996, Анализ факторов большого масштаба. Спектр для
Wissenschaft 9/96, 80-88
[11] П.В. Шор, 1994 г. Алгоритмы для квантовых вычислений: дискретные логарифмы
и разложение на множители.
[12] Сэмюэл Л. Браунштейн, 1995 Квантовые вычисления: учебное пособие
[13] Дэвид Бекман и др., 1996 Эффективные сети для квантового факторинга
[14] Артур Экерт и Ричард Джозса, 1996 Квантовый алгоритм Шора для
Разложение чисел на множители, Обзор современной физики, 68 (3), 733-753
72
БИБЛИОГРАФИЯ 73
[15] Г.Х. Харди и Э.М. Райт, 1965 г. "Введение в теорию
чисел" (4-е издание)
[16] У. Куммер и Р. Траусмут, 1988 год, "Скрипт для чтения", 131,869 -
Квантовая теория
[17] Б. Оемер, 1996, Моделирование квантовых компьютеров [неопубликовано]
Список таблиц
1.1 классические и квантовые вычислительные модели . . . . . . . . . . 4
2.1 Дискретное преобразование Фурье в QCL . . . . . . . . . . . 17
2.2 классические типы и литералы . . . . . . . . . . . . . . . . . . . . . 22
2.3 арифметические операторы . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 сравнение и логические операторы . . . . . . . . . . . . . . . . . 25
2.5 тригонометрические и гиперболические функции . . . . . . . . . . . . . 26
2.6 экспоненциальные и связанные с ними функции . . . . . . . . . . . . . . . . 26
2.7 функции для комплексных чисел . . . . . . . . . . . . . . . . . . 26
2.8 другие функции QCL . . . . . . . . . . . . . . . . . . . . . . . 27
2.9 квантовые выражения . . . . . . . . . . . . . . . . . . . . . . . 35
2.10 swap.Пользовательская реализация Swap в qcl . . . . . . . . . . . 39
2.11 иерархия подпрограмм QCL и допустимые побочные эффекты . . . . . 43
2.12 рулетка.квантовая рулетка qcl . . . . . . . . . . . . . . . . . 47
2.13 раздвоение.пользовательская реализация раздвоения в qcl . . . . . . . . . 53
74
Приложение A
Программы QCL и включают в себя
Файлы
A.1 по умолчанию.qcl
extern qufunction разветвляется(quconst a,quvoid b);
extern qufunction подкачивает(qureg a,qureg b);
внешний оператор Matrix2x2(
комплекс u00, комплекс u01,
комплекс u10, комплекс u11,
квартал q);
матрица внешних операторов 4x4 (
комплекс u00, комплекс u01, комплекс u02, комплекс u03,
комплекс u10, комплекс u11, комплекс u12, комплекс u13,
комплекс u20, комплекс u21, комплекс u22, комплекс u23,
комплекс u30, комплекс u31, комплекс u32, комплекс u33,
qureg q);
матрица внешних операторов 8x8(
комплекс u00, комплекс u01, комплекс u02, комплекс u03,
комплекс u04, комплекс u05, комплекс u06, комплекс u07,
комплекс u10, комплекс u11, комплекс u12, комплекс u13,
комплекс u14, комплекс u15, комплекс u16, комплекс u17,
комплекс u20, комплекс u21, комплекс u22,комплекс u23,
комплекс u24, комплекс u25, комплекс u26, комплекс u27,
комплекс u30, комплекс u31, комплекс u32, комплекс u33,
комплекс u34, комплекс u35, комплекс u36, комплекс u37,
комплекс u40,комплекс u41,комплекс u42, комплекс u43,
комплекс u44,комплекс u45,комплекс u46,комплекс u47,
комплекс u50, комплекс u51, комплекс u52,комплекс u53,
75
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ И ВКЛЮЧАЕМЫЕ ФАЙЛЫ QCL 76
комплекс u54, комплекс u55, комплекс u56, комплекс u57,
комплекс u60, комплекс u61, комплекс u62, комплекс u63,
сложный u64, сложный u65, сложный u66, сложный u67,
сложный u70, сложный u71, сложный u72, сложный u73,
сложный u74, сложный u75, сложный u76, сложный u77,
qureg q);
внешний параметр Perm2(int p0 ,int p1 ,последовательность q);
внешний параметр Perm4(int p0 ,int p1 ,int p2 ,int p3 ,последовательность q);
внешний параметр Perm8(
int p0 ,int p1 ,int p2 ,int p3 ,int p4 ,int p5 ,int p6 ,int p7 ,
параметр q);
внешний параметр Perm16(
int p0 ,int p1 ,int p2 ,int p3 ,int p4 ,int p5 ,int p6 , int p7 ,
int p8 ,int p9 , int p10,int p11,int p12,int p13,int p14,int p15,
параметр q);
внешняя функция Perm32(
int p0 , int p1 , int p2 , int p3 , int p4 , int p5 , int p6 , int p7 ,
int p8 , int p9 , int p10, int p11, int p12, int p13, int p14, int p15,
int p16, int p17, int p18,int p19,int p20, int p21, int p22, int p23,
int p24, int p25, int p26, int p27, int p28, int p29, int p30,int p31,
qureg q);
внешний параметр Perm64(
int p0 ,int p1 ,int p2 ,int p3 ,int p4 ,int p5 ,int p6 , int p7 ,
int p8 ,int p9 ,int p10,int p11,int p12,int p13,int p14,int p15,
int p16,int p17,int p18, инт р19, инт р20, инт р21, инт р22, инт р23,
инт р24, инт р25, инт р26, инт р27, инт р28, инт р29, инт р30, инт р31,
int p32,int p33,int p34,int p35,int p36,int p37,int p38,int p39,
int p40,int p41,int p42,int p43,int p44,int p45,int p46,int p47,
int p48, int p49,int p50,int p51,int p52, int p53,int p54, int p55,
int p56, int p57, int p58,int p59, int p60, int p61, int p62, int p63,
qureg q);
extern qufunction Not(последовательность q);
extern qufunction CNot(последовательность q,последовательность c);
фаза внешнего оператора(действительное значение phi,последовательность q);
внешний оператор Rot(real theta,qureg q);
внешний оператор Mix(qureg q);
внешний оператор qufunction ModExp(int n,int x,quconst a,quvoid b);
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ QCL И ВКЛЮЧАЕМЫЕ ФАЙЛЫ 77
логический бит(int n,int b) {
возвращает n/2^b mod 2 == 1;
}
значение функции(int n,qureg q) {
int i;
для i=0 до #q-1 {
если бит(n,i) { Не(q[i]); }
}
}
константа pi=3,141592653589793238462643383279502884197;
A.2 функции.
набор qcl разрешает переопределять 1;
// возвращает наименьший множитель > 1 из n или 1, если n является простым
int findfactor(int n) {
int i;
если n<=0 _BOS_ выход "findfactor принимает только положительные аргументы"; }
для i=2 до этажа(sqrt(n)) {
if n mod i == 0 { возвращает i; }
}
возврат 1;
}
// проверить, является ли n простым числом
, логическим значением testprime(int n) {
int i;
если n<=1 { возвращает значение false; }
для i=2 до значения floor(sqrt(n)) {
if n mod i == 0 { возвращает значение false; }
}
возвращает значение true;
}
// проверить, является ли n
логическим значением простой мощности testprimepower(int n) {
int i;
int f;
i=2;
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ QCL И ВКЛЮЧАЕМЫЕ ФАЙЛЫ 78
пока i<=этаж(sqrt(n)) и f==0 {
если n, то я == 0 { f=i; }
i=i+1;
}
для i=2 до этажа(log(n,f)) {
if f^i==n { возвращает true; }
}
возвращает false;
}
// возвращает x^a mod n
int powmod(int x,int a,int n) {
int u=x;
int y=1;
int i;
для i=от 0 до 30 {
if a/2^i mod 2 == 1 { y=y*u mod n; }
u=u^2 mod n;
}
возвращает y;
}
// возвращает модуль, обратный модулю n или 0, если gcd(a,n)>1
int invmod(int a,int n) {
int b=a;
int i;
если gcd(a,n)>1 { возвращает 0; }
для значений от i=1 до n {
если b*a по модулю n == 1 { возвращает b; }
b=b*a по модулю n;
}
возвращает 0;
}
// находит знаменатель q наилучшего рационального приближения p/q
// для x с q<qmax
в знаменателе(действительный x,int qmax) {
действительный y=x;
действительный z;
int q0;
int q1=1;
int q2;
пока это правда {
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ QCL И ВКЛЮЧАЕМЫЕ ФАЙЛЫ 79
z=y-этаж(y);
если z<0,5/qmax^2 { возвращает q1; }
y=1/z;
q2=этаж(y)*q1+q0;
if q2>=qmax { возвращает q1; }
q0=q1; q1=q2;
}
}
set allow-переопределяет значение 0;
A.3 qufunct.qcl
set allow-переопределяет значение 1;
// псевдоклассический оператор для замены порядка
битов qufunction flip(qureg q) {
int i; // объявляет счетчик циклов
для i=0 на #q/2-1 { // меняет местами 2 симметричных бита
Поменять местами(q[i],q[#q-i-1]);
}
}
// Условный Xor
, который выполняет функцию cxor(значение a,значение b,значение e) {
int i;
для i=0 до #a-1 {
CNot(b[i],a[i] & e);
}
}
// Двоичный сумматор с условным мультиплексированием для одного из 2 классических
// битов и 1 кубита.
// Полный сумматор, если #сумма=2, половинный сумматор, если #сумма=1.
qufunction muxaddbit(логическое значение a0,логическое значение a1,quconst sel,quconst b,qureg sum,quconst e) {
qureg s=sel; // повторно объявить sel как qureg
, если (a0 xor a1) { // a0 и a1 отличаются?
if a0 {Не(s); } // запишите a в кубит sect
, если #sum>1 { // установите перенос, если доступно
CNot(sum[1],sum[0] & s & e);
}
CNot(sum[0],s & e); // добавить
ПРИЛОЖЕНИЕ A. QCL-ПРОГРАММЫ И ВКЛЮЧИТЬ ФАЙЛЫ 80,
если a0 {Не(s); } // восстановить разделенный кубит.
} else {
если a0 и a1 {
если #сумма>1 { // установить перенос, если доступно
CNot(сумма[1],сумма[0] и т.д.);
}
CNot(сумма[0],e); // добавить a
}
};
// Добавить кубит b
, если #сумма>1 { // установить перенос, если доступно
CNot(сумма[1],b и сумма[0]);
}
CNot(sum[0],b); // добавить b
}
// двоичный сумматор с условным мультиплексированием для одного из 2 целых чисел
// и 1 квадратичного числа. Перенос выходных данных отсутствует.
qufunct muxadd(int a0,int a1,qureg sel,quconst b,quvoid sum,quconst e) {
int i;
для i=0 до #b-2 { // полное добавление первых #b-1 битов
muxaddbit(бит(a0,i),бит(a1,i),sel,b[i],сумма[i:i+1],e);
}
// наполовину добавляем последний бит
}
// Оператор сравнения. флаг снимается, если b<a.
// b будет перезаписан. В качестве аргумента требуется #b-1 кубитный мусорный регистр j
//, который остается незащищенным.
qufunct lt(int a,qureg b,qureg flag,quvoid j)
_BOS_ int i;
бит if(a,#b-1) _BOS_ // отключить дальнейшее сравнение
CNot(j[#b-2],b[#b-1]); // и установите флаг результата, если
нет(b[#b-1]); // MSB(a)>MSB(b)
CNot(флаг,b[#b-1]);
} else {
Не(b[#b-1]); // отключить дальнейшее сравнение
CNot(j[#b-2],b[#b-1]); // если MSB(a)<MSB(b)
}
для i=#b-от 2 до 1 шага -1 _BOS_ // продолжайте для младших битов
, если бит (a,i) _BOS_ // установите новый ненужный бит, если не определились
CNot(j[i-1],j[i] и b[i]);
Not(b[i]); // почитайте последний ненужный бит и
CNot(flag,j[i] & b[i]); // установить флаг результата, если a[i]>b[i]
} еще {
Не(b[i]);
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ QCL И ВКЛЮЧАЕМЫЕ ФАЙЛЫ 81
CNot(j[i-1],j[i] и b[i]);
}
}
бит if(a,0) {
Не(b[0]); // если все еще не определился (j[0]=1)
CNot(флаг,j[0] & b[0]); // результат - LSB(a)>LSB(b)
}
}
установить allow-переопределяет значение 0;
A.4 modarith.qcl
set allow-переопределяет значение 1;
включает "функции.qcl";
включает "qufunction.qcl";
// условное сложение по модулю n для 1 целого числа и 1 переменной
// флаг устанавливается, если a+b<n для обратимости
qufunct addn(int a,int n,quconst b,qucoid flag,qucoid sum,quconst e) {
параметр s=сумма[0\#b-1];
параметр f=сумма[#b-1];
qureg bb=b; // сумма "неправильного использования" и b в качестве нуля
lt(n-a,bb,f,s); // для оператора меньше, чем
CNot(flag,f & e); // сохранить результат сравнения
!lt(n-a,bb,f,s); // восстановить сумму и b
-умножение(2^#b+a-n,a,флаг,b,сумма,e); // добавить либо a, либо a-n
}
// Условное перезаписывающее сложение по модулю n: sum -> (a+sum) по модулю n
, которое содержит значение oaddn(int a,int n,qureg sum,quconst e) {
qureg j[#сумма];
qureg f[1];
addn(a,n,сумма,f,j,e); // мусор -> a+b mod n
Поменять местами(сумма,j); // поменять местами мусор и сумму
CNot(f,e); // переключить флаг
!addn(n-a,n,сумма,f,j,e); // вычислить значение b равным нулю
}
// Условное умножение по модулю n целого числа a на число b,
// prod <- ab mod n.
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ И ВКЛЮЧАЕМЫЕ ФАЙЛЫ QCL 82
qufunct muln(int a,int n,quconst b,qureg prod,quconst e)
_BOS_ int i;
для i=0 до #prod-1 {
если бит(a,i) { CNot(prod[i],b[0] & e); }
}
для i=1 до #b-1 {
oaddn(2^i*a mod n,n,prod,b[i] & e);
}
}
// Умножение с условной перезаписью по модулю n: b-> ab по модулю n
, которое выполняется автоматически(int a,int n,qureg b,quconst e) {
qureg j[#b];
если gcd(a,n)>1 {
выход "omuln: a и n должны быть относительно простыми";
}
muln(a,n,b,j,e);
!muln(invmod(a,n),n,j,b,e);
cxor(j,b,e);
cxor(b,j,e);
}
// Модульное возведение в степень: b -> x^a mod n
qufunct expn(int a,int n,quconst b,quvoid ex)
_BOS_ int i;
Не(например,[0]); // начните с 1
для i=0 до #b-1 {
omuln(powmod(a,2^i,n),n,например,b[i]); // ex -> ex*a^2^i mod n
}
}
установить разрешение -переопределяет значение 0;
A.5
оператор dft.qcl dft(qureg q) _BOS_ // основной оператор
const n=#q; // задает значение n для длины входных
данных int i; int j; // объявляет счетчики циклов
для значений от i=0 до n-1 {
для значений от j=0 до i-1 { // применить условные фазовые регуляторы
Фаза(2*pi/2^(i-j+1),q[n-i-1] И q[n-j-1]);
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ QCL И ВКЛЮЧАЕМЫЕ ФАЙЛЫ 83
}
Смешивать(q[n-i-1]); // вращать кубиты
}
переворачивать(q); // менять порядок битов в выходных
данных }
A.6 shor.qcl
включает "modarith.qcl".;
включить "dft.qcl";
сокращение процедуры(int number) {
int width=ceil(log(number,2)); // размер числа в битах
параметр reg1[2*ширина]; // первый регистр
qureg reg2[ширина]; // второй регистр
int qmax=2^ширина;
int коэффициент; // найденный коэффициент
int m; реальный c; // измеренное значение
int x; // основание возведения
в степень int p; int q; // рациональная аппроксимация p/q
int a; int b; // возможные множители числа
int e; // e=x^(q/2) mod number
, если число mod 2 == 0 { выход "число должно быть нечетным"; }
если testprime(число) { выход "простое число"; }
если testprimepower(число) { выход "первичная мощность"; };
{
{ // генерируем случайную базу
x=этаж(случайный()*(число-3))+2;
} пока gcd(x,число)==1;
выводим "выбранный случайным образом x =",x;
Смешиваем(reg1); // Преобразование Адамара
expn(x,число,reg1,reg2); // мера модульного возведения
в степень reg2; // мера 2-го регистра
dft(reg1); //
мера преобразования Фурье reg1,m
; // сброс 2-го регистра измерения; // очистка локальных регистров
, если m==0 { // ошибка при измерении 0
выведите "измеренный ноль в 1-м регистре. пытаюсь снова...";
} еще {
c=m*0,5^(2*ширина); // фиксированная форма точки m
q=знаменатель(c,qmax); // найти рациональное приближение
p=этаж(q*c+0,5);
выведите "измеренное",m,", приближение для",c,"равно",p,"/",q;
если q mod 2==1 и 2*q<qmax { // нечетное q ? попробуйте расширить p/q
ПРИЛОЖЕНИЕ A. ПРОГРАММЫ QCL И ВКЛЮЧАЕМЫЕ ФАЙЛЫ 84
выведите "нечетный знаменатель, увеличенный на 2".;
p=2*p; q=2*q;
}
if q mod 2==1 _BOS_ // ошибка, если нечетное значение q
выводит "нечетный период. пытаюсь снова...";
} else {
вывести "возможный период равен",q;
e=powmod(x,q/2,число); // вычисляем кандидатов для
a=(e+1) номера модуля; // возможные общие коэффициенты
b=(e+number-1) номер модуля; //
выводим число x,"^",q/2,"+ 1 мод",число,"=",a,",",
x,"^",q/2,"- 1 мод",число,"=",b;
коэффициент=max(gcd(число,a),gcd(число,b));
}
}
} до тех пор, пока коэффициент не будет>1 и коэффициент не будет<число;
выведите
}
Приложение B
Диаграммы QCL
Синтаксис B.1
Выражения B.1.1
комплексная координата ; [ + | - ] цифра { digit } [ . { digit }]
const ; цифра { разряд } [ . { цифра }]
; ( комплексная координата , complex-coord )
; истина | ложь
; " { символ } "
выражение ; константный
; идентификатор [ [ выражение [( : | .. ) выраж ] ] ]
идентификатор ; ( [ выражение { , выражение }] )
; ( выражение )
; # выражение
; выражение ^ выражение
; - выражение
; выражение ( * | / ) выражение
; выражение mod expr
; выражение ( + | - | & ) выражение
; выражение ( == | != | < | <= | > | >= ) выражение
; не выражать
; выражение и expr
; выражение ( или | xor ) выражение
85
ПРИЛОЖЕНИЕ B. ДИАГРАММЫ QCL 86
B.1.2
Блока инструкций ; { stmt { stmt } }
вариант ; буква _BOS_ буква | - }
идентификатор stmt ; [ ! ] ( [ выражение { , выражение }]) ;
; идентификатор = выражение ;
; выражение ( -> | <- | <-> ) выражение ;
; для идентификатора = expr в блок expr [ шаг expr ]
; блокировать значение while expr
; блокировать до тех пор , пока не будет выполнено значение expr ;
; блокировать значение if [ блокировать else ]
Процедурный формализм для квантовых вычислений Бер
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906718
Свидетельство о публикации №125110906718
Рецензии