Квантовое программирование в QCL Бернхард Омер

Квантовое программирование в QCL
Бернхард Омер
20 января 2000 года
Институт информационных систем
Венский Технический Университет
Электронная почта: oemer@tph.tuwien.ac.at
Домашняя страница: http://tph.tuwien.ac.at/~производитель
Содержание
1 Квантовая физика в двух словах 4
1.1 Краткая история квантовой физики. . . . . . . . . . . . . . 4
1.1.1 Части и волны . . . . . . . . . . . . . . . . . . . 4
1.1.2 Постоянная Планка . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Модель атома Бора. . . . . . . . . . . . . . . . . . . . 5
1.1.4 Корпускулярно-волновой дуализм . . . . . . . . . . . . . . . . . . 6
1.2 Волновая механика . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Классические состояния . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Волновая функция . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Уравнение Шредингера. . . . . . . . . . . . . . . . 10
1.3 Алгебраическая квантовая физика . . . . . . . . . . . . . . . . . . . 13
1.3.1 Гильбертово пространство. . . . . . . . . . . . . . . . . . . . 13
1.3.2 Операторы . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.3 Составные системы . . . . . . . . . . . . . . . . . . . . 20
2 Квантовые компьютеры 22
2.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.1 Тезис Черча-Тьюринга. . . . . . . . . . . . . . . . 22
2.1.2 Вычислительные машины . . . . . . . . . . . . . . . . . . . 23
2.1.3 Вычисления - это Физический процесс . . . . . . . . . . . 24
2.2 Компоненты Квантового Компьютера . . . . . . . . . . . . . . 25
2.2.1 Квантовая память . . . . . . . . . . . . . . . . . . . . 25
2.2.2 Обрабатывающие устройства . . . . . . . . . . . . . . . . . . . . . 29
2.2.3 Ввод и вывод данных . . . . . . . . . . . . . . . . . . . . . 34
3.2 Типы вычислений . . . . . . . . . . . . . . . . 36
2.3.1 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ КОНТРОЛЯ КАЧЕСТВА. . . . . . . . . . . . . 36
2.3.2 Квантовые машины Тьюринга. . . . . . . . . . . . . . . . 37
2.3.3 Квантовые схемы . . . . . . . . . . . . . . . . . . . . . 37
2.3.4 Языки квантового программирования . . . . . . . . . . . 38
1
СОДЕРЖАНИЕ 2
3 Квантовое программирование 41
3.1 Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1 Компьютеры и программирование . . . . . . . . . . . . . . 41
3.1.2 Требования к сложности . . . . . . . . . . . . . . . . 42
3.1.3 Гибридная архитектура . . . . . . . . . . . . . . . . . . . 42
3.2 QCL Как Классический язык . . . . . . . . . . . . . . . . . . 43
3.2.1 СТРУКТУРА программы QCL. . . . . . . . . . . . . . . 44
3.2.2 Типы данных и переменные . . . . . . . . . . . . . . . . 44
3.2.3 Выражения . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.4 Простые утверждения . . . . . . . . . . . . . . . . . . . . 47
3.2.5 Управление потоком . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.6 Классические подпрограммы . . . . . . . . . . . . . . . . . . . 50
3.3 Квантовые Состояния И Переменные. . . . . . . . . . . . . . . . . . 51
3.3.1 Управление квантовой памятью . . . . . . . . . . . . . 51
3.3.2 Квантовые переменные . . . . . . . . . . . . . . . . . . . . 54
3.3.3 Квантовые выражения . . . . . . . . . . . . . . . . . . 57
3.4 Квантовые операции . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.1 Неунитарные операции . . . . . . . . . . . . . . . . . 58
3.4.2 Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4.3 Общие операторы . . . . . . . . . . . . . . . . . . . . 60
3.4.4 Унитарные вентили . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.5 Псевдоклассические операторы . . . . . . . . . . . . . . . . 64
3.4.6 Квантовые функции . . . . . . . . . . . . . . . . . . . . 65
3.4.7 Псевдоклассические вентили . . . . . . . . . . . . . . . . . . 67
3.5 Методы программирования . . . . . . . . . . . . . . . . . . . . . 69
3.5.1 Разработка квантовых алгоритмов . . . . . . . . . . . . . 69
3.5.2 Работа с обратимостью . . . . . . . . . . . . . . . . 73
4 Квантовые алгоритмы 76
4.1 Поиск по базе данных Гровера . . . . . . . . . . . . . . . . . . . . 76
4.1.1 Формулирование запроса . . . . . . . . . . . . . . . . . . . 76
4.1.2 Алгоритм . . . . . . . . . . . . . . . . . . . . . . 77
4.1.3 Реализация . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Алгоритм Шора для квантовой факторизации . . . . . . . . . . 81
4.2.1 Мотивация . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2.2 Алгоритм . . . . . . . . . . . . . . . . . . . . . . 82
4.2.3 Квантовое преобразование Фурье . . . . . . . . . . . . . . . 85
4.2.4 Модульная арифметика . . . . . . . . . . . . . . . . . . . 86
4.2.5 Реализация . . . . . . . . . . . . . . . . . . . . . . 88
СОДЕРЖАНИЕ 3
Синтаксис QCL 96
A.1 Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
A.2 Заявления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
A.3 Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
B Алгоритм Шора в QCL 99
B.1 по умолчанию.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
B.2 функции.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
B.3 функция qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
В.4 dft.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
B.5 модарит.qcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
В.6 краткий курс квантовой физики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Глава 1
Квантовая физика в двух словах
Пока это возможно- представить квантовые вычисления строго алгебраическим образом, даже не упоминая о таких вещах “реального мира”, как электроны, состояния частиц или плотности зарядов1, некоторые базовые знания об общей квантовой физике могут значительно улучшить понимание того, почему определенные квантовые алгоритмы или методы программирования действительно работают и являются важным инструментом,  мерой предосторожности против распространенных заблуждений.
1.1 Краткая история квантовой физики
1.1.1 Частицы и волны
Важной проблемой физики до принятия квантовой теории было различие между корпускулярными и волновыми явлениями.
На первый взгляд, обе концепции имеют очень мало общего: никто не будет рассматривать летящую пулю как волновой пакет, а распространение звука — как поток частиц, но когда частицы и длины волн уменьшаются, все становится не так ясно:

В 17 веке Ньютон использовал обе теории, чтобы охватить различные аспекты света [23], объясняя его периодичность и интерференцию как волну, а линейное распространение - как явление, связанное с частицами. Позже волновая теория света стала общепринятой, поскольку такие ученые, как Янг и Френель, смогли объяснить поведение большинства частиц в рамках волнового формализма. За исключением одного фундаментального требования: Очевидное отсутствие физической среды, которое приводит к несколько надуманной и неудовлетворительной гипотезе “Эфира”.
1, который все еще должен находиться на безопасном расстоянии от представлений большинства людей о “реальном”
4
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 5
Что касается частиц, то закон множественных пропорций Дальтона предполагает,
что химические вещества состоят из атомов разной массы. В 19 веке Больцман разработал свою теорию газов, основанную на атомистических концепциях, и эксперименты с катодными лучами показали, что электрические заряды всегда кратны элементарному заряду e, который составляет примерно 1,6 ; 10-19 Кулон.
1.1.2 Постоянная Планка
В 1900 году Макс Планк объяснил энергетический спектр излучения абсолютно черного тела со специальным предположением, что возможные энергетические состояния ограничены значением E = n;v, где n - целое число, ; - частота, а h - Постоянная Планка, фундаментальная постоянная квантовой физики, со значением
h= 2n; = 6,626075 · 10;34джс
В 1888 году Герц продемонстрировал, что отрицательно заряженная пластинка разряжается под воздействием ультрафиолетового излучения. Позже Ленард обнаружил, что кинетическая энергия электронов не зависит от интенсивности света, но коррелирует
с его частотой, так что
eU = Cv ; P
с некоторой зависящей от материала константой P. В 1905 году Эйнштейн переформулировал формулу этого соотношения к
E = e(U + P) = hv = ;;
, интерпретируя E как энергию легкой частицы, позже названной фотоном.
1.1.3 Модель атома Бора
Анализируя видимый спектр водорода, было обнаружено, что интенсивность света имеет очень отчетливые пики на определенных длинах волн. В 1885 году Бальмер показал, что длина волны l очень точно определяется формулой
l = 364,56 a2 /(a2 ; 4) нм (1,1)
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 6
Это можно обобщить  уравнением Ридберга, которое также учитывает невидимые части спектра
Это говорит о том, что электрон в атоме водорода ограничен определенными энергетическими уровнями, что противоречит классической механике.
Модель Бора-Зоммерфельда учитывает это, вводя квантовое условие: Хотя предполагается, что электроны по-прежнему обращаются вокруг ядра по своим классическим орбитам, их угловой момент должен быть кратен h. Это ограничение можно было бы оправдать, приписав электрону волновые свойства и потребовав, чтобы соответствующие волновые функции образовывали стоячую волну; однако такого рода гибридная теория оставалась неудовлетворительной.
Полное решение задачи было найдено в 1923 году Гейзенбергом, который использовал формализм, основанный на матрицах. В 1925 году Шредингер опубликовал альтернативное решение, использующее комплексные волновые функции. Прошло два года, прежде чем Дирак показал, что оба формализма на самом деле эквивалентны.
1.1.4 Корпускулярно-волновой дуализм
В 1924 году де Бройль предположил, что — по аналогии с фотонами — каждую частицу с энергией E и импульсом  на самом деле можно рассматривать как волну, частота которой
; и волновой вектор задаются как
; = E/;  и (1.3)
Это соотношение было подтверждено в 1927 году в дифракционных экспериментах с электронами , проведенных Дэвисоном и Гермером. Обратный эффект — поведение фотонов в виде частиц — был продемонстрирован в 1933 году в экспериментах по электронно-фотонному рассеянию Комптоном.
1.2 Волновая механика
1.2.1 Классические состояния
В классической физике мгновенное состояние частицы определяется ее местоположением
  и скоростью .
Однако, когда мы говорим о временном поведении динамических систем, с понятием “состояние” несколько сложно работать, поскольку, по определению, текущее состояние системы постоянно меняется. Это
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 7
особенно актуально, когда речь заходит о периодическом движении, поэтому часто более уместно говорить о текущей орбите спутника (которая остается постоянной до тех пор, пока она не будет активно изменена внешним вмешательством), чем приводить фактические координаты (которые постоянно меняются).
Таким образом, в более абстрактном определении состояния изолированной классической системы - это положения  всех включенных частиц в зависимости от времени t.2
1.2.1.1 Изменения состояния
Приведенное выше определение подразумевает, что состояние системы может изменяться только при взаимодействии с другой системой.
Как правило, продолжительность взаимодействия (например, столкновения двух бильярдных шаров) очень мала по сравнению с продолжительностью изолированных состояний, поэтому для практических целей взаимодействие часто можно считать мгновенным.
1.2.1.2 Законы сохранения
Изолированные системы сохраняют свою полную энергию E и импульс3 , которые задаются как4

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

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


2 Обратите внимание, что, поскольку , это также включает скорости.
3 Существует несколько других законов сохранения углового момента, электрического заряда,
количество барионов и т.д. которые здесь не упоминаются
4 Форма потенциальной энергии V фактически определяет физическую проблему и может также зависеть от скоростей частиц, времени, спинов и т.д.
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 8
Любое текущее состояние системы может быть использовано в качестве начального значения для приведенного выше уравнения для определения ее поведения во времени.
1.2.2 Волновая функция
В квантовой физике состояние одночастичной системы характеризуется комплексной функцией распределения  с нормировкой
(1.7)
Два состояния, отличающиеся постоянным фазовым коэффициентом ei;, считаются
равнозначными.
1.2.2.1 Местоположение частицы
Классическое понятие местоположения частицы заменено пространственным распределением вероятностей ; = ;;;, которое может быть охарактеризовано его математическим ожиданием  и его неопределенность ;r, которые определяются как

1.2.2.2 Зависимость от времени Когда классическая система включает движущиеся частицы, расположение частиц зависит от времени. Это не обязательно относится к квантовым системам и описывающее распределение вероятностей ;: если квантовое состояние ; имеет вид    с 
|;(t)| = 1, то е зависит от времени.
На рисунке 1.1 показана частица, зажатая между двумя отражающими “ зеркалами”.5 Классическая частица будет периодически перемещаться из одного конца в другой с постоянной скоростью, ее местоположение может быть описано периодической треугольной функцией времени. Однако невозмущенная квантовая частица в подобной ловушке не имеет определенного местоположения; вероятность “встретить” (т.е. измерить) частица в определенном месте остается постоянной во времени6, но изменяется в пространстве, или, выражаясь более физически, частица образует стоячую волну, подобно вибрирующей фортепианной струне, зажатой между двумя неподвижными концами.
5 Математически такие идеальные “зеркала” описываются бесконечно глубокими потенциальными ямами.
6 Это относится только к собственным состояниям; в смешанных состояниях локальная вероятность может колебаться из-за различных периодов соответствующих фазовых функций ;i(t).
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 9


Рисунок 1.1: Шар, зажатый между двумя зеркалами как классическая частица и как квантовая
частица
Постоянное распределение вероятностей характерно для связанных состояний с определенной энергией, т.е. для частиц, попавших в яму с постоянным потенциалом, например, для электрона , находящегося в электрическом поле протона.
1.2.2.3 Математические ожидания
Выше было показано, как классическая концепция четко определенного местоположения частицы была заменена квантовой концепцией статистического ожидаемого значения. Однако это соответствие не ограничивается только пространством. В фактически, все классические физические величины системы могут быть описаны как ожидаемое значение соответствующего оператора (некоторые примеры приведены в таблице 1.1).
Наблюдаемый Классическое значение оператор
Местоположение ~r ~R = ~r, Ri = ri
Обороты ~р = м;~р;т ~р = ;ихъ;, Пи = ;ИИ ;;Ри
Момент импульса ~л = ~р ; ~р ~л = ~р ; ~п , ли = ;ih2ijkrj ;;РК
Энергия E = p22m + V (~r) H = ; h22m ; + V
Таблица 1.1: Некоторые наблюдаемые величины и соответствующие им операторы

По аналогии с уравнением 1.2.2.1, математическое ожидание ;O; и неопределенность-
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 10
погрешности для наблюдаемого O определяются как

1.2.3 Уравнение Шредингера
Квантовой аналогией Третьего закона Ньютона (см. уравнение 1.6) является уравнение
Шредингера

, которое определяет динамику системы частиц. Оператор Гамильтона H описывает полную энергию системы в данный момент времени и может быть очень сложным.
1.2.3.1 Уравнение Шредингера, не зависящее от времени
Если мы возьмём простой случай частицы, находящейся в поле статического потенциала V,
то уравнение 1.10 можно записать в виде

Если мы разделим зависящую от времени часть, используя анзац- подход ;(, t) = ;();(t)
из 1.2.2.2 и параметр разделения E, мы получим
Временная часть определяется как ; = e-i;t с ; = e/;. E — энергия состояния, поскольку

Оставшаяся задача на собственные значения E; = H; также называется
не зависящим от времени уравнением Шредингера.7
1.2.3.2 Энергетические спектры
В зависимости от наложенных граничных условий уравнение Шредингера часто разрешимо только для определенных значений E, т.е. оно имеет дискретный спектр энергии
7 Обратите внимание, что для этого требуется, чтобы оператор Гамильтона не зависел от времени, что не обязательно соответствует действительности
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 11
и возможные собственные значения En (также называемые энергетическими членами) можно перечислить. Решение для наименьшего собственного значения E0 называется основным состоянием ;0 системы.
Поскольку для большинства физических приложений важно только значение энергетических слагаемых, вряд ли когда-либо возникает необходимость в фактическом вычислении собственных состояний.
Квантовая физика получила свое название благодаря открытию дискретных энергетических состояний, поскольку любое изменение собственного состояния ;n на ;m предполагает обмен квантами энергии ; e = Em ; En.
1.2.3.3 Электрон в конденсаторе
В качестве примера рассмотрим электрон в конденсаторе. Для простоты конденсатор должен быть смоделирован с помощью бесконечно глубокой одномерной потенциальной ямы (см. также 1.2.2.2), таким образом
V (~R) = V (x) {0, если 0 < x < l
; в противном случае (1.14)

Это приводит нас к не зависящему от времени уравнению Шредингера

граничные условия
;(0) = 0 и ; (l) = 0 (1.16)
Подход ; (x) = N sin (kx) автоматически удовлетворяет первому критерию граничных условий BC и приводит к . Чтобы удовлетворить второму критерию BC, мы должны ввести условие квантования kl = n;. Константа нормализации N должна быть
выбрана такой, чтобы , таким образом, конечный результат равен

и соответствующие энергии

Общее решение, зависящее от времени

На рисунке 1.2 показаны первые 3 собственных состояния ;1, ;2 и ;3 и соответствующее
им пространственное распределение вероятностей ;n = |;n | 2.
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В двух СЛОВАХ 12

Рисунок 1.2: первые три собственных состояния электрона в потенциальной яме

ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 13
1.2.3.4 Трехмерная ловушка
Приведенный выше пример можно расширить до трех измерений, используя потенциальную


0, если 0 < x < L и 0 < y < L и 0 < z < l
, в противном случае
(1.21)
Это приводит к собственным функциям

и энергиям

Поскольку различные состояния могут иметь одинаковую энергию (например, E211 = E121 = E112), т.е. собственные значения оператора Гамильтона H вырождены, измерения энергии недостаточно для определения фактического распределения электронов.
1.3 Алгебраическая квантовая физика
В то время как уравнение Шредингера, в принципе, позволяет вычислить все детали распределения частиц и точные энергетические слагаемые, необходимость иметь дело с дифференциальными уравнениями в частных производных, граничными условиями и нормирующими коэффициентами обычно очень громоздкое и часто не поддается аналитическому расчету, никаким  способом.
Хотя никто не стал бы пытаться разработать цветной телевизор, решая уравнения Максвелла, обсуждение сложных квантовых систем требует более абстрактного формализма.
1.3.1 Гильбертово пространство
1.3.1.1 Состояния в виде векторов
Решения ;n(x) из примеров, приведенных в разделе 1.2.3.3 и 1.2.3.4, являются комплексными функциями на интервалах I = [0, l] или I = [0, l]3, соответственно. Давайте введем следующие сокращения8
|n; ; |;n; ; ;n(X) и ;n| ; ;;n| ; ;n * (х) (1.24)
8 Этот формализм называется нотация Брекета и внесен Дираком: в ;·| термины обозначаются как “bra”, а термины |·; - как “ket”-векторы.
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В двух СЛОВАХ 14
или, в случае k индексов

а также введем скалярное произведение ;;|;;, определяемое как

Скалярное произведение ;i|j; собственных функций ;i и ;j на примере обьёмного конденсатора (1.2.3.3) дает

Подстановка ; = ;/l x приводит к
Таким образом, собственные функции оператора Гамильтона H ортонормированы в соответствии со скалярным произведением (1.26) и поэтому образуют основу ортонормированного векторного пространства H, состоящего из всех возможных линейных комбинаций {;1, ;2, . . .}. Это пространство является гильбертовым пространством для данной конкретной задачи, и можно показать , что собственные значения любого оператора, описывающего физическую наблюдаемую величину, образуют ортогональную базу.9 
1.3.1.2 Полнота
Поскольку уравнение Шредингера является линейным дифференциальным уравнением, любая линейная комбинация решений также является решением и, следовательно, допустимым физическим состоянием. Для расчета стоимости значение ожидания ;H; энергии для данного состояния ;(х, t) мы должны решить интеграл
;H; = ;;|H|;; =;;;(x, t)H;(x, t)dx (1.29)
Если ;(x, t) задано как сумма собственных функций, как в уравнении 1.19, интегрирования можно избежать, так как
9 Поскольку физические наблюдаемые величины являются реальными величинами, соответствующие им операторы O должны быть самосопряженными, т.е. O† = O
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 15
Исходя из H |i; = Ei|i; и ;i|j; = ;ij , ;H; может быть выражена как взвешенная сумма собственных значений:
;H; = ;i|ci|2Ei (1.31)
Используя собственные функции для одномерного конденсатора (1.2.3.3), комплексные амплитуды ci для произвольной непрерывной функции f (x) на [0, l] задаются как

Здесь описано стандартное синусоидальное преобразование Фурье. Исходная функция может
быть восстановлена с помощью комбинации собственных функций ;n(x) с компонентами Фурье ci
Как и ранее, можно показать, что собственные значения любого оператора Гамильтона всегда образуют полную ортонормированную базу, таким образом
I = ;i|i><i|    при  I |;> = |;> (1.34)
1.3.1.3 Определения
Гильбертово пространство H - это линейное векторное пространство над скалярным телом C. Пусть |f ;, |g;, |h; ; H и ;, ; ; C, тогда определены следующие операции [23]:
 |f ; + |g; ; H линейная комбинация (1.35)
;|f ; ; H скалярное умножение (1.36)
|f ; + |0; = |f ; нулевой элемент (1.37)
|f ; + | ; f ; = |0; обратный элемент (1.38)
Внутреннее произведение ;·|·; удовлетворяет следующим условиям:
;f |g + h; = ;f |g; + ;f |h; (1.39)
;f |;g; = ;;f |g; (1.40)
;f|g; = (;g|f ;); (1.41)
;f |f ; = 0 ;; |f ; = |0; (1.42)
 (1.43)
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 16
1.3.2 Операторы
1.3.2.1 Операторы как матрицы
Как мы показали в 1.3.1.2, все допустимые состояния ; могут быть выражены как сумма
собственных функций, т.е.
Если мы используем {;0, ;1, . . .} в качестве единичных векторов, мы можем записать bra- и ket-векторы из ; как бесконечномерные векторы строк и столбцов

тогда независимое от времени уравнение Шредингера можно записать в виде

Оператором Гамильтона является диагональная матрица H = diag(E0, E1, . . .). В случае множественных индексов, как в 1.2.3.4, для упорядочения собственных функций может использоваться диагонализация, такая как, например, {;000, ;100, ;010, ;001, ;110, . . .}. Если такая диагонализация существует для гильбертова пространства H, то каждый линейный оператор O из H может быть записан в матричной форме с элементами матрицы
Oij = ;i|O|j;.

1.3.2.2 Физические наблюдаемые величины
Как упоминалось в 1.2.2.3, в квантовой физике физическая наблюдаемая величина O выражается в виде линейного оператора O (см. таблицу 1.1), в то время как классическим значением O является математическое ожидание ;O;. Очевидно, что значение наблюдаемой величины, такой как положение или импульс, должно быть реальным, поскольку длина (1 + i) метра не будет иметь физического значения, поэтому нам требуется ;O; ; R.
О† называется присоединённый оператор в О. Если

Глава 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 17
Если O задано в матричной форме, то O† является сопряженной перестановкой O, т. е.
O† = (OT);. Оператор O с O† = O называется само присоединённым или эрмитовым.
Все квантовые наблюдаемые представлены Эрмитовыми операторами так, мы можем переформулировать требование ;O; ; R, как ;О; = ;О;; или
;;|O|;; = (;;|O|;;); = ;;|O†|;; (1.49)
1.3.2.3 Измерение
В классической физике наблюдаемые параметры системы, такие как местоположение частиц,
их момент, энергия и т.д. считаются четко определенными объектами, которые изменяют их значения с течением времени согласно определенным динамическим законам, и, несмотря на технические трудности, их можно в принципе наблюдать, не нарушая работу самой системы. Фундаментальным открытием квантовой физики является то, что это не так.
• Измеренные значения: Измеренные значения oi всегда являются собственными значениями соответствующего им оператора O.
• Спектр вероятностей: если собственное значение oi не вырождено и имеет собственный вектор ;i, то вероятность измерения oi равна pi = |<;i|;>|2. Если собственное значение oi  вырождено в di раз, а  является ортонормированный базис соответствующего собственного пространства, тогда
(1.50)
• Уменьшение волновой функции: если собственное значение oi не вырождается, то состояние после измерения |;'; = |;i;, в противном случае

  (1.51)
Рассмотрим состояние |; , представляющее собой совокупность двух собственных состояний |;1> и |;2> не зависящего от времени уравнения Шредингера с различными собственными значениями энергии E1 и E2
|;; = c1|;1; + c2|;2;при  |c1|2 + |c2|2 = 1 (1,52)
Ожидаемое значение энергии ;H; = |c1|2E1 + |c2|2E2, но если мы на самом деле выполнив измерение, мы измерим либо E1, либо E2 с вероятностью |c1|2 и |c2|2. Однако, если мы снова измерим результирующее состояние,
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В двух СЛОВАХ 18
мы всегда будем получать ту же энергию, что и при первом измерении, поскольку волновая функция рухнула либо до ;1, либо до ;2.
|;; ;{ |;1; с вероятностью |c1|2
|;2; с вероятностью |c2|2 (1,53)
Тот факт, что ;H; является всего лишь статистической величиной, поднимает вопрос о том, когда разумно говорить об энергии состояния (или о любой другой наблюдаемой величине, если уж на то пошло) или, другими словами, существует ли физическое качество системы само по себе или оно неизменно связано с процессом измерения.
Копенгагенская интерпретация квантовой физики утверждает, что наблюдаемый O существует только в том случае, если рассматриваемая система находится в собственном состоянии соответствующего оператора O [22].
1.3.2.4 Принцип неопределенности
Разрушительный характер измерений ставит вопрос о том, могут ли два наблюдаемых объекта A и B быть измерены одновременно. Это может иметь место только в том случае, если состояние ;' после измерения является собственной функцией A и B
А|;'; = а|;'; и B|;'; = b|;'; (1.54)
Используя коммутатор [A, B] = АВ ;BA, это эквивалентно условию [А, В] = 0. Если A и B не коммутируют, то произведение неопределенностей (см. 1.2.2.3) (;A)(;B) > 0. Найти нижний предел (;А)(;B) мы представляем операторы ; A = А ; ;А; и ;B = B ; ;B; и может выразить продукт неопределенности в квадрате как
(;А)2(;B)2 = ;(;A)2;;(;B)2; = ;;|(;A)(;A)|;;;;|(;B)(;B)|;; (1.55)
Поскольку ;A и ;B самоприсоединены, мы выражаем это как (;A)2(;B)2 = ||;A;||2||;B;||2. Используя неравенство Шварца ||f ||2||g||2 ; ||f g||2 и тот факт, что [A, B] = [;A, ;B], мы получаем
(;A)(;B) ; 1/2||[A, B]|| (1.56)
Наблюдаемые с ненулевым коммутатором [A, B] размерности действия (т.е. произведения энергии и времени) канонически сопряжены. Если мы возьмем, например, операторы местоположения и импульса из 1.2.2.3, мы обнаружим, что
(;Ri)(;Pj ) ; 1/2||[ri, ;ih ;;rj]|| = 1/2h;ij (1,57)

Это означает, что невозможно определить местоположение и импульс для одной и той же координаты с произвольной точностью; однако возможно измерить местоположение в направлении x вместе с импульсом в направлении y.
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В двух СЛОВАХ 19
1.3.2.5 Темповая эволюция
В 1.2.3.1 мы показали, как можно разделить уравнение Шредингера, если  оператор Гамильтона не зависит от времени.
Если у нас есть проблема с начальным значением с ;(t = 0) = ;0, мы можем определить оператор U (t) таким образом, что
HU (t) | ;0; = ih ;;tU (t) |;0; и U (0)|;; = /;; (1,58)

Мы получаем операторное уравнение HU = ih ;/;t U с решением
U это оператор темповой эволюции и удовлетворяет критерию
U (t) |;(t0); = |;(t0 + t); (1.60)
Если |;; = ;i ci|i; представляет собой раствор-решение не зависящего от времени уравнения Шредингера, тогда

является соответствующим решением, зависящим от времени (см. 1.2.3.1).
1.3.2.6 Унитарные операторы
Оператор темповой эволюции удовлетворяет условию
Операторы U с U † = U (-1) называются унитарными. Поскольку темповая эволюция квантовой системы описывается унитарным оператором, а U †(t) = U (;t) - из этого следует, что временное поведение квантовой системы обратимо, пока не выполняется измерение.10
Унитарные операторы также могут использоваться для описания абстрактных операций, таких как вращения
Rz (;) |n1, n2, n3; = cos(;)|n1, n2, n3; + i sin(;)|n2, n1, n3; (1.63)
10 поскольку измерение может привести к уменьшению волновой функции (см. 1.3.2.3), как
правило, невозможно восстановить |;; из состояния после измерения |;';
ГЛАВА 1. КВАНТОВАЯ ФИЗИКА В ДВУХ СЛОВАХ 20
, или смена собственных состояний
Не |n; =;;;; ;1; , если n = 0
|0; , если n = 1
|n; в противном случае (1.64)

без необходимости указывать, как на самом деле выполняются эти преобразования , или иметь дело с зависящими от времени операторами Гамильтона.
Математически унитарные операции могут быть описаны как преобразования базиса между двумя ортонормированными базисами (точно так же, как вращения в R3). Пусть A и B
- эрмитовы операторы с ортонормированными собственными функциями ;n и ;n и |;; = ;i ci|;i; = ;i ci| ;i;, тогда коэффициенты Фурье  задаются формулой

1.3.3 Образуемые системы
1.3.3.1 Вращение -спин
В разделе 1.2.3.4 мы рассчитали собственные состояния ;n1,n2,n3 для электрона, находящегося в трехмерной ловушке. Реальные электроны также характеризуются ориентацией своего спина, которая может быть либо “вверх” (;), либо “вниз” (;). Таким образом, спиновое состояние |;> электрона можно записать в виде
|;; =(;
;)= ;| ; + ;/ ; при  /;|2 | /;|2 | 1 (1.66)

Спины также образуют конечное гильбертово пространство HS = C2 с ортонормированным
основанием {| ;;, | ;;}. Если мы объединим HS с пространством решений HR для задачи без
вращения (уравнение 1.22), мы получим совместное гильбертово пространство H = HR ; HB
с базовыми векторами
|Н1, Н2, Н3, з; = |;n1,Н2,Н3 ;|с; с Н1, Н2, Н3 ; Н, с ; {;, ;} (1.67)

1.3.3.2 Состояние Продукта
Если у нас есть две независимые квантовые системы A и B , описываемые операторами Гамильтона HA и Hb с ортонормированными собственными векторами ;Ai и ;Bj , которые находятся в состояниях

Глава 1. КВАНТОВАЯ ФИЗИКА ВКРАТЦЕ 21
затем общее состояние |;; дается
Такие состояния называются состояниями продукта. Унитарные преобразования и измерения применяются только для одной подсистемы не влияя на другие, так

, а вероятность pA i измерить энергию EAi в системе A равна

1.3.3.3 Запутанность
Если |;; не является состоянием продукта, то операции в одной подсистеме могут влиять
на другую. Рассмотрим два электрона с общим спин-состоянием
|;; = 1/;2 (| ;;; + | ;;;) (1.72)
Если мы измерим спин первого электрона, то получим либо |;›, либо |;› с равной вероятностью p = 1/2, что соответствует результирующему значению после измерения |;;›
или |;;›. Следовательно, если мы измерим спин второго электрона, то всегда оказывается, что он антипараллелен первому.
Две системы, общая волновая функция которых |;; не является состоянием продукта, запутаны.
11 Здесь мы предполагаем, что собственное значение EA i не вырождено, в противном случае решение аналогично уравнению 1.50.
Глава 2
Квантовые компьютеры
Применение принципов квантовой физики в области вычислений приводит к созданию концепции квантового компьютера, в котором данные хранятся не в виде битов в обычной памяти, а в виде объединенного квантового состояния многих систем кубитов с двумя состояниями.
В этой главе представлены теоретические основы, компоненты и основные операции квантового компьютера, а также несколько моделей квантовых вычислений.
2.1 Введение
2.1.1 Тезис Черча-Тьюринга
Основной идеей современной компьютерной науки является представление о вычислениях как о механическом, а не чисто умственном процессе. Метод или процедура M для достижения некоторого желаемого результата называется эффективным или механическим методом во всяком случае [17]
1. M задается в терминах конечного числа точных инструкций (каждая инструкция выражается с помощью конечного числа символов).;
2. M, если оно выполняется без ошибок, всегда приводит к желаемому результату за конечное число шагов;
3. M может (на практике или в принципе) быть выполнено человеком без помощи каких-либо механизмов, кроме бумаги и карандаша;
4. M не требует от человека, осуществляющего это, понимания или изобретательности.
22
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 23
Алан Тьюринг и Алонсо Черч формализовали приведенное выше определение, введя концепцию вычислимости с помощью машины Тьюринга и математически эквивалентную концепцию рекурсивных функций , сделав следующие выводы:
Тезисы Тьюринга LCMs [логические вычислительные машины, т.е. машины Тьюринга] может делать все, что можно было бы назвать ”эмпирическим правилом” или ”чисто механическим”. [19]
Тезис Черча о том, что функция целых положительных чисел эффективно вычислима только в том случае, если она рекурсивна. [18]
Поскольку приведенные выше утверждения эквивалентны, их обычно называют тезисом Черча-Тьюринга, который определяет сферу применения классической компьютерной науки.
2.1.2 Вычислительные машины
Несмотря на свой операционалистический подход, приведенная выше концепция вычислимости не имеет много общего с непрерывной природой физики, поэтому, чтобы построить вычислительную машину M, мы должны ввести функцию маркировки m который отображает аналоговые физические состояния S(t) (например, напряжение конденсатора) в цифровые вычислительные состояния s = (S(t)) (например, значение бита). Цифровые состояния должны быть строками из некоторого конечного алфавита ;.
Поскольку приведенное выше определение возможности расчёта требует конечного числа как символов, так и команд, функция маркировки должна применяться только к дискретным промежуточным состояниям машины S(t0), S(t1), ...таким образом, временная эволюция состояния машины S(t) отображается в виде последовательности вычислительных состояний {s0, s1, ... sn}, где каждый переход si ; si+1 соответствует одной функции Ii : ;; ; ;; из перечислимого набора I (простых) инструкций.1 Последовательность ; = {I0, I1, ... In;1} называется программой.
1 Для гипотетических машин с неограниченной памятью набор команд I также может быть бесконечным, что не соответствует первоначальному определению вычислимости (возможности расчёта), данному Тьюрингом.
Машина Тьюринга позволяет избежать этой проблемы, расширяя вычислительные состояния si целым числом p и используя это “положение головы” в качестве дополнительного параметра для генерируемых инструкций. Поскольку p (которое может быть сколь угодно большим) будет “храниться” в физическом положении головы, а не в состоянии самой головы, все равно можно утверждать, что TM работает “конечными средствами”.
Даже с нашей более простой моделью мы могли бы избежать бесконечного набора команд, например, интерпретировав состояние s = 1p0t с t ; ;; как пару s = (p, t) и определив инструкции следующим образом Ii(p, t) : N0 ; ;; ; N0 ; ;;.
Поскольку мы обсуждаем физические компьютеры, которые обычно не имеют неограниченной памяти,
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 24
Состояния s0 и sn называются входным и выходным состояниями. Таким образом, машина M = (S, m, ;, ;) реализует функцию
f (s0) = (I0 ; I1 ; . . . ; В;1)(s0), где s0 = m(S(0)) ; ;; (2.1)

2.1.3 Вычисление как физический процесс
Приведенное выше определение расчётной машины накладывает строгие ограничения на интерпретацию физических состояний. Если мы будем рассматривать расчёты как физический процесс, а не как “механическую” манипуляцию символами, как это определено в 2.1.1, мы можем отбросить все ограничения в приведенном выше определении, которые не имеют физического эквивалента.
2.1.3.1 Индетерминизм — отрицание объективности причинной связи
Как мы показали в 1.3.2.3, измерение наблюдаемой величины O с помощью соответствующего оператора O является детерминированным только в том случае, если система находится в собственном состоянии, равном O. Для учета стохастической природы квантовых измерений мы должны заменить функцию маркировки m вероятностным оператором M : H ; ;;, который случайным образом выбирает строку s в соответствии с некоторым распределением вероятностей
;; : s ; [0, 1] при ;s ;;(s) = 1.
2.1.3.2 Темповая эволюция
Поскольку неразрушающее измерение квантовой системы невозможно, и нас интересует только результат вычисления, в любом случае, нет необходимости определять маркировку для промежуточных этапов от ;(t1) до ;(tn-1) вычислений, т. е. не требуется “наблюдать” за временной (темповой) эволюцией системы, при условии наличия маркировки для входного и выходного состояний ;0 и ;n задано.
Хотя переходы ;(ti) ; ;(ti+1) по-прежнему должны соответствовать (простым) операциям Ui из перечислимого набора команд квантовых преобразований, операторы Ui не обязательно должны напрямую соответствовать функциям в ;;.2
В 1.3.2.6 мы показали, что временная эволюция квантовой системы математически описывается унитарными операторами, поэтому квантовая программа ; = {U0, U1, ... Un;1} представляет собой совокупность элементарных унитарных преобразований.

мы можем проигнорировать эту проблему и использовать более простое и общее компьютерное определение, приведенное выше.
2 Из-за обратимости унитарных операторов прямое соответствие было бы возможно только для биективных функций f : ;; ; ;;
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 25
2.2 Компоненты квантового компьютера
Классический, как и квантовый компьютер, по сути, состоит из 3 частей: памяти, в которой хранится текущее состояние компьютера, процессора, который выполняет элементарные операции над состоянием компьютера, и некоторого вида ввода/вывода , который позволяет устанавливать начальное состояние и извлекать конечное состояние расчёта.
2.2.1 Квантовая память
2.2.1.1 Кубит
Квантовой аналогией классического бита является квантовый бит или кубит. Так же, как лассический бит представлен системой, которая может принимать одно из двух различных состояний “0” и “1”, мы можем определить квантовый бит следующим образом:
Определение 1 (кубит) Кубит или квантовый бит - это квантовая система, состояние которой может быть полностью описано суперпозицией двух ортонормированных собственных состояний, обозначенных как |0; и |1;.
Общее состояние |;; ; H кубита задается формулой
|;; = ;|0; + ;|1;при  |;|2 + |;|2 = 1 (2.2)
Значением кубита является наблюдаемое значение N с эрмитовым оператором N /i; =
i |i; в гильбертовом пространстве H = C2 или в матричном представлении
N = (0 0
0 1)(2.3)

Математическое ожидание N задается формулой
;N ; = ;;/N /;; = (;; ;; ) (0 0
0 1) (;
;)= |;|2 (2.4)

таким образом, ;N ; дает вероятность нахождения системы в состоянии |1;, если
на кубите выполнено измерение.
2.2.1.2 Комбинация кубитов
Если мы объединим 2 кубита, то общее состояние результирующей системы будет следующим
|;; = ;/00; + ;/10; + ;/01; + ;/11; с /;/2 + /;/2 + /;/2 + /;/2 = 1 (2.5)

ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 26
Хотя мы все еще можем определить различные наблюдаемые величины N (1) и N (2) для значения каждый кубит с операторами N (1) |ij; = i |ij; и N (2) |ij; = j |ij;, их математическими ожиданиями
;N (1); = |;|2 + |;|2 и ;N (2); = |;|2 + |;|2 (2.6)
не позволяют нам восстановить фактическое распределение вероятностей между собственными значениями. Чтобы проиллюстрировать это, рассмотрим состояния

Все эти состояния имеют ожидаемые значения ;N (1); = ;N(2); = 1/2, т. е. если мы измеряем один кубит, то мы получим либо |0; и |1; с равной вероятностью; мы получим однако, совершенно другие пост-измерений состояния.
Если мы измеряем |1; в первом кубите, получаемые после измерения состояния есть

и математические ожидания для второго кубита теперь задаются как

2.2.1.3 Состояние машины




В то время как состояние классического компьютера может быть представлено в виде отдельных состояний всех битов в памяти и регистрах процессора, термин “состояние кубита” не имеет смысла, если состояние машины представляет собой объединенное состояние более чем одной системы3.
Определение 2 (Состояние машины) Состояние машины ; квантового компьютера с n кубитами - это текущее состояние совместной системы из n идентичных кубитных подсистем.
В целом, машины состояние ; из n-кубитов квантового компьютера дается так


3 Если только состояние машины не является состоянием продукта (см. 1.3.3.2).
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 27
Таким образом, совместное гильбертово пространство H представляет собой композицию из n 1-кубит-гильбертовых пространств Hi = C2, т.е.
H = H1 ; H2 ; . . . ; Hn =  (2.11)
Если мы интерпретируем собственные векторы |d0 . . . dn;1; как двоичные цифры, а d0 - как младший значащий бит, мы можем записать это как

Оператор Ni для значения Ni i-го кубита задается формулой
Ni |d0 . . . dn;1; = di |d0 . . . dn;1; (2.13)
и имеет математическое ожидание

2.2.1.4 Подсистемы
Как мы показали выше, память n-кубитного квантового компьютера представляет собой совмещённую систему из n идентичных кубит-подсистем. Поскольку разбиение на подсистемы носит чисто методический характер, мы можем рассматривать первые m кубитов (m < n) как единую подсистему и записать ; как
Поскольку базовые векторы |i, j; являются состояниями продукта |i, j; = |i;|j;, Гильбертово пространство H может быть записано как комбинация
Пусть U ' и U " являются унитарными операторами над H' и H", тогда коммутатор [U ', U "] = 0 как
Это означает, что унитарные преобразования, применяемые к различным подмножествам кубитов, независимы.
Унитарное преобразование U ' для первых m кубитов также не влияет на измерение остальных кубитов, поскольку вероятность p" для измерения j  в остальные n ; m кубитов, то есть после измерения состояние формы |;'; = |;j ;|j;, является инвариантной относительно U ', как

Глава 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 28
2.2.1.5 Квантовые регистры
Приведенное выше понятие подсистем m-кубитов может быть легко распространено на произвольные последовательности кубитов.
Определение 3 (Квантовый регистр) Квантовый регистр s на m кубитах представляет собой последовательность взаимно отличающихся позиций кубита на нулевой основе ;s0, s1 ... sm;1;некоторого состояния машины |;; ;  при n ; m.
Операторы переупорядочивания Пусть s - это m кубитный регистр состояния n кубитов
|;;. Используя произвольную перестановку ; над n элементами с ; i = si для i < m, мы можем построить унитарный оператор переупорядочения ;s путем перестановки кубитов.
Обратите внимание, что существует (n ; m)! перестановки ;(k) s, которые вписываются в приведенное выше определение, поскольку ni определено только для i < m.
Унитарные операторы соответствуют базовым преобразованиям (см. 1.3.2.6), поэтому мы можем записать | ;; = ;s/;; как
Как указано выше, преобразованное гильбертово пространство H может быть записано в виде комбинации
Унитарные операторы Пусть U ' - унитарный оператор m-кубита над H' и U = U ' ; I (n ; m), где I (k) - оператор идентификации k-кубита.
Для каждой перестановки ;(k) s мы можем определить оператор обратного преобразования
с элементами матрицы





Поскольку преобразованные базовые векторы  одинаковы для всех перестановок ;(k)s и
;;(k)/;;k); = ;j 'j ,


из этого следует , что обратное преобразование U ' ; I ; U не зависит от выбранной перестановки ;(k) s .
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 29
Регистрируя наблюдаемые объекты Точно так же, как в случае с отдельными кубитами, мы можем определить наблюдаемые S для данного m-кубитного регистра s с помощью оператора
S = (Nn0 , Nn1 , . . . Nnm;1 ) и Ni |d0 . . . dn;1; = di |d0 . . . dn;1; (2.25)

или, если мы интерпретируем двоичные векторы как целые числа,

2.2.2  Установки Обработки
2.2.2.1 Унитарные операторы
В классическом n-разрядном компьютере каждый вычислительный шаг может быть описан функцией перехода I: Bn ; Bn, которая принимает текущее состояние S всех битов  в качестве входных данных и возвращает соответствующее состояние после выполнения команды S'.
Как мы показали в 1.3.2.6, временная эволюция квантовой системы может быть описана унитарными операторами. Общий вид n-кубитного унитарного оператора U в гильбертовом пространстве   имеет вид
Если мы сравним булевы функции с унитарными операторами со строго функциональной точки зрения, мы можем выделить три основных различия между классическими и квантовыми операциями:
• Обратимость: поскольку унитарные операторы, по определению, соответствуют условию-
 U †U = I для каждого преобразования U существует обратное преобразование U†. Как следствие, квантовые вычисления сводятся к обратимым функциям.4
• Суперпозиции: Собственное  состояние |;; = |К; может быть преобразовано в суперпозицию-наложение состояний.

Математическое объяснение этой особенности заключается в том, что требование;i|U †U |j; = ;ij слабее, чем псевдоклассическое (см. 2.2.2.4) условие

4 Классическим аналогом был бы класс обратимых булевых функций
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 30
, которое требует, чтобы преобразованные собственные состояния были не только ортонормированными, но и имели вид U |k; = |;k; с некоторой соответствующей перестановкой (т.е. обратимой функцией) ; над  .
• Параллелизм: если машинное состояние |;; уже является суперпозицией нескольких собственных состояний, то преобразование U применяется ко всем собственным состояниям
одновременно.
Эта особенность квантовых вычислений называется квантовым параллелизмом и является следствием линейности унитарных преобразований.
2.2.2.2 Регистровые операторы
Основные команды классического компьютера обычно обрабатывают только очень небольшое количество битов и, как правило, не зависят от общего объема доступной памяти. Поэтому более полезно описывать эти инструкции не как логические функции F по всему пространству состояний Bn (в случае n битой машины), но как параметризованные функции fx над Bm, где вектор x ; Zn содержит только разрядные позиции соответствующих аргументов. Следовательно, мы относим результирующую команду F как “применение f к битам x0, x1... xn;1”.
Хотя ясно, что мы подразумеваем, например, под “заменой битов 3 и 5” на классическом компьютере, мы не можем слепо применять эту концепцию к квантовым вычислениям, поскольку унитарные операторы оперируют состояниями, а у отдельного кубита нет состояния.5
В разделе 2.2.1.5 мы определили квантовый регистр как последовательность (взаимно
различных) положений кубитов s = ;s0, s1 . . . sm;1;, которые являются квантовым аналогом приведенного выше вектора аргументов v, и класс (n ; m)! операторов переупорядочения - реорганизации ;(k) s, которые удовлетворяют условию
Определение 4 (Регистровый оператор) Регистровый оператор U (s) для m- кубитного унитарного оператора U :  и m-кубитный квантовый регистр s на n-кубитном квантовом компьютере является n-кубитным оператором
с произвольным оператором переупорядочивания ;s
5 если это не единственный кубит в квантовом компьютере, то в любом случае вопрос
об адресованных инструкциях становится спорным.
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 31
Таким образом, U (s) |;›- это то, что мы на самом деле подразумеваем под “применением оператора U к квантовому регистру s”. Поскольку их n!/(n-m)! возможные m-кубитные регистры на n-кубитной машине, данный m-кубитный оператор U может описывать n!/(n;m)! различных преобразований U (s).
По аналогии с булевыми сетями, унитарные операторы, которые могут быть применены к произвольным наборам кубитов, также называются квантовыми вентилями.
2.2.2.3 Универсальные квантовые вентили.
Хорошо известный результат классической булевой логики состоит в том, что любая возможная функция f: Bn ; Bm может быть построена как композиция из небольшого универсального набора операторов, если мы можем “связать” входы и выходы с произвольными битами в сети прямой подачи фид-форвард. Примерами универсальных наборов логических элементов являются {;,¬ }, {;,¬ } или {}.
Как упоминалось в 1.3.2.6, унитарные операции могут быть описаны как абстрактные
“вращения” в гильбертовом пространстве. Комплексное вращение одного кубита имеет общий вид

Если бы этот оператор можно было применить к произвольным двумерным подпространствам H' = C2 из H = H' ; H", то любое унитарное преобразование можно было бы построить путем композиции не более чем за шагов [14], очень похоже на общее вращение в Rn  может быть разложено на  простых вращений в координатных плоскостях.
Однако в нашем определении квантовых вентилей гейтс мы ограничены подпространствами, соответствующими квантовым регистрам (см. 2.2.1.5), поэтому в случае
n-кубитного квантового компьютера (dim H = 2n) у нас остается только n возможных 1- кубитных подпространств H' и соответствующие наборы операторов регистра U2(i)(;, ;, ;, ;). Поскольку [U2(i), U2(j)] = 0, любая композиция U из U2 элементов гейтс приведет к преобразованию вида
Таким образом, точно так же, как элемент гейтс NOT сам по себе не является универсальным для булевой логики, для создания универсального набора квантовых элементов нам требуется дополнительная 2-кубитная операция для создания запутанных многокубитных состояний.
Одной из возможностей для нетривиального 2-кубитного оператора является XOR, который определяется как XOR : |x, y; ; |x, x ; y; или в матричной записи:

ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 32
Дойч [6] показал, что множество {U2(;, ;, ;, ;), XOR} на самом деле является  универсальным для унитарного преобразования. Кроме того, поскольку {U2(;', ;', ;', ;')n} является плотным в {U2(;, ;, ;, ;)} практически для любого набора параметров, {U2, XOR} является универсальным для большинства U2 в том смысле, что любое унитарное преобразование U может быть аппроксимировано с произвольной точностью.
Дойч также предложил 3-кубитный вентиль D(;), который является универсальным, но требует только одного параметра:

2.2.2.4 Псевдоклассические операторы







Общая форма унитарного оператора U над n кубитами такова

Если матричные элементы uij имеют вид uij = ;i;j с некоторой перестановкой ;, то их влияние на базисные состояния может быть описано в терминах классической обратимой булевой логики.
Определение 5 (Псевдоклассический оператор) Псевдоклассический оператор с n-кубитами -
это унитарный оператор вида U : |i; ; |;i; с некоторой перестановкой ; над .
При ; = ;/2 универсальный немецкий элемент D(;) (2.36) вырождается в
псевдоклассический оператор

T - это 3-разрядный элемент управления not или Тоффоли гейт(вентиль), который является универсальным элементом обратимой булевой логики.
Пусть f :  - биективная функция, тогда соответствующий севдоклассический оператор F задается в виде

6 по сути, требуется, чтобы отношения между ;', ;', ;', ;' и ; были иррациональными.
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 33
2.2.2.5 Квантовые функции
Одной из очевидных проблем квантовых вычислений является их ограниченность обратимыми вычислениями. Рассмотрим простую арифметическую операцию, такую как целочисленное деление на 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 остается псевдоклассическим.7.
Определение 6 (Квантовые функции) Для любой функции f : Bn ; Bm (или эквивалентно f :  ) существует класс псевдоклассических операторов F : , работающие с входным регистром из n кубитов и выходным регистром из m кубитов с F |x, 0; = |x, f (x);. Операторы такого рода называются квантовыми функциями.
Для любой логической функции f : Bn ; Bm существует (2n+m ; 2n)! различных квантовых функций F .
2.2.2.6 Условные операторы
Классические программы допускают условное выполнение кода в зависимости от содержимого логической переменной (условное ветвление).
Унитарный оператор, с другой стороны, статичен и не имеет внутреннего управления потоком. Тем не менее, мы можем условно применить n-кубитный оператор U к квантовому регистру, используя разрешающий кубит и определяя n + 1 кубитный оператор U '

Таким образом, U применяется только к базовым векторам, для которых установлен разрешающий бит. Это может быть легко расширено до разрешающих регистров произвольной длины.
Определение 7 (Условный оператор) Условный оператор U[[e]] с разрешающим регистром e является унитарным оператором вида
7 В этом частном случае достаточно одного дополнительного кубита для хранения младшего бита аргумента , чтобы расширить DIV2 ' до унитарного оператора.
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 34
Условные операторы часто используются в арифметических квантовых функциях и других псевдоклассических операторах.
Если архитектура позволяет эффективно реализовать элемент ( вентиль, гейт) управляемого отсутствия (нот) C : |x, y1, y2 . . .; ; |(x ; ;i yi), y1, y2 . . .;, тогда условные псевдоклассические операторы могут быть реализованы простым добавлением строки enable в регистр управления всеми контролируемыми операциями отсутствия.
2.2.3 Ввод и вывод данных
2.2.3.1 Квантовые вычисления и обработка информации
В разделе 2.1.3 мы показали, что интерпретация вычислений (расчётов) как физического процесса, а не абстрактного манипулирования символами, приводит к расширенному представлению о вычислимости. Мы также определили концепцию унитарных преобразований как адекватную парадигму для “физической вычислимости”.
Унитарные преобразования описывают переход между состояниями машины и, следовательно, эволюцию квантовой системы во времени. Само понятие однако (квантовый) компьютер как “вычислительная машина” требует, чтобы эволюция физической системы соответствовала обработке информации.
Классическая теория информации требует, чтобы любая “разумная” информация могла быть выражена в виде последовательности ответов на вопросы "да" и "нет", то есть строки битов. Но в отличие от классических символьных вычислений, где каждый отдельный шаг расчёта может быть отображен в битовую строку, физические расчёты требуют такой маркировки только для начального и конечного состояния машины (см. 2.1.3.2)., меток, из которых состоят входные и выходные данные расчётов.
Это требование полностью соответствует копенгагенской интерпретации квантовой физики, которая гласит, что установка и результат любого эксперимента должны быть описаны в классических терминах.
2.2.3.2 Маркировка состояний
Поскольку машинное состояние ; недоступно напрямую, любая физически реализуемая маркировка должна соответствовать наблюдаемой O. Как было показано в 1.3.2.2, в квантовой физике наблюдаемая O выражается эрмитовым оператором O.
Естественным выбором для O на n-кубитном квантовом компьютере были бы классические значения N = (N0, N1, ... Nn;1) отдельных кубитов с эрмитовыми операторами
N = (N0, N1, . . . Nn1 ) = N0 + 2N1 + . . . + 2n;1Nn;1 (2.42)
Ni |d0 . . . dn;1; = di |d0 . . . dn;1;
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 35
Поскольку N определено только для собственных состояний N (см. 1.3.2.3), обозначение m : H ;Bn определено только для состояний ; ; H вида
|;; = ei;/d0 . . . dn-1; (2.43)
2.2.3.3 Инициализация





Для перевода квантового компьютера в желаемое начальное состояние |;0; = |s0;соответствующей логической входной строке s0, то достаточно предоставить средства для первоначального “охлаждения” всех кубитов до |0;, а затем применить любое унитарное преобразование U, которое соответствует условию U |0; = |s0;.
Определение 8 Оператор сброса R является постоянным оператором над H и определяется
как R|;› = |0›.
2.2.3.4 Измерение
Как было описано в 1.3.2.3, невозможно наблюдать квантовое состояние ;, не заставляя в то же время систему принимать состояние ;', которое является собственным состоянием эрмитова оператора O, соответствующего наблюдаемому количеству (куонтити) O. Таким образом, вероятность перехода задается как
p;;;' = |;;'/;;|2 (2.44)
Если мы измерим двоичные значения N квантового компьютера с n кубитами в состоянии

следовательно, вероятности измерения i и различных состояний после измерения  равны

pi = |ci|2 и |;'
2.2.3.5 Частичное измерение
Измерения не обязательно должны охватывать все состояние машины, но также могут быть
ограничены отдельными кубитами или квантовыми регистрами.
Рассмотрим два квантовых регистра с n и m кубитами в состоянии

ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 36
Вероятность pi измерить число i в первом регистре и соответствующее состояние после измерения |;'i; задаются как

Измерение кубитов - единственная неунитарная операция, которую квантовый компьютер должен быть способен выполнять во время вычислений.
2.3 Модели квантовых вычислений
В классической теории информации концепция универсального компьютера может быть представлена несколькими эквивалентными моделями, соответствующими различным научным подходам. С математической точки зрения, универсальный компьютер — это машина, способная вычислять частичные рекурсивные функции, считают ученые-компьютерщики, часто использующие машину Тьюринга в качестве своей любимой модели, инженеры-электрики , возможно, будут говорить о логических схемах, в то время как программисты, безусловно, предпочтут универсальный язык программирования.
Что касается квантовых вычислений, то у каждой из этих классических концепций есть
квантовый аналог: [25]
Классическая квантовая модель
Математическая частичная рекурсивная функция унитарные операторы
Машина машина Тьюринга QTM
СХЕМА Логическая схема квантовых вентилей
Алгоритмический язык программирования QPLs
Таблица 2.1: Классическая и квантовая вычислительные модели

2.3.1 Математическая модель QC
Парадигма вычислений как физический процесс требует от КК — в принципе — можно описать с помощью тех же средств, как и любой другой физической реальности, который, в области квантовой физики, математический формализм Гильбертова пространства алгебра оператора. Основы этого формализма, насколько они применимы к КК, были рассмотрены в разделе 1.3 и главе 2.
Моральным эквивалентом частично рекурсивных функций, математической концепции классической вычислимости, в КК являются унитарные операторы. Поскольку каждая классически вычислимая задача может быть переформулирована как вычисление значения
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 37
для частичной рекурсивной функции каждое квантовое вычисление должно иметь соответствующий унитарный оператор.
Математическое описание оператора по своей сути является декларативным; фактическая реализация определенной квантовой архитектуры, т. е. алгоритмическое разложение на элементарные операции, выходит за рамки этого формализма. Кроме того, поскольку математическая модель рассматривает унитарные операторы как черные ящики, мера сложности не предусмотрена.
2.3.2 Квантовые машины Тьюринга
По аналогии с классической машиной Тьюринга (ТМ) несколько положений квантовой теории- были созданы машины Тьюринга (QTM), как модель универсального квантового компьютера [3, 1].
Таким образом, полное состояние машины |;› задается путем наложения базовых состояний |l, j, s›, где l - внутреннее состояние головки, j - положение головки , а s - двоичное представление содержимого ленты. Чтобы сохранить возможность разделения H, (бесконечная) битовая строка s должна удовлетворять условию нулевого конечного состояния, т.е. допускается только конечное число битов с sm ; 0.
Квантовый аналогон функции перехода классического вероятностного TM - это ступенчатый (шаговый степ) оператор T, который должен быть унитарным, чтобы допускать существование соответствующего гамильтониана (см. 1.3.2.5) и удовлетворять условиям локализации для задействованного ленточного кубита, как и для перемещения головки.
QTMS обеспечивают измерение времени выполнения, но, как и в случае с классическим TM, поиск подходящего оператора шага может быть очень сложным, а сложность во время выполнения (т.е. количество применений T по отношению к размеру задачи) остается проблемой. За рамками теории квантовой сложности QTM имеют второстепенное значение.
2.3.3 Квантовые схемы
Квантовые схемы являются эквивалентом КК классических логических сетей с прямой подачей, с одним существенным отличием: поскольку все квантовые вычисления должны быть унитарными, все квантовые схемы могут быть вычислены в обоих направлениях (как в классической обратимой логике). Квантовые схемы состоят из элементарных элементов (гейтс) и работают с кубитами, таким образом, dim(H) = 2n, где n - (фиксированное) количество кубитов. Таким образом, “подключение” между элементами управления соответствует унитарным операторам переупорядочивания ;s (см. 2.2.1.5).
По сравнению с классическими булевыми сетями с прямой связью (фид-форвард) это накладывает следующие ограничения:
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 38
• Разрешены только сети n-to-n, т.е. общее количество входов должно соответствовать общему количеству выходов.
• Разрешены только n-to-n вентилей.
• Разветвление входов запрещено. Это напрямую связано с тем фактом, что кубиты не могут быть скопированы, т.е. не существует единой операции
Копировать |;;/0; ; /;;/;; с /;; ; C2 (2.49)

который может преобразовать общее состояние кубита в собственное производное состояние.
• “Тупики” не допускаются. Опять же, это связано с удалением кубита
Стереть |;; ; /0; с помощью |;; ; C2 (2.50)

это не унитарная операция.
Чтобы обеспечить реализацию всех возможных унитарных преобразований, должен быть доступен универсальный набор элементарных элементов управления, из которых могут быть созданы составные элементы управления (см. 2.2.2.3). Каждый элемент управления m-кубитный U, таким образом, описывает до n!/(n;m)! различных унитарных преобразований U (s) в зависимости от подключения входов (см. 2.2.2.2).
В отличие от операторного формализма, логарифмическая запись является по своей сути конструктивным методом, и, в отличие от QTMS, сложность задачи напрямую отражается на количестве логарифмов, необходимых для ее реализации.
2.3.4 Языки квантового программирования
Когда дело доходит до программирования и разработки неклассических алгоритмов, мы можем рассматривать математическое описание как спецификацию, а квантовые схемы - как язык ассемблера QC.
Как и классические языки программирования, языки квантового программирования (QPLS) предоставляют конструктивные средства для определения последовательности элементарных операторов, допуская при этом вложенные уровни абстракции.
2.3.4.1 Управление потоком
В своей простейшей форме квантовый алгоритм состоит всего лишь из однократного преобразования и последующего измерения результирующего состояния. Это позволило бы например, это может иметь место, если квантовый компьютер используется для имитации поведения другой квантовой системы.

ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ 39
классическая структура управления
квантовые операции
сброс состояния машины
унитарное преобразование
измерение состояния машины
оценка результатов измерений
найдено решение?
начало
ОСТАНОВИТЬ
нет
да
Рисунок 2.1: Простой неклассический алгоритм

Для более “традиционных” вычислительных задач, таких как, например, поиск или математические вычисления, эффективные квантовые реализации часто имеют форму вероятностных алгоритмов. На рис. 2.1 показана основная схема вероятностного неклассического алгоритма с простым циклом вычисления.
Более сложные квантовые алгоритмы, такие как, например, алгоритм Шора для квантуум -факторинга (см. 4.2) также может включать классические случайные числа, частичные измерения, вложенные циклы вычисления и множественные условия завершения:
Реальные квантовые операции, такие как сброс состояния машины, унитарные преобразования и измерения, погружены в классическую структуру управления потоком.
Формальным способом описания классической структуры управления является рассмотрение квантовых операций как специальных операторов (утверждений) в рамках классического процедурного языка. Поэтому любой QPL также должен быть универсальным языком программирования.
2.3.4.2 Спецификация операторов
Классические процедурные языки обеспечивают различные уровни абстракции, позволяя группировать примитивы в многократно используемые подпрограммы (procedures), которые могут работать с различными данными (параметрами, ссылками) и использовать их временно
ГЛАВА 2. КВАНТОВЫЕ КОМПЬЮТЕРЫ с 40
выделенную память (локальные переменные).
Если эта концепция используется для определения унитарных операторов, то должны быть предусмотрены элементы языка, которые учитывают обратимость унитарного преобразования и нелокальную природу запутанных квантовых битов.
• Математическая семантика: Действие оператора должно быть униформно и должно быть ограничено состоянием квантовой машины, т. е. использование оператора не должно влиять на классическое состояние машины.
Это означает, что реализация оператора должна зависеть только от его параметров и не должна вызывать никаких побочных эффектов. Это особенно важно исключает использование глобальных переменных и недетерминированных функций (таких как случайные числа).
• Унитарность: необходимо обеспечить, чтобы операторы были ограничены унитарным преобразованием. Это исключает неунитарные квантовые операции, такие как измерение.
• Обратимость: Поскольку для любого унитарного оператора существует обратный сопряженный (присоединненный) оператор, QPL должен предоставлять средства для выполнения операторов в обратный ход.
• Символьные регистры: оператор должен уметь работать с любым набором кубитов. Для этого требуется умение определять символьные квантовые регистры.
Глава 3
Квантовое программирование
В этой главе обсуждается программирование квантовых компьютеров и разработка квантовых алгоритмов на экспериментальном квантовом языке программирования QCL.
3.1 Введение
3.1.1 Компьютеры и программирование
Как было показано в разделе 2.1.2, компьютер - это, по сути, устройство, которое
1. сохраняет физическое состояние машины S
2. способен выполнять набор четко определенных инструкций I для преобразования между состояниями машины
3. предоставляет средства для инициализации и измерения состояния машины, интерпретируя S как дискретные символьные вычислительные (расчётные) состояния s
Последовательность команд ; = ;I1, I2, . . . In; для преобразования исходного состояния S в конечное состояние Sn называется программой.
Способ, которым на самом деле задается ;, зависит от вычислительной модели; возможности варьируются от явного перечисления, использования сетей прямой связи (фид форвард) (как в логических схемах) и деревьев решений до конечных автоматов (как в машине Тьюринга).
Общим требованием к любому методу спецификации является то, что механизм используемый для создания ; не должен быть более мощным или сложным, чем машина, на которой он выполняется, что, в первую очередь, противоречило бы цели использования компьютера.
41
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 42
3.1.2 Требования к сложности
Как указывалось в разделе 2.3.4, QPLS используют классический универсальный язык программирования для определения фактической последовательности ; команд для квантового компьютера. Согласно приведенному выше критерию, такой подход полезен только в том случае, если квантовые компьютеры по меньшей мере столь же мощны, как универсальные классические компьютеры.
Если мы рассматриваем квантовый компьютер с вентилем Тоффоли (см. 2.2.2.4) в качестве единственной доступной команды, то любое преобразование состояния машины
должно иметь вид

Поскольку логический элемент Тоффоли универсален для обратимой булевой логики, любая биективная булева функция g может быть непосредственно реализована на квантовом компьютере.
Общая булева функция f над Bn может быть реализована с помощью псевдоклассического оператора F
Таким образом, любая классически вычислимая функция f также может быть реализована на квантовом компьютере. Более того, К. Х. Беннет показал, что обратимая реализация f может быть реализована с максимальными затратами O(2) по времени и O(;n) по пространственной сложности (см. 3.5.2). [8]
С другой стороны, поскольку общее квантовое состояние n-кубита состоит максимум
из 2n собственных состояний с ненулевой амплитудой, унитарные преобразования принимают форму линейных операторов и, следовательно, могут быть описаны как
классический компьютер может моделировать любой унитарный оператор с произвольной точностью- вычисление осуществляется путем кодирования комплексных амплитуд в виде двоичных чисел с фиксированной точкой. Однако в общем случае это потребует экспоненциальных затрат как во времени , так и в пространстве.
Из-за стохастической природы квантовых измерений эмулирующему компьютеру также потребуется источник истинной случайности (например , вероятностная машина Тьюринга).
3.1.3 Гибридная архитектура
Таким образом, QPLS можно рассматривать как языки метапрограммирования, поскольку программа предназначена для запуска не на самом квантовом компьютере, а на ( вероятностном) классическом компьютере, который, в свою очередь, управляет квантовым компьютером. В
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ
43
 двоичное состояние программы
измеряемые значения
состояние квантовой машины
квантовые операции
классический ввод
классический вывод
Программа QCL

Рисунок 3.1: Гибридная архитектура QCL

с точки зрения классической информатики, вы можете описать эту установку как универсальный компьютер с квантовым оракулом. Рисунок 3.1 иллюстрирует эту гибридную
архитектуру.
С точки зрения пользователя, квантовые программы ведут себя точно так же, как и любая другая классическая программа, в том смысле, что они принимают классические входные данные, такие как параметры запуска или интерактивные данные и выдает классический результат.  Состояние управляющего компьютера (т.е. программный счетчик, значения переменных, а также отображение квантовых регистров) также является строго классическим и называется состоянием программы.
Фактическая программа ;, т.е. последовательность квантовых команд , состоящая из элементарных логических элементов, команд измерения и инициализации , передается квантовому компьютеру по четко определенному интерфейсу, в то время как возвращаемый вывод ограничен двоичными значениями измерений. Квантовый компьютер не требует какой-либо управляющей логики, поэтому его вычислительное состояние может быть полностью описано общим квантовым состоянием ; его кубитов, также называемым состоянием машины.
3.2 QCL как классический язык





Поскольку вычислительная модель QPLs представляет собой классический компьютер с
квантовым оракулом, QCL содержит все функции классического универсального
языка программирования, такие как переменные, циклы, подпрограммы и условное
ветвление.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ44
3.2.1 Структура программы QCL
Синтаксическая структура QCL-программы описывается контекстно-свободной грамматикой
LALR(1) (см. приложение A) с инструкциями и определениями в виде верхних символов:
qcl-input ; { stmt | def }
3.2.1.1 Инструкции
Инструкции варьируются от простых команд, от вызовов процедур до сложных структур управления и выполняются при их обнаружении.
qcl> if random()>=0.5 { выводится "red"; } else { выводится "black"; }
: red
3.2.1.2 Определения
Определения не выполняются, но привязывают значение (определение переменной или константы) или блок кода (определение процедуры) к символу (идентификатору).
qcl> счетчик int=5;
qcl> int fac(int n) { если n<=0 {возвращает 1;} else {возвращает n*fac(n-1);} }

Следовательно, каждый символ имеет связанный с ним тип, который может быть либо типом данных, либо типом процедуры и определяет, осуществляется ли доступ к символу посредством ссылки или вызова.
3.2.1.3 Выражения
Многие операторы и процедуры принимают аргументы определенных типов данных. Эти выражения могут состоять из литералов, ссылок на переменные и подвыражений, объединенных операторами и вызовами функций.
qcl> выведите "5 из 10:",fac(10)/fac(5)^2,"комбинации".
: 5 из 10: 252 комбинаций.

3.2.2 Типы данных и переменные
Классическими типами данных QCL являются арифметические типы int, вещественные и
комплексные, а также общие типы boolean и string.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 45
типы описание Примеры
int integer 1234, -1
real действительное число 3.14, -0.001
complex сложное комплексное число (0,-1), (0.5, 0.866)
boolean логическое значение true, false
string строка символов "hello world", ""
Таблица 3.1: классические типы и литералы

3.2.2.1 Константы
Часто используемые значения могут быть определены как символьные константы. Синтаксис
объявления константы -
const-def ; const identifier = expr ;
Определение pi в стандартном включаемом файле например,
 const pi=3.141592653589793238462643383279502884197;
3.2.2.2 Переменные
Определение переменных в QCL аналогично C:
var-def ; идентификатор типа [ = expr ] ;

Если начальное значение не задано, новая переменная инициализируется нулем, false или
"" соответственно. Значение переменной может быть изменено путем присвоения, ввода пользователем (см. 3.2.4.3) и квантового измерения (см. 3.4.1):
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)

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 46
3.2.3 Выражения
3.2.3.1 Операторы
В таблице 3.2 показаны все операторы QCL, упорядоченные от высокого к низкому приоритету.1 Все бинарные операторы являются левоассоциативными, таким образом, a ; b ; c = (a ; b) ; c. Явная группировка может быть достигнута с помощью круглых скобок.
Операции описание Тип аргумента
# размера регистра квантовые типы
^ мощность всех арифметических
целых чисел степень int
- унарный минус вся арифметика
* умножение  вся арифметика
/ деление вся арифметика
целочисленное деление int
mod, целочисленный модуль int
+ сложение вся арифметика
- вычитание вся арифметика
& объединение в строку строка, квантовые типы
== равно все арифметические значения, строка
!= неравно все арифметические значения, строка
< меньше целое, действительное
<= меньше или равно int, действительное
> больше int, действительное
>= больше или равно int, действительное
not логическое значение не boolean
and логическое значение и, boolean
или включающее логику, или логическое
xor исключающее или логику логическое значение boolean
Таблица 3.2: Операторы QCL

Арифметические операторы обычно работают со всеми арифметическими типами данных и
возвращает наиболее общий тип (перегрузка оператора), например.
1 Для полноты картины в таблицу 3.2 также включены операторы # и &, которые принимают
квантовые регистры в качестве аргументов, см. 3.4.3.1 и 3.3.3.2
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 47

qcl> вывести 2+2; // вычисляется как int
: 4
qcl> вывести 2+2.0; // вычисляется как реальный
: 4.000000
qcl> вывести 2+(2,0); // вычисляется как сложный
: (4.000000,0.000000)

Чтобы обеспечить чистую целочисленную арифметику, существуют два исключения, позволяющие избежать приведения типов:
• Оператор деления / выполняет целочисленное деление, если оба аргумента являются целыми числами.
• Оператор степени ^ для целых оснований определен только для неотрицательных целых показателей. Для действительных показателей основание должно быть неотрицательным.
3.2.3.2 Функции
Выражения QCL также могут содержать вызовы встроенных или определяемых пользователем функций.
В таблице 3.3 показаны все встроенные унарные арифметические функции.
Тригонометрическая функция. Гиперболическая функция.
sin(x) синус x sinh(x) гиперболический синус x
cos(x) косинус x cosh(x) гиперболический косинус x
tan(x) тангенс x tanh(x) гиперболический тангенс x
cot(x) котангенс x coth(x) гиперболический котангенс x
Сложная функция. Экспоненциальная функция, связанная с ней.
Re(z) действительная часть z exp(x) e, возведенная в степень x
Im(z) мнимая часть z log(x) натуральный логарифм x
abs(z) величина z log(x,n) логарифм по основанию x
conj(z) сопряженный из z sqrt(x) квадратный корень из x
Таблица 3.3: Арифметические функции QCL

В дополнение к вышесказанному, QCL также содержит n-арные функции, такие как minimum или gcd, функции преобразования и псевдофункцию random() (таблица 3.4). Поскольку последняя не является функцией в математическом смысле, она не может использоваться в рамках определения пользовательских функций и квантовых операторов.
3.2.4 Простые инструкции,утверждения
3.2.4.1 Присваивание
Значение любой классической переменной может быть задано оператором присваивания =.
Правое значение должно быть того же типа, что и переменная. В con-
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 48
Функция. Описание
ceil(x) - ближайшее целое число к x (округленное в большую сторону)
этаж(x) - ближайшее целое число к x (округленное в меньшую сторону)
max(x,...) максимальный
min(x,...) минимальный
gcd(n,...) наибольший общий делитель
lcm(n,...) наименьшее общее кратное
случайное() случайное значение из [0, 1)
Таблица 3.4: другие функции

QCL, в отличие от арифметических операторов и встроенных функций, неявное приведение
типов не выполняется.
qcl> сложный z;
qcl> z=pi; // приведение
типов не выполняется! несоответствие типов: недопустимое назначение
qcl> z=conj(pi); // неявное приведение типов

3.2.4.2 Вызов
Синтаксис вызова процедуры следующий:
stmt ; идентификатор ( [ выражение { , выражение }]) ;

Как и в случае присваиваний, для классических типов аргументов не выполняется приведение типов.
Из-за потенциальных побочных эффектов, влияющих на состояние программы, вызов процедуры может не выполняться в рамках определения функций или операторов.
3.2.4.3 Ввод данных
Команда ввода запрашивает ввод данных пользователем и присваивает значение идентификатору переменной. При желании вместо стандартного запроса может быть задана строка запроса expr , которая указывает тип и имя переменной.
qcl> real n;
qcl> введите "Введите количество итераций:",n;
? Введите количество итераций: 1000

3.2.4.4 Вывод
Команда print выводит список выражений, разделенных запятыми, на консоль. Перед каждым выводом ставится двоеточие и переводится новая строка.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 49
qcl> int i=3; действительный x=pi; комплексный z=(0,1); логическое значение b;
qcl> вывести i,x,z,b;
: 3 3.141593 (0.000000,1.000000) ложь

3.2.5 Управление потоком
3.2.5.1 Блоки
Все инструкции по управлению потоком работают с блоками кода. Блок - это список
инструкций, заключенных в фигурные скобки:
block ; { stmt { stmt } }
Блоки могут содержать только исполняемые инструкции, без определений. В отличие от C, a
блок не является составным оператором и всегда является частью управляющей структуры. Чтобы избежать двусмысленностей при вложении, фигурные скобки обязательны даже для отдельных команд.
3.2.5.2 Условное ветвление
Инструкции if и if-else допускают условное выполнение блоков в зависимости от значения логического выражения.
stmt ; if expr block [ else block ]
Если значение expr равно true, выполняется if-блок. Если значение параметра expr равно false, выполняется блок else, если он определен.
3.2.5.3 Подсчет циклов
для-циклы принимают идентификатор счетчика типа integer, который увеличивается от
expr from к expr to . Тело цикла выполняется для каждого значения идентификатора .
stmt ; для идентификатора = expr from к блоку expr to [ step expr step ]

Внутри тела счетчик обрабатывается как константа.
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 .
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 50
3.2.5.4 Условные циклы
QCL поддерживает два типа условных циклов:
stmt ; while expr блокирует
; блокирует до тех пор, пока не будет выполнено expr ;
Цикл while повторяется до тех пор, пока не будет выполнено условие expr. Когда значение expr равно false, цикл завершается. Цикл until выполняется хотя бы один раз и повторяется до тех пор, пока не будет выполнено условие expr.
3.2.6 Классические подпроцедуры
3.2.6.1 Функции
Пользовательские функции могут быть любого классического типа и принимать произвольное количество классических параметров. Значение функции передается вызывающему выражению с помощью инструкции return. Локальные переменные могут быть определены в верхней части тела функции.
int Fibonacci(int n) { // вычисляем n-е
число Фибоначчи int i; // Число Фибоначчи
int f; // путем итераций
от i = 1 до n {
f = 2*f+i;
}
return f;
}

QCL требует, чтобы функции имели математическую семантику, поэтому их значение должно быть детерминированным, а их выполнение не должно оказывать никакого побочного влияния на состояние программы.
qcl> int randint(int n) { return floor(n*random()); }
! в функции randint: недопустимая область действия: функция random не разрешена
в этой области
qcl> int foo=4711;
qcl> int bar(int n) { foo=foo+n; возвращает foo; }
! в строке функций: неизвестный символ: Неизвестная локальная переменная foo

Функции могут вызывать другие функции внутри своего тела. Также разрешены рекурсивные вызовы.
int fac(int n) { // вычислить n!
if n<2 _BOS_ // путем рекурсии
возвращает 1;
} else {
возвращает n*fac(n-1);
}
}

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 51
3.2.6.2 Процедуры
Процедуры являются наиболее общим типом рутины и используются для реализации классических структур управления квантовыми алгоритмами, которые обычно включают в себя циклы оценки, выбор применяемых операторов, интерпретацию измерений и классические вероятностные элементы.
За исключением обычных объявлений, процедуры допускают те же операции, которые доступны в глобальной области видимости (например, в командной строке), что позволяет произвольно изменять как программу, так и состояние компьютера. Операции, исключительные для процедур, - это
• Доступ к глобальным переменным
• (Псевдо) Случайные числа с помощью псевдофункции random()
• Неунитарные операции с состоянием компьютера с помощью команд reset и
measure (см. 3.4.1)
• Ввод данных пользователем с помощью команды input (см. 3.2.4.3)
Процедуры могут принимать любое количество классических или квантовых аргументов и
вызывать все типы подпрограмм.
3.3 Квантовые состояния и переменные
3.3.1 Управление квантовой памятью
3.3.1.1 Состояние машины и состояние программы
Память квантового компьютера обычно представляет собой комбинацию подсистем с двумя состояниями, называемых квантовыми битами (кубитами). Как указывалось в разделе 2.2.1.3
, “содержимое памяти” - это объединенное состояние |;; всех кубитов. Это состояние называется состоянием (квантовой) машины, в отличие от состояния программы , которое является текущим состоянием управляющего (классического) алгоритма (например, содержимое переменной, стек выполнения и т.д.), описываемого программой QCL.
Машинное состояние |;›—кубитного квантового компьютера представляет собой вектор в гильбертовом пространстве  , однако из-за деструктивного характера измерения (см. 1.3.2.3) -|;› невозможно непосредственно наблюдать и, следовательно , оно недоступно из QCL.
В связи с нехваткой в настоящее время реально работающих квантовых компьютеров, интерпретатор qcl содержит библиотеку эмуляции libqc, которая может моделировать квантовый  компьютер с произвольным количеством кубитов. Он также предоставляет интерфейс для доступа к моделируемому состоянию машины с помощью команд загрузки, сохранения и сброса данных
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 52
(см. раздел 3.3.1.6). Однако эти команды не влияют на состояние программы
.
3.3.1.2 Квантовые регистры
QCL использует концепцию квантовых регистров (см. 2.2.1.5) в качестве интерфейса между состоянием машины и управляющим классическим компьютером. Квантовый регистр является указателем на последовательность (взаимно отличающихся) кубитов и, таким образом, хотя и относится к квантовой подсистеме, все же является классической переменной.
Все операции с состоянием компьютера (за исключением команды сброса, см. 3.4.1) используют квантовые регистры в качестве операндов. Поскольку квантовый компьютер с n кубитами допускает n!/(n;m)! различныx m кубитных регистров s ; Zm n , любая операция объединения или измерения в m кубитном регистре может привести к n!/(n;m)! различным операциям над состоянием машины: это требует, чтобы все элементарные унитарные операции квантового компьютера были применимы к произвольным кубитам, и требует, чтобы физическая архитектура позволяла измерять отдельные кубиты.2
3.3.1.3 Квантовая куча
В QCL связь между регистрами и кубитами обрабатывается прозрачно путем выделения и освобождения кубитов из квантовой кучи, что позволяет использование локальных квантовых переменных. Вся свободная (т.е. нераспределенная) квантовая память должна быть пустой.
Определение 9 (Пустые регистры) Квантовый регистр s пуст, если
P0(s) |;; = |;; при P0 = |0;;0| (3.4)
При запуске или после команды сброса все состояние компьютера остается пустым,
таким образом ;;= | 0;.
Состояние машины n-кубитного квантового компьютера с m выделеным кубитами поэтому это состояние продукта -товара формы
|;; = |;;s|0;s; с S ; Zmn  s;  ; Zn;m n (3.5)

Как указывалось в 1.3.3.2, две квантовые системы, общая волновая функция которых является производным (продукта) состоянием, физически независимы. Это, в частности, означает, что ни измерения, ни унитарные преобразования выделенных битов s не повлияют на то, что s; находится в подсостоянии |0;.
Концепция квантовой кучи допускает две важные абстракции:
2 Поскольку операторы Ni для значений кубитов коммутируют (т.е. [Ni, nj ] = 0), количество физически различных операций измерения составляет всего лишь , поскольку дополнительные перестановки битов на самом деле являются классическими операциями.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 53
• Поскольку распределение регистров является прозрачным, нет необходимости указывать расположение кубитов.
• Поскольку распределенные и нераспределенные кубиты находятся в состоянии произведения, определение квантовых алгоритмов не зависит от общего количества кубитов.
3.3.1.4 Распределение регистров
Квантовые регистры распределяются, когда определена квантовая переменная. Позиции кубитов для каждого регистра можно проверить с помощью инструкции print.
$ qcl -b10 # запустите qcl-интерпретатор с 10 кубитами.
qcl> qureg a[4]; // выделяем 4-кубитный регистр
qcl> qureg b[3]; // выделяем еще один 3-кубитный регистр
qcl> вывести a,b; // показать фактические отображения кубитов
: |......3210> |...210....>
qcl> qureg c[5]; // попробуйте выделить еще 5 кубитов
! ошибка памяти: недостаточно квантовой памяти

В QCL квантовая куча организована в виде стека: кубиты перемещаются при выделении и всплывают при освобождении. Квантовый регистр освобождается, когда область действия переменной выходит за ее пределы.
qcl> qureg a[3]; // выделяем 3 кубита
qcl> процедура foo() { qureg b[2]; вывести a,b; }
qcl> foo(); // temp. будет выделен регистр b
: |.......210> |.....10...>
qcl> qureg c[3]; // выделяются еще 3 кубита
qcl> вывести a,c; // кубиты из b были восстановлены
: |.......210> |....210...>

3.3.1.5 Управление исходным (страгивания скретч) пространством
Если используются временные регистры, то, чтобы избежать повреждения квантовой кучи, необходимо убедиться, что регистр пуст, прежде чем он будет освобожден. Квантовые функции (см. 2.2.2.5) позволяют объявлять локальные квантовые переменные как исходное пространство (см. 3.3.1.5), и в этом случае “вычисление” временных регистров осуществляется прозрачно с помощью следующей процедуры, предложенной Беннетом: [8]
Пусть F - квантовая функция с регистром аргументов x (тип quconst, см. 3.3.2.2), целевым регистром y (тип quvoid, см. 3.3.2.3) и начальным регистром s (тип quscratch, см. 3.3.2.4).

Глава 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 54
Во время применения F регистр s заполняется временными ненужными битами j(i). Для восстановления s QCL выделяет вспомогательный регистр t и преобразует F в оператор F ', который определяется как
F '(x, y, s, t) = F †(x, t, s) Разветвление(t, y) F (x, t, s) (3.7)

Оператор разветвления - это квантовая функция, определяемая как
Разветвление : |i;|0; ; |i;|i; (3.8)

Применение функции F ' восстанавливает исходный регистр s и вспомогательный регистр
a до |0;, сохраняя при этом значение функции в целевом регистре t:
|i, 0, 0, 0; ; |i, 0, j(i), f (i); ; |i, f (i), j(i), f (i); ; |i, f (i), 0, 0; (3.9)
3.3.1.6 Моделирование
Интерпретатор qcl может моделировать квантовые компьютеры с произвольным числом кубитов. В соответствии с гибридной архитектурой, представленной в разделе 3.1.3, численное моделирование выполняется библиотекой (libqc) для отделения состояния классической программы от состояния квантовой машины. QCL предоставляет специальные
команды для проверки моделируемого состояния машины.
Команда dump выводит текущее состояние машины в системе счисления Braket. Когда задается квантовое выражение, вместо него выводится спектр вероятности.
qcl> qureg q[2];
qcl> Смешать(q);
qcl> сбросить;
: СОСТОЯНИЕ: 2/4 кубита выделены, 2/4 кубита свободны
0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> сбросить q[0];
: СПЕКТР q[0]: |...0>
0.5 |0> + 0.5 |1>

Текущее состояние машины может быть загружено и сохранено с помощью команды загрузить и сохранить
.
3.3.2 Квантовые переменные
Квантовые регистры, привязанные к символическому имени, называются квантовыми
переменными.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 55
3.3.2.1 Общие регистры
Общий квантовый регистр с n = expr кубитами может быть объявлен с помощью
var-def ; qureg идентификатора [ expr ] ;

Пустая квантовая память выделяется из кучи и привязывается к символьному идентификатору.
Глобальное объявление определяет постоянный квантовый регистр, который не должен быть подвержен необходимости управления исходным пространством. Это означает, что, как и в случае с классическими глобальными переменными, нет способа вернуть выделенные кубиты в пределах той же области.
Сброс состояния компьютера с помощью команды reset не влияет на привязку регистров.
[0/4] 1 |0000>
qcl> задать q[1]; // выделить кубит
qcl> сбросить; // сброс: |Psi> -> |0>
[1/4] 1 |0000>
qcl> список q; // регистр q все еще существует
: глобальный символ q = |...0>:
qreg q[1];

Квантовые типы quvoid и quscratch ограничены псевдоклассическими операторами (qufunct и эквивалентны qureg, за исключением того, что они по-разному обрабатываются управлением памятью (подробнее см. раздел 3.3.1.5).
3.3.2.2 Квантовые константы
Регистры можно объявить постоянными, используя регистр типа quconst. A квантовая постоянная должна быть инвариантна ко всем применяемым операторам.
Определение 10 (Инвариантность регистров) Квантовый регистр c считается инвариантным к регистровому оператору U (s, c), если U удовлетворяет условию
U : |i, j; = |i;s|j;c ; (Uj |i;s) |j;c (3.10)
Квантовой константы имеют фиксированный спектр вероятности: пусть |;; = ; аіј |i, j;
такой статус  машины и |;'; = U (s, c) |;; и p(J) и p'(J) проба



возможность измерения J в регистр c до и после применения оператора,
тогда
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 56
Если аргумент оператора объявлен как quconst, регистр должен быть инвариантен ко всем последующим вызовам оператора в пределах определения оператора.
qcl> operator foo(quconst c) { Rot(pi,c); }
! в operator foo: несоответствие параметров: quconst используется в качестве неконстантного
аргумента для Rot

При использовании в качестве типа аргумента к квантовой функции постоянные регистры
не заменяются при вычислении локальных исходных (промежуточных скретч) регистров (см. 3.3.1.5).
3.3.2.3 Пустые регистры
Если аргумент v для оператора объявлен quvoid, ожидается, что квантовый регистр будет пустым при обычном вызове оператора или не будет вычислен, если оператор вызывается инвертированным (см. 3.4.3.2). Таким образом, в зависимости от флага присоединения оператора, состояние машины |;; должно соответствовать до
У (в, . . .) : |;; = |0;в|;; ; |;'; или U †(в, . . .) : |;; ; |0;в|;'; (3.13)

Это можно проверить во время выполнения с помощью опции симулятора --check.
qcl> qureg q[4];
qcl> qureg 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 заменяются временным регистром, если вычисляются локальные исходные (промежуточные скретч) регистры.
3.3.2.4 Исходные (промежуточные скретч) регистры.




В качестве аргумента s для оператора регистры типа quscratch считаются явными исходными регистрами, которые должны быть пустыми при вызове оператора и должны быть вычислены до завершения работы оператора, поэтому оператор и статус машины должны удовлетворять условию
U (s, . . .) : |;; = |0;s|;; ; |0;s|;'; = |;'; (3.14)
Если в теле квантовой функции определен промежуточный (исходный скретч) регистр, для повторного освобождения регистра используется метод “вычисления” временных регистров Беннета (Bennet) (см. 3.3.1.5).
Квантовые функции, использующие локальные промежуточные (скретч) регистры, могут не брать главные (qureg) регистры в качестве аргументов.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 57
qcl> qufunct nop(qureg q) { quscratch s[1]; }
! недопустимый тип: локальные регистры scratch не могут использоваться с
аргументами qureg

3.3.2.5 Ссылки на регистры
Для удобства обращения к подрегистрам или комбинированным регистрам (см. ниже) количественным (квантовым) выражениям можно присвоить имена, объявив ссылку на регистр.
def ; идентификатор типа [ = expr ] ;
Квантовое выражение expr привязано к регистровому идентификатору квантового типа, который может быть qureg или quconst.
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.>:
qureg oddbits;
: младшие разряды глобальных символов = |............3210>:
qureg младшие разряды;

Ссылки также можно использовать для переопределения проверки типов, повторно объявив quconst как qureg, что может быть полезно, если постоянный аргумент должен быть временно
использован в качестве исходного (скретч) пространства, но позже будет восстановлен.
3.3.3 Квантовые выражения
Квантовое выражение - это анонимная ссылка на регистр, которая может использоваться
в качестве аргумента оператора или для объявления именованных ссылок (см. выше).
Выражение Описание Регистр
a ссылка ;a0, a1 . . . an;
a[i] кубит ;ai;
а[i:j] подстроки ;ai, ai+1 . . . aj ;
а[i\l] подстроки ;ai, ai+1 . . . ai+l;1;
a&b конкатенация ;a0, a1 . . . an, b0, b1 . . . bm;
Таблица 3.5: квантовые выражения

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 58
3.3.3.1 Подрегистры




К подрегистрам можно обращаться с помощью оператора подстрочного индекса [. . .]. В зависимости от синтаксиса (см. таблицу 3.5) отдельные кубиты задаются их нулевым смещением, а подстроки задаются смещением первого кубита или смещением последнего кубита (синтаксис [·:·]).) или общая длина подрегистра (синтаксис [·\·]).
qcl> создать q[8];
qcl> вывести q[3],q[3:4],q[3\4];
: |....0...> |...10...> |.3210...>

Индексы могут быть произвольными выражениями типа int. Недопустимые индексы вызывают ошибку.
qcl> int i=255;
qcl> вывести q[этаж(журнал(i,2))];
: |0.......>
qcl> напечатать q[этаж(log(i,2))\2];
! ошибка диапазона: неверный квантовый регистр

3.3.3.2 Комбинированные регистры
Регистры могут быть объединены с помощью оператора объединения &. Если регистры
перекрываются, возникает ошибка.
qcl> вывести q[4:7]&q[0:3];
: |32107654>
qcl> вывести q[2]&q[0:3];
! ошибка диапазона: квантовые регистры перекрываются

3.4 Квантовые операции
3.4.1 Неунитарные операции
Как указано в разделе 3.1.3, любое квантовое вычисление должно представлять собой совокупность инициализаций, унитарных операторов и измерений. Типичный вероятностный
квантовый алгоритм обычно выполняет цикл вычисления, подобный этому:
{
reset; // R: |Psi> -> |0>
myoperator(q); // U: |0> -> |Psi’>
измерьте q, m; // M: |Psi’> -> |m>
} пока не будет ok(m); // выбрано правильное значение m?

Команда reset сбрасывает машинное состояние |;; на |0;, которое также является начальным состоянием при запуске qcl. Квантовая куча и привязка квантовых переменных остаются неизменными.
stmt ; measure expr [ , идентификатор ] ;

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 59
Команда measure измеряет значение quantum register expr и присваивает измеренную битовую строку идентификатору переменной int. Если переменная не указана, значение отбрасывается.
Результат измерения определяется генератором случайных чисел, который по умолчанию инициализируется текущим системным временем. Для обеспечения воспроизводимости результатов моделирования можно задать начальное значение с помощью опции --seed.
Поскольку операции сброса и измерения необратимы, они не должны выполняться в рамках определений операторов.
3.4.2 Подпроцедуры
3.4.2.1 Иерархия подпроцедур
Помимо классических подпроцедур типа procedure и function, QCL предоставляет два типа квантовых процедур для общих унитарных операторов (operator) и псевдоклассических операторов (qufunct). QCL позволяет инвертировать операторы и может выполнять управление пространством с нуля (скретч) для квантовых функций, поэтому допустимые побочные эффекты как для классического состояния программы, так и для состояния квантовой машины должны быть строго заданы.
рутинный тип состояние программы состояние машины рекурсия
процедура все все да
оператор нет унитарный нет
qufunct нет псевдоклассический нет
функций нет нет да

Таблица 3.6: Иерархия подпрограмм (рутин, процедур) QCL и разрешенные побочные эффекты

4 типа подпрограмм QCL образуют иерархию вызовов, что означает, что подпрограмма может вызывать только подпрограммы того же или более низкого уровня (см. таблицу 3.6).
Математическая семантика операторов и функций QCL требует, чтобы каждый вызов был воспроизводимым. Это означает, что эти процедуры (рутины) не только не должны изменять состояние программы, но и что их выполнение никоим образом не должно зависеть от глобального состояния программы, которое включает глобальные переменные, опции и состояние внутреннего генератора случайных чисел.
3.4.2.2 Внешние процедуры (рутины)
В то время как QCL включает в себя классический язык программирования,  предоставляет все необходимые средства для изменения состояния программы, аппаратного набора нет ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 60
элементарных операторов для управления состоянием квантовой машины, поскольку для этого потребуются предположения об архитектуре моделируемого квантового компьютера.
Элементарный оператор или qufunct  можно включить, объявив его как extern.
def ; внешний идентификатор оператора arg-list ;
; внешний функциональный идентификатор arg-list ;
У внешних операторов нет тела, поскольку они не выполняются в QCL, но они просто служат связующим звеном (крюком) для двоичной функции, которая реализует требуемую операцию напрямую с помощью числовой QC-библиотеки и связана с интерпретатором.
В разделах 3.4.4 и 3.4.7 описаны элементарные унитарные и псевдоклассические вентили (гейтс), которые предоставляются встроенным симулятором qcl.
3.4.3 Общие операторы
Рутинный тип operator используется для общих унитарных операторов. В соответствии с математическим понятием оператора, вызов с одинаковыми параметрами должен приводить к точно такому же преобразованию, поэтому ни ссылок глобальных переменных, ни
 случайных элементов или зависимостей на входе  не допускается.
Поскольку тип operator ограничен обратимыми преобразованиями состояния машины, команды reset и measure также запрещены.
3.4.3.1 Аргументы оператора
Операторы работают с одним или несколькими квантовыми регистрами, поэтому вызов оператора m кубитов с общей квантовой кучей из n кубитов может привести к n! /(n;m)! различным унитарным преобразованиям.
В QCL этот полиморфизм еще больше расширяется за счет того факта, что квантовые регистры могут быть разного размера, поэтому для каждого квантового параметра s, размер регистра #s = |s| является неявным дополнительным параметром типа int. В дополнение к этому операторы могут принимать произвольное количество явных классических аргументов.
Если задано более одного регистра аргументов, их кубиты могут не перекрываться.
qcl> qureg q[4];
qcl> qureg p=q[2:3];
qcl> CNot(q[1\2],p);
! ошибка во время выполнения: квантовые аргументы перекрываются

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 61
3.4.3.2 Обратные операторы
Вызовы операторов могут быть инвертированы с помощью префикса присоединения "!". Оператор, присоединенный к композиции унитарных операторов, равен3
Поскольку последовательность применяемых вспомогательных операций задается с использованием классического процедурного языка, который не может быть выполнен в обратном порядке, инверсия композиции достигается за счет отложенного выполнения вызовов операторов.
Когда флаг присоединения установлен, выполняется тело оператора и все вызовы вспомогательных операторов помещаются в стек, который затем обрабатывается в обратном порядке с перевернутыми флагами присоединения.
3.4.3.3 Локальные регистры
В отличие от псевдоклассических операторов, в общем случае невозможно предположить (отключить-вычислите анкомпьют)  унитарный оператор, чтобы снова освободить локальный регистр, неразрушая при этом предполагаемый результат вычисления. Это фундаментальное ограничение QC, известное как теорема о неклонировании, которое вытекает из того факта, что операция клонирования, т.е. преобразование с помощью, удовлетворяет условию
U : |;;|0; ; |;;|;; (3.16)
для произвольного 4 |;; не может быть унитарным, если |;; находится в составе расчётного статуса, потому что

U может быть унитарным только в том случае, если |;; является базисным состоянием, т. е.
 |;; = |i;, и в этом случае U = Разветвление  U=Fanout.
Из-за отсутствия операции однократного (унитарного) копирования для квантовых состояний управление пространством с нуля (скретч) в стиле Беннета невозможно для обычных операторов, поскольку оно основано на клонировании результирующего регистра.
Несмотря на это ограничение, в QCL возможно выделение временных количественных регистров, но программист должен правильно вычислить (анкомпьют) их снова. Если установлена опция --check, правильность очистки проверяется симулятором.
3 Чтобы избежать двусмысленностей с некоммутативными матричными произведениями  (продуктами), мы используем соглашение;ni=1 fi = fnfn;1 . . . f1
4Ибо любое конкретное |;; бесконечное количество унитарных “клонирования” операторов тривиально существует, так, например, U; = ;i,j,k |i, j ; k;;k|;;;i, j|
Глава 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 62
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>
Локальные регистры полезны, если оператор содержит некоторые промежуточные псевдоклассические операции, для выполнения которых требуется исходное (скретч) пространство.
3.4.4 Унитарные вентили
3.4.4.1 Унитарные матрицы



Наиболее общей формой определения унитарного оператора (или любого другого линейного
преобразования) является определение его матричных элементов: унитарный оператор U из n кубитов описывает преобразование U :  и, следовательно, соответствует
матрице 2n;2n в C
Поскольку для унитарного преобразования U †U = (U *)TU = I(n), матрица U является унитарной тогда и только тогда, когда
QCL предоставляет внешние операторы для обычных унитарных 2x2, 4x4 и 8x8 матриц, которые программист может использовать для прямой реализации пользовательского набора
элементов с 1, 2 и 3 кубитами.
матрица внешних операторов 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. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 63
3.4.4.2 Вращение кубита
Вращение одного кубита определяется матрица преобразование U (;)
Коэффициент -1/ 2 до ; задается по аналогии с вращениями спина, которые, как можно показать, имеют вид D = exp(; 1/2 ;j ;j )и, следовательно, имеют период 4;.
вращение внешнего оператора (действительная тета, число q);
extern operator Rot (real teta, qureg q);
В отличие от большинства других внешних операторов, Rot не является универсальным для работы с регистрами произвольного размера.
qcl> Rot(pi/2,q);
! внешняя ошибка: вращать можно только отдельные кубиты

3.4.4.3 Элемент (гейт, вентиль) Адамара
Вентиль Адамара является частным случаем обобщенного вращения кубита и определяется матрицей преобразования H

Для случая n-кубитных регистров значение H может быть обобщено до
Векторы B' = {i ; Bn | |i'; = H |i;} образуют базу по Адамару , или двойную базу , или базовую четность для B = {i ; Bn | |i;}.
Преобразование Адамара является самоприсоединнёным (самосопряженным) (т.е. H† = H), что для унитарных операторов означает, что H2 = I.
Поскольку B' содержит только однородные суперпозиции, отличающиеся только знаками из базовых векторов, внешняя реализация H называется Mix.
оператор внешнего смешивания (qureg q);
extern operator Mix(qureg q);
3.4.4.4 Вентиль фазы по условию
Вентиль фазы по условию является патологическим случаем условного оператора (см. 2.2.2.6) для фазового оператора ei; с нулевым кубитом.
V(;) : |;; ;{ei; |;;, если 2 = 111 . . .
|;; в противном случае (3.24)

В квантовом преобразовании Фурье используется вентиль фазы по условию (см. 4.2.3).
фаза внешнего оператора (действительное число phi, число q);
extern operator Cphase(real phi, qureg q);
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 64
3.4.5 Псевдоклассические операторы
Рутинный тип qufunct используется для псевдоклассических операторов и квантовых функций, поэтому все преобразования должны иметь вид
|;; = ; i ci / i; ; ;i, jci;j;i / j; = |;'; (3.25)

с некоторой перестановкой ;. Таким образом, все псевдоклассические операторы F с n-кубитами имеют общее собственное состояние
3.4.5.1 Биективные функции
Наиболее простым применением в лоб псевдоклассических операторов является прямая реализация биективных функций (см. 2.2.2.4)
qufunction inc (qureg x) {
int i;
for i = #x-от 1 до 1 {
CNot (x[i], x [0:i-1]);
}
Not (x[0]);
}

Оператор inc сдвигает базовые векторы своего аргумента. По аналогии с бозонными состояниями, где приращение собственного состояния соответствует генерации для частицы inc является оператором создания.5
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>
3.4.5.2 Условные операторы
Когда дело доходит до более сложных арифметических операций, часто требуется применить преобразование к регистру a,  в зависимости от содержимого другого регистра e.
5 На самом деле, это не совсем верно, поскольку кроме тех промежуточных состояний (бозонов), регистр n кубитов ограничен 2n состояниями, поэтому inc |2n ; 1; = | 0;, где a† / 2n ; 1; = | 2n;
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 65
Если для выполнения преобразования требуется задать все кубиты e, оператор является условным оператором с инвариантом (quconst) возможного регистра e (см. 2.2.2.6).
Простым примером условного оператора является вентиль (элемент, гейт) Тоффоли
T : | x, y, z; ; | x ; (y ^ z), y, z; (3.27)
или, как его обобщение, управляемый элемент (вентиль) не (нот) (см. 3.4.7.4). Условную версию приведенного выше оператора приращения также легко реализовать:
qufunction cinc (qureg x,quconst e)
_BOS_ 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>
3.4.6 Квантовые функции
Как определено в п. 2.2.2.5, квантовая функция F является псевдоклассическим оператором
с характеристикой
F:|x ; x |0 ; y ; |x ; x / f (x) ; y с f: Bn ; Bm (3.28)
Если мы требуем, чтобы регистр аргументов x был инвариантен к F, объявляя x как quconst, это оставляет нам ((2m ; 1)!)2n  возможные псевдоклассические реализации F для любого заданного f. Чтобы отразить тот факт, что значение F |x, y; 0; не определено, целевой регистр должен иметь тип quvoid. (см. 3.3.2.3).
Поскольку, согласно приведенному выше определению, квантовые функции являются просто обычными псевдоклассическими операторами, спецификация которых ограничена определенными типами входных состояний, они также используют ту же процедуру QCL типа qufunction.
В следующем примере вычисляется четность x и сохраняется в y:
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 66
четность функций (число x, число 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>

3.4.6.1 Параметры царапин (скретч)
Мы можем расширить понятие квантовых функций, также допустив явный начальный регистр s (см. 3.3.2.4) в качестве необязательного параметра для F, так что в итоге мы получим оператор F (x, y, s) с характеристикой
Ф : С |Х;Х|0;г|0; - ы ; |х;х|ф (х);г|0;в (3.29)
Используя четность parity и оператор cinc из приведенных выше примеров, мы можем реализовать функцию "добавления четности" f(x) = x + четность (x) (f(x) = x + parity), предоставив исходный (скретч) кубит:
qufunction добавляет четность (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, который функционально эквивалентен:
qufunctaddparity2(quconst x,quvoid y) {
qureg 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>

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 67
Явные начальные параметры полезны для экономии памяти, если квантовая функция 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) (3.31)
если S инвариантно к x, а F инвариантно к x и s, потому что вычисление (предположение, анкомпьют) s не требует дополнительного регистра для временного сохранения y (см. 3.3.1.5). как было бы в случае, если бы вместо этого использовался управляемый локальный скретч регистр  типа quscratch (см. ниже).
3.4.7 Псевдоклассические вентили
3.4.7.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);
! внешняя ошибка: нет перестановки
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 68
3.4.7.2 Разветвление
Операция разветвления  является квантовой функцией (см. 2.2.2.5) и обозначает
класс преобразований с характеристикой  разветвление (Fanout) : |x, 0; ; |x, x;
Внешний оператор разветвления QCL определяется как
Разветвление (Fanout): |x, y; ; |x, x ; y;, (3.33)
однако полагаться на эту конкретную реализацию считается плохим стилем программирования.
внешнее разветвление extern qufunct Fanout (quconst a,quvoid b);
QCL также предоставляет специальный синтаксис a->b и a<-b в качестве сокращений для
Разветвление (Fanout)(a,b) и !Разветвление(!Fanout)(a,b).
3.4.7.3 Обмен
Оператор обмена (Swap) обменивает кубиты двух регистров одинакового размера (
Swap :|x, y; ; |y, x;). Оператор обмена кубитами один к одному имеет матрицу преобразования


extern выполняет функцию Swap(qureg a,qureg b);

Как и в случае с оператором разветвления, a<->b является синтаксическим дополнением (сахар) для Swap(a,b).
3.4.7.4 Не (нот) и контроль  не (нот)
Оператор не (нот, not) C инвертирует кубит. Его матрица преобразования равна
C = ( 0 1
1 0) (3.35)
Оператор контролируемого отсутствия C[[e]] является условным оператором (см. 2.2.2.6) для
C с регистра разрешения (возможности) е:
С[[Д]] : |Б;|2;е ;{|1 ; Б; |2;е если 2 = 111 . . .
|Б;|2;электронной иначе (3.36)

внешний параметр не работает(параметр q);
внешний параметр не работает(параметр q,параметр c);
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 69
QCL-версии Not и CNot также работают с целевыми регистрами, и в этом случае C[[e]] применяется ко всем кубитам:
se C[[e]] применяется ко всем кубитам:
qcl> параметр q[4]; параметр p[4];
qcl> Не(q);
[8/8] 1/00001111>
qcl> CNot(p,q);
[8/8] 1 |11111111>
3.5 Методы программирования
3.5.1 Разработка квантовых алгоритмов
Как было показано в разделе 3.1.2, квантовые компьютеры и вероятностные классические
компьютеры эквивалентны в вычислительном отношении, но для определенных задач квантовые алгоритмы могут обеспечить более эффективное решение, чем классические реализации.
Чтобы добиться какого-либо ускорения по сравнению с классическими алгоритмами, необходимо воспользоваться уникальными возможностями квантовых вычислений, а именно
• Наложение
• Квантовый параллелизм
• Интерференция
3.5.1.1 Наложение
Ключевым элементом любого универсального языка программирования является условное ветвление. Любая классическая программа может быть смоделирована как дерево решений, где каждый узел соответствует двоичному состоянию sn и приводит к одному или нескольким последующим успешным состояниям s(i) n+1. В детерминированной машине Тьюринга (TM) возможен только один из этих переходов sn ; s(k) n+1, поэтому вычислительный путь ;s0, s1, ... sn;предопределен.
В вероятностном TM переходы характеризуются вероятностями pi с ;i pi = 1 и одним из возможных последующих успешны состояний s(i)n+1 выбирается по ладам случайным образом.
Поскольку собственные векторы |i; непосредственно соответствуют классическим бинарным состояниям, мы могли бы интерпретировать унитарное преобразование
U : |s; ; ;s'uss' |s'; с s, s' ; Bn и uss' ; C (3.37)
как вероятностный переход из классического состояния s в последующие успешны состояния s' с вероятностями перехода ps' = |uss' |2, но если мы не выполним
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ В 70
измерения, результирующее состояние машины остается в виде суперпозиции всех
возможных классических последующих успешны состояний
Таким образом, с классической точки зрения, мы можем рассматривать унитарный оператор, который преобразует собственное состояние в суперпозицию из n собственных состояний с ненулевыми амплитудами, как 1–n-разветвительную операцию, которая позволяет квантовому компьютеру следовать нескольким классическим вычислительным путям одновременно.
Большинство неклассических алгоритмов используют это превосходство, приводя регистр к даже (чётной, ивен) суперпозиции собственных состояний, чтобы он служил пространством поиска. Этого можно достичь, применив преобразование Адамара (см. 3.4.4.3) к каждому кубиту
[0/4] 1 |0000>
qcl> создать q[2]; // выделить 2-кубитный регистр
qcl> Смешать(q[0]); // повернуть первый кубит
[2/4] 0.707107 |0000> + 0.707107 |0001>
qcl> Смешать(q[1]); // повернуть второй кубит
[2/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
Классически это можно рассматривать как бинарное дерево решений с вероятностью 50% для переключения каждого бита. Для n-кубитного регистра это приводит к 2n классическим
вычислительным путям, которые выполняются одновременно, что приводит к суперпозиции 2n собственных векторов.
Поскольку преобразования Адамара для каждого отдельного кубита коммутируют, мы можем апостериорно имитировать классическое вероятностное поведение, выполняя измерение на отдельных кубитах; таким образом, временной порядок измерений не имеет значения, поэтому мы можем принять решение по второму кубиту, прежде чем нам принимать решение по первому, и реконструировать классический вычислительный путь в обратном направлении
qcl> измерить q[1]; // второй кубит дает 0
[2/4] 0.707107 |0000> + 0.707107 |0001>
qcl> измерить q[0]; // первый кубит дает 1
[2/4] 1 |0001>
3.5.1.2 Квантовый параллелизм
Если мы ограничим унитарные преобразования псевдоклассическими операторами (см. 2.2.2.4) затем классическое дерево решений вырождается в список, и мы получаем функциональность классического обратимого компьютера, т.е. для любой биективной двоичной функции f существует соответствующий псевдоклассический оператор
Uf : |s; ; |f (s); с s ; Bn и f : Bn ; Bn (3.39)

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 71
Ограничение на биективные функции не является таким строгим, как кажется, поскольку для любой общей двоичной функции g существует соответствующая квантовая функция
Ug : |s, 0; ; |s, g(s); с s ; Bn и f : Bn ; Bn (3.40)
может быть сконструирована, которая реализуюет g с максимальными затратами O(;n) в пространстве и O(2) во времени, так что, помимо этого незначительного снижения производительности, квантовый компьютер, использующий только псевдоклассические операторы, функционально эквивалентен детерминированному классическому компьютеру.
Однако, если мы используем квантовую функцию для суперпозиции собственных состояний, одно и то же классическое вычисление выполняется со всеми битовыми строками одновременно.
В классических терминах это можно описать как векторную операцию SIMD (с одной инструкцией и несколькими датами), в квантовых терминах эта функция называется
квантовым параллелизмом.
В качестве примера рассмотрим полный двоичный сумматор
Добавить(А, Б, С) : |А;А|B;б|0; - ы ; |д;А|B;Б|а + б;с (3.42)
Используя оператор управляя-не (controlled-not) C[[e]] (см. 3.4.7.4), это можно реализовать
как
ДОБАВЛЕНИЕ(a, b, s) = C[[ab]](s1) C[[b]](s0) C[[a]](s0) с помощью s = s0s1 (3,43)
Если мы поместим кубиты-аргументы a и b в четную суперпозицию |0; и |1;, то мы сможем выполнить сложение для всех возможных комбинаций входных данных одновременно:
qcl> параметр a[1]; // аргумент a
qcl> параметр b[1]; // аргумент b
qcl> параметр s[2]; // целевой регистр s=a+b
qcl> Смешать(a & b); // привести аргументы в суперпозицию
[4/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0001> + 0.5 |0011>
qcl> CNot(s[0],a); // вычислить младший бит суммы
[4/4] 0.5 |0000> + 0.5 |0010> + 0.5 |0101> + 0.5 |0111>
qcl> CNot(s[0],b);
[4/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |0011>
qcl> CNot(s[1],a & b); // вычислить старший бит суммы
[4/4] 0.5 |0000> + 0.5 |0110> + 0.5 |0101> + 0.5 |1011>

ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 72
3.5.1.3 Интерференция (Помехи)
В то время как суперпозиционирование и квантовый параллелизм позволяют нам выполнять параллельно невероятно большое количество классических вычислений, единственный способ считывания любых результатов - это выполнить измерение, при котором все собственные состояния, кроме одного, отбрасываются. Поскольку не имеет никакого значения, определяется ли вычислительный путь во время вычисления (как с вероятностной ТМ) или апостериорно (с помощью квантовых измерений) использование квантовых компьютеров не дало бы никаких преимуществ по сравнению с вероятностными классическими компьютерами.
Однако квантовые состояния - это не просто распределение вероятностей двоичных значений, а векторы, т.е. каждое собственное состояние в суперпозиции характеризуется не реальной вероятностью, а комплексной амплитудой, так что

опишет разные состояния, даже если они имеют одинаковый спектр вероятностей.
Таким образом, при использовании вероятностной ТМ вероятности двух разных предполагаемых (компьютерных) путей, ведущие к одному и тому же конечному состоянию s, просто складываются (добавляются вверх), это не обязательно имеет место в квантовом компьютере, поскольку обычно
|; + ;|26 = |;|2 + |;|2 для ;, ; ; C (3.45)

Чтобы проиллюстрировать эту мысль, рассмотрим три состояния
|;1; = |0;, |;2; = |1; и |;3; = 1 ;2(|0; + |1;) (3.46)

Если мы применим преобразование Адамара H (см. 3.4.4.3) к собственным состояниям |;1;
и |;2;, мы получим
|;;
1; = H |;1; = 1 ;2(|0; + |1;) и |;'2; = H |;2; = 1 ;2(|0; ; |1;) (3.47)
Пока |;' 1; и |;' 2; имеют одинаковое распределение вероятностей , а |;3; просто суперпозиция |;1; и |;2;, классически мы будем считать, что |;' 3; также показывает тот же спектр вероятностей,  однако
таким образом, в случае |0; вероятности суммировались, в то время как в случае |1; комплексные амплитуды имели противоположные знаки, что приводило к частичной вероятности, равной 0. Это явление называется положительной или отрицательной интерференцией.
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 73
Таким образом, хотя вычислительные (компьютюшионал) пути в вероятностной ТМ независимы, интерференция позволяет взаимодействовать вычислениям (компьютюшион) в суперпозиционных состояниях, и именно это взаимодействие позволяет квантовому компьютеру решать определенные задачи более эффективно, чем классические компьютеры. Преобладающим принципом разработки любого квантового алгоритма для этого является использование интерференции для увеличения вероятности “интересных” собственных состояний при попытке уменьшить вероятность “скучных (далл)” состояний, чтобы повысить вероятность того, что измерение выберет одно из бывших.
Поскольку любой унитарный оператор U также может рассматриваться как базовое преобразование (см. 1.3.2.6), вышеуказанную задачу также можно переформулировать как поиск подходящей наблюдаемой для измерения, тем самым эффективно заменяя регистровую наблюдаемую S (см. 2.2.1.5) на наблюдаемую S с эрмитовым оператором
S = U (s) S U †(s) (3.49)
Если всей  машины состояние измеряется сразу, то собственные значения | |;из
являются векторами столбцов U
Преобразования Фурье, в частности, полезны, если глобальные свойства классических функций такие, как периодичность для задачи  интересны.
3.5.2 Деяния с обратимостью
В 2.2.2.5 мы показали, что для любой необратимой булевой функции f :
Bn ; Bm существует набор унитарных квантовых функций
F : |x;x|0;y ; |x;x|f (x);y с |x| = n и |y| = m (3.51)
которые могут быть использованы для обхода присущего квантовым компьютерам ограничения на обратимые операции.
3.5.2.1 Повторное использование регистра
Хотя сохранение копии аргумента позволит нам вычислять необратимые функции, это также вынуждает нас предоставлять дополнительную память для промежуточных результатов. Поскольку более длительные вычисления обычно включают в себя составление множества квантовых функций, это привело бы к постоянно растущему количеству “ненужных (джанк)” битов, которые не имеют никакого отношения к конечному результату. Простая реализация
f (x) = l(k(h(g(x)))) уже использует 3 дополнительных регистра (значения функций
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 74
представлены в префиксной записи, O обозначает квантовую функцию O : |x, 0; ; |x, o(x);,
индексы указывают на используемые регистры):
Как правило, для записи n необратимых функций требуется n — 1 регистров для хранения промежуточных результатов.
Простое и элегантное решение этой проблемы было предложено Беннетом [8, 9]: Если необходимо вычислить композицию из двух необратимых функций f (x) = h(g(x)) , то исходное (скретч) пространство для промежуточного результата может быть “переработано” с помощью следующей процедуры:
Последний шаг является просто инверсией первого шага и вычисляет промежуточный результат. Затем второй регистр может быть повторно использован для дальнейших вычислений.
Без управления с нуля (скретч) оценка состава данных с глубиной d требует выполнения 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 скретч/джанк (пустых/ненужных) регистра) будет выполняться следующим образом (значения функций указаны в префиксной записи):
Используя этот метод, мы можем сократить необходимое пространство на O(1/;d) при
вычислениях превышая O(2).
3.5.2.2 Ненужные (джанк) регистры
Если при вычислении функции f (x) пустой регистр заполняется ненужными битами j(x) (т. е.
 |x, 0, 0; ; |x, f (x), j(x);), аналогичная процедура может освободить регистр
ГЛАВА 3. КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 75
снова:
Опять же, последний шаг - это инверсия первого. Промежуточным этапом является операция разветвления (см. 3.4.7.2), которая копирует результат функции в дополнительный пустой регистр. Возможными реализациями являются, например
Разветвление : |x, y; ; |x, x ; y; или |x, (x + y) mod 2n; (3.56)
3.5.2.3 Перезапись обратимых функций
Как указывалось в п. 2.2.2.4, каждой обратимой функции f :  соответствует псевдоклассический оператор F : |i; ; |f (i);. Хотя прямая реализация F возможна с любым полным набором псевдоклассических операторов6 , реализация в виде квантовой функции может быть существенно более эффективной.
Если у нас есть эффективные реализации квантовых функций Uf : |i, 0; ;
|i, f (i); и  : |i, 0; ; |i, f -1(i);, тогда оператор перезаписи F ' может  быть сконструирован с использованием n-кубитного исходного (скретч) регистра.
6 Одним из примеров может служить элемент (гейтс) Тоффоли T : |x, y, z; ; |x ; (y ; z), y, z;, который может быть использован для реализации любого псевдоклассического оператора для 3 или более кубитов
Глава 4
Квантовые алгоритмы
В этой главе представлены два квантовых “убийцы приложения” — быстрый квантовый поиск Гровера и алгоритм факторизации Шора, которые решают традиционные задачи в области вычислительной техники и обеспечивают существенное ускорение по сравнению с самыми быстрыми известными классическими решениями.
4.1 Поиск по базе данных Гровера
Многие задачи в классической информатике можно сформулировать как поиск в списке уникального элемента, который соответствует некоторому предопределенному условию. Если нет дополнительной информации об условии поиска C, лучшим классическим алгоритмом является поиск методом перебора, т.е. элементы последовательно проверяются на соответствие C, и как только элемент соответствует условию, алгоритм завершается. Для списка из N элементов требуется выполнить в среднем N/2 сравнения.
Используя преимущества квантового параллелизма и интерференции, Гровер нашёл квантовый алгоритм, который может найти соответствующий элемент всего за O(;N ) шагов. [20]
4.1.1 Формулирование запроса
Наиболее простой способ, хотя и не самый удобный для алгоритма, реализовать условие поиска в виде квантовой функции
запрос : |x, 0; ; |x, C(x); с x ; Bn и C : Bn ; B (4.1)
поскольку это позволяет нам сформулировать проблему в рамках классической булевой логики.
76
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 77
Алгоритм Гровера может быть затем использован для решения уравнения C (x) = 1, при этом, помимо того факта, что решение существует и что оно уникально, никаких дополнительных знаний о C(x) не требуется .
Обычно, реализация запроса будет восполненной (сложной) достаточно как нельзя, позволить эффективное алгебраическое решение, но поскольку внутренняя структура C(x) не имеет значения для алгоритма, мы можем легко реализовать тестовый запрос с решением n в виде
qufunct запроса(qureg x,quvoid f,int n). {
int i;
от i=0 до #x-1 { // x -> НЕ (x XOR n)
, если не бит(n,i) { Не(x[i]); }
}
CNot(f,x); // переверните f, если x=1111..
от i=0 до #x-1 { // x <- НЕ (x XOR n)
, если не бит(n,i) { !Не(x[i]); }
}
}

Более реалистичным применением был бы поиск ключа шифрования в атаке с использованием известного открытого текста. Поскольку p является известным открытым текстом для зашифрованного текста c, реализация QCL может выглядеть следующим образом:
qufunct encrypt(int p,quconst key,quvoid c) { ... }
qufunct запрос(int c,int p,quconst ключ,quvoid f)
_BOS_ int i;
quscratch s[длина блока];
шифровать(p,ключ,s);
для i=0 до #s-1 { // s -> НЕ (s XOR p)
, если не бит(p,i) { Не(x[i]); }
}
CNot(f,x); // переверните f, если s=1111..
}
Обратите внимание, что, в отличие от приведенного выше примера, эта функция запроса использует локальный начальный (скретч) регистр, поэтому нет необходимости явно вычислять s, так как, это будет принято, за это отвечает система управления внутренним исходным (скретч) пространством QCL (см. раздел 3.3.1.5).
4.1.2 Алгоритм
4.1.2.1 Настройка пространства поиска
Пространство решений для условия C n-разрядного запроса равно Bn. На квантовом компьютере это пространство поиска может быть реализовано как суперпозиция всех
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 78
собственных состояний регистра из n кубитов, т.е.
В разделе 3.5.1.1 мы показали, как такое состояние может быть получено с помощью n-кубитного преобразования Адамара
(см. 3.4.4.3) от исходного состояния машины |0;.
4.1.2.2 Основной цикл
Основной цикл алгоритма состоит из двух этапов
1. Выполните условный фазовый сдвиг, который изменяет фазу всех собственных
векторов, соответствующих условию C, на ; радиан.
Q : |i; ;{;|i;, если C(i)
|i;, если C(i) (4.4)
2. Применение оператора диффузии
Поскольку  только один собственный вектор | i0; поддерживается для соответствия поисковому условию C, условный сдвиг фазы будет включать начальную даже суперпозицию
Влияние оператора диффузии на произвольный собственный вектор |i;
так одна итерация в состоянии формы
восходит к

Глава 4. QUANTUM ALGORITHMS 79
4.1.2.3 Число итераций
Если оператор  свыше петли DQ неоднократно применяется к первоначальной суперпозиции-
затем состояния результатов все еще находятся в форме |;(K, l) ; и комплекс амплитуд
k и l описываются следующей системой рекурсий: [21]
Использование замены sin2 ; = 1/N решение системы свыше можно записать в закрытой форме.
Вероятность p к мере i0 дается как p = k2 и имеет максимум к ; = ;/(2 (2J+1)) . Поскольку для большего перелистывания (повторений), 1;N « 1 мы можем предпололжить, что sin ; ; ; и ; » 2;, и число итераций m для максимума p является около  c  p > (N -1)/N (необходимо обойти ошибки). Иначе , если содержание с p > 1/2, затем  итераций делать.
4.1.3 Вовлечение( развертывание)
4.1.3.1 Оператор Запроса
Если мы выберем определение запроса как функцию с флагом кубита f, что позволит для строго классической реализации, предложенной в 4.1.1, затем оператор  Q может быть собран как
Q = query†(x, f) V (;) (f) query (x, f ) (4.15)
используя условные фазовые ворота V (;) (см. 3.4.4.4) и рассматривая регистр флага f как временное скретч пространство.
Глава 4. QUANTUM ALGORITHMS 80
4.1.3.2 Диффузионный Оператор
Использование преобразования Адамара Н (см. 3.4.4.3) и  фазы вращения по условию R: |i; = - (-1) ;i0 / и, диффузионный оператор
можно также написать как D = HRH с тех пор
 и
Используя оператор not из 3.4.7.4 и условный фазовый элемент V (;), мы можем реализовать оператор диффузии в виде
оператора diffuse(qureg q) {
Смешать(q); // Преобразование Адамара
Не(q); // Инвертировать q
CPhase(pi,q); // Повернуть, если q=1111..
!Не(q); // отменить инверсию
!Смешать(q); // отменить преобразование Адамара
}
На самом деле, приведенный выше оператор реализует ;D, но поскольку общие этапы
не имеют физического значения, это не имеет значения.
4.1.3.3 Процедура гровер grover
Используя вышеописанное, мы теперь можем предоставить QCL-реализацию полного алгоритма:
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 81
процедура Гровера(int n) {
int l=этаж(log(n,2))+1; // количество кубитов
int m=ceil(pi/8*sqrt(2^l)); // количество итераций
int x;
int i;
параметр q[l];
параметр f[1];
{
сброс;
Смешать(q); // подготовить суперпозицию
для i= 1 - m { // основной цикл
запрос(q,f,n); // вычислить C(q)
CPhase(pi,f); // отрицание |n>
!запрос(q,f,n); // отмена C(q)
рассеяния(q); // оператор рассеяния
}
измерение q,x; //
вывод значения "измерено",x;
} до тех пор, пока x==n;
}
Аргумент процедуры n - это число, которое необходимо найти; размер квантовых регистров, а также количество итераций устанавливаются соответствующим образом:
qcl> grover(500);
: 9 кубитов с использованием 9 итераций
: измерено 500
qcl> grover(123);
: 7 кубитов, используя 5 итераций
: измерено 74
: измерено 123
qcl> grover(1234);
: 11 кубитов, используя 18 итераций
: измерено 1234

4.2 Алгоритм Шора для квантовой факторизации
4.2.1 Мотивация
В отличие от поиска и умножения больших простых чисел, эффективного классического алгоритма для факторизации больших чисел не известно. Алгоритм называется эффективным, если время его выполнения, т.е. количество элементарных операций, пропорционально многочлену от длины его входных данных, измеряемой в битах. Самому известному (или, по крайней мере, опубликованному) классическому алгоритму (квадратичной сетке)
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ
82) требуется O (exp ((64/9 )1/3 N 1/3(ln N )2/3)) операций для разложения на множители двоичного числа из N бит [12], т.е. масштабируются экспоненциально в зависимости от размера входных данных.
Таким образом, умножение больших простых чисел является односторонней функцией, т.е. функцией, которая может быть легко вычислена в одном направлении, в то время как ее инверсия практически невозможна. Односторонние функции играют важную роль в криптографии и необходимы для криптосистем с открытым ключом, где ключ для расшифровки является общедоступным, и только ключ для декодирования остается секретным.
В 1978 году Ривест, Шамир и Адлеман разработали криптографический алгоритм, основанный на одностороннем умножении двух больших (обычно более 100 десятичных знаков) простых чисел. Метод RSA (названный по инициалам его изобретателей) стал самой популярной системой открытых ключей и реализован во многих коммуникационных программах.
Хотя обычно считается (хотя формально это и не доказано), что эффективная факторизация простых чисел на классическом компьютере невозможна, эффективный алгоритм для квантовых компьютеров был предложен в 1994 году П.У. Шором [11].
4.2.2 Алгоритм
В этом разделе алгоритм Шора описывается с функциональной точки зрения, что означает, что он не имеет отношения к реализации для конкретной аппаратной архитектуры. Подробную реализацию вентиля Чирака-Цоллера можно найти в [13], более строгое математическое описание приведено в [15], а более подробное описание реализации QCL приведено в [25].
4.2.2.1 Модуляр возведение в степень
Пусть N = n1n2 с наибольшим общим делителем gcd(n1, n2) = 1 является число, подлежащее разложению на множители, x - случайно выбранное число, простое относительно N (т.е. gcd (x, N ) = 1) и вычисляем модулярную функцию возведения в степень с периодом r:
expn(k, N ) = xk mod N, expn(k + r, N ) = expn(k, N ), xr ; 1 по модулю N
(4.19)

Период r имеет порядок x по модулю N . Если r четный, мы можем определить значение y = xr/2, которое удовлетворяет условию y2 ; 1 по модулю N и, следовательно, является решением
одной из следующих систем уравнений:
У1 ; 1 мод Н1 ; 1 мод Н2 (4.20)
У2 ; -1 мод Н1 ; -1 мод Н2
У3 ; 1 мод Н1 ; -1 мод Н2
У4 ; -1 мод Н1 ; 1 мод Н2

ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 83
Первые две системы имеют тривиальные решения y1 = 1 и y2 = -1, которые не отличаются от решений квадратного уравнения y2 = 1 в Z или поля Галуа GF (p) (т.е. Zp с простым числом p). Последние две системы имеют нетривиальные решения y3 = a, y4 = -a, как это постулируется китайской теоремой об остатках, утверждающей, что система из k одновременных конгруэнций (т.е. система уравнений вида y ; ai mod mi) с взаимно простыми модулями m1, . . . , mk (т.е. gcd (mi, mj ) = 1 для всех i ; j) имеет единственное решение y с 0 ; x <m1m2 . . . mk.
4.2.2.2 Нахождение множителя
Если r четное и y = ±a, при a; 1 и a; N ; 1, то (a + 1) или (a ; 1) должен иметь общий делитель с N, потому что a2 ; 1 по модулю mod 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 (4.21)
Можно показать, что случайный x соответствует вышеупомянутым условиям с вероятностью p > 1/2, если N не имеет вида N = p; или N = 2p;. Поскольку существуют эффективные классические алгоритмы для разложения на множители чистых простых степеней (и , конечно, для распознавания коэффициента, равного 2), можно найти эффективный вероятностный алгоритм для разложения на множители, если период r модульного возведения в степень может быть определен за полиномиальное время.
4.2.2.3 Период функции
Пусть F - квантовая функция F : |x, 0; ; |x, f (x); от целочисленной функции  f : Z ;  с неизвестным периодом r < 2n.
Чтобы определить r, нам нужны два регистра размером 2n и m кубитов, которые следует сбросить на |0, 0;.
В качестве первого шага мы создаем однородную суперпозицию всех базовых векторов в первом регистре, применяя оператор U с
Это может быть достигнуто, например, с помощью преобразования Адамара H. Применение F к результирующему состоянию дает
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 84
Измерение второго регистра с результатом k = f (s) при s < r приводит к уменьшению состояния до
Состояние первого регистра после измерения |;'; состоит только из базовых векторов вида
|rj + s;, поскольку f (rj + s) = f (s) для всех j. Таким образом, он имеет дискретный однородный спектр.
Непосредственно извлечь период r или его кратное путем измерения первого регистра невозможно из-за случайного смещения s. Эту проблему можно решить, выполнив дискретное преобразование Фурье (см. 4.2.3).
в регистре, поскольку спектр вероятностей преобразованного состояния - инвариант смещения (т.е. изменяются только фазы, но не абсолютное значение комплексных амплитуд).
Если N = 22n кратно r, то , если i кратно N/r, а в противном случае 0. Но даже если r не является степенью 2, спектр | ;'; показывает отчетливые пики с периодом N/r, потому
что
Это также являетсnя причиной, по которой мы используем первый регистр из 2n кубитов, когда r < 2n, потому что это гарантирует по крайней мере 2n элементов в приведенной выше сумме и, следовательно, ширину пика порядка O(1).
Если мы теперь измерим первый регистр, то получим значение c, близкое к ;N/r, при ;  Zr



Это можно записать как c/N = c · 2;2n ; ;/r. Мы можем рассматривать это как нахождение рационального приближения a/b с a, b < 2n для фиксированного точечного двоичного числа c · 2;2n. Эффективный классический алгоритм для решения этой задачи
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 85
с использованием цепных дробей описан в [16] и реализован в функции знаменателя (denominator) (приложение B.2).
Поскольку форма рационального числа не является однозначной, ; и r определяются как a/b = ;/r только в том случае, если gcd(;, r) = 1. Вероятность того, что ; и r взаимно просты, больше, чем 1/ln r, поэтому для получения постоянной вероятности успеха, максимально приближенной к 1, требуется всего O(n) попыток.1
4.2.3 Квантовое преобразование Фурье
Для N-мерного вектора |;; дискретное преобразование Фурье определяется как
Поскольку |;› - это объединенное состояние n кубитов, N всегда равно степени 2. Классическое быстрое преобразование Фурье (БПФ ) использует двоичное разложение показателя степени для выполнения преобразования за O(n2n) шагов.
Как предположил Копперсмит [7], тот же принцип можно было бы адаптировать к квантовым компьютерам, используя комбинацию преобразований Адамара H (см. 3.4.4.3) и условных фазовых вентилей V (см. 3.4.4.4). Приведенные ниже индексы указывают кубиты подключённые:
DFT ' выполняет итерацию кубитов из MSB в LSB, "разбивает" кубиты с помощью преобразования Адамара, а затем условно применяет фазы в соответствии с их относительным двоичным положением (e2ni 2i;j+1 ) для каждого уже разделенного кубита.
Базовые векторы преобразованного состояния | ;'; = DFT ' |;; задаются в обратном порядке битов, поэтому, чтобы получить фактический DFT , биты должны быть перевернуты.
оператор dft(qureg q) _BOS_ // основной оператор
const n=#q; // присваивает n длине входных
данных int i; int j; // объявляет счетчики циклов
для значений от i=0 до n-1 {
для значений от j=0 до i-1 _BOS_ // применяем условные фазовые вентили
Фаза(2*pi/2^(i-j+1),q[n-i-1] и q[n-j-1]);
}
Mix(q[n-i-1]); // вращение кубита
}
flip(q); // изменение порядка битов в выходных данных
}

1 Если предполагаемый период r' = b, полученный из рационального приближения a/b ; c2;2m, нечетный или gcd(xr'/2 ± 1, N ) = 1, то можно попытаться увеличить a/b на некоторый целочисленный коэффициент k, чтобы угадать фактический период r = kb.
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 86
4.2.4 Модулярная арифметика
Наиболее сложной частью реализации алгоритма Шора является построение эффективной квантовой функции для возведения в степень по модуляр.
expna,n(b, e) : |b;b|0;e ; |b;b|ab mod n;e (4.31)
Предполагая, что у нас уже есть реализация для модульного сложения, мы могли бы использовать ее для построения модулярного умножения и, наконец, возведения в степень, поскольку
4.2.4.1 Модулярное сложение
Сложение по модуло n классического целого числа a и квантового регистра b может привести либо к a + b, либо (a ; n) + b), в зависимости от конкретного базового вектора |b;.
В то время как при b < n операция обратима, это не относится к b ; n, итак, если n не является степенью 2, то, помимо целевого сопротивления ys для суммы, нам нужен дополнительный флаг-кубит yy, чтобы разрешить квантовую функцию addn, которая является унитарной и инвариантной к b:
Фактическую реализацию addn можно найти в приложении B.5.
Поскольку addnn;a,n является квантовой функцией для модулярного вычитания и, таким образом, реализует функцию, обратную f -1a,n(b) = b ; a по модулю mod n к fa,n = a + b по модулю mod n, мы можем построить перезаписывающую версию oaddn модулярного сложения, используя представленный метод в пункте 3.5.2.3:
добавление addnn;a,n не отменяет флаг переполнения yf , поэтому мы должны переключить его вручную:
Исходные целевые регистры ys и yf теперь могут быть выделены как неуправляемые локальный перезапись (скретч).
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 87
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 равным нулю
}

Регистр e является разрешающим (возможным) регистром (см. 2.2.2.6), поэтому addn и oaddn на
самом деле являются условными операторами, которые влияют только на собственные векторы вида |x;|111 . . .;e.
4.2.4.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);
}
}
Как указано выше, мы можем создать перезаписывающую версию, если существует реализация обратной функции. Это тот случай, когда gcd (a, n) = 1, так что a и n относительно простые, потому что тогда модульная обратная a;1 с a;1a mod n = 1 существует. Поскольку мы намерены использовать оператор для алгоритма Шора, который требует, чтобы gcd(ak, n) = 1, этого товаром для нас достаточно.
Используя два условных элемента XOR , определенных как

для замены регистров2 мы можем реализовать условную перезаписывающую версию muln, определенную как
omuln[[e]],a,n|b; ; |ab mod n; (4.38)
2 обычно для замены регистра требуется выполнить 3 операции исключения XOR, но поскольку один регистр пуст, достаточно 2 операций исключения XOR.
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 88
функция 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);
}

4.2.4.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,например,b[i]); // ex -> ex*a^2^i mod n
}
}

4.2.5 Реализация
4.2.5.1 Вспомогательные функции
В реализации алгоритма Шора используются следующие функции:
• логическое значение testprime(int n)
Проверяет, является ли n простым числом
• логическое значение testprimepower(int n)
Проверяет, является ли n простой степенью 3
• int powmod(int x,int a,int n)
Вычисляет xa mod n
• в знаменателе int(действительный x,int qmax)
Возвращает знаменатель q наилучшего рационального приближения p/q ;; x
при p, q < qmax
Для получения информации о реальных реализациях этих функций, пожалуйста, обратитесь к приложению B.2.
3 Поскольку обе тестовые функции не являются частью самого алгоритма, были использованы короткие, но неэффективные реализации с O(;n)
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 89
4.2.5.2 Процедура шор , сокращающая
Процедура Шора проверяет, подходит ли целое число для количественной факторизации, а затем повторяет алгоритм Шора до тех пор, пока не будет найден множитель.
процедура shor(внутренний номер) {
int width=ceil(log(число,2)); // размер числа в битах
параметр reg1[2*ширина]; // первый регистр
параметр reg2[ширина]; // второй регистр
int qmax=2^ширина;

int factor: / / найденный коэффициент
int m; реальный c; / / измеренное значение
int x; // основание возведения в степень
p; int; int; int; int; int; int; int; рациональное приближение; p / q
a; int b; / / возможные коэффициенты числа
int; / / e=x^(q/2) номер модуля
if mod number 2 == 0 { выход "число должно быть нечетным"}
if testprime (число) {выход из "простого числа"}
if testprimepower (число) {выход из режима "основная мощность"};
{
{//сгенерировать случайную базу
x = этаж(случайный ()*(число-3))+2;
} до тех пор, пока gcd(x,число)==1;
выведите "выбранный случайным образом x=", x;
Смешать (reg1): / / Преобразование Адамара
expn(x,число,reg1,reg2); / / модульное возведение в степень
измерить reg2; / / измерить 2-й регистр
dft (reg1): / / преобразование фурье
измерьте reg1, m; / / измерьте 1-й регистр
сброс; / / очистка локальных регистров
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 90
if m=0 { // ошибка при измерении 0
выведите " измеренный ноль в 1-м регистре. пытаюсь снова ...";
 еще {
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
напечатать " нечетная точка. пытаюсь снова ...";
 еще {
выведите "возможно ли это", q;
e=powmod(x,q/2,число); / / вычислить кандидатов для
a=(e+1) номер модуля; / / возможные общие факторы
b=(e+число-1) номер модуля; // с номером
выведите x,"^", q/2, "+ 1 мод", число,"=", a,",",
x,"^", q / 2, "- 1 мод",число,"=", b;
коэффициент=макс(gcd(число,a),gcd(число,b));
}
}
} до тех пор, пока коэффициент не будет>1 и коэффициент не будет<число;
вывести число,"=", коэффициент,"*", число/коэффициент;
}






4.2.5.3 Факторинг 15
15 - это наименьшее число, которое может быть разложено на множители с помощью алгоритма Шора, так как оно наименьшие нечетные числа 3 и 5. Наша реализация модулярного возведения в степень требует 2l + 1 кубита чистого (скретч) пространства с l =
[ld (15 + 1)] = 4. Самому алгоритму требуется 3l кубитов, так что в общей сложности требуется 21 кубит
должны быть предоставлены.
$ qcl-b21-я короткая позиция.qcl (контроль качества)
короткий( 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 должно быть
ГЛАВА 4. КВАНТОВЫЕ АЛГОРИТМЫ 91
возведено, можно ожидать  период около ;n  предполагая, что первые степени n имеют тот же порядок величины. Это привело бы к периоду q/;n после того, как DFT и вероятность p = 1/;n случайно выберут базовый вектор |0;, было бы p = 25,8%.
В  особом случае начального значения x = 4 период модулярного возведения в степень равно 2, так как 42 по модулю mod 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
квант-ph/9708054
[2] Я.I. Сирак, П. Золлер, 1995 Квантовые вычисления с джонами в холодной ловушке,
Физика. Оборот. Латыш. 74, 1995 , 4091
[3] Д. Дойч, 1985 Квантовая теория, принцип Черча-Тьюринга и
универсальный квантовый компьютер. Лондонское Королевское общество
Звоните по телефону 400-97-117
[4] Я. Груска, 1998 "Основы вычислительной техники", гл. 12: "Границы -
Квантовые вычисления”
[5] Р. W. Джей Би Би Си Кейз 1988 Вещь. Развивать. 32, 24
[6] Д. Deutsch, 1989 Квантовые вычислительные сети. Материалы заседания
Лондонское королевское общество по телефону 439-553-558
[7] Д. Копперсмит 1994 Приближенное преобразование Фурье, полезное в
Квантовый факторинг, отчет IBM Research №. RC19642
[8] С. H. Беннет, 1973. Логическая обратимость вычислений. IBM I. Вещь.
Развивать. 17, 525
[9] С. H. Беннет, 1989 СИАМ И.Компьютер. 18, 766
[10] Джон Бухманн, 1996, исследование факторов глобального масштаба. Спектр дер
Виссеншафт 9/96, 80-88
[11] П.W. Шор. 1994 алгоритмы для квантовых вычислений: дискретный логотип-
рифма и факторинг
[12] Сэмюэл Л. Браунштейн, 1995 Квантовые вычисления: учебное пособие
[13] Дэвид Бекман и др. 1996 эффективные сети для квантового факторинга
92
БИБЛИОГРАФИЯ 93

14] Ф.Д. Мурнаган, 1962, "Унитарные и ротационные группы", Spartan
Books, Вашингтон
[15] Артур Экерт и Ричард Джозса, 1996, "Квантовый алгоритм Шора для
Разложение чисел на множители, ред. Современная физика, 68 (3), 733-753
[16] Г.Х. Харди и Э.М. Райт, 1965 г. "Введение в теорию
чисел" (4-е издание).
[17] Б. Джек Коупленд, 1996, Диссертация Черча-Тьюринга. Стэнфордская
энциклопедия философии ISSN 1095-5054
[18] Э.Л. Пост, 1936. ‘Конечные комбинаторные процессы - формулировка 1". Журнал
символической логики, 1, с. 103-105.
[19] А. М. Тьюринг, 1948 Интеллектуальная техника. Национальная физическая лаборатория
Отчет. В книге Мельцера Б., Мичи Д. (ред.) 1969. Машинный интеллект 5.
Эдинбург: Издательство Эдинбургского университета., 7
[20] Лов К. Гровер, 1996, Быстрый квантово-механический алгоритм поиска в базе
данных. Материалы 28-го ежегодного симпозиума ACM по теории
Вычисления
[21] Мишель Буайе, Жиль Брассар, Питер Хойер, Ален Тапп, 1996 г. - Жесткие
рамки квантового поиска. Труды PhysComp96
[22] Хилари Патнэм, 1965 г. - Философский взгляд на квантовую механику
[23] У. Куммер и Р. Траусмут, 1988 год, "Скрипт для чтения", 131,869 -
Квантовая теория
[24] Бернхард Омер, 1996, Моделирование квантовых компьютеров [неопубликовано]
[25] Бернхард Омер, 1998, Процедурный формализм для квантовых вычислений,
магистерская диссертация, Венский технический университет
Список рисунков
1.1 Шар, зажатый между двумя зеркалами как классическая и как
квантовая частица . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Первые три собственных состояния электрона в потенциальной яме . 12
2.1 Простой неклассический алгоритм . . . . . . . . . . . . . . . . . 39
3.1 Гибридная архитектура QCL . . . . . . . . . . . . . . . . . 43
94
Список таблиц
1.1 Некоторые наблюдаемые величины и соответствующие им операторы . . . . . . 9
2.1 классические и квантовые вычислительные модели . . . . . . . . . . 36
3.1 классические типы и литералы . . . . . . . . . . . . . . . . . . . . . 45
3.2 Операторы QCL . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Арифметические функции QCL . . . . . . . . . . . . . . . . . . . . 47
3.4 другие функции QCL . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 квантовые выражения . . . . . . . . . . . . . . . . . . . . . . . 57
3.6 иерархия подпрограмм QCL и допустимые побочные эффекты . . . . . 59
95
Приложение А
Синтаксис QCL
A.1
Сложные выражения-координата ; [ + | - ] цифра { digit } [ . { digit }]
const ; цифра { разряд } [ . { цифра }]
; ( комплексная координата , complex-coord )
; истина | ложь
; " { тип char } "
выражение ; константный
; идентификатор [ [ выражение [( : | .. ) выраж ] ] ]
 идентификатор ; ( [ выражение { , выражение }] )
; ( выражение )
; # выражение
; выражение ^ выражение
; - выражение
; выражение ( * | / ) выражение
; выражение mod выражение
; выражение ( + | - | & ) выражение
; выражение ( == | != | < | <= | > | >= ) выражение
; не выражение
; выражение и выражение
; выражение ( или | xor ) выражение
96
ПРИЛОЖЕНИЕ A. СИНТАКСИС QCL 97
A.2
Блока инструкций ; { stmt { stmt } }
вариант ; буква _BOS_ буква | - }
идентификатор stmt ; [ ! ] ( [ выражение { , выражение }]) ;
; идентификатор = выражение ;
; выражение ( -> | <- | <-> ) выражение ;
; для идентификатора = expr в блок expr [ шаг expr ]
; хотя выражение блока
; блокировать, пока выражение ;
; если expr блок [ блок else ]
; вернуться выражение ;
 ввод ; [ выражение ] , идентификатор ;
 печать ; выражение [ , выражение ] ;
 покинуть ; [ выражение ] ;
 мера ; выражение [ , идентификатор ] ;
; сброс ;
 дамп ; [ выражение ] ;
 список ; [ идентификатор {идентификатор }] ;
; ( загрузка | сохранение ) [ выражение ] ;
; раковины ;
 параметр ; [, выражение ] ;
; полу ;
А. 3 Определения
тип ; инт | недвижимого | | комплекса строку
; qureg | quvoid | quconst | quuscratch - число , которое вы хотите изменить .
const-def ; идентификатор const = выражение ;
var-def ; идентификатор типа [ выражение ] ;
; идентификатор типа [ = выражение ] ;
arg-def ; идентификатор типа
arg-list ; ( [ arg-def { , arg-def }])
тело ; { { const-def | var-def } { stmt } }
def ; const-def | var-def
ПРИЛОЖЕНИЕ A. СИНТАКСИС QCL 98
; идентификатор типа arg-тело списка
; идентификатор процедуры arg-тело списка
; идентификатор оператора arg-тело списка
; функциональный идентификатор arg-тело списка
; список аргументов внешнего идентификатора оператора ;
; список аргументов внешнего функционального идентификатора ;

Приложение B
Алгоритм сокращения в QCL
B.1 по умолчанию.qcl
extern qufunction Разветвляет(quconst a,quvoid b);
extern qufunction заменяет(qureg a,qureg b);
матрица внешних операторов 2x2(
комплекс 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,
комплекс u54,комплекс u55,комплекс u56,комплекс u57,
комплекс u60, комплекс u61, комплекс u62,комплекс u63,
99
ПРИЛОЖЕНИЕ В. АЛГОРИТМ ШОРА В QCL 100
сложный 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, 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,
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,
инт р48, инт р49, инт р50, инт р51, инт р52, инт р53, инт р54, инт р55,
инт р56, инт р57, инт р58, инт р59, инт р60, инт р61, инт р62, инт р63,
курег q);
внешнее значение qufunction Not (последовательность q);
внешнее значение qufunction CNot (последовательность q, последовательность c);
фаза внешнего оператора (действительное значение phi, последовательность q);
внешний оператор Rot (real Theta, qureg q);
внешний оператор Mix(qureg q);
внешний оператор qufunction ModExp (int n,int x, quconst a, quvoid b);
логический бит (int n,int b) {
ПРИЛОЖЕНИЕ В. АЛГОРИТМ ШОРА В QCL 101
возвращает значение n / 2^b по модулю 2 == 1;
}
qufunct set (int n,qureg q) {
int i;
для i=0 до #q-1 {
Если бит (n,i) { Не (q [i]);}
}
}
константа Pi=3,141592653589793238462643383279502884197;
В.2 функции.
набор qcl разрешает переопределять 1;
// возвращает наименьший множитель > 1 из n или 1, если n является простым
int findfactor (int n) {
int i;
если n<=0 _BOS_ выход "findfactor принимает только положительные аргументы";}
для i=2 до этажа(sqrt(n)) {
если я не хочу возвращаться;)
}
верните 1;
}
/ проверьте, является ли n простым числом
, логическое значение testprime (int n) {
int i;
если N<=1 { верните false;}
для i=2 до значения floor(sqrt(n)) {
если я не хочу, чтобы значение было ложным;)
}
верните значение true;
}
/ проверьте, является ли n простой мощностью.
логическое значение testprimepower (int n) {
int i;
int f;
i=2;
пока я<=floor(sqrt (n)) и f==0 {
если я это сделаю, то i= = 0 { f = i;}

i=i+1;
}
ПРИЛОЖЕНИЕ В. АЛГОРИТМ СОКРАЩЕНИЯ В QCL 102
для значений от i=2 до floor(log(n,f)) {
if f^i==n { возвращает значение true; }
}
возвращает значение false;
}
// возвращает X^мод Н
тип int powmod(тип int х,int и А,инт Н) {
инт у=Х;
инт у=1;
int i;
для i=от 0 до 30 {
если a/2^i по модулю 2 == 1 { y=y*u по модулю n; }
u=u^ 2 по модулю 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
int знаменатель(действительный x,int qmax) {
действительный y=x;
настоящий z;
int q0;
int q1=1;
внутренний квартал 2;
пока это правда {
z=y-этаж(y);
если z<0,5/qmax^2 { возвращает q1; }
y=1/z;
q2=floor(y)*q1+q0;
ПРИЛОЖЕНИЕ B. АЛГОРИТМ ШОРА В QCL 103
if q2>=qmax { возвращает q1; }
q0=q1; q1=q2;
}
}
set allow-переопределяет значение 0;
B.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); // добавить,
если a0 {Не(s); } // восстановить разделенный кубит
} else {
если a0 и a1 {
если #sum>1 { // установить перенос, если доступно
CNot(сумма[1],сумма[0] и e);
ПРИЛОЖЕНИЕ B. АЛГОРИТМ ШОРА В QCL 104
}
CNot(sum[0],e); // добавить a
}
};
// Добавить кубит b
, если #sum>1 { // установить перенос, если доступно
CNot(sum[1],b & sum[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]);
CNot(j[i-1],j[i] и b[i]);
}
}
бит if(a,0) {
Не(b[0]); // если все еще не определился (j[0]=1)
ПРИЛОЖЕНИЕ В. АЛГОРИТМ ШОРА В QCL 105
CNot(флаг,j[0] & b[0]); // результатом является LSB(a)>LSB(b)
}
}
set allow-переопределяет значение 0;
B.4
.оператор 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]);
}
Смешивание(q[n-i-1]); // вращение кубита
}
перевернуть(q); // поменять порядок битов выходных
данных }
В.5 modarith.qcl
set allow-переопределяет значение 1;
включить "functions.qcl";
включить "qufunct.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];
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
}
// Условное перезаписывающее сложение по модулю n: sum -> (a+sum) по модулю n
, которое содержит значение oaddn(int a,int n,qureg sum,quconst e) {
qureg j[#сумма];
qureg f[1];
addn(a,n,sum,f,j,e); // junk -> a+b mod n
ПРИЛОЖЕНИЕ B. АЛГОРИТМ СОКРАЩЕНИЯ В QCL 106
Поменять местами(сумма,j); // поменять местами мусор и сумму
CNot(f,e); // переключить флаг
!addn(n-a,n,сумма,f,j,e); // вычислить значение b равным нулю
}
// Условное умножение по модулю n целого числа a на число b,
// prod <- ab по модулю n.
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
qufunction 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
}
}
установить allow-переопределяет значение 0;
ПРИЛОЖЕНИЕ B. АЛГОРИТМ ШОРА В QCL 107
B.6 shor.qcl
включает "modarith.qcl";
включает "dft.qcl";
процедура 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(число) { выход "простая мощность"; };
{
{ // генерируем случайную базу
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-м регистре. пытаюсь снова...";
} еще {
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
выведите "нечетный знаменатель, увеличенный на 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. АЛГОРИТМ ШОРА В QCL 108
b=(e+number-1) номер модуля; // с номером
выведите x,"^",q/2,"+ 1 мод",число,"=",a,",",
x,"^",q/2,"- 1 мод",число,"=",b;
коэффициент=max(gcd(число,a),gcd(номер,b));
}
}
} до тех пор, пока коэффициент не будет>1 и коэффициент не будет<число;
выведите }