Структурированное квантовое программирование Бернх

Структурированное квантовое программирование
Бернхард Омер
, первая версия
26 мая 2003 г.
последняя редакция
2 сентября 2009 г.
Институт теоретической физики
Венский технологический университет
Электронная почта: oemer@tph.tuwien.ac.at
Домашняя страница: http://www.itp.tuwien.ac.at/~oemer/
Содержание
Предисловие iii
1 Квантовые вычисления 1
1.1 Путь к квантовым вычислениям . . . . . . . . . . . . . . . . 1
1.1.1 От Гюйгенса к Планку . . . . . . . . . . . . . . . . . 1
1.1.2 Век квантовой физики . . . . . . . . . . . . 2
1.1.3 За рамками тезиса Черча-Тьюринга . . . . . . . . . . . . 3
1.2 Квантовая механика . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Квантовые вычисления как квантово-механическая теория 4
1.2.2 Линейная алгебра . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Постулаты квантовой механики . . . . . . . . . 9
1.3 Классические вычисления . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Тезис Черча-Тьюринга . . . . . . . . . . . . . . . . 13
1.3.2 Машины . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.3 Программы . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Элементы квантовых вычислений . . . . . . . . . . . . . . . . 20
1.4.1 Квантовая память . . . . . . . . . . . . . . . . . . . . 20
1.4.2 Квантовые операции . . . . . . . . . . . . . . . . . . . 24
1.4.3 Ввод и вывод данных . . . . . . . . . . . . . . . . . . . . . 31
1.5 Концепции квантовых вычислений . . . . . . . . . . . . . . . 34
1.5.1 Модели и формализмы . . . . . . . . . . . . . . . . . 34
1.5.2 Квантовые алгоритмы . . . . . . . . . . . . . . . . . . . 38
2 Структурированное квантовое программирование 45
2.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.1.1 Мотивация . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.1.2 Квантовые языки программирования . . . . . . . . . . . 45
2.1.3 Классификация языков программирования . . . . . . . . . 46
2.1.4 Цели . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.1.5 Современное состояние . . . . . . . . . . . . . . . . . . . . . . 49
2.2 Вычислительная модель квантового программирования . . . . . 50
2.2.1 Квантовые схемы . . . . . . . . . . . . . . . . . . . . . 51
2.2.2 Конечные квантовые программы . . . . . . . . . . . . . . . . 51
2.2.3 Гибридная архитектура . . . . . . . . . . . . . . . . . . . 56
2.3 Структурированное программирование . . . . . . . . . . . . . . . . . . . . . 59
2.3.1 Структура программы . . . . . . . . . . . . . . . . . . . . 59
2.3.2 Выражения и переменные . . . . . . . . . . . . . . . . 60
2.3.3 Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.4 Утверждения . . . . . . . . . . . . . . . . . . . . . . . . 62
2.4 Элементарные квантовые операции . . . . . . . . . . . . . . . . 64
2.4.1 Квантовые регистры . . . . . . . . . . . . . . . . . . . . 65
2.4.2 Элементарные вентили . . . . . . . . . . . . . . . . . . . . . 69
2.4.3 Измерения . . . . . . . . . . . . . . . . . . . . . . . 73
2.5 Операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.5.1 Квантовые подпрограммы . . . . . . . . . . . . . . . . . . 74
2.5.2 Общие операторы . . . . . . . . . . . . . . . . . . . . 78
2.5.3 Базовые перестановки . . . . . . . . . . . . . . . . . . . . 85
2.6 Управление квантовым потоком . . . . . . . . . . . . . . . . . . . . . . 92
2.6.1 Условные операторы . . . . . . . . . . . . . . . . . . 92
2.6.2 Условное ветвление . . . . . . . . . . . . . . . . . . 97
2.6.3 Квантовые условия . . . . . . . . . . . . . . . . . . . 102
Краткий справочник по QCL 108
A.1 Синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.1.1 Выражения . . . . . . . . . . . . . . . . . . . . . . . . 109
A.1.2 Заявления . . . . . . . . . . . . . . . . . . . . . . . . 110
A.1.3 Определения . . . . . . . . . . . . . . . . . . . . . . . . . 110
A.2 Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
A.2.1 Типы данных . . . . . . . . . . . . . . . . . . . . . . . . 111
A.2.2 Оператора . . . . . . . . . . . . . . . . . . . . . . . . . 113
A.2.3 Элементарные функции . . . . . . . . . . . . . . . . . . 114
A.3 Утверждения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.3.1 Простые инструкции . . . . . . . . . . . . . . . . . . . . 114
A.3.2 Управление потоком . . . . . . . . . . . . . . . . . . . . . . . 115
A.3.3 Интерактивные команды . . . . . . . . . . . . . . . . . . 116
A.4 Опции интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . 118
Литература 119
ii
Предисловие
В отличие от квантовых схем, квантовых машин Тьюринга или алгебраического определения унитарных преобразований, языки программирования позволяют использовать- полное и конструктивное описание квантовых алгоритмов, включая их классическую структуру управления для произвольных размеров входных данных и аппаратных архитектур.
В этой тезисе исследуется, как классический формализм структурированного программирования может быть адаптирован к области квантовых вычислений, основанный на машинной модели универсального компьютера с квантовым оракулом, позволяющей применять унитарные вентили и измерять отдельные кубиты. Начнем с абстрактного понятия программ как конечных автоматонов (finite programs) и, по аналогии с классическими языками программирования, концепция структурированных квантовых языков программирования (QPLs) развивается и иллюстрируется экспериментальным языком QCL.
QPL называется императивным, если он предоставляет квантовые регистры (квантовые переменные), элементарные логические элементы и измерения в одном кубите. Процедурный QPL дополнительно поддерживает унитарные подпрограммы и неклассические концепции, такие как обратное выполнение кода для получения присоединённого (сопряженного, адджойнт) оператора или унитарное “предположение (вычисление анкомпьютинг” временных квантовых регистров (управление пространством исходного(с нуля, скретч). Процедурный QPL называется структурированным, он также позволяет использовать кубиты и логическое выражение кубитов (квантовые условия) в структурированных операторах управления потоком (квантовая инструкция (утверждение) if).
Интерпретатор QCL для операционной системы Linux, а также числовой симулятор для произвольных квантовых оракулов доступны в виде бесплатного программного обеспечения по адресу
http://www.itp.tuwien.ac.at/~oemer/qcl.html
Обзор
В главе 1 дается общее введение в квантовые вычисления и описываются ключевые концепции и формализм, необходимые для обсуждения QPLs.
После краткого исторического обзора (1.1) формализм и постулаты квантовой механики представлены в разделе 1.2. Раздел 1.3 знакомит с ключевыми понятиями классических вычислений и развивает формальное представление о машинах и программах, которое отличается от обычных формализаций тем, что машины и программы рассматриваются как отдельные сущности. В разделе 1.4 концепция абстрактной машины применяется к квантовым вычислениям и основным компонентам квантового компьютера, а именно к кубитным регистрам, унитарным вентилям (элементам управления, гейтс) и кубитному измерению, обсуждаются с использованием нового формализма, называемого регистровой нотацией (записью), который позволяет получить компактное и абстрактное описание квантовых схем. Наконец, в разделе 1.5 обсуждается формальное описание и разработка квантовых алгоритмов.
В главе 2 представлена концепция структурированных языков квантового программирования как нового формализма для квантовых вычислений.
После общего введения в классический и квантовый языки программирования (2.1) в разделе 2.2 рассматриваются универсальные квантовые компьютеры и представлена гибридная квантовая архитектура как компьютерная (компьютюшионал, вычисления) модель квантового  программирования. После ознакомления с ключевыми элементами классических языков структурированного программирования (2.3) в оставшейся части главы 2 демонстрируется, как эти концепции могут быть адаптированы к квантовым вычислениям: в разделе 2.4 рассматриваются минимальные требования к универсальному QPL (императивному квантовому программированию), раздел 2.5 представляет унитарную подрутину (процедуру) (процедурное квантовое программирование) и, наконец, раздел 2.6 демонстрирует, как условные операторы могут быть использованы для реализации семантики условного ветвления на кубитах и квантовых условий (структурированное квантовое программирование).
iv
Глава 1
Квантовые вычисления
1.1 Путь к квантовым вычислениям
1.1.1 От Гюйгенса к Планку
До принятия квантовой теории одной из главных проблем того, что сейчас называют классической физикой, была двойственная природа света. В то время как его линейное распространение и отсутствие физической среды, по-видимому, предполагают поведение, подобное поведению частиц, такие явления, как интерференция и дифракция, являются хорошо известными свойствами волн.
В 1690 году Кристиан Гюйгенс объяснил оптическое двойное лучепреломление в своей книге "Дело  света", где он разработал всеобъемлющую волновую теорию света. [35]
14 лет спустя Исаак Ньютон опубликовал свою книгу "Оптика", в которой объяснил такие явления, как отражение, дисперсия, цвет и поляризация, интерпретируя свет как поток частиц разного размера.
Корпускулярная теория света доминировала в научных дискуссиях до начала 19-го века, когда Янг и Френель продемонстрировали ряд недостатков этой теории, которые могут быть устранены при условии распространения поперечных световых волн в универсальной среде, называемой Эфиром. В 1873 году в своем Трактате об Электричестве и Магнетизме, Максвелл опубликовал набор из 4 дифференциальных уравнений в частных производных уравнения, которые лежат в основе классической электродинамики и элегантно объясняют свет как электромагнитные волны. Однако теория Максвелла все еще не могла объяснить излучение абсолютно черных тел, а также дискретные энергетические спектры атомов. Оба недостатка оказались решающими в развитии квантовой теории.
1
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 2
1.1.2 Век квантовой физики
Классическая электродинамика предсказывает, что распределение энергии в полости – и, следовательно, спектр абсолютно черного тела – пропорционален числу колебательных мод, что приводит к плотности энергии
U;(T ) = 8nkT ;;4,
известной как закон Рэлея-Джинса, который не поддается интеграции. [14]
В 1900 году Макс Планк нашел способ избежать этого противоречия, которое также известно как ультрафиолетовая катастрофа, с помощью специального предположения, что
возможные энергетические состояния ограничены значением E = nhv, где n - целое число,
; - частота, а h - постоянная Планка, фундаментальная постоянная квантовой физики, со значением
h = 2n; = 6,626075 · 10-34джс.
Это ограничение приводит к экспоненциальному уменьшению вероятности частот ; »kT/;
и приводит к интегрируемому распределению
Uv (T ) = 8;;2/c3 (hv/(ehv/kT ; 1))

, что также в точности соответствует экспериментальным данным.
Пять лет спустя Альберт Эйнштейн объяснил фотоэлектрический эффект, постулируя существование легких частиц, позже названных фотонами, с энергией E = hv.
В 1913 году Нильс Бор вычислил значение постоянной Ридберга по формуле предположим, что угловой момент электронов, вращающихся вокруг ядра , удовлетворяет условию квантования L = n; = nh/2;. Это ограничение можно было бы оправдать, приписав электрону волновые свойства и потребовав, чтобы соответствующие им волновые функции образовывали стоячую волну; однако такого рода гибридная теория оставалась неудовлетворительной.
Полное решение этой проблемы было найдено в 1923 году Вернером Хайзенбергом, который использовал матричный формализм; два года спустя Эрвин Шредингер опубликовал эквивалентное решение с использованием сложных волновых функций.
В 1927 году Гейзенберг сформулировал принцип неопределенности, который формализует картину взаимодополняемости волны и частицы, утверждает Бор, которые, хотя и являются взаимоисключающими, и необходимы для полного описания квантовых событий. Вместе со статистической интерпретацией волновой функции Шредингера они закладывают теоретическую основу для Копенгагенской интерпретации квантовой механики. [17]
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 3
“Мы рассматриваем квантовую механику как законченную теорию, для которой фундаментальные физические и математические гипотезы больше не поддаются модификации”.
Вернер Гейзенберг и Макс Борн, Сольвеевский конгресс 1927 года.
Хотя ее объяснение квантовых явлений, таких как запутанность или измерение, все еще кажется несколько неудовлетворительным, даже спустя 75 лет интерпретацию Копенгагена все еще можно рассматривать как основное направление в квантовой физике. Очевидные противоречия, такие как знаменитый ЭПР-парадокс [29], не только были подтверждены экспериментально, но и служат фундаментальными принципами для новых областей исследований, таких как квантовая криптография и квантовые вычисления.
1.1.3 За рамками тезиса Черча-Тьюринга
Основной идеей современной информатики является представление о вычислениях как о механическом, а не чисто умственном процессе. В 1936 году Алан Теринг формализовал эту концепцию, создав абстрактное устройство, которое теперь называется Машина Тьюринга, которая, как он доказал, способна выполнять любые эффективные (т.е. механические, алгоритмические) вычисления. Примерно в то же время Алонзо Черч показал, что любая функция натуральных чисел эффективно вычисляется только в том случае, если она рекурсивна. Оба вывода, по сути, эквивалентны и обычно называются тезисом Черча-Тьюринга. В своей сильной форме его можно суммировать- описывается как
Любой алгоритмический процесс может быть эффективно смоделирован с помощью
Машины Тьюринга
Это означает, что независимо от того, какой тип машины фактически используется для
определенных вычислений, можно найти эквивалентную машину Тьюринга, которая решает ту же задачу только с полиномиальными издержками.
Сильный тезис Черча-Тьюринга подвергся критике, когда в 1977 году Роберт Соловей и Фолькер Штрассен опубликовали быстрый тест на простоту методом Монте-Карло [55, 43], для решения которого в то время не было известно эффективного детерминированного алгоритма.1 Хотя эту проблему можно было бы легко решить с помощью проблемы- обладая способностями машины Тьюринга, возникает вопрос, существуют ли еще более мощные
модели вычислений.
В 1985 году Дэвид Дойч применил более общий подход и попытался разработать абстрактную машину, Универсальный квантовый компьютер, который не ориентирован на какое-то формальное понятие вычислимости, но должен быть способен
1 В 2002 году Маниндра Агравал, Нирадж Каял и Нитин Саксена в конечном итоге нашли
детерминированный тест на первичность [40] с временной сложностью в наихудшем случае, равной O(n12).
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ
эффективно моделировать произвольную физическую систему и, следовательно, любое реализуемое вычислительное устройство [24, 56]. Дойч также описал простой квантовый алгоритм, который был бы способен за один шаг определить , является ли данная однобитовая функция оракула f : B ; B постоянной или сбалансированной. Позже алгоритм был обобщен для n-разрядных функций f: Bn ; B (задача Дойча-Йозса [26]) и продемонстрировал, что квантовый компьютер действительно более мощный, чем вероятностная машина Тьюринга.
В то же время Ричард Фейнман показал, как можно построить локальные гамильтонианы для выполнения произвольных классических вычислений [31].
В 1994 году Питер Шор продемонстрировал, как разложение на простые множители и
вычисление дискретного логарифма могут быть эффективно выполнены на квантовом компьютере [54]. Огромное практическое значение этих задач для криптографии сделало алгоритм Шора “убийственным приложением” квантовых вычислений.
Год спустя Лов Гровер разработал квантовый алгоритм для нахождения уникального решения задачи Q (x) = 1 в неструктурированном пространстве поиска размера n, требующий всего лишь O (;n) вычислений функции Q-оракула черного ящика [32].
В это время Питер Цоллер и Игнасио Сирак продемонстрировали, как линейная ионная ловушка может использоваться для хранения кубитов и выполнения квантовых вычислений [19]. В 2001 году команде IBM удалось реализовать алгоритм Шора на 7-кубитном квантовом компьютере на базе ЯМР для разложения числа 15 на множители [18].
1.2 Квантовая механика
1.2.1 Квантовые вычисления как Квантово-Механическая Теория
Строго говоря, алгебраическая формулировка квантовой механики, которая будет представлена в этом разделе, сама по себе не является физической теорией, а скорее обеспечивает основу для формулирования физических теорий в ее рамках. В зависимости от того, как именно построены гильбертовы пространства и гамильтонианы, появляются различные теории, от нерелятивистской квантовой электродинамики, которая все еще поддерживает множество формальных аналогий с классической физикой, до квантовой хромодинамики, которая вводит такие сущности, как кварки и глюоны, которые совершенно бессмысленны вне рамок квантовой механики.
Квантовые вычисления - это еще одна теория, дополняющая абстрактный квантово
-механический формализм. Однако это не физическая теория в том смысле, что она пытается точно описать естественные процессы, а построена на абстрактных понятиях, таких как кубиты и квантовые вентили, без учета лежащих в их основе физическая квантово-динамическая модель.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 5
Этот нисходящий (топ-даун) подход является одновременно и самой сильной, и самой слабой стороной квантовых вычислений. Хотя это гарантирует, что его вычислительная модель на самом деле является наиболее общей из физически реализуемых в квантовомеханической вселенной, отсутствие конкретной и масштабируемой “эталонной (референс) реализации”, подобной машине Тьюринга для классических вычислений, оставляет открытым вопрос о том, могут ли квантовые компьютеры с более чем нескольким количеством кубитов на самом деле быть способны, при реалистичных предположениях о шуме и точности эксперимента.
1.2.2 Линейная алгебра
1.2.2.1 Порядок записи (Система счисления, нотация) Брекета
Нотация Брекета является очень компактным формализмом для линейной алгебры и была введена Дираком. В таблице 1.1 перечислены наиболее часто используемые выражения.
Нотация Описание
|;; главный (общий) вектор "ket", например |;; = (c0, c1, . . .)T
;;| двойной вектор “bra" для |;;, например ;;| = (c;0, c;1, . . .)
|n; n-й базисный вектор некоторого стандартного базиса N = {|0;, |1;, . . .}
|; базисный вектор альтернативного базиса  = {|;, |;, . . .}
;;|;; внутренний продукт |;; и |;;
|;; ; |;; тензорное произведение |;; и |;;
|;;|;; сокращено -тензорное произведение |;; ; |;;
|i, j; сокращено -тензорное произведение векторов базиса |i; и |j;
М † присоединённый оператор (матрица) M † = (M T );
;;|м |;; внутренний продукт |;; и M |;;
; ; ; сокращено норма ;|;;;
Таблица 1.1: Обозначения (нотация) Дирака

1.2.2.2 Гильбертово Пространство
Определение 1 Множество V называется векторным пространством над скалярным полем F, если определены операции + : V ; V ; V (сложение векторов) и · : F ; V ; V (скалярное
умножение), и
(i) (V, +) является коммутативной группой,
(ii) ;|; >= |;>;,
(iii) ;(;|;>) = (;;)|;>,
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 6
(iv) (; + ;)|;> = ;|;> + ;|;>,
(v) ;(|;; + |;;) = ;|;; + ;|;>.
Отныне мы будем рассматривать только комплексные векторные пространства, т.е. F = C.
Определение 2. Пусть V - комплексное векторное пространство. Функция ;·|·; : V;V ; C
называется внутренним произведением , если
(я) ;;|(;|;; + ;|;;) = ;;;|;; + ;;;|;;,
(ii) ;;|;; = ;;|;;;,
(iii) ;;|;; ; R ;;|;; ; 0, ;;|;; = 0 ; |;; = о.
Внутренний продукт также определяет норму ;|;;; =;;;|;; (также пишется как
;;;). Следующие неравенства применить:
|;;|;;| ; ;;;;;; (неравенство Шварца) (1.1)
;|;; + |;;; ; ;;; + ;;; (неравенство треугольника) (1.2)
Определение 3 (полнота) Пусть V - векторное пространство с нормой ; · ;
и |;n; ; V последовательность векторов.
(i) |;n; является последовательностью Коши  если ;; > 0 ;N > 0 так, что
;n, m > n,  ;|;n; ; |;m;; < ; (1.3)
(ii) |;n; сходится если |;; ; V так, что
;; > 0 ;N > 0 ;n > N ;|;n; ; |;;; < ; (1.4)
V является полным, если каждая последовательность Коши сходится.
Определение 4. Полное векторное пространство H с внутренним произведением ;·|·; и
соответствующей нормой ;;; = называется гильбертовым пространством.
Гильбертово пространство H является сепарабельным (неразборным), если существует перечислимое множество S ; H, которое является плотным в H, т.е. для любого |;>; H и
; > 0 существует |;> S с ;|;; - |;;; < ;. Отныне мы будем рассматривать только сепарабельные гильбертовы пространства.
Вектор |;>H нормализован или юнит-вектор , если ;;; =1. Нумеруемый набор нормализованных векторов называется B={|;0>,|;1>,…} ортонормальной

ГЛАВА 1. КВАНТОВАЯ ВЫЧИСЛИТЕЛЬНАЯ
системой , если ; ;i |;j >= ;ij . Ортонормированная система B является ортонормированным базисом  H, если  любой вектор |;>; H может быть записан в виде
Поскольку гильбертовы пространства по определению являются полными, любое отдельное комплексное Гильбертово пространство H с некоторым базисом B алгебраически изоморфно и изометрично для того, чтобы либо
(i) C n с основанием {|0;, |1;, . . . / n ; 1}} при |k> = (;0k, ;1k, ... ;n-1, k) T, если dim H = | B| = n или
(ii) l2 (т.е. пространство комплексных последовательностей <;n> для которых определено значение ;;k | ;n | 2 с базисными векторами | k> = (;0k, ;1k,. . .) T, если dim H = |B | = N0
В квантовых вычислениях мы обычно имеем дело с конечномерными гильбертовыми
пространствами, поэтому, если не указано иное, мы всегда будем предполагать, что H = Cn. В Cn  вектор “ket " |;> может быть записан как вектор-столбец и двойной вектор "bra" <;| может быть записан в виде вектора строк <;| = (|; ;;) T, что позволяет формально выразить внутреннее произведение ; · | · ; как обычное матричное умножение.
Определение 5 Пусть H1 и H2 - гильбертовы пространства с основаниями B1 и B2, тогда тензорное произведение
также гильбертово пространство с базисом В = В1 ; В2 и внутренний продукт (произведение)
;i,j|i', j'; = ;i|i';;j|j'; = ;ii' ;jj'  при |i;, |i'; ; B1   |i;, |i'; ; В2
.
1.2.2.3 Линейные операторы
Определение 6 Пусть V - векторное пространство, а A - функция A: V ; V. A
называется линейным оператором в V, если
А(;|;; + ;|;;) = ;A(|;;) +;А(|;;) = ;A|;; + ;А|;;. (1.6)
В Cn линейный оператор A может быть записан в виде матрицы n ; n с матричными элементами aij = <i | A |j>

Глава 1. QUANTUM COMPUTING 8
В следствии (1.6), линейный оператор на векторном пространстве V с базисом B полностью определен его эффектом на базисных векторах, так что выше оператор A можно записать как
Определение 7 Оператор А† = (AT) *= ;i,j aij*|i><j| называется присоединенным оператором А.
Определение 8 Линейный оператор А называется
(i) нормальный если A†A = AA†,
(ii) самоприсоединения  или Эрмитский если A† = A,
(iii) положительный если < ;|A|; > R+0   |;> H,
(iv) унитарный если A†A = I, при I — идентичный оператор,
(v) идемпотент если А2 = A,
(vi) самоинверсный если А2 = I,
(vii) (ортогональная) проекция, если A является самоприсоединенным и идемпотентным.

SU (n) является группой унитарных операторов на Cn с определителем 1. Так как
для каждого подразделения U на Cn существует физический эквивалент U ' = ei;U ;SU (n) (см 1.2.3.1), мы так же используем SU (n) отметить любой набор операторов  физически эквивалентных  SU (n).
Определение 9 a C с по крайней мере одно не -нуль решение |a> уравнения A|a> =
 a | a>  называется собственным значением  A, при | a> являющимся собственным вектором для a. Набор {|; ; H|A|; >= a|;>} известен как собственное пространство A для собственных значений А.
Любой линейный оператор может быть написан в терминах его собственных векторов как
Эта форма называется спектральной декомпозицией А.
Определение 10 Пусть будет линейный оператор на Н1 и Б линейный оператор на Н2, тогда тензорный продукт
это линейный оператор на Н1 ; Н2.
Определение 11 Пусть А и Б  линейные операторы на Х. В оператор [А, Б] = АБ-БА называется коммутатором и {А, Б} = АБ + БА называется антикоммутатор а и Б.
Глава 1. QUANTUM COMPUTING 9
1.2.3 постулаты квантовой механики
1.2.3.1 Квантовые постулаты
Постулат 1 Сопоставленное к любой физической системе комплексное гильбертово пространство H известно как пространство состояний  S. Состояние S полностью описано юнит (единицы) вектором | ; > ; H с ;; ;= 1, который называется вектором состояния S. Два вектора состояния |;; и |;'; равны (|;;; '|;';) если |;'; = ei;|;; при действительном ;.
Насколько точно пространство состояния для данной физической системы было построено,  за пределами области этого постулата.
Кубиты Простейшая не тривиальная квантово- механические система - квантовый бит или  кубит с пространством состояний B = C2. Состояние |;> кубита можно описать линейной комбинацией (также называемая суперпозицией) всего двух базисных состояний под маркой | 0>  и |1>
1.2.3.2 Эволюция
Постулат 2 Временная эволюция состояния закрытой квантовой системы описано уравнением Шрёдингера

с (экспериментальным) постоянным Планка H ; 1.05457 * 10-34джс и фиксированным самоприсоединённым оператором H по пространству состояния ;, известному как гамильтониан системы.
В квантовой физике, это обычное дело,  использовать систему измерения где
; = 1, так что (1.12) может быть записано в безразмерной форме i| ;> = H|;>.
Гамильтониан H полностью описывает динамику закрытой квантовой системы. Как с  пространством состояний, конкретная форма H (или приближение отсюда) должна быть определена физической теорией, используемой для описания системы.
Унитарная еволюция Если мы знаем системы явь в самом начальном состоянии | ;0 >
во время t = 0, мы можем определить оператор U (t) так
Глава 1. QUANTUM COMPUTING 10
и получить уравнения оператора
с решением
U (t) является оператором временной эволюции и удовлетворяет критерию
U(t) | ; (t0) > = |;(t0 + t) > (1.16)
U (t) унитарный потому что H = H† и таким образом
U(t)U †(t) = e;iHte+iHt = I, (1.17)
На самом деле, U (t) и гамильтониан являются эквивалентными описаниями динамики системы. Поскольку любой унитарный оператор  U может быть выражен как экспоненциальный самоприсоединенного оператора H так, что  U = e-iH, мы можем переформулировать 2-й постулат в непрерывной, дискретной версии:
Временная эволюция закрытой квантовой системы от состояния | ; > во время  t1 к состоянию | ; '> во время  t2 может быть описан унитарным оператором U = U (t2-t1) так что  |;' > = U |; >.
В иной формулировке, постулаты только применимы к закрытым системам, так как H или U(t) являются фиксированными операторами. Это довольно часто возможно для взаимодействия с квантовой системой таким способом, что она может быть обработана как изолированая,  в то время как эффект взаимодействия может быть математически описан времени- изменяющимся гамильтонианом. Даже в том случае, дискретная эволюция системы между двумя точками во времени t1 и t2 все еще могут быть описаны унитарным оператором U = U (t1, t2). В этом контексте мы будем говорить о применении оператора в  квантовое состояние | ; >.
1.2.3.3 Измерения
Постулат 3 (Проективное) измерение 2 было описано самоприсоединённым oператором M, названным наблюдаемым, со спектральным разложением M = ;m mPm, где Pm проектор на собственное пространство собственного значения M.
Собственные значения  m из М корреспондируют с возможными выходами измерения. Измерения | ;> будут давать результата  m с вероятностью p (m) =
2 Более главная формулировка квантового измерения позволяющая не проективного измерения операторы. Смотрите [43] для деталей.
Глава 1. QUANTUM COMPUTING 11
< ;|Pm|;>, таким образом уменьшив |; > к пост-измерения состоянию
Для состояния кубита, оператор само-присоединения N
известен как стандарт наблюдаемый. В основном, для систем с пространством состояний H = Cn, стандарт наблюдаемый N может быть определен как N = ;i i|i><i|
и / и ; ; и|.
Определение 12 Взвешенное среднее < M> над всем возможными выходами измерения  M названы значениями ожидания and определены как
Определение 13 Стандартное отклонение ;М всех возможных выходов измерения определяется как
Принцип неопределенности Гейзенберга Разрушительная природа измерения поднимает вопрос о том, что 2 наблюдаемые А и В могут быть измерены одновременно. Это может быть только случай, если состояние после измерения | ;'> - собственный вектор А и В
Это соответствует условию [A, B] = 0. Если А и В не коммутируют, тогда произведение неопределенности (;A) (; B) > 0.
Чтобы найти нижний предел для (;A) (; B)  мы вводим операторы ;A =
A-<A>  и ;B = B-<B> и можно выразить квадрат произведения неопределенности
(;A)2(;B)2 = ;(;A)2;;(;B)2; = ;;|(;A)(;A)|;;;;|(;B)(;B)|;; (1.23)
Поскольку ;A и ;B являются самоприсоединением, мы можем показать выше  показанное как
(;A)2(;B)2 = ;;A|;;;2 ;;B|;;;2. (1.24)
Используя (1.1) and [A, B] = [;A, ;B] we get
Глава 1. QUANTUM COMPUTING 12
1.2.3.4 Сводные системы
Постулат 4 Пространство состояний H сводной физической системы -тензорное произведение  пространств состояний Hi его компонентов. Более того, если подсистема в состоянии |;i > ;Hi, тогда состояние присоединения  |;> ;H сводной системы | ; > = | ;1 >;  |;2 >;  . . .  ; | ;n >.
Пусть S сводная система S1 и S2 с  пространством состояний  H = H1 ; H2. Измерение наблюдаемого  M: H1 ; H1 в S1, равно измерению наблюдаемого M (1) = M ;  I в S с I оператором тождества на Н2. Эквивалентно, унитарное преобразование U: H1 ; H1 для S1
описывается проложенным оператором U (1) = U ; I для H.
Присоединенное состояние формы | ; = | ;1 >;  |;2 > называется состоянием продукта, которое может быть расширено до
В состоянии продукта, унитарные преобразования или измерения выполняются на
одной системе, не влияяя на состояния других систем.
Запутанность (Ентаглемент) Нет никакого присоединенного состояния — состояние продукта. Состояние
где коэффициенты cij не могут быть написаны как  cij = aibj названы запутанными(ентаглед).
Рассмотрим следующие присоединенные состояния двух кубитов
Отдельное измерение другого кубита ( используя стандартное наблюдаемое как определено в  (1.19)) дает 0 или 1 с равной вероятностью  p = 1/2. Итог этого, измерение первого кубита дает результат m, соответственно пост измерения состояние
Измерение второго кубита | ;'> ещё дает случайный результат , пока в случае | ;';, выход коррелирует с предыдущим измерением и всегда выдает m. | ;B > также известен как состояние Белла.
Глава 1. QUANTUM COMPUTING 13
1.3 Классические Вычисления
1.3.1 Черч-Тьюринг Тезис
Как уже упоминалось в 1.1.3, вычислительная наука основана на парадигме из вычислений, являющихся механическими, скорее, чем чисто ментальный процесс. A метод, или процедура Р для достижения некоторых неудачных результатов называется эффективным или механическим если [21]
1. P набор выхода в терминах конечного числа точных инструкций (каждая инструкция выражена значениями конечного числа символов);
2. P будет, если выводит без ошибок, всегда выдает желаемый результат в конечном числе шагов;
3. P может (в практике или в принципе) вынесен человеком прицельно   любой машиной сохраняя бумагу и карандаш;
4. P просит не понимания не мастерства по части человека вынести это вон.
Алан Тьюринг и  Алонзо Чёрч оба формализовали над определением введения концепции вычислительной мощности машиной Тьюринга и математически эквивалентной  концепции рекурсивных функций со следующими заключениями:
Тезис Тьюринга LCMs [логические вычислительные машины т.e. Машины Тьюринга]
могут делать всё что можно описать как "правило большого пальца" или " чисто механически". [58]
Черч Teзис Функция положительных целых чисел эффективно рассчитывается только если рекурсивна. [50]
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 13
Поскольку приведенные выше утверждения эквивалентны, их обычно называют тезисом Черча-Тьюринга, который определяет сферу применения классических вычислений.
1.3.1.1 Частично рекурсивные функции
Класс частично рекурсивных функций P математически отражает концепцию “эффективных” функций f : Nn ; Nm. P может быть сконструирован из более простых классов следующим образом: [39]
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 14
1. Базовая функция f : Nn ; Nm - это функция f : x ; y, где yi -либо константа yi = ci, ci ; N, либо элемент входного вектора yi = x;(i). Класс BF базовой функции прикрыт под базовыми
операторами BO = {;, ;}, где “;” обозначает функциональную композицию, а “;” - обычное перекрестное произведение.
2. Класс PR примитивных рекурсивных функций генерируется из BF;{S} путем закрытия (замыкания) в соответствии с BO ; {Pr}, где
(i) S : N ; N - это функция-преемница (успешно продолжить) S(n) = n + 1, а
(ii) Pr обозначает примитивную рекурсию h = Pr[f, g]
h(x, 0) = f (x), h(x, n + 1) = g(x, n, h(x, n)) (1.32)
3. P генерируется из PR путем замыкания при BO ; {;0}. Оператор ;0 называется ;0-рекурсией (минимизацией) и определяется как
;0[f ] : x ; min
k;N [f (x, k) = 0] при f ; PR (1.33)
Поскольку ;0[f ](x) определяется только в том случае, если ;k ; N, f (x, k) = 0, P является классом частных функций. Класс R ; P всеобщих (тотальных) функций в P называется рекурсивными функциями.
1.3.2 Машины
1.3.2.1 Общие машины
Определение 14 Машина M представляет собой набор из 5 элементов (кортеж) (S, O, T, ;, ;), где [39]
(i) S - это набор вычислительных состояний
(ii) O = {fi : S ; S} - это перечислимый набор операций над S (команды памяти).
(iii) T = {ti : S ; B} - это перечислимый набор предикатов для S (тестовых команд
).
(iv) ; : I ; S - входная функция для перечисляемого набора входных данных I
(v) ; : S ; O - выходная функция для перечисляемого набора выходных данных O
Предоставляя набор (простых) элементарных операций и предикатов, машина определяет структуру для описания эффективных процедур.  Перечислимость O и T гарантирует, что такое описание, называемое программой, может быть конечным и представлено в виде строки с конечным набором символов.
Глава 1. QUANTUM COMPUTING 15
1.3.2.2 Дискретные Машины
Более жесткая интерпретация эффективности также требует, чтобы ее можно было перечислить, так это не только программа, но и компьютерное состояние может быть расширено ”конечными значениями" и какие вычисления могут быть реализованы на самом деле манипулируя символами  "на бумаге". Такие машины известны как дискрет. Для любой машины M = (S, O, T, ;, ;) с O = {f1, f2, . . .} и входным набором I = {x1, x2, . . .} эквивалентная дискретная машина M' = (S', O, T, ;, ;) может быть собрана диагонализацией
Машины Тьюринга Машина Тьюринга (ТМ) в уме содержит оперируя бесконечной лентой ячеек памяти. В самом простом случае, каждая ячейка может только принять одно из двух возможных состояний, помеченных 0 (также называется пустым) и 1.
Если мы указываем клетки по их относительной позиции в голову, мы можем описать
содержание ленты содержания как функция s: Z ; B и записать
Пространство состояния T — набор всех лент содержащих только конечное число из 1.3
Мы теперь можем определить TM как машину M = (T, {S, E, L, R}, {T}, ;, ;)
с командами
(i) S (. . . s-1 / s0s1s2 . . .) = (. . . s-1|1s1s2 . . .) (набор)
(ii) E(. . . s-1 / s0s1s2 . . .) = (. . . s-1|0s1s2 . . .(стирание)
(iii) L (s) = s '  где   s' i  = si+1 (движение влево)
(iv) R (s) = s ' где   s' i  = si-1 (двигаться вправо)
(v) Т(s) = s0 (тест)
Для  I = Nm и O = Nn мы можем определить машину Тьюринга TMmn =(T, {S, E, L, R}, {T}, ;m, ;n) с унарным кодом (унари енкодинг)

3Этот нуль хвост условие(зеро тайл кондишион)  необходим как набор  T ' = {s: Z ; B} будет не перечисляемый.
Глава 1. QUANTUM COMPUTING 16
1.3.2.3 Конечные Машины
Для дискретной машиины М с бесконечностью S, число символов представить вычислительное (компьютюшионал, обложенное, совместное) состояние s ;S можно получить произвольно большим так любая реализация М будет требовать неограниченную память. Если объём памяти ограничен, также число компьютишионал состояний. Дискретная машина М с ограниченной памятью названа конечной (финит, завершенной).
Ёмкость памяти конечной машины М с конечным пространством состояний S — S = log2|S| бит.
1.3.2.4 Оракулы
Если машина M1 = (S1, O1, T1, ;1, ;2) расширяется для включения вычислений на другой машине M2 = (S2, О2, Т2, ;2, ;2), затем машина результатов М = М1 ;;M2 упоминается как M1-машина с M2-оракулом.
Взаимодействие между M1 и M2 было описано командами оракула формы
fO: S1 ; S2 ; S1 ; S2 or tO: S1 ; S2 ; B (1.39)
и  M можно записать как
M = (S1 ; S2, O1 ; {I1} {{fO}, T1 {{tO}, ;, ;) (1.40)

с I2 быть идентичной с S2.
В зависимости от определения fo и to, призывы оракула могут коррелировать с отдельным  M2 — командовать вплоть до  выполнения полностью конечной программы (см. 1.3.3.2)  M2. Так что, с отношением к времени комплексности , оракулa вызовы считать как единый вычислительный шаг.
1.3.2.5 Вероятностные Машины
А машина М = (S, О, Т, ;, ;) вероятностная, если она обеспечивает в конце случайную тестовую команду с;Т. A random predicate c: S 7 ; B может быть математически описанн распределением вероятности  p (c|s) где s ; S, так
c: s  ;{true with p = p(c|s)
false with p = 1-p (c|s) (1.41)
Мы можем обобщить это определение, также используя случайной памяти команды f: S  ; S

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 17
и выходные функции ; : S ; O. В последнем случае p; (y|s) при y ; O также называется (вероятностным) спектром s.
Для любой вероятностной машины M можно формально построить соответствующую детерминированную машину ;M, работающую в пространстве распределения
Состояние ;s ; ;S имеет энтропию (Шеннона)
Вероятностная машина Тьюринга Вероятностная машина Тьюринга (PTM) может быть построена на основе детерминированной TM путем добавления без состояния случайного числа оракула (рандом оракл), который предоставляет тестовую команду C “честным подбрасыванием монеты” с p(C) = p(C) =1/2.
1.3.3 Программы
Программа ; для некоторой машины M = (S, O, T, ;, ;) представляет собой конечный набор инструкций (также называемых утверждениями (стейтмент), который определяет, как итеративно преобразовывать входное состояние s0 = ;(x), используя память машины и тестовые команды до тех пор, пока не будет выполнено некоторое условие остановки. Если программа останавливается, результирующее состояние sh называется выходным состоянием.
;
;
ввод
-вывод
тестовых команд, команд памяти
S
Рисунок 1.1: Программа ;, управляющая машиной M = (S, O, T, ;, ;)

Передаточная функция ;; : s0 sh - это частичная функция от S, определенная для всех входных состояний s0 ; S, для которых ; останавливается. F (;, M) обозначает частичную функцию x ; ;(;;(;(x))), реализуемую ; при M = (S, O, T, ;, ;).
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 18
Интерпретация программы ; класса программ ; определяется ступенчатой(шаговой, степ) функцией ; : ; ; P ; S ; P ; S. P = P(;) - это набор возможных управляющих -состояний с уникальным p0 ; P, называемым начальным состоянием, и подмножеством   , называемым состояниями остановки(хальт, достаточно).
Пара (p, s) ; P ; S называется конфигурацией. ; имеет общий вид

где P = Pf ; Pt ; Ph, f;(;,p) ; O и t;(;,p) ; T .
Для входного состояния s0 = ;(x), (p0, s0) = (p0, ;(x)) называется начальной конфигурацией. Передаточная функция ; определяется как
(ph, ;;(s0)) = pn(p0, s0) при n = minkpk(p0, s0) ; Ph ; S (1,46)
Если ; останавливается при заданном значении x ; I, то n называется (временной) сложностью вычисления.
1.3.3.1 Последовательности
Определение 15 Программа ; ; On для машины M = (S, O, T, ;, ;), состоящая из статического списка n команд в памяти, называется последовательностью. Передаточная функция ;; : s ; (;1 ; ;2 ; . . . ; ;n)(s) является суммарной функцией.
Определение 16 Пусть S состоит из идентичных индексированных ячеек памяти Mi с пространством состояний S, таких, что S = S1 ; S2 ; ... для некоторой подходящей композиции ; и g функция g : Sn ; Sn. Класс функций ;(g) = {gi1i2...in : S ; S}, где gi1i2...in обозначает применение g к перестановке n взаимно отличающихся ячеек Mi1 , Mi2 ... Min, называется n-арным элементом.
Если O - это объединение элементов, то последовательность ; ; O* может быть интерпретирована как сеть прямой связи (фид форвард) и также называется схемой.
Набор операций O является универсальным, если для любой функции f : I' ; O, определенной для конечного подмножества I' ; I, существует последовательность ; ; O* такая, что f (x) = ;(;;(;(x))) для всех x ; I'.
Хотя, как правило, для полного использования вычислительного потенциала машины M = (S, O, T, ;, ;) требуются более мощные концепции программирования, последовательностей достаточно для реализации любой функции, которая может быть реализована, если либо
(i) O является универсальным, и (a) M является конечным, или (b) I является конечным множеством,
(ii) M  предоставляет отсутствие тестовых команд, т.е. T =


ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 19
1.3.3.2 Конечные программы
Определение 17 Пусть M - машина (S, O, T, ;, ;), а L - перечислимый набор меток с элементом l0 ; L, называемым начальной меткой.
(i) Тройка (l, f, p) ; L ; O ; L называется функцией- инструкцией
(ii) Набор из 4 элементов (l, t, p, q) ; L ; T ; L ; L называется тестовой инструкцией
Метки l называются инстукцией (стейтмент)-, p и q - метками перехода-. Конечная программа ; ; ; для M представляет собой конечный набор инструкций (операторов) с уникальными метками l.
Функциональные и тестовые операторы также записываются как
l : f, затем p
l : если t, то p, иначе q
Программа ; ; ; описывает конечный автоматон, работающий на M с помощью ступенчатой функции

где Ln обозначает набор выражений-меток в ;, а ;l : L; ; ; — оператор (инструкция) с меткой l.
Согласно тезису Черча-Тьюринга, любая эффективная функция f : Nn ;Nm может быть реализована в виде конечной программы ; для TMmn и набора вычислимых по Тьюрингу функций
F (TM) = {F (;, TМmn ) | ; ; ;, n, m ; N} (1.48)
идентиченым P.
Определение 18 (Универсальный компьютер) Машина M = (S, O, T, ;, ;) с кодировками ; : N* ; S и ; : S ; N* является универсальным компьютером, если для любого f ; P существует конечная программа ; для M, такая, что f = F (;, M).
1.3.3.3 Языки программирования
Определение 19 Язык программирования L  ;* для машины M — это класс описаний алгоритмов p ; ;* по некоторому алфавиту ;, который может быть эффективно преобразован в конечную программу ; ; ; для M другой программой ;L для машины
ML = (S, O, T, ; : ;* ; S, ; : S ; ;) (1.49)
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 20
Пара (;L, ML) называется компилятором для L. Обычно требуется, чтобы компиляция была эффективной, т.е. имела полиномиальную временную и пространственную сложность.
Язык программирования L является универсальным, если M является универсальным компьютером и для любого f ; P существует программа p ; L, такая, что f = F (p, M) =
F (F (;L, ML), M).
1.4 Элементы квантовых вычислений
Как и классическая машина, квантовый компьютер, по сути, состоит из трех частей: памяти, в которой хранится текущее состояние машины, процессора, который выполняет элементарные операции с состоянием машины, и некоторого рода входного/выходного сигнала, который позволяет задать начальное состояние и извлечь конечное состояние вычисления.
Формально мы можем описать квантовый компьютер как вероятностную машину
M = (H, O, T, ;, ;), где
• H - пространство состояний квантовой системы, выполняющей операции,
• O - набор (детерминированных) унитарных преобразований,
• T - набор (вероятностных) команд измерения,
• ; - оператор инициализации и
• ; описывает конечное измерение.
1.4.1 Квантовая память
1.4.1.1 Кубиты
Квантовым аналогом классического бита является квантовый бит или кубит (см. 1.2.3.1).
Определение 20 Кубит или квантовый бит - это квантовая система, состояние которой может
быть полностью описано суперпозицией двух ортонормированных базисных состояний, обозначенных как |0; и |1;.
Пространством состояний кубита является гильбертово пространство B = C2. Ортонормированная система {|0;, |1;} называется вычислительным (компьютюшионал, совместным, возложенным)  базисом.
Классическое значение кубита описывается стандартной наблюдаемой N = |1;;1| (1.19). ;N ; дает вероятность нахождения системы в состоянии |1;, если на кубите выполнено измерение.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 21
Сфера Блоха Игнорирует несущественный общий фазовый коэффициент, общее состояние кубита можно записать в виде
|;; = cos ;/2|0; + ei; sin ;/2|1; (1.50)
Интерпретируя ; и ; как полярные координаты
;r = (соѕ ; sin ; , sin ; sin ;, cos;), (1.51)
каждое состояние кубита имеет единственное представление в виде точки на трехмерной
единичной сфере, также известный как сфера Блоха.

Рис. 1.2: представление сфере Блоха кубита состояние |;;

Блок(юнит, единица)-вектор ;r = ;r; называется вектор Блоха |;;. Векторы Блоха имеют свойство
;r ; = ;;r x ;; <;|;> = 0. (1.52)
1.4.1.2 Состояние машины
Определение 21 Пространство состояний квантового компьютера представляет собой разделяемого комплекса Гильбертово пространство H с заданной перечислимой ортонормированной системой B = {|i;} называется вычислительный базис. Состояние квантового компьютера - это единицы(юнит) вектор |;; ; H, известный как машинное состояние.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 22
Классически общее пространство состояний S составной системы, состоящей из n ячеек памяти с пространствами состояний Si, задается перекрестным произведением S = S1 ; S2 ; . . . ; Sn. В квантовой механике это справедливо только для состояний продукта (см. 1.2.3.4).
Пространство состояний H квантового компьютера, состоящее из n идентичных подсистем с пространством состояний S, задается как тензорное произведение
H = S;n =n раз; ;; ;S ; . . . ; S (1.53)

Таким образом, машинное состояние |;; квантового компьютера с n-кубитами является
единицы (юнит) вектором в H = B;n = C2n
|;; = ;(d0...dn-1;;Bncd0...dn;1 |d0 . . . dn;1; с ; |cd0...dn;1/2 = 1 (1,54)

Базисные векторы |d0 . . . dn;1; могут быть интерпретированы как двоичные числа и обозначены как |k; с k = ;n;1 i=0 2idi, поэтому B можно записать как B = {|k;|k ; Z2n }.
Квантовый компьютер M = (H, O, T, ;, ;) конечен, если dim H < ;. Объем памяти конечного квантового компьютера равен log2 dim H кубитов.
Неограниченная память Поскольку пространство состояний квантового компьютера является разделяемым гильбертовым пространством, оно изоморфно либо Cn, либо l2 (см. 1.2.2.2).
Гильбертово пространство B;, являющееся результатом композиции бесконечного числа
кубитов неотделимо. Однако мы можем построить отделимое подпространство
B? ; B;;, которое изоморфно l2, введя условие нулевого конечного (хвоста, тейл) состояния.
B? = {|;; ; |0;;; ;;; |;; ; B;n, n ; N}(1.55)

1.4.1.3 Квантовые регистры
Определение 22 Пусть H - пространство состояний квантового компьютера M с вычислительным  базисом B = {|i;}. Квантовый регистр s представляет собой подсистему из M с конечномерным пространством состояний Hs и базисом Bs = {|i>s}, таким что H = Hs  Hs и B = Bs ; Bs. Если M конечно, то s называется дополнительным регистром к s.
Регистр s определяет разложение для вычислительного базиса B, поэтому любой базисный вектор |k; ; B может быть записан как состояние продукта |k; = |ik;s|jk;;s при  |ik;s ; BS и |jk;;s  ; B;s .
В H классическое значение регистра s описывается регистром наблюдаемым N (s)

Глава 1. КВАНТОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ 23
где Ns - это стандарт, наблюдаемый в Hs, и оператор идентификации в Hs. Аналогично, унитарное преобразование U в Hs может быть выражено как регистровый оператор U (s) в H
где ui,i' - элемент матрицы ui,i' = ;i|U |i';.
Регистры кубитов Когда H ; это пространство состояний композиции кубитов qi, т.е. H = B;m или H = B*, тогда любой qi определяет регистр qi с разложением
Аналогично, любая перестановка (s0s1 . . . sn;1) = (qk0, qk1 . . . qkn;1 ) взаимно отличающихся кубитов sj ; {qi} определяет n-кубитный регистр s = qk0 ; qk1 ; . . . ; qkn;1
с разложением
Порядок расположения кубитов важен, поэтому, хотя a ; b и b ; a относятся к одной и той же 2-кубитной подсистеме, это два разных регистра.
Если s - это n-кубитный регистр, а U - оператор на Bn, то регистровый
оператор U (s) также называется квантовым затвором(гейтс, вентиль).
Состояния регистра Строго говоря, состояние регистра s определяется только в том случае, если машинное состояние |;; имеет вид |;; = |;;s|;;s. В этом случае мы говорим , что s находится в чистом состоянии |;; ; Hs. В качестве альтернативы, состояние s может быть
описано оператором (приведенной) плотности ;s.
Определение 23 Пусть H = Ha ; Hb - пространство состояний составной системы a ; b. Для состояния машины
сокращённый оператор плотности  ;а : На ; На определяется как
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 24
Если регистр s находится в чистом состоянии, то ;s = |;> и tr|;2s ) = tr;s = 1. Если
s запутан, то ;s  является положительным оператором со спектральным разложением

и tr(;2s ) < 1. В этом случае также считается, что s находится в смешанном состоянии ;s .4
Оператор плотности позволяет рассматривать s как изолированную систему с учетом унитарной эволюции и измерений до тех пор, пока над ;s не выполняется никаких операций:
(i) Пусть U - унитарный оператор на Hs, тогда


(II) пусть M оператор эрмитов на Hs со  спектральным разложением
М = ;mmPm, то p(m) = ;;|Pm(s)|;; = tr(Pm;s) и

Разложение Шмидта Если s и s перепутаны, состояние машины всегда можно записать в виде

таких, что |;i; ; Hs  и |;i; ; Hs имеют ортонормированное состояние, т. е. ;;i|;j ; = ;ij
и ;;i|Хj ; = ;ij . Это представление называется разложением Шмидтa.
1.4.2 Квантовые операции
1.4.2.1 Унитарные операторы
Согласно 2-му постулату квантовой механики (см. 1.2.3.2), эволюция замкнутой квантовой системы является унитарной и может быть описана оператором U (t) = e;iHt. Следовательно, команды памяти O квантового компьютера M = (H, O, T, ;, ;) являются унитарными преобразованиями в пространстве состояний H.
Унитарное преобразование U является линейным оператором вида U U † = I и описывает базисное преобразование B U;; В . С вычислительной точки зрения, эти математические свойства объясняют три фундаментальных различия между классическими и квантовыми вычислениями:
4 Термин “смешанное состояние” относится к тому факту, что ; демонстрирует ту же статистику измерений, что и система, которая, как известно, находится в состоянии |;k; с вероятностью pk.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 25
• Обратимость: Поскольку унитарные операторы, по определению, соответствуют условию U U † = I, для каждого преобразования U существует обратное преобразование U (-1) = U†. Как следствие, квантовые вычисления ограничены обратимыми функциями.5
• Суперпозиция: “Классическое” состояние |;; = |к; ; B может быть преобразовано в суперпозицию нескольких векторов базиса

и наоборот.
• Параллелизм: Если машинное состояние |;; уже является суперпозицией нескольких базисных векторов, то преобразование U применяется ко всем базисным состояниям одновременно.
Эта особенность квантовых вычислений называется квантовым параллелизмом и является следствием линейности унитарных преобразований.
1.4.2.2 Кубитные операторы.
Простейшим случаем унитарных преобразований являются операторы, работающие с одним кубитом. Общая двумерная комплексная унитарная матрица U ; SU (2) может быть записана в виде
Как мы показали в 1.4.1.1, каждое состояние кубита |;; ; B может быть представлено вектором Блоха ;r;. Поворотам вокруг ;x, ;y и ;z-осей в сфере Блоха соответствуют операторы
5 Классическим аналогом был бы класс биективных функций на Bn.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 26
на B. Легко проверить, что R†i (;) = Ri (;), поэтому все Ri являются унитарными операторами.
Используя обратимые друг к другу матрицы Паули
главное (общее) вращение 6 вокруг единичного вектора ;n можно записать в виде
Пусть U ; SU (2) имеет ортонормированные собственные векторы |u > и | v; и
собственные значения u и v, тогда U можно записать в виде

где ;n  - вектор Блоха |u;, а ; - разность фаз между u и v, т. е. v = ei;u.
1.4.2.3 Универсальные операции с кубитами
Поскольку кубит-операторы соответствуют вращениям в сфере Блоха, любая унитарная операция с кубитом может быть U на B может быть реализованa как комбинация из трех поворотов вокруг двух ортогональных осей и общего фазового коэффициента (физически несущественного)7  , например
U = ei;Rz (;)Ry (;) Rz (;) (Z-Y разложение) или (1.75)
U = ei;Rx (;)Ry(;) Rx (;) (разложение по X-Y) (1.76)
Это означает, по соображениям симметрии, что для любых двух ортогональных единиц (юнит) векторов ;u и ;v, набор операторов Ouv = {R;u(;) / ; ; R} U {R;v(;) | ; ; R} является универсальным для операций одиночного кубита .
Определение 24 (Универсальность множеств операторов) Пусть H - отдельное Гильбертово пространство, а O - множество унитарных операторов на H. O является универсальным на H, если для любого унитарного оператора U: H ; H и для любого ; ; R+ существует композиция ; = U1 ; U2 ; . . . Uk при Ui ; O и общей фазой ei; такой , что
6 Обратите внимание, что, несмотря на математический период, равный 4;, R;n(;) и R;n (; + 2;) = - R;n(;) описывают одну и ту же физическую операцию.
7 Обратите внимание, что расширение (1.75) непосредственно приводит к (1.68).
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 27
Пусть O = {R;n (;) | ; ; R} - класс вращений вокруг некоторой оси вектора ;n. Пока
множество {Rk;n(;) | k ; N} c O является плотным в O, если ; ; 0, а ; / ; иррационально.
Таким образом, любая пара {R;u(q;), R;v (p;)} ортогональных вращений кубита, где ;u ;;v и
p, q ; I +, уже представляет собой универсальный набор кубитных операторов.
Приведенный выше результат можно обобщить на неортогональные вращения: Пусть
V = R;v(;) и W =R;w(;) - унитарные кубитные операторы, где 0 < |(;v ,;u) | < 1 , и пусть ;u  - ортонормированная ось вектора к ;v . Поскольку W можно записать в виде W = R;v(;1)R;u  (;) R;v(;2), мы можем построить вращение кубита
ортогонально V . При условии, что ; / ;, ;/; ; I+, существуют k1, k2 ; n, такие , что R;v(;;i) ; Vki с произвольной точностью, а пара операторов {V, W } универсальна.
1.4.2.4 Квантовые вентили
Определение 25 Пусть H = B;n  или H =  B* - пространство состояний составной системы кубитов S = {qi}, а Rk (S) = {s / S / = k} обозначает упорядоченные подмножества k-кубитов из S, т.е. множество k-кубитных регистров. Класс
; (U) = {U (s) | s ; Rk (S)} (1.80)
регистр операторов на H для некоторого унитарного k-кубитного оператора на B;k называется k-кубитным квантовым затвором .
Неофициально мы можем описать k-кубитный затвор как унитарный оператор, который может быть в равной степени применен к любому k-кубитному регистру квантового компьютера. В этом случае термин “вентиль" также используется для обозначения оператора с одним регистром U(s) ;; (U ), а также самого оператора U.
Общие элементарные вентили
Вентили с одним кубитом
* Вентили Паули

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 28
* Вентили Адамара

* Фазовый и ; / 8-вентиль 8
Два кубитных вентиля
* управляемый-не вентиль
* переключающий элемент (вентиль обмена)
* управляемый фазовый вентиль
Три кубитных вентиля
* Элемент Тоффоли (управляемый-управляемый -не)
* Fredkin-gate (управляемая замена)

1.4.2.5 Управляемые вентили
Единственным наиболее важным 2-кубитным элементом является вентиль- управляющий -не(отрицание). CNot-вентиль работает с целевым кубитом t и управляющим (или разрешающим) кубитом e и может быть определен с помощью X-вентиля в виде матрицы

8T называется ;/8-вентилем как T;еi;;x / 8.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 29
или как регистровый оператор

Неофициально мы можем описать CNot-логический элемент как условно применяющий оператор X (одиночный бит not) к целевому кубиту t в зависимости от элемента управления кубита e. Это можно обобщить на произвольные логические элементы и умножаюшие управляющие биты:
Определение 26 (Управляемый элемент) Пусть U - унитарный элемент с m-кубитами.
Управляемый U-элемент с n управляющими кубитами определяется как

на B;n +m или в регистровой записи

Для любого отдельного кубитного элемента U C[U ] может быть реализован с использованием операций с одним кубитом и CNot: Пусть U = ei;Rz (;)Ry(;)Rz(;) — ZY-разложение (1.75) из U , A = Rz (;)Ry(;/2), B = Ry(;;/2)Rz (;(; + ;)/2) и C = Rz ((; ; ;)/2), тогда
Фазовый вентиль Операторы фазовых вентилей вида V (;) = Cn[ei;] называются (управляемыми) фазовыми вентилями и представляют собой интересный частный случай в качестве оператора U = ei; является физически несущественной общей фазой и технически может рассматриваться как вентиль с нулевым кубитом, поэтому только управляемые версии U обладают нетривиальным физическим эффектом.
Примерами управляемых фазовых вентилей являются Rz (;) ; C[ei ;] (см. 1.4.2.2), Z =
C[-1], S = C[i], T = C[ei;/4] и C Phase= C2[i] (см. 1.4.2.4).
1.4.2.6 Универсальные вентили
Хорошо известный результат классической булевой логики состоит в том, что любая возможная функция f: Bn ; Bm может быть построена как композиция из небольшого универсального набора операторов, если мы можем “привязать” входы и выходы к произвольным битам в сети прямой связи. Примерами универсальных наборов логических элементов являются {;,¬ }, {;, ¬} или {;;}.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 30
В разделе 1.4.2.3 мы уже продемонстрировали, как практически любая пара одиночных кубитов вращения могут быть использованы для аппроксимации произвольного унитарного оператора на B.
Можно показать, что любая n-мерная унитарная матрица может быть разложена
на произведение не более () = n(n ; 1)/2 двухслойных унитарных матриц  [42, 52],9 т.е.
Если H = B;n  представляет собой композицию кубитов, то для любого одиночного кубитного элемента U , Cn;1[U ] также является двухслойной матрицей. Используя подходящие базисные перестановки ;ij : |k; ; |;k; при ;i = 2n ; 2 и ;j = 2n;1 двухслойные матрицы Uij из (1.94) можно записать в виде
Поскольку базисные перестановки по существу реализуют биективные функции над
Bn (см. 2.5.3), любого квантового логического элемента, который реализует универсальный обратимый логический элемент, вместе с управляемыми операциями с одним кубитом достаточно для реализации произвольных унитарных операторов на B;n .
Примером универсального обратимого логического элемента является классический
элемент Тоффоли T: (x, y, z) ; (x ; (y ^ z)) [57]. В отличие от T, его квантовый аналог (1.87) может быть разложен на 2-кубитные операторы, например.

Выбрав V таким образом, что U = V2, приведенную выше факторизацию можно использовать для построения C2 [U ] для произвольных одиночных кубит-вентилей. Более того, аналогичные декомпозиции могут быть найдены для любого числа управляющих кубитов, поэтому операции CNot и с одним кубитом универсальны [28].
Другими примерами универсальных наборов квантовых вентилей являются
• стандартный набор [43, 13]10
{H, S, T, CNot} (1.97)
9 Это аналогично тому факту, что общее вращение в Rn может быть разложен на ()
простых вращений в координатных плоскостях.
10 Поскольку S = T2, фазовый вентиль (1.83) включен только для удобства.

ПРИМЕР 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 31
Стандартный набор является универсальным, несмотря на то, что H и T являются ; и ;/4 вращениями в сфере Блоха, поскольку угол ; поворота R;n(;) = TH и можно показать , что R ;m(;) = HT , которое задается через cos ; = cos2 ;/8 , является иррациональным кратным ; [13].
• немецкий Дойча элемент [25]
Доказательство универсальности включает в себя построение вентиля Тоффоли , который может быть использован для реализации произвольных базисных перестановок ; : |i; ; |;i;. Затем они могут быть использованы для построения 3-кубитных двухслойных вращений между любыми двумя базисными векторами, которые, как может быть показано, достаточны для построения произвольных унитарных преобразований [41].
1.4.3 Ввод и вывод данных
1.4.3.1 Квантовые вычисления и обработка информации
Как уже упоминалось в разделе 1.2.1, конечная цель квантовых вычислений заключается в том, что интерпретация вычислений как физического процесса, а не абстрактного манипулирования символами, приводит к расширенному представлению о вычислительной способности. В соответствии с постулатами квантовой механики (см. 1.2.3), мы также определили концепцию унитарных преобразований как наиболее общую парадигму “физической вычислимости”.
Унитарные преобразования описывают переход между состояниями машины и, таким образом, временную эволюцию квантовой системы. Однако само понятие (квантового) компьютера как “вычислительной машины” требует, чтобы эволюция физической системы соответствовала обработке информации.
Классическая теория информации требует, чтобы любая “разумная (причинно-следственная, причинно-способая” информация могла быть выражена в виде последовательности ответов "да" и "нет" на вопросы , т.е. последовательности битов. Но в отличие от классических символьных вычислений, где каждый отдельный шаг вычисления может быть отображено в виде последовательности битов, для физических вычислений требуется такая маркировка только для начального и конечного состояния машины, метки которых составляют входные и выходные данные вычисления.11
Если мы рассматриваем квантовый компьютер как вероятностную машину M (см. 1.3.2.5 и 1.4), вышеуказанные требования эквивалентны перечислимости входных и выходных наборов I и O.
11 Это соответствует копенгагенской интерпретации квантовой физики, которая гласит, что установка и результат любого эксперимента должны быть описаны в классических терминах.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 32
1.4.3.2 Операторы измерения
В классическом машинном определении (см. 1.3.2) тестовая команда t ; T представляет собой функцию t : S ; B. Однако в случае квантового компьютера M = (H, O, T, ;, ;) состояние машины |;> ; H недоступно напрямую, и любая физически реализуемая тестовая команда должна быть равна измерению некоторого наблюдаемого значения M.
Согласно 3-му постулату квантовой механики (см. 1.2.3.3), измерение M на |;> является детерминированным и инвариантным к |;>  только в том случае, если |;> оказывается, это собственное состояние M , поэтому тестовые команды больше не являются логическими предикатами для S, а являются вероятностными операторами измерения, т.е.
T = {µi : H ; H ; B} (1.99)

Определение 27 Пусть M — самосопряженный (присоединённый) оператор на H со спектральным составом M = ; m ;mPm, тогда оператор измерения ;[M ] является вероятностным отображением ;[M ] : H ; H ; R, определяемым как
Поскольку предполагается, что тестовые команды выдают логические результаты, каждый µi соответствует проекционному оператору Pi, т.е. эрмитову с собственными значениями 0 и 1. Таким образом, µi = µi[Pi] и
Если P = N (s), мы также записываем ;(s) ; ;[N (s)]. Кроме того, мы иногда будем игнорировать одно из значений функции, если это удобно и может быть сделано без двусмысленности.
Измерения одним кубитом Если H = B;n, то естественным выбором для Pi являются стандартные наблюдаемые значения
N (qi) = I;i ; |1;;1/ | I;n-i-1 (1,102)
для каждого кубита qi. Если M предоставляет универсальный набор О унитарных операторов, то отдельного измерения кубита в вычислительной базе достаточно для измерения произвольного P :

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 33
Общая проекция P имеет вид
где ~B - произвольный ортонормированный базис H. Если O универсален, то можно реализовать унитарный оператор U = ; n |n><~n|, а P может быть выражено как P = U †P 'U с P ' = ; n ;'n|n><n|.
Чтобы измерить P ', мы можем использовать дополнительный скретч кубит s в состоянии |0>s и использовать унитарный оператор
для подготовки состояния запутанной машины
Измерение N (s) на |;'; теперь эквивалентно измерению P ' на |;;. Если результат равен 1 и, следовательно, s остается в состоянии |1;s, предыдущее состояние может быть восстановлено путем применения X(s).
Выходная функция Для получения классического результата вычисления требуется окончательное измерение. Используя стандартную наблюдаемую величину N на H, мы можем определить вероятностную выходную функцию ; : H; N как ; = ;[N ].12
1.4.3.3 Подготовка состояния
Для установки или сброса квантового компьютера M в желаемое начальное состояние |;0; не требуется никаких дополнительных операций, кроме унитарных преобразований и необходимых измерений . Предполагая, что H = B;n, достаточно измерить все кубиты, чтобы привести M в известное состояние |;; = |m;, а затем применить произвольный унитарный
оператор Um, который удовлетворяет условию ;;0 |Um|m| = 1.
Если |;0; = |d0d1 . . . dn;1;, то для подготовки требуется не более n X-вентилей .13 Также удобно включить специальную команду сброса неунитарной памяти
reset : |;; ; |0; (1.106)
для инициализации состояния компьютера.
12Это обозначение  на самом деле является сокращением для ;(|;;) = м ;; ;  [N ]|;; = (|;m;, m).
13For произвольного |;0;, количество необходимых вентилей, как правило, возрастает в геометрической прогрессии.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 34
Входная функция Чтобы обеспечить возможность подготовки “классических” входных состояний, мы можем определить входную функцию ;(s) : N ; H как ;(s) = |s;. Для квантовых алгоритмов, которые принимают входные данные в виде оракульских операторов14 и , следовательно, не требуют каких-либо классических входных данных, обычно предполагается начальное состояние |;0; = ;(s) = |0;.
1.5 Концепции квантовых вычислений
1.5.1 Модели и формализмы
Как мы продемонстрировали в разделе 1.3, концепция универсального компьютера может быть представлена несколькими эквивалентными моделями, соответствующими различным научным подходам. С математической точки зрения универсальный компьютер — это машина, способная вычислять частично рекурсивные функции (1.3.1.1), специалисты по информатике часто используют машину Тьюринга (1.3.2.2) в качестве своей любимой модели, инженер-электронщик, возможно, будет говорить о логических схемах, в то время как программист, вероятно, предпочтет универсальный язык программирования (1.3.3.2)..
Что касается квантовых вычислений, то у каждой из этих классических концепций есть квантовый аналог: [47, 48]
модель Классическая квантовая
Математическая частично рекурсивная функция. унитарные операторы
машина Машина Тьюринга QTM
Схема логическая схема квантовые вентили
Алгоритмический универсальный язык программирования QPLs
Таблица 1.2: Классическая и квантовая вычислительные модели

1.5.1.1 Математическая модель
Парадигма вычислений как физического процесса требует, чтобы алгоритмы — в принципе — могли быть описаны теми же средствами, что и любая другая физическая система, что для области квантовой физики является математическим формализмом алгебры Гильбертова пространства. Основы этого формализма были представлены в разделе 1.2.
Квантовым эквивалентом частично рекурсивных функций является унитарные операторы. Точно так же, как любая классически вычислимая задача может быть переформулирована в виде
14 Оракула функция или оператор - это специальная команда памяти “черного ящика” или тестовая команда, которая может использоваться либо для описания проблемы, либо для расширения функциональных возможностей машины.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 35
вычисления значения частичной рекурсивной функции, каждое квантовое вычисление может быть описано унитарным оператором.15
Математическое описание оператора по своей сути является декларативным; фактическая реализация определенной квантовой архитектуры, т. е. алгоритмическое разложение на элементарные операции, выходит за рамки этого формализма. Кроме того, поскольку математическая модель рассматривает унитарные операторы как черные ящики, мера сложности не предусмотрена.
Регистровая нотация Для упрощения обсуждения операторов, применяемых к перестановке кубитов при H = B;n и H = B* мы ввели концепцию квантовых регистров (см. 1.4.1.3). В таблице 1.3 приведены все важные выражения для регистров.
Описание обозначение
: s общий регистр, т.е. упорядоченный набор кубитов
s дополнительный регистр к s
| . . .;s ket-вектор регистра s
|s| длина s, т.е. количество кубитов в s
СС |s|-кубит подпространства {|;;С} ч, ГС ; ГС = ч
в ; объединения в регистры A и B, А ; Б 6 = ; Б а
П (с) Регистра оператор U ; я на гв ; УГ
;(s) оператор стохастического измерения ;[N (s)] : H7 ; H ; B|s|
оператор плотности регистра ps ps = trs (|;/)
U (a, b) мультирегистровый оператор U (a ; b)
U[[b]](a) оператор условного регистра C|b|[U ](a ; b)
Таблица 1.3: Обозначения регистров
1.5.1.2 Квантовые машины Тьюринга
По аналогии с классической машиной Тьюринга (ТМ) было предложено несколько типов квантовых машин  Тьюринга (QTM) были предложены в качестве модели универсального квантового компьютера [5, 24, 6, 9].
Полное машинное состояние |;; ; H QTM определяется как суперпозиция базовых состояний |l, j, s;, где l ; Zn - состояние головки, j ; N - положение головки и
s = (... s-2s;1|s0s1s2 . . .) (1.107)
15 При этом предполагается, что любые измерения выполняются в конце вычисления. Однако существуют алгоритмы, которые используют присущую квантовым измерениям функцию сокращения состояний, поэтому аналогия не является универсальной.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 36
двоичное представление содержимого ленты. Чтобы сохранить разделимость H, s должен удовлетворять условию нулевого конечного (хвоста) состояния (см. 1.3.2.2), т.е. допускается только конечное число битов с sm ; 0, так что s ; B* и H = Cn ; l2 ; B*
Квантовый аналог переходной функции классического вероятностного TM - это унитарный оператор  шага T, который должен соответствовать условиям локализации для затронутого ленточного кубита, а также для перемещения головки.16
QTM обеспечивают измерение времени выполнения, но, как и в случае классического
ТМ — найти подходящий пошаговый оператор может быть очень сложно.
1.5.1.3 Квантовые схемы
Квантовые схемы являются квантовым эквивалентом классических логических сетей с прямой связью, с одним существенным отличием: поскольку все квантовые вычисления должны быть унитарными, квантовые схемы могут быть вычислены в обоих направлениях (как классическая обратимая логика). Квантовые схемы состоят из элементарных элементов и работают на кубитах.17 “Схема подключения” между вентилями определяет регистр, на котором работают вентили, поэтому m-кубитный вентиль U в n-кубитной схеме может описывать до n!/(n;m)! различных унитарных преобразований U (s).
В отличие от математического формализма, логарифмическая запись является по своей сути конструктивным методом, и сложность задачи напрямую отражается на количестве вентилей необходимых для ее реализации. Однако, поскольку квантовые схемы описывают статические последовательности, размер входных данных, а также количество кубитов фиксировано, поэтому без дополнительных допущений квантовые схемы нельзя использовать для анализа сложности в зависимости от размера задачи. По той же причине квантовые схемы также не подходят для машин с неограниченной памятью.
Ограничения По сравнению с классическими логическими сетями с прямой связью, это накладывает следующие ограничения:
• Разрешены только сети n-к-n, т.е. общее количество входов должно соответствовать общему количеству выходов.
• Разрешены только n-к-n вентилей.
16 Вместо унитарного пошагового оператора T также возможно непосредственно построить (локальный) гамильтониан H (см. 1.2.3.2) [5, 6]. В этом случае вычисление не обязательно должно быть дискретным, и T ' = U (t0) = e;iHt0 не требуется для соответствия условиям локальности.
17 Существуют также расширения, охватывающие измерения и классические биты [43]. В этом случае квантовые схемы также могут быть использованы для описания необратимых вычислений.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 37
• Раздвоение входных данных запрещено. Это напрямую связано с тем фактом, что кубиты не могут быть скопированы, т.е. не существует единой операции
Скопируйте |;;/0; ; /;;/;; с помощью |;; ; C2 (1.108)
которая может преобразовать общее состояние кубита в собственное производное состояние.
• "Тупики" не допускаются. Опять же, это связано с тем, что стирание кубита
Стирание |;; ; |0; с помощью |;; ; C2 (1.109)

не является однократной операцией.
Обозначения Некоторые общие элементы управления (см. 1.4.2.4) имеют специальные символы.  Схема на рис. 1.3 реализует оператор18

Рис. 1.3: Схема обозначения для распространенных вентилей

1.5.1.4 Квантовые Языки Программирования
Возможным способом обобщения квантовых схем для произвольных размеров входных данных является использование классического компьютера с неограниченной памятью (например, TM) для генерации схем в зависимости от размера входных данных. Таким образом, вместо прямой спецификации отдельной схемы в терминах проводов и вентилей, с помощью классической программы задается целый класс квантовых схем.
Языки квантового программирования (QPLs) еще больше расширяют эту абстракцию, напрямую используя квантовый компьютер Mq в качестве оракула (см. 1.3.2.4) для классической машины Mc. Это не только устраняет необходимость в описании промежуточной схемы, но и позволяет вычислениям зависеть от предыдущих измерений, что позволяет квантовым программам быть более эффективными. описывать полные алгоритмы, а не просто унитарные преобразования.
18 Обратите внимание, что порядок следования операторов обратный.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 38
1.5.2 Квантовые алгоритмы
1.5.2.1 Классическая и квантовая вычислимость
Если мы рассматриваем конечный квантовый компьютер с вентилем Тоффоли (см. 1.4.2.4) в качестве единственной доступной команды, то любое преобразование состояния машины должно иметь вид
|;; = |i; ;|g(i); = |;'; при g : Bn ; Bn (1.111)
Поскольку логический элемент Тоффоли универсален для обратимой булевой логики, любая биективная двоичная функция g может быть непосредственно реализована на квантовом компьютере.
Общая двоичная функция f на Bn может быть реализована произвольным унитарным оператором F, который удовлетворяет условию F |i, 0; = |i, f (i);.
Таким образом, любая функция f, вычисляемая на (конечной) классической машине, также может быть реализована на квантовом компьютере с универсальным набором логических элементов. Более того, К. Х. Беннет показал, что обратимая реализация f может быть реализована с максимальными затратами O(2) по времени и O (;n) по пространственной сложности [7].
С другой стороны, общее квантовое состояние n-кубита состоит из максимально 2n базисных векторов с ненулевой амплитудой и, следовательно, могут быть описаны массивом из 2n комплексных чисел. Кроме того, любой квантовый элемент m-кубита может быть описан комплексной матрицей 2n ; 2n с элементами uij = ;i|U |j;.
Путем кодирования комплексных амплитуд в виде пары двоичных чисел с плавающей запятой числа классический компьютер может моделировать любой унитарный оператор с произвольной точностью.19 Как правило, для этого требуются накладные расходы в размере O(en) как по времени, так и по пространственной сложности. Из-за стохастической природы квантовых измерений эмулирующему компьютеру также потребуется источник истинной случайности (например, вероятностная машина Тьюринга).
Таким образом, классические и квантовые компьютеры эквивалентны в вычислительном отношении, но, хотя можно эффективно смоделировать классический компьютер на квантовом компьютере, противоположный случай может привести к экспоненциальным накладным расходам. Следовательно, не расширяя нашего представления о вычислимости, для некоторых задач квантовые алгоритмы могут обеспечить более эффективные решения, чем классические реализации.
1.5.2.2 Алгоритм Дойча
В 1985 году Дойч предложил вероятностный алгоритм [24], который для некоторой функции оракула g : B ; B позволяет вычислить g(0) ; g(1) с вероятностью 1/2, используя только 1 применение G:
19линейность унитарных преобразований гарантирует, что небольшие ошибки не будут увеличиваться.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 39
Пусть G : |x, y; ; |x, y ;  g(x); - 2-кубитный оракул-оператор, реализующий логическую функцию оракула g : B ; B.
1. Подготовить пустой начальное состояние |;0; = |0;х|0;y.
2. Распространяется H(х)
3. Примените оператор оракула G, дающий
4. Примените H(x ; y), в результате чего
5. Измерьте значения x и y.
Так  (1.114) может быть упрощено до
регистр x будет содержать значение g(0);g(1) всякий раз, когда значение 1 измеряется
в y, что происходит в 50% случаев.
Хотя, строго говоря, это не обеспечивает никакого ускорения по сравнению с классическим случаем, если принять во внимание, что для реального измерения g(0) ; g(1) требуется в среднем две попытки, алгоритм Дойча стал первым доказательством того, что квантовые компьютеры способны выполнять вычисления способами, которые невозможны на классическом компьютере.20
Как правило, для достижения какого-либо ускорения по сравнению с классическими алгоритмами необходимо необходимо использовать уникальные возможности квантовых вычислений, а именно
• Суперпозиция (шаг 2)
• Квантовый параллелизм (шаг 3)
• Интерференция (шаг 4)
20 Существует несколько улучшений и обобщений по сравнению с оригинальной версией
алгоритма Дойча [26, 20], один из которых — алгоритм Дойча-Йозса — описан
в разделе 1.5.2.6.
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 40
1.5.2.3 Суперпозиция
Ключевым элементом любого универсального языка программирования является условное ветвление. Любая классическая программа (см. 1.3.3) может быть смоделирована в виде дерева решений, где каждый узел соответствует двоичному состоянию sn и ведет к одному или нескольким последующим состояниям s(i)n+1. В детерминированной машине Тьюринга (TM) возможен только один из этих переходов sn ; s(k)n+1, поэтому вычислительный путь ;s0, s1, ... sn;предопределен.
В вероятностном TM (см. 1.3.2.5) переходы характеризуются вероятностями pi с ;i pi = 1, и одно из возможных последующих состояний s(i)n+1 выбирается соответственно случайным образом.
Поскольку базисные векторы |i; непосредственно соответствуют классическим бинарным состояниям, мы могли бы интерпретировать унитарное преобразование
U : |s; ; ;s'uss' |s';при s, s' ; Bn и uss' ; C (1.116)
в качестве вероятностного перехода формируют классическое состояние s в последующие состояния s' с вероятностями перехода ps' = |uss' |2, но если мы не проведем измерение, результирующее состояние машины остается в суперпозиции всех возможных классических состояний-преемников
Таким образом, с классической точки зрения, мы можем рассматривать унитарный оператор, который преобразует собственное состояние в суперпозицию из n собственных состояний с ненулевыми амплитудами, как 1–n-разветвительную операцию, которая позволяет квантовому компьютеру следовать нескольким классическим вычислительным путям одновременно.
Преобразование Адамара - большинство неклассических алгоритмов используют преимущества этой функции, приводя регистр к равномерной (чётной, даже, ивен) суперпозиции всех базовых состояний, которые служат пространством поиска. В алгоритме Дойча это достигается применением логического элемента Адамара к первому кубитному регистру.
Логический элемент H может быть обобщен на n-кубитные регистры путем применения H к каждому отдельному кубиту. Результирующий унитарный оператор называется преобразованием Адамара и определяется как:
где x · y = ;i xiyi обозначает двоичное внутреннее произведение. Преобразованный базис
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 41
иногда называют дуальным базисом.
Классически преобразование Адамара |;; = |0; можно рассматривать как бинарное дерево решений с вероятностью переворота каждого бита 50%. Для n-кубитного регистра это приводит к 2n классическим вычислительным путям, которые выполняются одновременно, что приводит к суперпозиции 2n собственных векторов.
1.5.2.4 Квантовый параллелизм
Если мы ограничим унитарные преобразования базисными перестановками (т.е. операторами
вида |i; ; |;i; ), то классическое дерево решений вырождается в список и в итоге мы получаем функциональность классического детерминированного обратимого компьютера, т.е. для любой биективной двоичной функции f: Bn ; Bn существует соответствующий унитарный оператор
F : |s; ; |f (s); при  s ; Bn. (1.120)
Ограничение на биективные функции не является таким строгим, как кажется, поскольку для  любой общей двоичной функции g : Bn ; Bm соответствующая квантовая функция
G : |s, 0; ; |s, g(s); при s ; Bn (1.121)
может быть построена, которая реализует g с максимальными затратами O(;n) в пространстве и O(2) во времени.
Однако, если мы используем квантовую функцию для суперпозиции собственных состояний, то же классическое вычисление выполняется по всем бит-строкам одновременно.
В классических терминах это можно описать как векторную операцию SIMD (single instruction, multiple data одна инструкция , множество данных), в квантовых терминах эта функция называется квантовым параллелизмом.
В алгоритмах Дойча квантовый параллелизм используется путем применения G
на суперпозицию |;1; = (|00; + |10;)/;2.
1.5.2.5 Интерференция
В то время как суперпозиции и квантовый параллелизм позволяют нам проводить экспоненциально большое количество классических параллельных вычислений единственным способом считывания каких-либо результатов является выполнение измерения, при котором отбрасываются все наложенные (суперпозиции) собственные состояния, кроме одного. Поскольку не имеет никакого значения, определяется ли вычислительный путь во время вычисления (как в случае с вероятностной ТМ) или апостериорно (путем квантового измерения),
глава 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 42
использование квантовых компьютеров не дало бы никаких преимуществ по сравнению с вероятностными классическими компьютерами.
Однако квантовые состояния - это не просто распределение вероятностей двоичных значений, но комплексные векторы, т. е. каждое базисное состояние в суперпозиции характеризуется не реальной вероятностью, а комплексной амплитудой, поэтому
опишут разные состояния, даже если они имеют одинаковый спектр вероятностей.
Таким образом, в то время как в вероятностном TM вероятности двух различных вычислительных путей, ведущих к одному и тому же конечному состоянию s, просто складываются, в квантовом компьютере это не обязательно так, поскольку обычно
|; + ;|2; |;|2 + |;|2 для ;, ; ; C. (1.124)
Чтобы проиллюстрировать эту концепцию, рассмотрим три состояния
|;1; = |0;, |;2; = |1; и |;3; = 1;2(|0; + |1;). (1.125)
Если мы применим Адамара-преобразование  Н в базисные состояния |;1; и |;2;, то получим
Поскольку |;'1; и |;'2; имеют одинаковые распределения вероятностей и |;3; является просто суперпозицией |;1; и |;2;, классически мы будем считать, что |;; 3; также покажет тот же спектр вероятностей, однако
таким образом, в случае |0; вероятности суммируются, в то время как в случае |1; комплексные амплитуды имели противоположные знаки, что приводило к частичной вероятности, равной 0. Это явление называется положительной или отрицательной интерференцией.
Таким образом, хотя вычислительные пути в вероятностной ТМ независимы, интерференция позволяет вычислениям в суперпозиционных состояниях взаимодействовать, и именно это взаимодействие позволяет квантовому компьютеру решать определенные задачи более эффективно, чем классические компьютеры. Таким образом, основным принципом разработки любого квантового алгоритма является использование интерференции для увеличения вероятности “интересных” базовых состояний при одновременном снижении вероятности “неинтересных” состояний, чтобы повысить вероятность того, что при измерении будет выбрано одно из первых (бывших).

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 43
Базисные преобразования Поскольку любой унитарный оператор U также может рассматриваться как базисное преобразование, вышеуказанную задачу также можно переформулировать как поиск подходящей наблюдаемой для измерения, тем самым эффективно заменив стандартную наблюдаемую N эрмитовым оператором
Это представление особенно полезно, если для задачи представляют интерес глобальные свойства классических функций,  такие как периодичность.
В алгоритмах Дойча окончательное измерение выполняется в дуальном (двух режимах) базисе (1.119), который позволяет получить значение g(0) ; g(1) за одно измерение.
1.5.2.6 Алгоритм Дойча-Йожса
Алгоритм Дойча-Йозса [26] является улучшенной и обобщенной версией оригинального алгоритма, описанного в (см. 1.5.2.2). При n = 1 он дает детерминированное решение задачи Дойча:
Пусть F : |x, y; ; |x, y ; f (x); - кубитный оператор- оракул, реализующий логическую функцию f : Bn ; B. Далее предположим , что мы знаем, что f является либо константой ((;x)f (x) = b, где b ; B) или сбалансированный (; f (x) = 2n;1). В классическом случае для определения того, какая из возможностей применима, потребовалось бы 2n;1 + 1 оценок f. Следующий квантовый алгоритм может решить эту проблему принятия решения с помощью одного применения F :
1. Подготовить исходное состояние |;0; = |0;х|1;у.
2. Применить Н( X ; Y), чтобы настроить поиск пространства суперпозиции
3. Применить оператор оракула, обеспечивающий квантовый параллелизм
4. Примените H(x), что приведет к возникновению интерференции
ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ 44
5. Измерить x.
Вероятность измерения 0 в x равна |c0|2, где
Если f постоянно, то c0 = ±1, если f сбалансировано, слагаемые уравновешиваются (отменяются, кансел аут) и c0 = 0, так что ;(x)|;3 > = 0 ; f  постоянно.
Глава 2
Структурированное Квантовое Программирование
2.1 Введение
2.1.1 Мотивация
Поскольку квантовые вычисления находятся на пути к тому, чтобы стать устоявшейся дисциплиной в области компьютерных наук, много усилий вкладывается в разработку новых
квантовых алгоритмов. Обычно эти исследования имеют мало общего с экспериментальной работой на квантовых компьютерах и редко привязана к конкретному оборудованию, но вместо этого используется абстрактное понятие квантового компьютера с кубитами, регистрами и небольшим набором подходящих элементарных операций [3], что позволяет сконцентрироваться на текущей задаче.
Язык программирования, который по замыслу объединяет эти абстракции, должен быть полезным инструментом в ситуациях, когда гораздо более общий физический формализм алгебры Гильбертова пространства становится излишне сложным.
Возможность сформулировать и смоделировать алгоритм на  языка программирования также должен упростить оптимизацию реализации с учетом различных квантовых архитектур и позволить более точно оценивать время и  сложность памяти.
2.1.2 Языки квантового программирования
С точки зрения разработки программного обеспечения, мы можем рассматривать алгебраический формализм как язык специфичный, поскольку математическое описание квантового алгоритма по своей сути является декларативным и не предоставляет средств для
однозначного разбиения на элементарные операции для данного квантового оборудования.
45
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 46
С другой стороны, низкоуровневые формализмы, такие как, например, квантовые схемы [25], обычно ограничены конкретными задачами, такими как описание унитарных преобразований, и, следовательно, им не хватает общности (главности) для выражения всех аспектов неклассических алгоритмов.
Таким образом, назначение языков программирования двоякое, поскольку они позволяют выражать семантику вычислений абстрактным образом, а также автоматически генерировать последовательность элементарных операций для управления вычислительным устройством. Любой полезный язык квантового программирования (QPL) следовательно, он должен быть
• конструктивным
• аппаратно независимым
• обеспечивать произвольные уровни абстракции
• интегрировать неклассические функции на семантическом уровне
Хотя первые три требования в равной степени применимы к классическим и квантовым языкам программирования, QPL также должны отражать особенности квантовых вычислений, такие как, например,
• обратимость унитарных операций
• нелокальность кубитов
• ненаблюдаемость состояний
• разрушительный характер измерений
• отсутствие операции стирания
на уровне проектирования и, следовательно, должны обеспечить средства для принятия прогресса этих свойств (например, позволяя запускать код “в обратном порядке”).1
2.1.3 Классификация языков программирования
В традиционной CS (информатике, компьютерной науке, компьютер сайенс) языки программирования можно разделить на логические (например, Prolog), функциональные (например, LISP) или императивные (например, Assembler, Fortran, Pascal, C), причем последние наиболее широко используются для описания алгоритмов, а также для фактической реализации реальных программ в мире.
1классические языки с дополнительными квантовыми директивами (например, моделирование на C++ или API драйверов устройств), таким образом, не считаются QPL, поскольку в общем случае они не поддерживают эти неклассические концепции [61].
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ47
2.1.3.1 Императивные языки программирования
Императивное программирование основано на концепции состояния вычислений и командах, изменяющих это состояние [1]. Состояние является абстракцией для изменяемого хранилища базовой машинной модели и семантически выражается в терминах символьных переменных различных типов данных и текущего состояния управления (счетчик команд, указатель стека и т.д.), которые могут иметь или не иметь прямого представления в языке.
Во время своего выполнения программа генерирует последовательность состояний.
Переход от одного состояния к следующему определяется с помощью
• команд назначения, которые изменяют состояние переменных, и
• команд упорядочивания, которые изменяют состояние управления.
Прямое соответствие между вероятностями состояний и программными инструкциями приводит к концепции потока управления, т.е. вычисление может быть охарактеризовано фактической последовательностью команд. Это позволяет отслеживать императивную программу, отслеживая текущее состояние управления, и вводит понятие локальности выполнения.
Примерами императивных языков программирования являются язык ассемблер или БЕЙСИК. Концепции императивного программирования отражены в гибридной квантовой архитектуре (2.2.3) и концепции символьных квантовых регистров (2.4.1).
2.1.3.2 Процедурные языки программирования
Императивное программирование в сочетании с параметризованными подпрограммами ( процедурами, функциями) называется процедурным программированием. Наличие подпрограмм позволяет
• Функциональная абстракция: код с аналогичной или идентичной функциональностью может быть обобщен на многократно используемые параметризованные процедуры.
• Иерархическая структура программы: подпрограммы могут содержать вызовы других подпрограмм, что обеспечивает произвольные уровни абстракции и поддерживает нисходящий подход к разработке программного обеспечения.
• Рекурсия: подпрограммы также могут содержать вызовы для самих себя, что обеспечивает элегантную и эффективную реализацию сложных структур управления и напрямую поддерживает классический подход “разделяй и властвуй” при разработке программного обеспечения.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 48
• Частные области: подпрограммы предоставляют свое собственное пространство имен, которое уменьшает взаимозависимости внутри программы.
• Локальные переменные: Локальные пространства имен также позволяют использовать временные переменные с ограниченным сроком службы, что приводит к более эффективному использованию доступного хранилища и позволяет скрыть детали реализации от интерфейса вызова процедуры.
Примерами процедурных языков программирования являются Fortran и C.  Концепции процедурного программирования отражены в квантовых типах данных (2.4.1.3, 2.5.2.2), квантовых субрутинах (2.5.1) и управлении пространством с нуля (скретч) (2.5.3.5) [47].
2.1.3.3 Языки структурированного программирования
Как упоминалось в разделе 2.1.3.1, императивные программы состоят из команд назначения и
последовательности выполнения. Простой способ обеспечить управление потоком - это команда goto, которая явно передает управление помеченной команде, которая должна быть выполнена следующей.
label (метка) goto ;
if condition then goto label ;
Этот подход проблематичен, поскольку подразумевает плоскую структуру управления, в которой любая помеченная команда может быть переведена из любого места программы (или, в случае процедурных языков - текущая подпрограмма (субрутина)). Это приводит к
тому, что большие программы становятся нечитаемыми (“спагетти-код”).
В 1966 году Коррадо Бом и Джузеппе Якопини показали [11], что команда goto может быть заменена вложением (гнездованием, нестед)и суммированием (упорядочиванием) (стекинг, использование стека) трех основных управляющих инструкций
• последовательность (блочные инструкции),
• выбор (инструкции if) и
• итерация (условные циклы)
с четко определенными точками входа и выхода. Этот подход, называемый структурированным программированием [27, 23], подразумевает строго иерархическую структуру управления, которая это не только упрощает понимание программ, но и предоставляет полезную метаинформацию для компилятора.
Примерами структурированных языков программирования являются Pascal и Modula, но практически любой процедурный язык поддерживает необходимые управляющие команды, даже если их исключительное использование не предусмотрено. Концепции структурированного программирования отражены в квантовых условиях (2.6.3), условных
операторах (2.6.1) и квантовых if-заявлениях (инструкциях)(2.6.2.1).
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ49
2.1.4 Цели
Функциональная абстракция и иерархическая структура управления, а также очень интуитивное представление о потоке управления, отсутствующее в чисто декларативных формулах, по- видимому, соответствует способу рассуждения большинства людей о вычислительных задачах. Это делает структурированное программирование мощным формализмом не только для решения реальных задач кодирования, но и для описания алгоритмов в целом (блок-схемы, псевдокод).
В оставшейся части этой главы мы покажем, как знакомые концепции классического структурированного программирования могут быть применены в области квантовых вычислений. Примером может служить язык программирования QCL [45, 49] чтобы проиллюстрировать принципы структурированного квантового программирования.
В таблице 2.1 представлен обзор элементов квантового языка вместе с
их классическими семантическими аналогами.
Классическая концепция квантовый аналог
классическая машинная модель гибридная квантовая архитектура
переменные квантовые регистры
назначение переменных элементарные элементы(гейты)
классические входные данные квантовые измерения
подпрограммы (субрутины) операторы
типы аргументов и возвращаемых данных квантовые типы данных
локальные переменные промежуточные (скретч) регистры
динамическое памяти управление промежуточным (скретч) пространством
логические выражения квантовые условия
условное выполнение условные операторы
отбор квантовое если- инструкции
цикл по условию квантовое разветвление

Таблица 2.1: Концепции классического и квантового программирования
2.1.5 Состояние Исскуства
2.1.5.1 Программное обеспечение и симуляторы квантового вычисления
По мере того как в последние несколько лет рос общий интерес к квантовым вычислениям, росло и количество доступных симуляторов и вычислительных инструментов. Дж. Уоллес провел подробный обзор [61] 21 квантового компьютерного симулятора. Более свежий список из 36 проектов можно найти в Интернете [62].

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 50
Доступное программное обеспечение можно условно разделить на следующие категории
• библиотеки классов для существующих классических языков
• пакеты для систем компьютерной алгебры
• симуляторы квантовых схем
• моделирование специфического квантового оборудования
• моделирование конкретных алгоритмов
• другие методы квантового моделирования (QTM, квантовые байесовские сети и т.д.)
2.1.5.2 Языки квантового программирования
Помимо QCL [49], было предпринято как минимум 3 попытки разработать язык квантового
программирования
• 1996 Q-gol Грега Бейкера [2]
• 2000 qGCL Паоло Зулиани [63]
• 2002 Quantum C Language от Стивена Блаха [10]
Из них наиболее развитым проектом, вероятно, является qGCL от Зулиани. В своей диссертации [63] Зулиани предлагает абстрактный формализм со строгой семантикой и связанным с ним уточненным математическим анализом, который позволяет создавать программы и строго проверять их корректность. Однако интерпретатор или компилятор отсутствуют.
2.2 Вычислительная модель квантового программирования
В этом разделе мы покажем, почему квантовых схем и конечных программ недостаточно для универсальных квантовых вычислений, и представим гибридную квантовую архитектуру как вычислительную модель квантового программирования.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ51
2.2.1 Квантовые схемы
2.2.1.1 Детерминированные последовательные алгоритмы
В своей простейшей форме квантовый алгоритм P просто состоит из унитарного преобразования и последующего измерения результирующего состояния |;'; в вычислительном базисе B. Если |;'; = |y; является базисным состоянием, то результат измерения предопределен, и алгоритм P  детерминированный.  Примером для этого класса является алгоритм Дойча-Йожса, представленный в разделе 1.5.2.6.
Для задач фиксированного размера2 детерминированные последовательные алгоритмы могут быть полностью описаны как квантовые схемы (см. 1.5.1.3) или, что эквивалентно, как
последовательности (см. 1.3.3.1) для квантового компьютера M. Алгоритм Дойча- Йожца, например, может быть реализован с помощью следующих команд (при условии, что начальное состояние равно |0, 0;).
;DJ = X(y) ; H(x) ; H(y) ; F (x, y) ; H(x) ; ;(x) (2.1)
2.2.1.2 Общие вероятностные алгоритмы
Для решения многих вычислительных задач эффективные квантовые реализации имеют форму вероятностных алгоритмов. На рис. 2.1 показана основная схема  вероятностного квантового алгоритма с одним циклом вычисления.
Примером этого простого случая является алгоритм Дойча, представленный в 1.5.2.2. Более сложные квантовые алгоритмы, такие как, например, алгоритм Шора для разложения на квантовые множители [54, 30], могут также включать классические случайные числа, частичные измерения, вложенные циклы оценки и множественные условия завершения; таким образом, фактические квантовые операции встроены в классическую структуру управления
Поскольку квантовые схемы являются сетями прямой связи (прямой подачи) и не имеют внутреннего управления потоком, они не могут дать полного описания вероятностных алгоритмов. Даже в простом случае, показанном на рис. 2.1, решение о том, является ли измеренное значение “хорошим”, т.е. обеспечивает решение вычислительной задачи, выходит за рамки формализма и требует дополнительных предположений.
2.2.2 Конечные квантовые программы
В разделе 1.3.3.2 мы представили концепцию конечных программ, которые определяют конечные автомата для определения потока управления классической машиной M. Та же концепция также может быть использована для описания вероятностных квантовых алгоритмов.
2 Это относится не только к количеству классических входных битов, но , в случае “черного бокса” алгоритмов ,  также количество кубит-параметров для любых оракула-операторов.

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

Для квантового компьютера
Алгоритм Дойча (см. 1.5.2.2) может быть реализован, например, с помощью следующей
конечной программы:
1: сброс, затем 2
2: H (q0), затем 3
3: G (q0,q1), затем 4
4: H(q0), затем 5
5: H (q1), затем 6
6: если ;(q1), то 7, иначе 1
7: ; (q0), затем 0

Как правило, для задач фиксированного размера любой вероятностный квантовый алгоритм может быть реализован в виде конечной программы для квантового компьютера с
универсальным набором логических элементов.3
3 Это возможно, поскольку для задач фиксированного размера всегда существует верхняя граница количества кубитов, необходимых для реализации классической структуры управления.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ53
2.2.2.1 Машины с неограниченной памятью
В классических вычислениях машина M универсальна, если для любой частичной рекурсивной функции f ; P существует конечное ;, которое реализует f на M (см. 1.3.3.2). Поскольку не существует верхней границы размера входных данных, любая классическая универсальная машина должна обладать неограниченной памятью.
Определение 28 Пусть O ; SU (2) - перечислимый набор одиночных кубитных элементов, который имеет плотность в SU (2). Квантовый компьютер
UGM = (B*, {U (q) | U ; O} {CNot(q, p)}, {;(q)}, n ; |n;, ;[N ]) (2.3)
называется машиной с неограниченными воротами (гейтс).
Поскольку SU (2) и CNot являются универсальным набором логических элементов (см. 1.4.2.6), любой унитарный оператор с n кубитами может быть реализован в виде последовательности для UGM. Однако UGM не является универсальным компьютером в классическом смысле. В то время как это могло бы кажущаяся на первый взгляд удивительной неуниверсальность UGM (и любого другого квантового компьютера, работающего с помощью конечных логических элементов) становится очевидной, если мы рассмотрим следующую простую задачу решения:
Четность битовой строки s ; B* является нечетным, если ;i si = 1, и четным, если ;i si = 0. Если известно, что длина s не превышает n бит, то четность s может быть вычислена с помощью квантовой схемы из n кубитов с использованием n - 1 CNot;логических элементов. На рис. 2.2 показана схема для n = 4.s0

Рисунок 2.2: Проверка четности последовательности битов длиной 4

Предположим, что ; - это конечная квантовая программа для UGM, вычисляющая четность произвольных битовых строк. Если ; содержит n = |;| команд, то — независимо от того, насколько сложным окажется вычисление для любого заданного входного сигнала — передаточная функция ;; может привести только к комбинации не более чем из n различных элементов управления или измерений. Поскольку любая команда памяти или тестирования воздействует не более чем на 2 кубита, ;; может воздействовать только на 2n-кубитный регистр UGM. Следовательно, только 2n кубитов могут внести свой вклад в результат, и существует по меньшей мере 22n пар битовых строк a, b ; B2n+1, которые отличаются одним битом и, следовательно, имеют противоположные соотношения, для которых F (;, UGM)(a) = F (;, UGM)(b).

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 54
2.2.2.2 Универсальные квантовые компьютеры
Приведенные выше результаты показывают, что для того, чтобы конечные программы были универсальными, квантовый компьютер M = (H, O, T, ;, ;) должен обеспечивать по крайней мере один глобальный оператор U ; O, который действует нетривиально на l2 подпространствах H.4
Пусть H = T = B* ; B* - Гильбертово пространство двойной бесконечной “ленты”
кубитов с нулевыми конечными состояниями, т.е.
T = {|0;;; ; |;; ; |0;;; ; |;; ; B;n, n ; N} (2.4)
и B - вычислительный базис T с единичными кубитными регистрами l, h и r
Теперь мы можем определить унитарный оператор сдвига S на T как
Классическая квантовая машина Тьюринга Рассмотрим следующий квантовый компьютер
Очевидно, что M не предоставляет полного набора унитарных операторов, поскольку каждая из трех команд памяти работает в пределах B, поэтому суперпозиция не может быть создана.



 Однако M - универсальный компьютер; фактически M - это компьютер Тьюринга в камуфляже (см. 1.3.2.2). В таблице 2.2 приведены гомоморфизмы для преобразования конечных программ из M в TM.
Из-за этой эквивалентности мы называем M классической квантовой машиной
Тьюринга или CQTM.
Полуклассическая квантовая машина Тьюринга CQTM может быть расширена путем добавления универсального набора унитарных преобразований. Из-за наличия оператора сдвига эти операции могут быть локализованы и могут быть ограничены небольшим количеством фиксированных положений кубита.5
4 Примером может служить пошаговый оператор QTM (см. 1.5.1.2).
5 Это важная особенность и несколько предлагаемых аппаратных архитектур на основе ионных ловушек.- технологии квантовых компьютеров используют это преимущество [37, 53].
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ55
TM CQTM
L (слева) S
R (справа) S†
T (тест) ;(h)
S (установить) 1: если ;(h), то 0, иначе 2
2: X(h), тогда 0
E (стереть) 1: если ;(h), то 2, тогда 0
2: X(h), тогда 0
1: если T, то 2, тогда 3 X(h)
2: E, затем 0
3: S, затем 0
Таблица 2.2: Эквивалентные команды TM и CQTM
Определение 29 Квантовый компьютер
SQTM = (T , O, {;(h)}, s ; |0;|s;, ;[N ]) (2.8)
с помощью команд памяти
O = {H(h), T (h), CNot(h, l), CNot(h, r), S, S†} (2.9)
называется полуклассической (или простой) квантовой машиной Тьюринга.
Поскольку X = HT4H, SQTM способен эмулировать CQTM и также является универсальным компьютером.
Пусть qk обозначает k-й кубит относительно h, а U - произвольный единичный кубитный оператор U ; SU (2). Поскольку H и T универсальны для операций с одним кубитом (см. 1.4.2.6), существует композиция U ' = H Пi TniH
которая приближает U к произвольной точности. 6 Регистровый оператор U (qk) может быть затем реализован с помощью
Более того, поскольку
может быть реализована любая перестановка кубитов, а управление-не может быть применено к произвольным регистрам. Это означает, что SQTM может эмулировать UGM
и позволяет реализовывать произвольные унитарные преобразования.
6 Обратите внимание, что H является обратимым к самому себе, поэтому разложение U ' на множители не содержит высших степеней H, поскольку Hk +2 = Hk. По тем же соображениям, что ni < 8, что и Tk+8 = Tk.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 56
Общие квантовые алгоритмы Неклассические алгоритмы обычно требуют создания квантовых схем в зависимости от классических параметров, таких как размер задачи. В самом общем случае это описание дается рекурсивной функцией (см. 1.3.1.1), поэтому фактическая последовательность элементов может быть определена с помощью конечной программы на универсальном компьютере.
Чтобы продемонстрировать, что SQTM способен выполнять общие квантовые алгоритмы, нам нужно показать, как ленточные кубиты могут быть обработаны в результате классического вычисления. Возможный способ достичь этого - рассматривать все четные ленточные кубиты как классические биты и использовать их для эмуляции TM, в то время как все нечетные кубиты используются для выполнения реальных квантовых вычислений (чередование памяти).
В приведенном ниже примере показано, как применить элемент Адамара к k-му нечетному кубиту (q2k+1), позиция которого k закодирована унарно (см. 1.3.2.2), в четных
кубитах, которые используются классически.
1: если ;(h), то 2, иначе 4 достигнута конечная отметка (0)?
2: S, затем 3 переходим к следующему классическому биту
3: S, затем 1 и повторяем
4: S, затем 5 переходим к следующему кубиту
5: H(h), затем 6 примените затвор Адамара
6: S†, затем 7 возвращаемся к конечной отметке
7: S†, затем 8 возвращаемся к предыдущей
8: S†, затем 9-й классический бит
9: если ;(h), то 7, иначе 10 - начальная отметка (0) достигнута?
10: S, затем 11 переместите головку в исходное положение
11: S, затем в 0 положение

2.2.3 Гибридная архитектура
В разделе 2.2.2.1 мы показали, что квантовые компьютеры на основе гейтов не универсальны.
С другой стороны, глобальные унитарные операции, такие как оператор сдвига (см. 2.2.2.2), не могут быть выражены в рамках схемотехнической модели, не могут быть одинаково применимы к машинам с неограниченной и ограниченной памятью и не могут быть одинаково доступны на разных архитектурах квантового оборудования.
Чтобы преодолеть вышеуказанные ограничения, квантовое программирование использует классический универсальный язык для определения фактической последовательности элементарных команд для квантового компьютера, поэтому программа предназначена для запуска не на самом квантовом компьютере, а на (вероятностном) классическом компьютере, который, в свою очередь, управляет квантовым компьютером и обрабатывает результаты измерений.
С точки зрения пользователя, квантовая программа ведет себя точно так же, как любая другая классическая программа, в том смысле, что она принимает классические входные данные, такие как параметры запуска или интерактивные данные, и выдает классические выходные данные.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ

57.
квантовая программа
классический ввод квантовые операции
классический вывод Значения измерения
 бинарное состояние программы      состояние квантовой машины.
Рисунок 2.3: Гибридная квантовая архитектура.
Состояние управляющего компьютера (т.е. значения переменных, стек выполнения, а также отображение квантовых регистров) называется состоянием программы . Сам по себе квантовый компьютер не требует какой-либо управляющей логики, поэтому его вычислительное состояние может быть полностью описано общим квантовым состоянием
|;; его кубитов (машинным состоянием).
2.2.3.1 Модель машины
Формально описанную выше архитектуру можно описать как универсальный компьютер с квантовым оракулом (см. 1.3.2.4).:
Пусть Mc = (S, Oc, Tc, ;, ;) - универсальный классический компьютер с кодировкой ; : S ; N*, а Mq = (H, Oq, Tq, |0;, ;[N ]) - квантовый компьютер с неограниченной памятью H = B*, универсальный набор конечных элементов
и измерения на одном кубите
Tq = {;(qi)} = {;0, ;1, . . .}. (2.14)
Поскольку число кубитов в Mq не ограничено, Oc и Tc являются бесконечными множествами. Поскольку любые Ui ; Oc и µi ; Tc работают только с конечным числом кубитов, нам нужен метод, позволяющий Mc обращаться к произвольным командам Mq. Используя кодировку
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 58
мы определяем команды оракула
Используя U и M в качестве интерфейса, мы теперь можем определить гибридную машину M =Mc ./ Mq как
Рисунок 2.4: Классический компьютер с квантовым оракулом

2.2.3.2 Квантовый оракул
Для нашей формальной модели машины мы предположили, что Mq обладает неограниченной памятью. Однако ограничение на конечные вентили и измерения с одним кубитом также позволяет использовать квантовые оракулы с конечным числом кубитов.
Предполагается, что концепция квантового программирования не зависит от аппаратного обеспечения и применима к любой квантовой архитектуре, основанной на кубитах, поэтому мы не будем использовать конкретный набор элементарных элементов, если соблюдены следующие требования:
• Набор элементов является универсальным.
• Каждый элемент управления может быть в равной степени применен к произвольным кубитам.
• Для любого несамообратимого элемента управления U также доступен элемент управления U†.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 59
Элементарные вентили могут принимать любое количество классических параметров и могут быть ограничены или не ограничены в количестве кубитов, с которыми они работают.
Некоторые концепции структурированного квантового программирования требуют, чтобы определенные операторы были доступны либо в виде элементарных элементов, либо в виде определяемых пользователем операторов, т.е. процедурных комбинаций элементов, которые могут быть определены в самом языке программирования. Эти операторы являются
• операция разветвления, т.е. произвольный унитарный оператор, который соответствует
условию
Разветвление обычно реализуется как |a, b; ; |a, a ; b; с использованием CNot-gates
и требуется для прозрачного использования локальных скретч-регистров (см. 2.5.3.5).
• элемент Не (или X-) и элемент неуправляемый Cn[X] с произвольным количеством управляющих кубитов. При реализации Cn[X] могут использоваться кубиты с нуля. X и Cn[X] требуются для квантовых условий (см. 2.6.3) и квантовой инструкции if (см. 2.6.2.1).
2.3 Структурированное программирование
Поскольку вычислительная модель QPLs представляет собой классический компьютер с квантовым оракулом, любой QPL также является универсальным классическим языком программирования. В этом разделе мы кратко рассмотрим ключевые элементы классических
языков структурированного программирования.
2.3.1 Структура программы
Структурированная программа - это последовательность (блок) инструкций и определений,
которые обрабатываются сверху вниз и могут содержать сами блоки (управляющие инструкции, определения подпрограмм (субрутин)).
2.3.1.1 Инструкции
Инструкции варьируются от простых команд через вызовы подпрограмм до вложенных
управляющих инструкций и выполняются при их обнаружении.
qcl> if random()>=0.5 { выводится "red"; } else { выводится "black"; }
: red
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 60
2.3.1.2 Определения
Определения не выполняются, но привязывают значение (определение переменной или константы) или блок кода (определение подпрограммы) к символу (идентификатору).
qcl> int counter=5;
qcl> int fac(int n) { если n<=0 {возвращает 1;} else {возвращает n*fac(n-1);} }
Каждому символу соответствует свой тип, который может быть либо типом данных, либо типом подпрограммы.
2.3.1.3 Выражения
Операторы и вызовы подпрограмм могут принимать аргументы определенных типов данных.
Выражения могут состоять из литералов, переменных и констант, объединенных
операторами и вызовами функций.
qcl> вывести "5 из 10:",fac(10)/fac(5)^2,"комбинации".
: 5 из 10: 252 комбинации.
2.3.2 Выражения и переменные
В отличие от нетипизированных формализмов, таких как конечные программы или схемы, в языках программирования выражение обычно ассоциируется с типом данных T . Значение
v ; T называется экземпляром T .
2.3.2.1 Атомарные выражения
Прямое символьное представление экземпляра v ; T называется литералом.
Тип описание Примеры
int целое число 1234, -1
real действительное число 3,14, -0,001
complex комплексное комплексное число (0,-1), (0.5, 0.866)
Таблица 2.3: Скалярные арифметические типы и литералы в QCL

Символ, который постоянно привязан к значению v ; T, называется ( символической) константой типа T . Символ, который может быть привязан к произвольным значениям T, называется переменной типа T .
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 61
2.3.2.2 Определения
Константы и переменные должны быть определены (т.е. объявлены и инициализированы)
прежде чем их можно будет использовать. Для обеспечения детерминированного поведения (см. 2.5.1.2) мы требуем, чтобы переменная была привязана к зависящему от типа значению по умолчанию, если начальное значение не указано.
qcl> const pi = 3,141592653589793238462643383279502884197;
qcl> const I = (0,1);
qcl> комплекс z=exp(I*pi/4);
qcl> строка msg="Привет, мир";
qcl> действительный вектор v[3]; // v инициализируется значением [0,0,0]
После определения константа или переменная становится видимой и может использоваться в любых последующих инструкциях и определениях до конца текущей подпрограммы (локальный символ) или до конца программы (глобальный символ).7
2.3.2.3 Составные выражения
Литералы, константы и переменные являются атомарными выражениями. Общие выражения
могут быть рекурсивно построены из атомарного выражения с помощью операторов и вызовов функций.
выражение ; атомарное выражение
; функция ( выражение , . . .)
; выражение с унарным оператором
; выражение с бинарным оператором expr
; n-арный оператор ( выражение , . . .)
Таким образом, общие выражения могут быть описаны как деревья с литералами, константами и переменными в качестве конечных узлов, а операторы и функции - в качестве внутренних узлов.
qcl> напечатать (3^2+4^2)* sin(log(z)/I);
: 17.6777

2.3.3 Подпрограммы (субрутины)
Подпрограмма S - это именованный блок (также называемый телом S), которому предшествует список описаний параметров. Тело подпрограммы может содержать вызовы
самой себя (рекурсию).
Классические процедурные языки обычно предоставляют два типа подпрограмм:
7 Существуют также языки с более детальными правилами определения области видимости, например, C++, где переменные могут быть локальными для блока.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 62
2.3.3.1 Процедуры
Процедура - это общая подпрограмма с произвольными зависимостями и побочными эффектами от состояния программы. Это означает, что, помимо своих объявленных аргументов, процедура может также зависеть от скрытых параметров, внешнего ввода и случайных событий. Более того, процедуры также могут изменять привязку глобальных переменных.
int cash;
процедура игры в рулетку(int bet) {
int n;
введите "выбрать число:",n;
cash=ставка наличными;
если n==этаж(37*случайный()) { cash=наличные+36*ставка; };
}

В процедурном квантовом программировании процедуры, являющиеся наиболее распространенными-некоторые подпрограммы (см. 2.5) используются для реализации классической структуры управления квантовых алгоритмов (см. 2.2.1.2).
2.3.3.2 Функции
Функция - это подпрограмма, которая возвращает значение v ; T определенного типа данных
T.
В процедурном квантовом программировании функции имеют строгую математическую семантику, что означает, что v должно исключительно и детерминированно зависеть от объявленных аргументов и что вычисление v не должно оказывать никакого побочного влияния на состояние программы.8 Это означает, что ни глобальные переменные, ни вызовы менее ограниченных типов подпрограмм не могут отображаться в теле  какой-либо функции.
int фибоначчи(int n) {
если n<2 {
возвращает 1;
} else {
возвращает значение фибоначчи(n-1)+значение фибоначчи(n-2);
}
}

2.3.4 Заявления, утверждения, инструкции
2.3.4.1 Назначение
Присваивание привязывает переменную (или элемент структуры данных, такой как массив) типа T к значению, определяемому выражением того же типа.
8 Многие классические процедурные языки (например, C) менее строги и рассматривают функции как процедуры с возвращаемым значением.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 63
qcl> z=z^ 2;
qcl> v=вектор(cos(pi/6),sin(pi/6),0);
qcl> v[2]=1;
qcl> вывести z,v;
: (0,1) [0.866025,0.5,1]
Присваиваний и атомарных выражений достаточно для реализации класса BF базовых функций (см. 1.3.1.1).
2.3.4.2 Управляющие инструкции
В соответствии с принципами структурированного программирования управление потоком осуществляется с помощью управляющих инструкций, которые выполняют блоки в соответствии со значением логического выражения и имеют четко определенные точки входа и выхода.
Двумя основными управляющими структурами являются инструкции if и (условные) циклы.9 Условные циклы различаются по тому, вычисляют ли они условие цикла до (while-цикл) или после (until-цикл) тела. В последнем случае тело является выполняется хотя бы один раз.
true
true
false
falsetrue false
if;оператор while;цикл until;тело цикла
condcond
if;блок else;тело блока cond
Рисунок 2.5: Основные структуры управления
Поскольку условные циклы позволяют реализовать ;0-рекурсию, язык программирования с циклами while, присваиваниями, атомарными выражениями и операторами “+” и “=” является универсальным (см. 1.3.1.1).
Большинство структурированных языков также предоставляют специальную инструкцию для подсчета циклов в известном диапазоне целых чисел (for-loops).
9 Концептуально отдельный блок (последовательность) можно рассматривать как третью управляющую структуру
[11].

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 64
qcl> for i=от a до b { тело(i); }; // for-цикл и эквивалент
qcl> i=a; while i<=b { тело(i); i=i+1; } // цикл while
Поскольку циклы подсчета позволяют реализовать примитивную рекурсию, языка программирования с циклами for, присваиваниями, атомарными выражениями и дополнениями достаточно для реализации класса PR примитивно-рекурсивных функций (см. 1.3.1.1).
Постановление Break Интсрукция break позволяет немедленно завершить самый внутренний цикл, независимо от состояния цикла. В то время как возможность выхода из цикла из любой точки тела может рассматриваться как противоречащий духу структурированного программирования, поскольку он ставит под угрозу концепцию четко
определенных точек выхода, большинство структурированных языков предоставляют оператор break (как и QCL).
2.3.4.3 Вызовы
Вызов процедуры S привязывает список аргументов к параметрам S и выполняет основную часть S. Привязки параметров, а также любые определения символов в S являются локальными.
2.3.4.4 Ввод и вывод
Любой язык программирования должен обеспечивать средства для взаимодействия с внешним миром. Это может быть реализовано с помощью назначенных входных и выходных переменных при запуске и завершении программы или во время выполнения с помощью команд ввода-вывода.
qcl> введите "длина в см:",x;
? длина в см: 192
qcl> вывести x,"см =",x/2,54,"дюймы";
: 192 см = 75,5906 дюймов
2.4 Элементарные квантовые операции
Как показано в разделе 2.2.3, вычислительная модель квантового программирования представляет собой универсальный компьютер с квантовым оракулом. Формально интерфейс между классическим интерфейсом и квантовым бэкэндом может быть описан командами оракула, которые позволяют применять элементарные элементы управления и выполнять измерения который может быть выполнены на произвольных целевых кубитах.
В этом разделе мы покажем, как этот интерфейс может быть представлен в  рамках императивного (см. раздел 2.1.3.1) языка программирования (императивного квантового программирования).10
10 Даже если классический язык предоставляет подпрограммы и структурированное управление потоками,
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 65
2.4.1 Квантовые регистры
В 1.4.1.3 мы определили квантовый регистр s как произвольную подсистему с конечномерным пространством состояний Hs и четко определенной вычислительной базой Bs. Мы также сделаем следующие предположения относительно квантового оракула Mq (см. 2.2.3.2):
• Пространство состояний H в Mq представляет собой совокупность идентичных кубитных подсистем, т.е. H = B;n или H = B*.
• Элементарные элементы управления и измерения работают с конечным числом
кубитов.11
• Все операции Mq могут быть в равной степени применены к произвольным кубитам.
• Кубиты Mq нумеруются в порядке возрастания, начиная с нуля.
Ограничение на кубиты подразумевает, что любой регистр s является либо одиночным кубитом (s = qi), либо композицией одиночных кубитных регистров (s = qk0 ; qk1 ; . . . ; qkn;1 )  или нуль регистр (s = o). Таким образом, квантовый компьютер с n-кубитами допускает
разных регистров.
Обозначение Мы пишем Rnk для обозначения набора k-кубитных регистров для n-кубитного
квантового компьютера. Поскольку Rnk эквивалентно множеству возможных k-перестановок
из n элементов,
алее мы определяем
Rk = ;;
n=1 Rn
k (набор регистров из k кубитов) (2.22)
Rn = ;n
k=0 Rn
k (набор регистров из n кубитов) (2.23)
R = ;;
n=1 Rn (набор общих регистров) (2.24)

результирующий QPL по-прежнему будет рассматриваться как обязательный, поскольку в нем отсутствует семантическая поддержка операторов и квантовых if-инструкций.
11 Для удобства QCL также поддерживает (глобальную) команду сброса (см. 1.4.3.3).
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 66
2.4.1.1 Языковое представление регистров
В рамках структурированного QPL квантовые регистры являются экземплярами квантового
типа данных (см. 2.4.1.3).12 Семантически n-кубитный регистр s ; Q представляет собой конечную последовательность взаимно отличающихся позиций кубитов s = (s0, s1 ... sn;1), поэтому s не обозначает физический тип данных. регистр сам по себе, но служит указателем (логический регистр) к реальной подсистеме n-кубитов qs0 ; . . . ; qsn-1 Mq (физического регистра).
Это различие позволяет обращаться с регистрами так же, как с любыми другими классическими типами данных, поэтому регистровые переменные можно объявлять, выводить на печать и объединять в выражения, как и классические переменные.13
qcl> qureg q[1]; // выделять отдельный кубитный регистр.
qcl> qureg p[4]; // выделяем 4-кубитный регистр
qcl> qureg qp = q & p; // объявляем комбинированный регистр qp
qcl> выводим q,p,qp; // выводим сопоставления регистров
: <0> <1,2,3,4> <0,1,2,3,4>
qcl> вывести p[0..2] & q; // регистры могут быть объединены в выражения
: <1,2,3,0>
Регистры - это формальный интерфейс между классическим интерфейсом и квантовым оракулом. Все операции с состоянием машины выполняются в квантовых регистрах в качестве операндов14 и ограничены соответствующими им подпространствами.
qcl> H(q); // применяем элемент Адамара для регистрации q
[5/32] 0.70711 |0,0> + 0.70711 |1,0>
qcl> Not(p); // инвертировать кубиты в регистре p
[5/32] 0.70711 |0,15> + 0.70711 |1,15>
qcl> измерить q; // регистр измерения q
[5/32] 1 |1,15>
2.4.1.2 Квантовая куча
Сопоставление между логическими регистрами и физическими кубитами обрабатывается прозрачно путем выделения и освобождения регистров из набора всех доступных кубитов, также называемые квантовой кучей [46].15 Квантовыми регистрами являются явно выделяемыми, когда определена переменная регистр, но также и неявно
12 Поскольку квантовые типы данных используются только для ограничения возможных операций с регистрами, математически любой квантовый тип данных Q обозначает один и тот же набор перестановок кубитов, т.е. Q = R.
13чЧтобы обеспечить статическое распределение кубитов, QCL не допускает назначения регистров, поэтому в QCL переменные регистров рассматриваются как символьные константы.
14 В зависимости от нашей точки зрения, можно считать, что регистры передаются по значению (логические регистры) или ссылке (физические регистры).
15 В классическом программировании область памяти, зарезервированная для динамических переменных, называется кучей.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 67
для управления пространством с нуля (скретч, начерченных, царапать) (см. 2.5.3.5) и для оценки квантовых условий (см. 2.6.3).
Точно так же, как классические переменные инициализируются значениями по умолчанию, зависящими от типа, вновь выделяемыми регистрами и, следовательно, вся свободная (т.е. нераспределенная) квантовая память должна быть пустой.
Определение 30 (Пустые регистры) Квантовый регистр e пуст, если состояние машины |;; имеет вид |;; = |0;e|;;e или, что эквивалентно, ;e = /0;;0/.
Кроме того, временные регистры должны быть очищены перед освобождением, которое, в случае переменных локального регистра, происходит, когда символ покидает область видимости. Это может быть достигнуто либо путем измерения, либо путем вычисления (см. 2.5.3.5).
При запуске все состояние компьютера пустое, таким образом, |;; = |0;.
qcl> dump;
: СОСТОЯНИЕ: выделено 0/32 кубита, 32/32 кубита свободны
1 |0>

Концепция квантовой кучи допускает две важные абстракции:
• Поскольку распределение регистров является прозрачным, нет необходимости указывать позиции кубитов и определять регистровые литералы. Это также оставляет место для оптимизации, зависящей от архитектуры.
• Поскольку выделенные и нераспределенные кубиты находятся в состоянии произведения, определение квантовых алгоритмов не зависит от общего количества кубитов.
2.4.1.3 Типы квантовых данных
Различные типы квантовых данных могут быть использованы для ограничения того, как унитарные операции могут влиять на квантовые регистры. Это делается не только для предотвращения ошибок программирования и повышения читаемости кода, но и для предоставления информации компилятору или интерпретатору, позволяющей более эффективно использовать- настройки и для обозначения аргументного, целевого и начального регистров квантовых функций (см. 2.5.3.3), чтобы обеспечить прозрачное управление начальным (скратч) пространством.
Общие регистры не накладывают никаких ограничений и могут использоваться в качестве аргументов для произвольных операторов.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 68
тип Ограничение
qureg none
quconst является инвариантным для всех субоператоров
quvoid значение quvoid должно быть пустым при вызове неинвертированного оператора
quscratch значение quscratch должно быть пустым до и после вызова
Таблица 2.4: Типы квантовых данных в QCL
Регистры констант должны быть инвариантны ко всем операторам. Они используются для
обозначения регистров аргументов квантовых функций (см. 2.5.3.3). Разрешающие регистры управляемых элементов (см. 1.4.2.5) и условных операторов (см. 2.6.1) также относятся к этому типу данных.
Определение 31 (Инвариантность регистров) Квантовый регистр c является инвариантным  к регистровому оператору U (s, c) если
где Uj - произвольные |s|-кубитные унитарные операторы, поэтому U можно записать как
Оператор U приведенной выше формы также называется оператором выбора (см. 2.5.2.2).
Целевые регистры используются для обозначения результирующего регистра t для квантовых функций (см. 2.5.3.3) вида
F : |n;c|0;t ; |n;c|f (n);t. (2.27)
Поскольку F |x, y; не определено 16 для y;0, целевые регистры должны быть пустыми , когда вызывается F, или же действие оператора не определено.
16 Это сделано для того, чтобы разрешить различные способы накопления результата, поэтому F :|x, y; ; |x, y ; f (x); и F : |x, y; ; |x, (y + f (x)) mod 2n; просто рассматриваются как разные реализации одной и той же квантовой функции.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 69
Промежуточные (скретч) регистры - это временные регистры, которые могут использоваться в рамках реализации оператора, но должны быть пустыми до и после вызова.17
2.4.1.4 Регистровые выражения
В n-кубитном квантовом компьютере один k-кубитный элемент U может использоваться для
реализации до n!/(n;k)! различных унитарных преобразований U (ов) путем применения U
к различным регистрам. Чтобы реализовать все возможные перестановки кубитов, QPL должен предоставлять средства для извлечения подрегистров и объединения непересекающихся регистров.
Определение 32 Регистр a = (a0 . . . an;1) ; Rn является подрегистром a ; b из
b = (b0 . . . . bm;1) ; Rm, если

Определение 33 Два регистра a = (a0 ... an;1) ; Rn и b = (b0 ... bm;1) ;Rm не пересекаются, если
В таблице 2.5 показаны доступные в QCL операторы для управления квантовыми
регистрами.
Выражение Описание  регистр
ссылка ;А0, А1 . . . получите;
а[я] кубит ;АИ;
а[я..ж] под-регистр ;ИИ, AI+1 . . . ЭйДжей ;
подрегистр [i::l] ;ai, ai+1 . . . ai+l;1;
объединение a & b ;a0, a1 . . . an, b0, b1 . . . bm;
Таблица 2.5: Регистровые выражения в QCL

2.4.2 Элементарные элементы управления
Так же, как присваивания (см. 2.3.4.1) представляют собой атомарные изменения состояния программы, элементарные элементы управления являются фундаментальными примитивами для управления состоянием квантовой машины.
17 В QCL тип quscratch, используемый для локального регистра, обозначает управляемые промежуточные регистры (см. 2.5.3.5), которые вычисляются автоматически, в то время как локальный qureg — это неуправляемый промежуточный регистр (см. 2.5.2.4), который должен быть очищен самим оператором.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 70
2.4.2.1 Регистровые операторы
Элементарный элемент k-кубита (см. 1.4.2.4) представляет собой атомарное унитарное преобразование U, который может быть применен к произвольным k-кубитным регистрам s ; Rk квантового оракула (см. 2.2.3.2). Результирующее преобразование состояния машины
формально описывается оператором регистр(см. 1.4.1.3).
В схемотехнической модели оператор регистра описывает вентиль, который подключен для работы с определенными кубитами. В (2.30) “подключение” скрыто в базиса декомпозиции (разложении)  | . . .;s ; | . . .;;s, однако ее можно сделать явной, введя зависящий от регистра оператор переупорядочивания.
Определение 34 (Оператор переупорядочивания) Пусть H = B;n (или H = B*) и
s = (s0 . . . sk;1) ; Rnk (или Rk) - регистр k-кубитов в H. Перестановка кубитов
;s |d0, d1 . . . dn;1; = |d;0 , d;1 . . . d;n;1 ; (2.31)
на H, где ; является биективной функцией от Zn (или N) и ;i = si для i < k, называется оператором переупорядочения для s.
Определение ;s не является единственным; для H = B;n существует (n ; k)! разные
;(i)s и бесконечно много для H = B*.
Функционально оператор переупорядочивания можно сравнить с операциями сдвига и
обмена, используемыми для обращения к произвольным ленточным кубитам в SQTM (см.
2.2.2.2).
Определение 35 (Оператор регистра) Регистровый оператор U (s) для k- кубитного оператора U и квантового регистра k-кубита s ; Rn k для H = B;n (или s ; Rk для H = B*) определяется как
На рис. 2.6 показана квантовая схема для U (s) на 5-кубитной машине, где U  является 3-кубитным затвором и s = (0, 2, 3).
2.4.2.2 Языковое представление элементов
Поскольку предполагается, что квантовое программирование -формализм, не зависит от аппаратуры, помимо трех основных требований, указанных в п. 2.2.3.2 (универсальность, функциональная эквивалентность кубитов, наличие присоединённых вентилей), нельзя делать никаких предположений относительно операторов, предоставляемых квантовым оракулом, и не существует определенного набора элементарных вентилей.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 71
Рисунок 2.6: Оператор регистра U (s)
Следовательно, любой QPL должен допускать объявление произвольных элементарных элементов управления и прозрачную замену элементов управления пользовательскими операторами то есть неклассические подпрограммы (см. раздел 2.5). Следовательно, в процедурном QPL (см. 2.5) элементарные элементы управления рассматриваются как внешние подпрограммы, по крайней мере, с одним параметром квантового типа данных, указывающим регистр, с которым нужно работать.
внешний оператор H(qureg q); //
Внешний оператор вентиля Адамара RotX(real theta,qureg q); //
Внешнее вращение по оси X с функцией CNOT(qureg q,quconst c); // управляемый-нет
Синтаксис вызова вентиля идентичен процедурам, за исключением того, что вызовы
могут быть инвертированы, поскольку для любого вентиля U также существует вентиль U†. В QCL это для этого перед именем элемента управления следует добавить префикс “!”.
qcl> qureg a[1]; qureg b[1]; // выделить 2 кубита.
qcl> H(a); // применяем H к 1-му кубиту
[2/32] 0.7071 |0,0> + 0.7071 |1,0>
qcl> CNOT(b,a); // контролируемый-не
[2/32] 0.7071 |0,0> + 0.7071 |1,1>
qcl> RotX(pi/3,b); // повернуть 2-й кубит на pi/3
[2/32] 0,6123 |0,0> - 0,3535i |1,0> - 0,3535i |0,1> + 0,6137 |1,1>
qcl> !RotX(pi/3,b); // отменить последнюю операцию
[2/32] 0.7071 |0,0> + 0.7071 |1,1> // аналогично. для RotX(-pi/3,b)
2.4.2.3 Типы операторов
Помимо квантовых типов данных, процедурные QPL также предоставляют различные типы операторов, которые могут использоваться как для вентилей, так и для неклассических подпрограмм (см. 2.5). Как правило, для любого заданного элемента U следует использовать наиболее ограничительный тип оператора и наиболее ограничительные типы регистров, которые соответствуют определению U, поскольку элементы с ограниченным доступом могут вызываться менее ограниченными подпрограммами, но не наоборот (см. 2.5.1.1).
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 72
Общие операторы допускают произвольные унитарные преобразования в регистрах аргументов.
внешний оператор RotX(действительная тета, число q); // X-Вращение
Базисные перестановки - это операторы вида F : |n; ; |f (n);, где f является биективной булевой функцией.
extern qufunction CNOT(qureg q,quconst c); // управляемый-не
Условные операторы являются обобщением управляемых логических элементов (см. 1.4.2.5) для включения регистров произвольного размера (включая нулевой регистр, т.е. неуправляемый оператор).
Определение 36 Пусть s, e ; R - непересекающиеся регистры, а U (s) - регистровый
оператор, тогда оператор
называется условным оператором с разрешающим (или управляющим) регистром e
Общие операторы, а также базисные перестановки могут быть объявлены условными.
оператор extern cond Phase(действительный phi); // элемент условной фазы
extern cond qufunct Not(qureg q); // элемент условной not
Регистр enable передается в качестве неявного параметра, если оператор используется в теле квантовой инструкции if (см. 2.6.2.1), поэтому могут быть полезны операторы без явного регистра аргументов (условные фазовые вентили).
qcl> параметр s[1]; параметр e[2]; // выделяем 2 регистра
qcl> H(e); // создаем тестовое состояние в e
[3/32] 0.5 |0,0> + 0.5 |0,1> + 0.5 |0,2> + 0.5 |0,3>
qcl> if e[0] { Фаза(pi); } // перевернуть знак, если задан LSB для e
[3/32] 0.5 |0,0> - 0.5 |0,1> + 0.5 |0,2> - 0.5 |0,3>
qcl> если e {Не(s); } // инвертировать целевой кубит s для e=11
[3/32] 0.5 |0,0> - 0.5 |0,1> + 0.5 |0,2> - 0.5 |1,3>
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 73
2.4.3 Измерения
2.4.3.1 Регистрировать наблюдаемое
В квантовой механике классические физические величины (наблюдаемые величины) описываются эрмитовыми операторами (см. 1.2.3.3). В квантовом программировании мы ограничиваем измерения вычислительной базой B = {|n;}, выраженной стандартной наблюдаемой величиной N = ;n n|n;<n/. Используя регистровый базис Bs = {|k>s}, регистровые наблюдаемые N (s) могут быть определены как (см. 1.4.1.3)
Опять же, мы можем избежать использования регистрового базиса Bs, определив N (s) с помощью оператора переупорядочивания ;s (см. 2.4.2.1).
Определение 37 (Наблюдаемый регистр) Наблюдаемый N (s) регистр для квантового регистра k-кубита s ; Rn k при H =  B;n (или s ; Rk при H = B*) определяется как
Далее, мы предполагаем, что базисные векторы помечены как двоичные числа с малым порядком порядковых номеров (т.е. сначала LSB), поэтому для двух непересекающихся регистров a ; Rn и b ; Rm
N (a ; b) = N (a) + 2nN (b). (2.36)
2.4.3.2 Языковое представление результатов измерений
Поскольку QPL предназначены для управления классическим компьютером, который служит интерфейсом между пользователем и квантовым оракулом (см. 2.2.3), квантовые измерения обрабатываются аналогично внешнему классическому вводу (см. 2.3.4.4) и реализуются как команда квантового ввода с побочным эффектом, заключающимся в снижении состояния машины (см. 1.2.3.3).
qcl> qureg q[8]; // выделяем 8-кубитный регистр q
qcl> int m; // объявляем классическую входную переменную
qcl> H(q); // подготавливаем четную суперпозицию в q
[8/32] 0.0625 |0> + ... + 0.0625 |255> (256 условия)
qcl> измерить q[0..5],m; // измерить первые 6 кубитов q
[8/32] 0.5 |50> + 0.5 |114> + 0.5 |178> + 0.5 |242>
qcl> напечатать m; // результат измерения в печать
: 50

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 74
2.4.3.3 Инициализация
Поскольку многие квантовые алгоритмы являются вероятностными (см. 2.2.1.2) и предполагают повторение одних и тех же вычислений до тех пор, пока не будет найдено решение, удобно предоставить команду для сброса состояния машины |;; в исходное состояние |0; и очистки всех выделенных регистров, не влияя при этом на состояние программы, чтобы привязки переменных и сопоставления регистров остались в силе.
[8/32] 0.5 |50> + 0.5 |114> + 0.5 |178> + 0.5 |242>
qcl> сброс; // сброс квантового состояния, как сгенерировано выше
[8/32] 1 |0>
qcl> вывести q,m; // переменные q и m не затрагиваются
: <0,1,2,3,4,5,6,7> 50
Поскольку инициализация |;; может быть реализована путем измерения всех выделенных регистров и преобразования кубитов qi, находящихся в состоянии pqi = |1;;1|, в ноль, применяя элемент-не X(qi), квантовому оракулу нет необходимости предоставлять общую команду сброса (см. раздел 1.4.3.3).
процедура сброса регистра(qureg q) {
int i;
int m;
для i=0 до #q-1 { // перебирать кубиты
, измеряя q[i],m; // измерять i-й кубит
, если m==1 { Не(q[i]); } // инвертировать при измерении 1
}
}

2.5 Операторы
Хотя регистров, элементарных логических элементов и измерений уже достаточно для реализации произвольных квантовых алгоритмов, язык программирования, ограниченный этими понятиями, не сильно отличался бы от классического языка с драйвером квантового устройства, поскольку в нем отсутствовало бы семантическое представление для унитарных
операторов, которые являются сутью всех квантовых алгоритмов.
В этом разделе мы продемонстрируем, как унитарные операторы могут быть интегрированы в рамки процедурного языка программирования (процедурное квантовое программирование).
2.5.1 Квантовые подпрограммы
Процедурные языки программирования обеспечивают произвольные уровни абстракции, позволяя группировать простые вычислительные задачи в параметризованные подпрограммы, которые могут рекурсивно использоваться в качестве примитивов для определения более сложных подпрограмм.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 75
В процедурном QPL унитарные операторы представлены в виде квантовых подпрограмм, которые позволяют рекурсивно создавать сложные квантовые схемы из элементарных элементов.
2.5.1.1 Иерархия подпрограмм
В дополнение к классическим процедурам и функциям (см. 2.3.3), мы предоставляем два типа квантовых подпрограмм (см. 2.4.2.3) для общих унитарных операторов и базисных перестановок.
Оба типа квантовых подпрограмм (которые вместе мы будем называть операторами) имеют математическую семантику (см. 2.5.1.2) и могут быть инвертированы для получения сопряженного (присоединенного) оператора. Квантовые функции дополнительно позволяют прозрачно использовать (управляемые) предварительные (промежуточные, скретч) регистры (см. 2.5.3.5).
Подпрограмма    QCL S Н inv. скретч
процедура    процедура все все нет нет
общего унитарного    оператора нет унитарного да нет
базовой перестановки qufunction    нет                rev. логический    да                да
функции возвращают тип нет нет нет нет
Таблица 2.6: Иерархия подпрограмм
4 типа подпрограмм образуют иерархию вызовов, что означает, что подпрограмма может вызывать только подпрограммы того же или более низкого уровня. В таблице 2.6 перечислены подпрограммы с указанием их типа QCL, допустимых классических (S) и квантовых (H) побочных эффектов, их обратимости и поддержки управления пространством скретч(с нуля).
Алгоритм Дойча Чтобы проиллюстрировать изложенную выше концепцию, в следующей QCL -реализации алгоритма Дойча (см. 1.5.2.2) используются все 4 типа подпрограмм:
/* Определяем Oracle */
const coin1=(random()>=0.5); // Определяем два случайных логических значения
const coin2=(random()>=0.5); // константы
boolean g(boolean x) _BOS_ // Функция оракула g
, если coin1 _BOS_ // coin1=true -> g - константа
, возвращающая coin2;
} else { // coin1=false -> g сбалансировано
возвращает x xor coin2;
}
}
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 76
qufunct G(quconst x,quvoid y) _BOS_ // Построить oracle op. G из g
, если g(ложь) xor или g(истина) { CNot(y,x); }
если g(false) { Не(y); }
}
/* Алгоритм Дойча */
оператор U(последовательность x,последовательность y) _BOS_ // Объединяет все унитарные операции
H(x); // из алгоритма в один
G(x,y); // оператор U
H(x и y);
}
процедура deutsch() _BOS_ // Классическая структура управления
qureg x[1]; // выделяем 2 кубита
число y[1];
число m;
{ //
сброс цикла вычисления; // инициализация состояния машины
U(x,y); // выполнение единичного вычислительного
измерения y,m; // измерение 2-го регистра
} пока m==1; // значение в 1-м регистре допустимо?
измерьте x,m; // измерьте 1-й регистр, который
выводит "g(0) xor g(1) =",m; // содержит g(0) xor g(1) =
сброс; // очистка
}

2.5.1.2 Математическая семантика
В классических подпрограммах подпрограммы выполняются при их вызове ( линейное выполнение), т.е. когда управление достигает соответствующего оператора вызова (см. 2.3.4.3). Операторы, однако, поддерживают неклассические концепции, такие как обратимость (см. 2.5.2.3), управление пространством скретч(с нуля) (см. 2.5.3.5) и квантовые инструкции (операторы) if (см. 2.6.2.1), в результате чего ни число, ни порядок выполнения субоператоров обязательно соответствует классическому потоку управления (нелинейное выполнение).
Следовательно, операторы обладают математической семантикой, т.е. их действие полностью описывается унитарным преобразованием, которое они реализуют как функцию от их заявленных параметров; поэтому они должны быть воспроизводимыми и не зависеть от состояния программы и не оказывать побочных эффектов на нее. Это, в частности, исключает
• использование глобальных переменных
• пользовательский ввод и классические случайные числа
• измерения и сброс состояния машины
• вызовы процедур
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 77
2.5.1.3 Языковое представление операторов
Формально, как и в случае классической процедуры, оператор представляет собой именованный блок (см.2.3.1) со списком символьных параметров классического или квантового типов.  Последние используются для обозначения регистров, к которым применяется оператор.
Приведенный ниже оператор QCL реализует базисную перестановку
qufunct xreg(qureg a,int b) _BOS_ // xor reg. a с двоичным числом b
int i;
от i=0 до #a-1 { // перебрать кубиты a
, если бит(b,i) { Не(a[i]); } // инвертировать i-й кубит a, если
} // Установлен i-й бит из b
}
Синтаксис вызова операторов идентичен гейтс(элементы), включая возможность вызова присоединенного(сопряженного) оператора. Поскольку операторы имеют математическую семантику, оператор полностью эквивалентен элементарному гейт тем же объявлением и функциональностью. Таким образом, не имеет значения, например , обеспечивается ли Z-элемент (см. 1.4.2.4)
внешним оператором квантового оракула Z(qureg q); // pi-вращение вокруг оси Z
или реализуется в виде последовательности Z = HXH оператором
operator Z(qureg q) { H(q); Не(q); H(q); }

2.5.1.4 Полиморфизм
На n-кубитном квантовом компьютере k-кубитный элемент управления может реализовывать до n!/(n;k)! унитарных преобразований U (s) с s ; Rnk . В процедурном квантовом программировании этот полиморфизм расширяется за счет дополнительных абстракций:
• Размер регистра: Регистры аргументов могут быть разного размера, поэтому для каждого квантового параметра s размер регистра |s| передается как неявный классический параметр. В QCL размер регистра определяется оператором размера “#”, поэтому #s = |s|. Оператор с единственным регистром аргумента s ; Rn может реализовывать до n различных унитарных преобразований.
• Несколько регистров: операторы могут принимать несколько регистров аргумента. Поскольку для любого s ; Rk существует () возможные разложения s = s1 ; . . . ; sq (включая нулевые регистры), оператор с p аргументами регистра si с общим размером k = ;q i=1 |si| может реализовывать до () различных унитарных элементов.


ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 78
• Классические параметры: Помимо регистров аргументов, операторы также могут принимать произвольное число классических параметров. Любой классический параметр типа T увеличивает число возможных унитарных операций на коэффициент |T|.
Как правило, на n-кубитном квантовом компьютере оператор с q аргументами регистра и p классическими параметрами типов данных Ti может реализовать до
различных унитарных преобразований.
2.5.2 Общие операторы
2.5.2.1 Квантовые схемы
Общие операторы могут рассматриваться как процедурные описания квантовых схем в зависимости от размера их регистров аргументов, а также от классических параметров.
На рис. 2.7 показана 4-кубитная квантовая схема, которая генерируется следующей реализацией дискретного преобразования Фурье в QCL
используя алгоритм, подобный FFT, предложенный Копперсмитом [22].
оператор dft(qureg q) _BOS_ // Дискретное преобразование Фурье
const n=#q; // задает n в качестве длины входных
данных int i; int j;
для i=1 - n {
для j=1- i-1 { // применяет условные фазовые вентили
V(pi/2^(i-j),q[n-i] и q[n-j]);
}
H(q[n-i]); // элемент Адамара
}
перевернуть(q); // поменять местами порядок кубитов на выходе
}
Поскольку оператор может вызывать другие вспомогательные операторы, эти описания могут быть
вложенными. В приведенной выше реализации DFT, например, используется
переключение субоператора : |d0d1 . . . dn;1; ; |dn;1 . . . d1d0; (2.40)
чтобы сгенерировать последние два элемента обмена (подкачки), показанных на рис. 2.7.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 790
Рисунок 2.7: Квантовое преобразование Фурье для 4-кубитного регистра
qufunction flip(qureg q) { // Изменить порядок кубитов
в i;
для i=0 на #q/2-1 {
Поменять местами(q[i],q[#q-i-1]); // поменять местами 2 противоположных кубита
}
}
Реализация оператора может также содержать вызовы самого себя, что приводит к рекурсивному определению результирующей схемы. Приведенный ниже оператор QCL является рекурсивной реализацией фазового преобразования
используя условный фазовый элемент V (;) = Cn[ei;], который для n = 1 эквивалентен
Rz (;) = e;i;/2|0;;0 |+ ei;/2  |1;;1|.
оператор P(число q,действительный phi) _BOS_ // Фазовое преобразование
V(phi,q[0]); // повернуть LSB
, если #q>1 { // если есть кубиты большего размера
P(q[1..#q-1],2*phi); // вызов P с фазой 2*phi
}
}

На рис. 2.8 показано, как рекурсивно строится результирующая схема для
4-кубитного регистра q = q0 ; q1 ; q2 ; q3.
2.5.2.2 Типы параметров
Помимо общих регистров (QCL типа qureg), которые допускают произвольные квантовые схемы, в качестве регистров параметров могут использоваться более строгие типы квантовых данных (см. 2.4.1.3), указывающие на принадлежность оператора U к определенному классу
унитарных преобразований.

CHAPTER 2. STRUCTURED QUANTUM PROGRAMMING 80;(;)

Рисунок 2.8: Фазовое преобразование рекурсивное
Параметры Константы Регистр констант  c (QCL тип quconst) указывает что  c инвариант к оператору, т.e. что  U оператор выбора формы
Определение 38 (n + m)-кубитный оператор U формы
при Uk ; SU (2n) и m > 0 называется оператором выбора.
Чтобы ввести это ограничение, при реализации  U , c должно использоваться только как константа аргумента к любому подоператору. Так следующая реализация  Z-вентиля неверна, несмотря на факт, что
Z = HXH = |0;c;0|c ; |1;c;1|c (2.44)
форма (2.42).
qcl> operator z(quconst c) { H(c); X(c); H(c); }
! in operator z(quconst c) at "H(c); ":
! parameter mismatch: quconst used as non-const argument to H
С задачей позволить декларацию регистра параметра константы с даже когда с используется как главный регистр аргумента к вспомогательному оператору, в  QCL, ограничения выше могут привести к редекларации с как  qureg. Это задает программисту  проверить надлежащим образом семантику quconst — возможность отвечать. (см. также 2.5.3.2).
operator z(quconst c) { // Correct implementation of the Z-gate -правильная реализация вентиля Z
qureg q = c; // redeclare c as qureg -передекларация как qureg
H(q); // transform into dual basis- перевод в дуальный базис
X(q); // X-rotation in dual basis — Х -вращение в дуальном базисе
H(q); // transform back into — перевод обратно
} // computational basis — базис вычисления
CHAPTER 2. STRUCTURED QUANTUM PROGRAMMING 81
Целевые параметры Целевой регистр t (QSL  тип quvoid) ожидается пустым когда неинвертированный оператор вызван , так U |k;t|;;неопределён для k; 0.18 Таким образом, два оператора  U (1) и U (2) с целевым регистром  t рассматриваются равными если
U (1)|0;t|;;;t = U (2)|0;t|;;;t для всех|;; ; H;t. (2.45)
Пока целевые рагистры обычно используются как результатирующие регистры для квантовых функций (см. 2.5.3.3), они могут также использоваться для главных операторов:
operator prepare(quvoid t) { // Prepare test state for empty t -приготовить состояние теста
для пустого  t
H(t); // produce even superposition — приготовить чётную/даже/ суперпозицию
P(t,2*pi/2^#t); // phase transformation — фазовое преобразование
}
QCL оператор выше ожидает пустой регистр t приготовить состояние теста вида
используя фазовое преобразование P (;) (2.41) из2.5.2.1.
qcl> qureg q[5]; // allocate empty 5-qubit register -выделить пустой 5-кубитный регистр
qcl> prepare(q); // prepare test state — приготовить состояние теста
[5/32] 0.17678 |0> + ... + (0.17338-0.034487i) |31> (32 terms) /32 теста/
qcl> plot; // plot simulated state — начертить моделированное состояние
На рис. 2.9 показано 5-кубитное состояние теста
как приготовлено выше. Точка (“•”) и крест (“;”) обозначают реальную и мнимую части  (R(ck) и I(ck)) идлину вертикальных линий абсолютной переменной (|ck|) комплексными амплитудами ck.
18Конечно, U (t, s) дает детерминированный эффект для  ;t ; |0;;0|, только что этот эффект не часть операторов декларированной семантики и рассматривается в детальной реализации. 
Глава 2. STRUCTURED Quantum PROGRAMMING 82
5 использовано кубитов , 32 базовых вектора
Рисунок  2.9: 5-кубитное состояние теста
Параметры промежуточные/царапать/ Промежуточный/Царапать/ регистр s (QSL тип quscratch) ожидается пустым до и после вызванного оператора, так  U должен быть вида
Промежуточные/ Царапать/ параметры (также называются явные царапать регистры), имеют некоторую семантику неуправляемого (см. 2.5.2.4) расположения царапать переменных (QCL-тип qureg), кроме того они  предусмотренные как параметры вместо получения расположения из квантовой кучи (см. 2.4.1.2). Явные царапать параметры могут быть использованы для субоператоров, как они позволяют временно использовать целевые регистры, или другие регистры, которые известны тем, что должны быть пустыми в какой-то точке во время вычислений , как царапина, чтобы сохранить квантовую память.
2.5.2.3 Обратные Операторы
Не так как процедуры, вызовы оператора могут быть инвертированы. В QCL, это дано
подсоединённым префиксом "!” перед наименованием оператора. Присоединённый
оператор составлен из унитарных операторов19
19 Избегая неточности с некоммутативными матричными продуктами, мы используем соглашение
Пni=1 fi = fnfn-1 . . . f1
Глава 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 83
В модели схемы обратный оператор является простым исполнением схемы от правого к левому, где вентили былИ заменен их присоединёнными вентилями.
qcl> qureg q [3]; / / allocate 3 - Qubit register расположить 3- кубитный регистр
qcl> H(q[1]); / / prepare test state приготовить состояние теста
[3/32] 0.70711 |0> + 0.70711 |2>
qcl> set log 1; / / show gate sequence показать последовательность вентилей
qcl> dft (q); / / Quantum Fourier transform квантовое преобразование Фурье
@ H (qureg q = <2>)
@ V (real phi=1.5708, quconst q=<1.2>)
@ H (qureg q = <1>)
@ V (real phi=0.785398, quconst q = <0.2>)
@ V (real phi=1.5708, quconst q=<0.1>)
@ H (qureg q = <0>)
@ Swap (qureg a = <0>, qureg b=<2>) 0
11
0
22 часа
ХН / 2
; / 4 Hn / 2
[3/32] 0.5 |0> + (0.25+0.25 я) / 1> + (0,25-0,25 я) / 3> +
0.5 / 4> + (0.25+0.25 i) |5> + (0.25-0.25 i) / 7>
qcl> !dft (q); / / inverse transform
@ !Swap (qureg a = <0>, qureg b = <2>)
@ !H (qureg q = <0>)
@ !V (real phi=1.5708, quconst q=<0.1>)
@ !V (real phi=0.785398, quconst q = <0.2>)
@ !H (qureg q = <1>)
@ !V (real phi=1.5708, quconst q=<1.2>)
@ !H (qureg q = <2>) 0
11
0
22
H
H
H-;/2
;;/2
;;/4
[3/32] 0.70711 |0> + 0.70711 |2>

Задержанное Выполнение Пока последовательность применённых вспомогательных операторов уточнена  используя процедурный язык который не может выполняться в обратную сторону, присоединение было достигнуто  за счет задержанного выполнения вызова вспомогательных операторов.
Когда вызов вспомогательного оператора подсчитан  во время выполнения инвертированного оператора, имя субоператора и его оцененные аргументы были вытолкнуты на стёке выполнения. В последствии, вызовы вспомогательного оператора на стёке обработаны в обратном порядке. Таким образом, нормальные вызовы заменены инвертированными вызовами и наоборот.
2.5.2.4 Промежуточные /Царапать/  Регистры
Пусть произвольный  k-кубитный унитарный оператор в  B;k.  Пока любой универсальный набор вентилей G = {G1, G2 . . .} позволяет прямую реализацию U как
реализация  (k + s)-кубитного оператора
Глава 2. СТРУКТУРИРОВАННЫЕ КВАНТОВОГО ПРОГРАММИРОВАНИЯ 84
такая, что
U (2) |;;|0; = (U |;;) |0; для всех |;; ;B;k в (2.52)
может быть значительно более эффективным.
В квантовом программировании мы рассматриваем U (1) и U (2) как эквиваленты и
относимся к U (2) как к реализации U с помощью s царапать кубитов .
Формально, царапать регистр  - это локальная квантовая переменная, определенная в
теле определения оператора. Как и все другие квантовые переменные, локальные регистры пусты при распределении (см. 2.4.1.2). При этом, в отличие от квантовых функций (см. 2.5.3.3), для обычных операторов нет способа автоматически “очистить-всё“  царапать регистры сама реализация должна гарантировать, что локальный регистр s пуст (т.е. находится в состоянии ;s = |0;;0|) после вызова (неуправляемое промежуточное /царапать/ пространство).
В QCL неуправляемые промежуточные /царапать/ регистры являются локальными переменными типа qureg. Оператор, приведенный ниже, использует промежуточный кубит для реализации условного фазового
вентиля
используя Z-вращение единственного кубита Rz (см. 1.4.2.2) и обобщенный CNot-
вентиль
оператор cphase(действительный phi,qconst q) _BOS_ // Задает условную фазу
qureg s[1]; // одиночный кубит с нуля
CNot(s,q); // s=1, если q=111...
RotZ(phi,s); // добавить фазу, если s=1
CNot(s,q); // восстанавливаем кубит с нуля
}
Для регистра аргументов n-кубита cphase(;) может быть записана как (n+1)-
кубитная матрица
на B;N+1 и реализует  V(;, q) до неактуальной /не релевантной/ глобальной фазы как,
qcl> qureg q[2]; // выделяем 2 кубита
qcl> H(q); // подготавливаем тестовое состояние
[2/32] 0.5 |0> + 0.5 |1> + 0.5 |2> + 0.5 |3>
qcl> фаза c(pi,q); // повернуть фазу на |3>
[2/32] -0,5i |0> -0,5i |1> -0,5i |2> + 0,5i |3>

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 85
2.5.3 Базисные перестановки
Из-за линейности унитарных преобразований, оператор применяется к суперпозиции состояния |;; одновременно применены все векторы базиса, что представляют |;; так
Это свойство называется квантовым параллелизмом и используется в большинстве неклассических алгоритмов (см. 1.5.2.4).
Часто U реализует обратимую логическую или, что эквивалентно, биективную целочисленную функцию, рассматривая базисные векторы просто как последовательности битов или двоичных чисел.
Определение 39 Базисная перестановка на n-кубите - это унитарный оператор вида F : |k; ; |f (k);, где f является биективной функцией (т.е. перестановкой) на Z2n (или Bn).
2.5.3.1 Обратимые булевы сети
В то время как обычные операторы реализуют квантовые схемы, базовые перестановки представляют собой процедурные описания обратимых булевых сетей, работающих на кубитах. Это позволяет нам обсуждать вычисления на кубитах аналогично классическим битам, так что мы можем, например, описать эффект операции управляемый-не C[X](a, b) как “если установлен кубит b, то инвертируйте кубит a”.
Множество (набор) L = {X, C[X], C2[X]} является универсальным для базисных перестановок.20 Логические элементы в L могут быть обобщены до логического элемента CNot (2.54), который работает с аргументами и адресата (целевых) регистров произвольных размеров.
В QCL базовые перестановки представлены подпрограммой типа qufunct. На рис. 2.10 показана схема из 4 кубитов, сгенерированная оператором
qufunct inc(qureg x) { // Увеличить регистр
int i;
для i = #x-от 1 до 0, шаг -1 {
CNot(x[i],x[0::i]); // применить управляемый-не
} // из MSB в LSB
}

который реализует инкрементацию (приращение, добавление) базисного вектора
inc : |k;x ; |(k + 1) по модулю 2|x|;x. (2.58)
20 Фактически, элемент Тоффоли T = C2[X] сам по себе был бы универсальным, если бы были доступны два дополнительных постоянных кубита в состоянии |1;.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 860
Рисунок 2.10: Оператор инкремента
qcl> qureg q[8]; // выделяет квантовый байт
qcl> H(q[2] и q[5]); CNot(q[0],q[2]); // подготовка тестового состояния
[6/32] 0.5 |0> + 0.5 |5> + 0.5 |32> + 0.5 |37>
qcl> inc(q); // увеличение базисных векторов
[6/32] 0.5 |1> + 0.5 |6> + 0.5 |33> + 0.5 |38>
qcl> inc(q);
[6/32] 0.5 |2> + 0.5 |7> + 0.5 |34> + 0.5 |39>
qcl> !inc(q); // уменьшение базисных векторов
[6/32] 0.5 |1> + 0.5 |6> + 0.5 |33> + 0.5 |38>
2.5.3.2 Небулевы разложения на множители
В соответствии с иерархией подпрограмм (субрутин) (см. 2.5.1.1), любая подпрограмма (рутина) может выполнять только вызов подпрограммы (субрутин) того же или более ограниченного типа. Это, в частности, означает, что базовые перестановки могут не вызывать общие операторы или элементы управления в пределах их определения. Однако существуют универсальные наборы элементов G, где LG. Одним из примеров может служить стандартный набор (см. 1.4.2.6) {H, S, T, C[X]}, в котором отсутствуют элементы Не- и Тоффоли-.
Таким образом, процедурный QPL должен обеспечивать способ обойти иерархию подпрограмм, чтобы определять небулевы реализации для элементарных базисных перестановок. В QCL это может быть достигнуто с помощью двойного объявления, например
оператор qufunct Not(qureg q) _BOS_ // Стандартная реализация набора
int i; // обобщенного элемента Not
для значений от i=0 до #q-1 _BOS_ // для всех кубитов:
H(q[i]); // преобразуем в дуальный базис
S(q[i]); S(q[i]); // S^ 2 = Z = |0><0|-|1><1|
H(q[i]); // преобразуем обратно в
} // вычислительную базу
}
2.5.3.3 Квантовые функции
Одной из очевидных проблем квантовых вычислений является их ограничение обратимыми
вычислениями. Рассмотрим простую операцию, такую как подсчет количества заданных
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 87
кубитов в регистре q
с числом битов : |k;q ; |b(k);q с (2.59)
b(n) = n по модулю 2 + b(bn/2c) и b(0) = 0. (2.60)
Очевидно, что эта операция необратима, поскольку bitcount' |2n; = 1 для всех
n < |q|, поэтому bitcount' не является унитарным оператором. Однако, если мы используем
дополнительный регистр p с 2|p| > |q|, то мы всегда можем найти унитарный оператор bitcount, такой, что
bitcount : |k;q|0;p ; |k;q|b(k);p (2.61)
Определение 40 Пусть c ; Rn и t ; Rm - непересекающиеся регистры, а f - произвольная функция f : Z2n ; Z2m (или f : Bn ; Bm). Унитарный оператор F вида
называется квантовой функцией, реализующей f с функцией накопления
g.
Поскольку функция F должна быть унитарной, каждая hz : y ; g(z, y) должна быть 2m-
перестановкой с hz (0) = z. Таким образом, для любой заданной функции f: Z2n ; Z2m существует 2n(2m ; 1)! различные квантовые функции F (k), реализующие f .
В процедурном квантовом программировании две квантовые функции F (1) и F (2) считаются эквивалентными, если они реализуют одну и ту же функцию, поэтому F |x>t|y>t не определено для y; 0, что делает фактическое определение g несущественной деталью реализации.21
Приведенное выше понятие эквивалентности подразумевает, что t является целевым регистром (см.2.5.2.2). Кроме того, из формулы (2.62) следует, что c - это постоянный регистр (для констант). Используя типы регистров QCL quconst и quvoid, мы можем реализовать bitcount как квантовую функцию
qufunctbitcount(quconst q,quvoid p) { // подсчитать установленные биты в q
int i; int j;
если #q>=2^#p _BOS_ // убедитесь, что p - это широкий
выход "целевой регистр слишком мал"; // достаточно
}
для i=0 - #q-1 _BOS_ // перебираем кубиты в q
для j=#p-1 -0, шаг -1 _BOS_ // увеличиваем p, если q[i]
CNot(p[j],p[0::j] & q[i]); // устанавливается
}
}
}
21 Эта абстракция необходима, поскольку использование предварительных регистров (см. 2.5.3.5) может повлиять на g.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 88
с функцией накопления g(z, y) = (z + y) mod 2|p|, таким образом
 количество битов : |x;q|y;p ; |x;q|(y + b(k)) по модулю 2|p|;стр. (2.63)
qcl> qureg q[3]; qureg p[2]; // выделяем аргумент и выбираем reg.
qcl> H(q); // подготавливаем суперпозицию
[5/32] 0.3535 |0,0> + 0.3535 |1,0> + 0.3535 |2,0> + 0.3535 |3,0> +
0.3535 |4,0> + 0.3535 |5,0> + 0.3535 |6,0> + 0.3535 |7,0>
qcl> количество битов(q,p); // подсчет заданных кубитов
[5/32] 0.3535 |0,0> + 0.3535 |1,1> + 0.3535 |2,1> + 0.3535 |4,1> +
0.3535 |3,2> + 0.3535 |5,2> + 0.3535 |6,2> + 0.3535 |7,3>
2.5.3.4 Ненужные (джанк, выбросить) регистры
Хотя квантовые функции можно использовать для обхода обратимой природы квантовых вычислений, необходимость сохранять копию аргумента является проблемой, поскольку при более длительных вычислениях регистры будут заполнены промежуточными результатами.
Предположим, мы хотим сравнить количество заданных кубитов в двух регистрах a
и b, т.е. найти квантовую функцию для реализации предиката
c(x, y) ={1, если b(x) = b(y)
0 в противном случае . (2.64)
Используя вспомогательный регистр s и B = bitcount (количество битов) из (2.63), оператор
реализует c, но оставляет регистр s в “грязном” состоянии:
qufunct bitcmp0(количество битов a,количество битов b,количество битов t,количество битов s)
_BOS_ количество битов(a,s); // записать #битов(a) в s
!количество битов(b,s); // вычитаем b(b) из s
Не(s); // инвертируем s
CNot(t,s); // t=1, если #биты(a)-#биты(b)=0
}
Поскольку s не содержит полезной информации и обычно запутан (т. е. tr(;2s ) < 1), его нельзя сбросить путем измерения (см. 2.4.3.3) без влияния на другие регистры, s называется нежелательным (джанк) регистром. Квантовая функция
F : |x, 0;|0;s ; |x, f (x);|j(x);s (2.67)
с ненужным (джанк) параметром s называется грязной реализацией f .
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 89
qcl> параметр a[3];параметр b[3]; // выделять регистры a,b,s,t
qcl> параметр s[2];параметр t[1];
qcl> H(a[0]); Не(a[2]); // подготавливает тестовое состояние для
[9/32] 0.70711 |4,0,0,0> + 0.70711 |5,0,0,0>
qcl> H(b[1]); Не(b[0]); // подготовить тестовое состояние для b
[9/32] 0.5 |4,1,0,0> + 0.5 |5,1,0,0> + 0.5 |4,3,0,0> + 0.5 |5,3,0,0>
qcl> bitcmp(a,b,t,s); // сравниваем количество битов
[9/32] 0.5 |4,3,0,0> + 0.5 |5,1,2,0> + 0.5 |4,1,3,1> + 0.5 |5,3,3,1>
2.5.3.5 Управление промежуточным /пустым ,скретч, царапать/ пространством
Пусть F - грязная реализация классической функции f с регистром аргументов x, целевым регистром y и ненужным регистром s
При подсчете f (k), то F также заполняется с временно ненужными (джанк) битами j(k). Чтобы восстановить значение s, Беннетт предложил следующий метод [7], который известен как вычисление (анкомпьютинг):
1. Выделите (пустой) вспомогательный регистр t того же размера, что и y.
2. Замените F (x, y, s) оператором
Описанная выше процедура восстанавливает как ненужный, так и вспомогательный регистры, поэтому s и t являются скретч параметрами  (см. 2.5.2.2) F ', поэтому F ' - это чистая реализация f с скретч кубитами |s| + |t| (см. 2.5.2.4).:
Оператор разветвления Оператор разветвления - это квантовая функция, дополняющая тождество, т.е.

и обычно реализуется с использованием элементов |x| управляемый-не с функцией накопления gF (x, y) = x ; y.
cond qufunction Fanout(quconst a,quvoid b) {
int i;
если #a!=#b { выход "аргументы разветвления должны быть одинакового размера"; }
для i=0 до #a-1 { CNot(b[i],a[i]); }
}
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 90
Пусть F - грязная реализация f с функцией накопления g и ненужным регистром s, так что
Чистая версия F ' в соответствии с (2.69) с начальными регистрами s и t представлена в виде
Таким образом, в F ' исходная функция накопления g заменяется функцией накопления gF оператора разветвления.
Промежуточные/Царапины, царапать/ регистры  В процедурном квантовом программировании, метод вычисления (анкомпьютинг) (2.69) позволяет автоматически восстанавливать локальные регистры, которые остаются в непустом состоянии после выполнения основной части оператора (управляемые промежуточные регистры). В QCL управляемые промежуточные регистры — это локальные переменные типа quscratch.
Поскольку метод вычисления работает только для квантовых функций, управляемые начальные регистры ограничены базисными перестановками с постоянными и целевыми регистрами в качестве квантовых параметров.
Для bitcmp0 из (см. 2.5.3.4) можно создать чистую версию, создав управляемый локальный царапины регистр
qufunction bitcmp(значение a,значение b,значение t) {
quscratch s[ceil(log(max(#a,#b)+0,5,2))];
bitcmp0 (a,b,t,s);
}
который не только эквивалентен, но и реализует то же унитарное преобразование22, что и следующий оператор, используя два неуправляемых начальных регистра (см. 2.5.2.4).
qufunct числом bitcmp(quconst а quconst б,quvoid Т) {
qureg с[метод ceil(вход(Макс(#а#б)+0.5,2))];
параметр u[#t];
биткмп0 (a,b,u,s);
CNot(t,u);
!биткмп0 (a,b,u,s);
}
22 Обратите внимание, что для одиночных кубитов каждая возможная реализация оператора разветвления идентична логическому элементу CNot.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 91
2.5.3.6 Семантика вызовов
Потенциальное использование управляемых царапины регистров расширяет семантику вызовов базисных перестановок по сравнению с обычными операторами. Рассмотрим
квантовые функции
qufunct U1(quconst x,quvoid y,quvoid s) _BOS_ // s - ненужный (хлама, джанк) регистр
A(x,y,s);
B(x,y,s)
}
qufunct U2(quconst x,quvoid y) _BOS_ // s -для нулевого (царапины) регистра
;
A(x,y,s);
B(x,y,s)
}
В то время как вызовы U1(x,y,s) и !U1(x,y,s) аналогичны вызовам обычного оператора, т.е.
вызовы U2(x,y,s) и !U2(x,y,s) вызывают прозрачное выделение регистра t с |t| = |y| и приводят к преобразованиям
Обратите внимание, что U2 и U † 2 практически идентичны и что U2 = U †2 если используется эрмитова реализация оператора разветвления.
Двойное выполнение Когда выполняется общий оператор или базисная перестановка без использования управляемых царапать регистров, вызовы субоператоров выполняются либо обрабатывается немедленно (линейное выполнение) или помещается в стек выполнения (отложенное выполнение), в зависимости от того, был вызван обычный или обратный оператор (см. 2.5.2.3).
В случае квантовой функции с управляемыми царапать регистрами, после первоначального переназначения целевых регистров вызовы субоператора всегда выполняются и помещаются в стек выполнения (двойное выполнение). После обработки основной части подпрограммы выполняется соответствующая операция разветвления (обычный вызов) или разветвления† (инвертированный вызов), а затем выполняется  вызов стёка выполняются снова в обратном порядке с перевернутыми флагами присоединения.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 92
2.6 Управление квантовым потоком
Все классические языки программирования, так или иначе, допускают условное выполнение кода в зависимости от логической переменной или логического выражения (условное ветвление). В структурированных языках условное ветвление реализуется с помощью if-инструкций с четко определенными точками входа и выхода.
Хотя ненаблюдаемость кубитов запрещает прямую реализацию, мы покажем, как условные операторы могут использоваться для эмуляции условного ветвления на кубитах (квантовая инстукция if), а также (ограниченные) условные циклы с квантовыми условиями завершения позволяют использовать кубиты для управления потоком данных почти так же, как классические биты (структурированное квантовое программирование).
Далее мы продемонстрируем, как кубиты и регистры могут быть объединены в произвольные логические выражения и сложные предикаты (квантовые условия).
2.6.1 Условные операторы
Как уже упоминалось в разделе 2.4.2.3, для оператора унитарного регистра U (s) и
регистра включения (или управления) e ; R, не связанных с s, условный оператор
U[[e]](s) определяется как
Если e является кубитом, то |e| = 1, то неформально мы можем описать эффект U[[e]](s) как “если установлено значение e, то примените U (s)”, что относится к тому факту, что
2.6.1.1 Свойства условных операторов
Ортогональный включить Регистр Пусть U, V ; SU (2n) являются n-кубитными унитарными операторами, s ; Rn - n-кубитным регистром, а q ; R1 - кубитом, не пересекающимся с s (т.е. q s), тогда
Для произвольных регистровых операторов U (x) и V (y) выражение (2.79) можно обобщить до
где c ; Rn - непустой регистр c  e и x, y e.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 93
Условное разложение Легко проверить, что для произвольного U (s) и кубита q ; R1 q s
Определение 41 Базисная перестановка из n кубитов P : |k; ; |p(k); называется циклической, если она генерирует вычислительный базис B таким образом, что для любого
 |k; ; B
таким образом, p является перестановкой на Z2n с длиной цикла 2n. Если P циклично,  то A† P A также является циклическим для произвольной базисной перестановки A. Примером циклической базисной перестановки является оператор inc (2.58) из 2.5.3.1.
Теперь мы можем обобщить идентификатор (2.81) для разрешающих регистров e ; Rn, e s на
где P - произвольная n-кубитная циклическая базисная перестановка.
Условная композиция Пусть V, W ; SU (2n) являются n-кубитными унитарными
операторами, тогда оператор выбора
может быть реализован следующим образом
Аналогично, для любого (n + m)-кубитного оператора выбора
существует циклическая базисная перестановка P для m-кубита, такая, что
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 94
2.6.1.2 Условные подпрограммы
Поскольку условные операторы являются всего лишь частным случаем операторов выбора (см. 2.5.2.2), они могут быть реализованы как квантовые подпрограммы с постоянным регистром включения.
Приведенный ниже оператор cinc реализует условную версию оператора увеличения регистра (2.58), определенную как
qufunct cinc(qureg x,quconst e) _BOS_ // Условное приращение
int i; // как выбор
для i = #x-от 1 до 0, шаг -1 _BOS_ // оператор
CNot(x[i],x[0::i] & e);
}
}
Приведенный выше оператор является условной версией (2.58)
Структурированные QPL напрямую поддерживают условное выполнение, т.е. автоматическое построение U[[e]] из заданной реализации U , позволяя явно объявлять условные подпрограммы.
В QCL условные операторы могут быть определены путем добавления к объявлению подпрограммы ключевого слова cond.
cond qufunction inc(qureg x) { // Регистр условного приращения
int i; // как условный
для i = #x-от 1 до 0 шаг -1 { // подпрограмма
CNot(x[i],x[0::i]);
}
}
Условные вызовы Регистр включения e является неявным постоянным параметром и не является частью объявления параметра условной подпрограммы. Вместо этого e задается квантовой инстукцией if (см. 2.6.2.1) и прозрачно передается всем вспомогательным операторам, которые, следовательно, также должны быть либо условными операторами, либо условными элементарными элементами (см. 2.4.2.3).
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 95
qcl> qureg q[4];qureg e[1]; // распределяем количество и контролируем параметры.
qcl> H(q[3] & e); // подготавливаем тестовое состояние
[5/32] 0.5 |0,0> + 0.5 |8,0> + 0.5 |0,1> + 0.5 |8,1>
qcl> cinc(q,e); // условное приращение
[5/32] 0.5 |0,0> + 0.5 |8,0> + 0.5 |1,1> + 0.5 |9,1>
qcl> если e { inc(q); } // эквивалентно cinc(q,e)
[5/32] 0.5 |0,0> + 0.5 |8,0> + 0.5 |2,1> + 0.5 |10,1>
qcl> !cinc(q,e); // условное уменьшение
[5/32] 0.5 |0,0> + 0.5 |8,0> + 0.5 |1,1> + 0.5 |9,1>
qcl> если e { !inc(q); } // эквивалентно cinc(q,e);
[5/32] 0.5 |0,0> + 0.5 |8,0> + 0.5 |0,1> + 0.5 |8,1>
В приведенном выше примере инструкция if “if e { inc(q); }” приводит к тому, что управляющий кубит e добавляется к разрешающим регистрам поколения Cnot-gates.- определяемый вызовом inc(q), поэтому “if e { inc(q); }” и cinc(q,e) описывают одну и ту же квантовую схему (рис. 2.11).q0
Рисунок 2.11: Оператор условного приращения




Безусловные вызовы Если условная подпрограмма вызывается вне квантовой инструкции if23, то значение e является пустым (безусловный вызов), а семантика вызова идентична безусловным подпрограммам.
qcl> inc(q); // безусловное приращение
[4/32] 0.5 |1,0> + 0.5 |9,0> + 0.5 |1,1> + 0.5 |9,1>
Поскольку объявление оператора условным не влечет за собой никаких накладные расходы на безусловные вызовы, поэтому разумно всегда объявлять процедуры (рутины) как условные, если все требуемые вспомогательные (суб,под) операции доступны в виде условных подпрограмм (субрутины) или шлюзов.
23 В случае под- оператора это также включает все родительские операторы

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 96
2.6.1.3 Граф вызовов подпрограмм (субрутин)
Иерархия подпрограмм  (субрутин) (см. 2.5.1.1) подразумевает, что процедуры могут вызывать только подпрограммы того же или более ограниченного типа. Если, в дополнение к этому, мы также примем во внимание, что условные операторы не могут вызывать безусловные субоператоры, иерархия превращается в решетку, которая может быть представлена графом вызовов, изображенным на рис. 2.12.
процедура
оператор
функции
Рисунок 2.12: Граф вызовов подпрограмм QCL

2.6.1.4 Явные регистры включения
Условные операторы, по определению, должны быть способны обрабатывать регистры разрешений произвольного размера. Поскольку предполагается, что структурированное квантовое программирование является аппаратно-независимым формализмом, нельзя предполагать, что квантовый оракул предоставляет универсальный набор условных логических вентилей. На самом деле, большинство стандартных вентилей работают не более чем с тремя кубитами (см. 1.4.2.4).
Таким образом, структурированный QPL должен допускать реализацию базовых условных операторов с использованием безусловных вспомогательных операторов и вентилей и, следовательно, должен предоставлять средства для обеспечения доступности разрешающего регистра в качестве символической квантовой константы (явный разрешающий регистр).
В QCL это достигается путем повторного объявления разрешающего регистра как локального регистра типа quconst. Приведенный ниже пример является реализацией Not-gate в QCL по умолчанию:
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 97
extern не работает(qureg q); // безусловный не
работает(qureg q,quuconst c); // безусловный
не работает(qureg q) { // условный не
работает(qureg q) _BOS_ = cond; // e=включить (разрешить)  регистр
, если #e>0 { CNOT(q,e); } иначе { НЕ(q); } //
}

2.6.2 Условное ветвление
2.6.2.1 Квантовые инстукции If
В классических языках структурированного программирования условное выполнение последовательности операторов (блока) ; в зависимости от значения логической переменной
p выражается оператором if вида
if p then ;1, ;2 ... ;n endif
или, если один из двух блоков ; и ; должен выполняется,
если p, то ;1, ;2 . . . ;n иначе ;1, ;2 . . . tm endif
if p, то ;1, ;2 . . . ;n else ;1, ;2 . . . tm endif
Если вместо классической логической переменной if-условием является кубит p
 если p, то ;1, ;2 . . . ;n, иначе ;1, ;2 . . . tm
if p, то ;1, ;2 . . . ;n, else ;1, ;2 . . . tm
, то S называется квантовая if-инструкция (QIS). S называется
(i) недопустимая iff ; или ; содержит 24 вызова процедур, измерения, команды сброса или
ввода или используют случайные числа.
(ii) вложенная iff ; или ; содержит другие квантовые if-инструкции.
(iii) грязая iff ; или ; содержит назначения или прерывающие инструкции.
(iv) чистая, если она действительна и не загрязнена.
(v) простая, если она чиста и ; = (), т.е. ветвь else не определена.
Блочные и конечные операторы Подобно телу операторной подпрограммы, if- и else-ветви ; и ; в основном являются процедурными описаниями квантовых схем, или, точнее, последовательностей подоператоров, которые получают генерируется линейным выполнением. Однако, в отличие от подпрограммы, ; (; ) не имеет объявленного интерфейса, поэтому ее “параметрами” являются все классические и квантовые переменные, которые видны в текущей области. Кроме того, не гарантируется, что ; (; ) имеет математическую семантику (грязная QI).
24 Сюда также входят любые вложенные инструкции в структурах управления.

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 98
Мы запишем ; (; ) для обозначения состава подпрограмм (блок оператор ), который был бы сгенерирован, если бы ; (; ) выполнялся вместо S25, и ;; (;; ) для обозначения схемы, которая генерируется, когда выполнение продолжается до конца текущей подпрограммы (оператор конца/ тайл оператор/).26 В глобальной области ^; и ^; не определены.
В следующем примере значения ;;, ;; , ^; и ^; будут равны
оператор U(последовательность x,последовательность y) {
A(x);
if y { B(x); } else { C(x); } // квантовая инструкция if
D(x,y);
}
2.6.2.2 Условное выполнение
Простой QIS S имеет вид
if p, then ;1, ;2 . . . ;n endif
и реализует преобразование US = ;;[[p]]. Таким образом, простой QISs можно использовать
для установки разрешающих регистров условных операторов (условные вызовы, см.
2.6.1.2).
Поскольку p уже передан в качестве неявного параметра, ;; не должен работать с
p, т.е. ;; = ;;(;p), поэтому приведенный ниже QIS не является чудесной реализацией операции единого стирания, а просто вызывает ошибку
qcl> if q { Not(q); }
! при "Not(q); ":
! ошибка во время выполнения: аргументы совпадают с квантовым условием
Глобальный управляющий регистр Внутри системы передача разрешающих регистров в
условные подпрограммы обрабатывается глобальным управляющим регистром g.
Всякий раз, когда возникает простая QIS, происходит следующее:
1. Соответствующий разрешающий регистр p добавляется к g.
2. Выполняется if-ветвь ;.
3. p удаляется из g.
Всякий раз, когда возникает вызов условного логического вентиля, текущее значение
g передается в качестве разрешающего регистра в квантовй оракул.
25То есть схема, которая была бы сгенерирована, если бы S было классической инстукцией if с p = true
(p = false)
26 Обратите внимание, что, следовательно, даже если ветвь else не определена и, следовательно, ; = (), это не означает, что ^; = I.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 99
2.6.2.3 Квантовый отбор
Чистый QIS S с ;; () имеет вид
 если p, то ;1, ;2 . . . ;n, иначе ;1, ;2 . . . . tm конец
if p, то ;1, ;2 . . . ;n, еlse ;1, ;2 . . . . tm еndif
Семантика S (т.е. соответствующее унитарное преобразование) определяется как оператор выбора
Поскольку US содержит ; и ; в качестве вспомогательных операций, это означает, что, в отличие от классического оператора (утверждения) if-, выполняются обе ветви S. Поскольку мы предположили, что ни ;, ни ; не содержат присваиваний или других операторов, которые могли бы изменить состояние программы, обе ветви не могут проявлять взаимные побочные эффекты, и это может быть сделано без нарушения классической семантики.27
US реализуется как условная композиция (2.85)

таким образом, QIS слева соответствует правильной последовательности (см. 2.6.1.2)
if p {
inc(x); // cinc(x,p); условное приращение
} else { // Not(p); инвертировать включение кубита
!inc(x); // !cinc(x,p); условное уменьшение
} // Не(p); восстановить включенный кубит
2.6.2.4 Квантовое разветвление
Если тело классического if-утверждения S содержит изменения в состоянии программы (например, присвоения локальным переменным), то последующие вызовы оператора могут отличаться в зависимости от того, была ли выполнена ветвь if- или else-.  Однако, если S - это (грязная) QIS, тогда необходимо выполнить оба пути, чтобы определить соответствующий условный оператор US , который допускает неклассические побочные эффекты и может привести к классически несовместимым состояниям.
Чтобы проиллюстрировать проблему, рассмотрим оператор
27 Примером для несогласованного кода может быть, например
 логическое значение v := true
, если p, то v := v else v := v endif
, если v, то ошибка “классически недоступный код” endif
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 100
операторов U(qureg s,quconst p) {
int n;
если p { n=1; } иначе { n=0; } // грязный QIS
V(n,s); // n=0 или n=1?
}

На первый взгляд кажется невозможным придумать семантику U (s, p), которая
была бы классически непротиворечивой, а также давала бы разумную интерпретацию как утверждение  квантового управления, поскольку нет причин отдавать предпочтение одному из “очевидных” кандидатов V0 (s) и V1 (s) перед другим.
В качестве квантовой аналогии мы могли бы сказать, что QIS привела p и классическую переменную n в коррелированное состояние, что предполагает интерпретацию- утверждение, что V0(s) применяется ко всем базисным векторам |k>s|0>e, а V1(s) - ко всем базисным векторам |k>s|1>e, т.е.
Хотя эта семантика симметрична28 и имеет разумную квантовую интерпретацию, она не является классически последовательной, поскольку оставляет привязку n неопределенной. Но здесь математическая семантика операторов (см. 2.5.1.2) приходит  на помощь, поскольку в них указано, что операторы определяются своим единым действием и не могут изменять состояние программы. Поскольку n - это локальная переменная, которая вот-вот выйдет за пределы области видимости, мы могли бы оставить ее неопределенной. Однако эта семантика также подразумевает, что грязный QISs не может использоваться в глобальном масштабе или внутри процедур.
Приведенная выше интерпретация также может быть описана как расширение QIS, включающее оставшуюся часть оператора, поэтому U считается эквивалентным
оператору U(qureg s,quconst p) {
int n;
если p { n=1; V(n,s); } иначе { n=0; V(n,s); }
}
Поскольку это может быть сделано явно только в том случае, если рассматриваемый QIS не является частью управляющего утверждения (например, цикла while), необходимо более общее представление о том, что именно представляет собой “остаток от подпрограммы”. Это обеспечивается хвостовыми операторами ;; и ;; (см. 2.6.2.1).
Используя ;; и ;; , вышеуказанный метод может быть формализован таким образом , что для грязной QIS S вида
if p then ;1, ;2 . . . ;n else ;1, ;2 . . . tm endif
преобразование US, реализованное с помощью S, может быть определено как
28Т.о. выполнить обе ветви QIS равно.
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 101
и реализованное как





Многопоточное выполнение Поскольку вычисление ;; и ;; включает в себя не только
при выполнении соответствующего блока S, а не всей подпрограммы, грязная QIS разделяет классический поток управления на два отдельных потока (квантовое разветвление). Каждый поток выполняется независимо до тех пор, пока не будет достигнут конец подпрограммы (потоковое выполнение). В соответствии с (2.80) сгенерированные квантовые схемы ;; и ;; затем могут быть повторно объединены в
Ограничения В то время как концепция потокового выполнения позволяет условно выполнять классический код в зависимости от кубитов, грязная QISs также накладывает ряд ограничений:
• Поскольку разные потоки, как правило, приводят к разным состояниям программы, "грязные" QISs могут появляться только в подпрограммах с математической семантикой и, следовательно, доступны (ограничены) только операторам.
• Поскольку эффект "грязного" QIS распространяется на оставшуюся часть процедуры, все
доступные субоператоры должны быть условными, даже если процедура не объявлена условной и они не являются частью QIS.
• Если в цикле используется "грязный" QIS, то разрешающие регистры должны быть непересекающимися для каждой итерации.
2.6.2.5 Псевдоизмерения
Возможное применение QISs заключается в формальном преобразовании содержимого (ненаблюдаемых) квантовых регистров в классическую переменную (псевдоизмерения).
Приведенный ниже оператор QCL реализует оператор выбора
по условному составу (2.87).
cond qufunction mux(qureg q,quconst s) _BOS_ // Квантовый мультиплексор
int i;
int n = 0;
от i=0 до #s-1 { // накапливаем содержимое
if s[i] { n=n+2^i; } // регистр выбора в
} // классическая переменная
Not(q[n]); // переворачиваем выбранный выходной кубит
}
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 102
На рисунке 2.13 показана квантовая схема, генерируемая мультиплексором (s, q) в случае 2-кубитного регистра выбора s.
Рисунок 2.13: квантовый мультиплексор
2.6.2.6 Условные циклы
При условном выполнении инструкции break QISs может быть использован для реализации (ограниченных) условных циклов с квантовыми условиями завершения.
Приведенный ниже оператор QCL реализует фазовое преобразование
pdlog(;) = diag (1, ;, ;2, ;2, ;3, ;3, ;3, ;4 . . .) с ; = ei ei (2,98)
который вращает базисные векторы в соответствии с самым высоким установленным кубитом.
оператор pdlog (real phi,qureg q)
_BOS_ int i;
для i= # q-от 1 до 0, шаг -1 _BOS_//выполнить итерацию от MSB до LSB
, если установлен кубит/// выход если кубит установлен
Фаза (- phi); // поворот на-phi
}
}
На рисунке 2.14 показана 4-кубитная квантовая схема, сгенерированная pdlog.
2.6.3 Квантовые условия
Определение 42 (Логические формулы) Пусть s — набор (множество) символов, тогда B0(S) =S {{true, false} - это набор атомарных булевых формул в S. Множество B (S)
логических формул на S рекурсивно строится следующим образом
(i) если a  B0 (S), то a, в B (S)
(ii) если a B (S), то ¬a B (S)
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 103q0
вопрос 1
вопрос 2
Рисунок 2.14: Двойное логарифмическое фазовое преобразование
(iii), если a, b ; B (S), то a ^b, a ;b, a b B ; B (S)
Определение 43 (Квантовое Условие) Логическая формула C ; B (R1) кубитов называется квантовым условием. Квантовый регистр e = e0;. . .;en; en-1 ; Rn соответствует квантовому условию e0^. . .^ en-1. Два регистра p и q эквивалентны (p;q), если они соответствуют одному и тому же квантовому состоянию (т.е. состоят из одних и тех же кубитов)
2.6.3.1 Исключительная дизъюнктивная нормальная форма
Определение 44 Пусть S множество символов. Логическая формула F = B (S) вида
это в исключительно дизъюнктивной нормальной форме (XNF ДНФ). Также мы объявляем
Любая логическая формула f может быть преобразована в XFN путем рекурсивного
применения следующих правил.
(a) является ложным.
(ii) a ; a
(iii) a ; истина ; a
(iv) A ; B ; a ; a b ; b
(v) a ; ;

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 104
С этого момента мы будем предполагать, что квантовые условия заданы в XNF. Далее мы будем использовать обозначения
Определение 45 Пусть p, q ; R - регистры, а P = {pi}, Q = {qi} — множество кубитов в p, q. Регистры p ; q и p ; q, которые определяются как
Определение 46 Пусть С= {pi} квантовое состояние. Регистр
называется регистром условий C.
2.6.3.2 Квантовые предикаты
Определение 47 Пусть C = {pi} - квантовое условие с регистром условий
c = reg C и t ; R1. Оператор
называется квантовым предикатом C с целевым регистром t.
Определение 48 Пусть C = {pi} - квантовое условие с регистром условий
c = reg C, c : B|c| ; B, такое, что PC|x;c|0; = |x;c|c(x); и U -
унитарный оператор. (Расширенный) условный оператор U[[C]] определяется как
Используя пустой кубит s с нуля, U[[C]] может быть реализовано как
U[[C]] = PC(c, s) U[[s]] PC(c, s) (2.107)
Логические операции Пусть p, q будут кубитами, s - пустым исходным кубитом, а U - унитарным оператором. Расширенные условные операторы для логических операций not, and, xor и or могут быть реализованы как

ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 105
2.6.3.3 Языковое представление квантовых условий
В структурированном квантовом программировании квантовые условия представлены в виде специального типа данных (QCL-тип qucond), который представляет собой список постоянных квантовых регистров. Логические операторы могут использоваться для объединения регистров, квантовых условий и даже классических логических выражений:
qcl> qureg a[1]; qureg b[1]; // выделяем 2 кубита
qcl> выводим a и b, a или b, a xor b; // основные логические операторы
: <0,1> <0; 1; 0,1> <0; 1>
qcl> qucond c; // переменная qucond
qcl> c=not (a или b); // присвоение qucond
qcl> вывести c, #c, c[3]; // вывести c, количество
предложений : <*; 0; 1; 0,1> 4 <0,1> //, последний регистр
qcl> вывести c xor true, c и (1==2); // смешанные квантовые/логические
: <0; 1; 0,1> <> // выражения
qcl> c=(pi > 3); // логические выражения получают
qcl> вывести c; // преобразовать в qucond, если
: <*> // необходимо
QCL даже определяет оператор сравнения для сравнения регистров с другими
регистрами или целыми числами.
qcl> qureg q[4];
qcl> вывести q==15,q==7;
: <0,1,2,3> <0,1,2; 0,1,2,3>
2.6.3.4 Квантовые условия и If-утверждения
Квантовые условия в основном используются в качестве аргументов для квантовых if-утверждений.
если C, то ;1, ;2 . . . ;n еще ;1, ;2 . . . . tm endif
В зависимости от C существует 5 возможных случаев:
1. Если C = {} = false, выполняется переход else.
2. Если C = {o} = true, выполняется переход if.
3. Если C = {p} и |p| = 1, то QIS выполняется в обычном режиме.
4. Если C = {q} и |q| > 1 и QIS простая, то QIS выполняется
нормально.
5. В противном случае
(a) выделяется царапать кубит s с нуля.,
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 106
(b) квантовый предикат PC(c, s) применяется к s,
(c) C заменяется на s и выполняется QIS,
(d) s вычисляется с помощью PC(c, s) и освобождается.
qcl> параметр q[3];
qcl> параметр a[1]; параметр b[1];
qcl> H(a & b);
[5/32] 0.5 |0,0,0> + 0.5 |0,1,0> + 0.5 |0,0,1> + 0.5 |0,1,1>
qcl> если a { inc(q); }
[5/32] 0.5 |0,0,0> + 0.5 |1,1,0> + 0.5 |0,0,1> + 0.5 |1,1,1>
qcl> если a и b { inc(q); }
[5/32] 0.5 |0,0,0> + 0.5 |1,1,0> + 0.5 |0,0,1> + 0.5 |2,1,1>
qcl> если a или b { inc(q); }
[5/32] 0.5 |0,0,0> + 0.5 |2,1,0> + 0.5 |1,0,1> + 0.5 |3,1,1>
qcl> если не a или b { inc(q); }
[5/32] 0.5 |1,0,0> + 0.5 |2,1,0> + 0.5 |2,0,1> + 0.5 |4,1,1>
2.6.3.5 Квантовые функции условия
Вспомогательные функции могут использоваться для вычисления сложных условий. Следующая функция вычисляет квантовое условие для проверки на примитивность:
qucond isprime(quconst q) _BOS_ // Проверка на первичность для регистра q
int i;
qucond c; // переменная qucond c={}=false
для значений от i = 0 до 2^#q-1 _BOS_ // перебор возможных чисел
, если testprime(i) _BOS_ // если простое, то добавьте qucond(q==i)
c = c или q==i; // в c
}
}
верните c;
}
На рис. 2.15 показана квантовая схема квантового предиката Pisprime(q, p) для |q| = 4.
Рисунок 2.15: 4-кубитный XNF-тест на первичность
ГЛАВА 2. СТРУКТУРИРОВАННОЕ КВАНТОВОЕ ПРОГРАММИРОВАНИЕ 107
qcl> параметр q[4];
qcl> H(q);
[4/32] 0.25 |0> + 0.25 |1> + 0.25 |2> + 0.25 |3> + 0.25 |4> +
0.25 |5> + 0.25 |6> + 0.25 |7> + 0.25 |8> + 0.25 |9> + 0.25 |10> +
0.25 |11> + 0.25 |12> + 0.25 |13> + 0.25 |14> + 0.25 |15>
qcl> if isprime(q) { Фаза(pi); } // поменять знак, если простое
[4/32] 0.25 |0> + 0.25 |1> - 0.25 |2> - 0.25 |3> + 0.25 |4> -
0.25 |5> + 0.25 |6> - 0.25 |7> + 0.25 |8> + 0.25 |9> + 0.25 |10> -
0.25 |11> + 0.25 |12> - 0.25 |13> + 0.25 |14> + 0.25 |15>

Приложение А
Краткий справочник по QCL
Синтаксис A.1
Синтаксическая структура программы на QCL описывается контекстно-свободной грамматикой LALR(1). Для формального определения синтаксиса используется следующая запись
:
expression-name ; expression-def 1
; определение выражения 2
· · · · · ·
В определениях синтаксиса применяются следующие правила
• Ключевые слова и другой буквенный текст задаются в courier
• Подвыражения выделяются курсивом
• Необязательные выражения заключаются в [ квадратные скобки ]. Необязательные
выражения могут быть повторены 0 или 1 раз.
• Несколько выражений заключены в { фигурные скобки }. Несколько выражений могут
может повторяться 0, 1 или n раз.
• Варианты записываются в виде alt 1| alt 2| . . . Необходимо выбрать только один вариант
.
• Группировка выражений может быть принудительной (круглые скобки ).
Чтобы упростить обозначение литералов, определены следующие классы символов
:

108
ПРИЛОЖЕНИЕ А. КРАТКИЙ СПРАВОЧНИК ПО QCL 109
digit  десятичная цифра от 0 до 9.
*letter   алфавитная буква  от "a"  до  z или A до Z. Случай значительный.
* char - печатаемый символ кроме «.
Программа QCL представляет собой последовательность инструкций и определений, поэтому
qcl-вход ; stmt / def
Комментарии Как и C++, QCL поддерживает несколько комментариев. Все комментарии просто отбрасываются сканером.
Линейные комментарии начинаются с / / и длятся до конца текущего ряда
Комментарии в стиле C начинаются с / * и заканчиваются */ и могут продолжаться более нескольких линий. Комментарии в стиле C могут не быть вложенными.
A.1.1 Выражения
комплексы - координата [ + | - ] цифра { digit } [ . {{цифра }}]
const ; цифра { разряд } [ . {{цифра }}]
; ( комплексная координата , complex-coord )
 смотрите также ложь
 " символ "
подписаться на ; идентификатор [expr ]
отправлено по адресу: const | подстрочный индекс
 просмотрите выражение [ ... ].  аль-Кайим
; идентификация (выражение { , выражение})
; ( выражение )
 смотрите также описание
 смотрите также описание
 смотрите также: expr
 смотрите также выражение (expr )
; выражение mod expr
 выражение ( + | - | & ) выражение

ПРИЛОЖЕНИЕ А. КРАТКИЙ СПРАВОЧНИК ПО QCL 110
 смотрите также выражение ( = = != | < | <= | > | >= ) выражение
 не является выражением
 выражение и экспр
; выражение (или / xor) expr

A.1.2 Утверждения
блок {{stmt } }
опционная буква {{буква}}
stmt ; [! [ выражение {, выражение }]] ;
; ( идентификатор | нижний индекс ) = выражение ;
 смотрите также выражение ( -> | <- | <-> ) выражение ;
 следующее сообщение: от expr к блоку expr [шаг expr ]
 что такое блок expr
 блокировать до истечения срока действия ;
; блок expr [ блокировать ]
 смотрите также описание ;
 просмотр входного идентификатора [expr] ;
 смотрите также вывод выражения [, expr ] ;
 экспресс [ ... ] ;
 измерение значения expr [ , идентификатор ] ;
 перезагрузка ;
; дамп [expr ] ;
; список [идентификатор, identifier }] ;
; ( загрузить | сохранить) [expr ] ;
 по оболочке ;
 смотрите также опцию [expr ] ;
 по stmt ;

A.1.3 Определения
скалярный тип ; int / real / complex
квантовый тип ; qureg / quvoid / quconst | quscratch
тензорный тип ; (вектор | матрица | тензорная цифра) скалярный тип
ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК ПО QCL 111
othertype ; ( qucond | логический | строковый
тип ; скалярный тип | тензорный тип | квантовый тип | другой тип
const-def ; идентификатор const = expr ;
var-def ; идентификатор типа [ expr ] ;
; идентификатор типа [ = expr ] ;
arg-def ; идентификатор типа
arg-list ; ( [ arg-def { , arg-def }])
тело ; { { const-def | var-def } { stmt } }
def ; const-def | var-def
; идентификатор типа arg-тело списка
; идентификатор процедуры arg-тело списка
; [ cond ] идентификатор оператора arg-тело списка
; [ cond ] функциональный идентификатор оператора в виде списка аргументов
; внешний идентификатор оператора в виде списка аргументов ;
; список аргументов внешнего функционального идентификатора ;

A.2 Выражения
A.2.1 Типы данных
A.2.1.1 Классические скалярные типы
Классическими скалярными типами данных QCL являются арифметические типы целые, действительные и комплексные, а также логические и строковые.
Примеры описания типов
int целое число 1234, -1
действительное число 3,14, -0,001
сложное комплексное число (0,-1), (0.5, 0.866)
логическое значение типа "истина", "ложь
", строка символов "hello world", ""

A.2.1.2. Тензоры
Начиная с версии 0.5, QCL поддерживает векторы, (квадратные) матрицы и тензоры более высокого порядка вплоть до 9.
ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК по QCL 112
Примеры описания типов
вектор вектор-матрица(0,0.5,0.866)
матрица-квадратная матрица-матрица(0,(0,-1),(0,1),0)
тензор тензора порядка n тензор3(1,0,0,0,0,0,0,1)
Тензоры могут быть определены для арифметических скалярных типов int, real и
complex. Тензорная переменная v порядка n и размерности dim объявляется с помощью
синтакса
скалярного типа tensorn v [dim ];
Для тензоров 1-го и 2-го порядков можно использовать ключевые слова vector и matrix.
Оператор подстрочного индекса v [coord ] используется для доступа к элементам тензора, где coord представляет собой разделенный запятыми список из n целых индексов, основанных на нуле.
Здесь нет тензорных литералов; вместо этого используется тензорный объект порядка n и определение d создается функцией-конструктором tensorn (elem ), где elem представляет собой разделенный запятыми список скалярных выражений dn, упорядоченных в порядке возрастания их индексов, причем самый левый индекс является наиболее значимым.
Тензоры одинакового порядка и размерности могут быть сложены, вычтены и подписаны. Тензоры могут быть умножены на скаляры или на тензоры одинаковой размерности. В последнем случае умножение определяется как обобщенное точечное произведение, т.е. сокращение путем суммирования по самым внутренним индексам
A.2.1.3 Типы регистров
Для локальных переменных или параметров типов quvoid и quscratch пусть U
будет соответствующим унитарным оператором.
Тип функция ограничение
qureg общий регистр отсутствует
quconst квантовая константа, инвариантная ко всем операторам
quvoid целевой регистр пуст при вызове U
quscratch царапать регистр пуст при вызове U или U †
A.2.1.4 Квантовые условия
Логические выражения кубитов представлены QCL-типом qucond. Пусть C будет переменной типа qucond и











ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК по QCL 113
значение XNF (ДНФ) в C . Оператор size #C возвращает число n предложений в C, а C [k ] дает значение регистра quconst pk.
 A.2.2 Операторы
В следующей таблице перечислены все операторы QCL, упорядоченные по приоритету. arith
обозначает все арифметические скалярные типы, tensor - все типы тензоров, а quantum - все типы регистров.
Операция  описание  Тип аргумента
[ ] субрегистр кубита Квантовая переменная
предложение (клаус ДНФ) XNF куконд переменная (квантового условия)
векторный  индекс Векторной переменной
[ .. ] Подрегистр диапазона Квантовая переменная
[ :: ] Подрегистр по смещению и длине квантовая переменная
[ , ] тензорный индекс тензорная переменная
# размер регистра  квантовое
число предложений XNF , квантовое число
размерность тензор
^ степень , арифм (арифметический)
целочисленной степени int
- унарный минус арифм, тензор
* умножение арифм, тензор
/ деление арифм
, целочисленное деление int
mod, целочисленный модуль int
+ сложение арифм, тензор
- вычитание арифм, тензор
и конкатенации строка, квантовая
== равный арифм, строка
!= неравный арифм, строка
< меньше int, действительный
<= меньше или равен int, действительный
> больше int, действительный
>= больше или равно int, действительное
, логическое не логическое значение, quucond
и логическое значение и логическое значение, quucond
или логическое включающее или логическое значение, quucond
исключающее или логическое значение исключающее или boolean, qucond

ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК ПО QCL 114
A.2.3 Элементарные функции
Элементарные функции являются частью QCL и не нуждаются в объявлении. В отличие
от функциональных подпрограмм, элементарные функции
• не обязательно должны иметь фиксированное количество аргументов
• может принимать аргументы разных типов и
• может иметь различные типы возвращаемых данных в зависимости от типов аргументов






функции Описание Arg.
тригонометрические функции sin, cos, tan, coth - это
гиперболические функции sinh, cosh, tanh, coth
, возведенные в степень x
, log(x) натуральный логарифм от x
, log(x,n) по основанию-n логарифм от x.
sqrt(x) квадратный корень из значения x
, abs(x) абсолютное значение значения x
Re, Im действительная и мнимая части комплекса
conj(z) комплексное сопряжение z-го комплексного
уровня, ceil следующее большее и меньшее целое действительное
число gcd(n,...) наибольший общий делитель int
lcm(n,...) наименьшее общее кратное int
min, max минимальное и максимальное
не, и, или, xor двоичные функции int
бит(n,k) логическое значение k-го бита из n int
int, вещественные, комплексные, строковые явные типы скалярных
векторных, матричных, тензорных или тензорных конструкторов arith
random() случайное значение из [0, 1) отсутствует

A.3 Утверждения
Если не указано иное, параметры, написанные наклонным шрифтом(Ubuntu K), обозначают выражения
(см. A.1.1).
A.3.1 Простые утверждения
A.3.1.1 Присвоения
lvalue = rvalue ;
ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК по QCL 115
Значение lvalue может быть либо переменной, либо индексным выражением. Квантовые переменные (т.е. символьные регистры) не могут быть присвоены.
Неявное приведение типов выполняется от int и real к real или complex, а также от boolean и всех типов регистров к qucond. Во всех остальных случаях значения lvalue
и rvalue должны быть одного типа.
A.3.1.2 Вызовы подпрограммы
[!]sub (args)  ; //(аргументы );
args - это список аргументов, разделенный запятыми, и он может быть пустым.  Количество выражений в args должно соответствовать объявлению подпрограммы sub, которая может быть процедурой, оператором или qufunct.
Если sub является квантовой подпрограммой, то можно вызвать обратный оператор,, добавив к имени префикс “!”. Процедуры не могут быть инвертированы.
A.3.1.3 Ввод и вывод
input [ prompt , ] var ;
считывает классические данные, введенные пользователем, и присваивает их скалярной переменной var . Может быть указано необязательное приглашение типа string.
вывод списка ;
print list;
выводит список выражений, разделенных запятыми.
A.3.1.4 Измерение и инициализация
измерьте q [,var ];
measure q[,var];
измеряет значение регистра q и присваивает измеренное значение целочисленной переменной var, если она указана.
Сброс;
reset;
инициализирует состояние машины.
A.3.2 Управление потоком
 A.3.2.1 Циклы
Тело цикла представляет собой список инструкций. Фигурные скобки обязательны, даже если тело представляет собой одну инструкцию. Утверждение break
break;
может использоваться внутри тела для немедленного выхода из самого внутреннего цикла.

ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК ПО QCL 116
Условные циклы
, в то время как cond { тело }
{ body } до cond ;

cond - это логическое выражение. Тело цикла until выполняется хотя бы один раз.
Подсчет циклов
от i = a до b [ шаг s ] { body }
Диапазон a , b и необязательный размер шага s являются целочисленными выражениями. Переменная цикла i также имеет тип int и переопределяется как символическая константа в теле.
A.3.2.2 If-утверждение
if cond { sigma } [ else { tau }]
if-ветви sigma и необязательный tau else-ветви - это список утверждений
; фигурные скобки обязательны даже для отдельных утверждений.
Условие if cond является либо логическим выражением (классическое утверждение if)
, либо квантовым условием (квантовое утверждение if).
A.3.2.3 Аварийное завершение
exit msg;
выводит сообщение об ошибке msg и завершает работу программы QCL.
A.3.3 Интерактивные команды
Интерпретатор QCL qcl определяет дополнительные команды, которые в основном предназначены для интерактивного использования и отладки и не считаются основными частями QCL.
A.3.3.1 Команды моделирования
Следующие команды доступны только в том случае, если QCL используется совместно с
компьютерным симулятором.
дамп [ q ];
dump [q];
ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК по QCL 117
выводит спектр вероятности для регистра q . Если регистр не указан, выводится текущее состояние машины.
построить график [ q ];
plot [q];
выводит спектр вероятности для регистра q . Если регистр не указан, выводится текущее состояние машины.
построить q , p ;
plot p,q;
построить спектр вероятности q ;p в виде двумерного графика плотности.
сохранить файл ;
save file;
сохранить текущее состояние машины в файл .
загрузить файл ;
load file;
загрузить текущее состояние машины из файла .
A.3.3.2 Другие команды
устанавливают значение opt val ;
set opt val;
устанавливает для параметра интерпретатора opt (без начального /лидирующего/ “--”) значения val . Пожалуйста, обратитесь к приложению A.4 для получения полного списка опций.
список [sym ];
list [sym];
содержит определение символа sym в текущей области применения. Если символ не
указан, перечисляются все определенные в данный момент символы.
Ракушка;
shell;
открывает вложенную /вспомогательную/ оболочку, которую можно снова закрыть командой exit. Вложенные оболочки также могут быть открыты в ответ на прерывания с клавиатуры и
ошибки во время выполнения (см. A.4). Символы, определенные в вложенной оболочке, являются локальными и покидают область видимости при повторном выходе из оболочки.
Выход;
exit;
закрывает текущую оболочку. При закрытии оболочки верхнего уровня сеанс завершается.

ПРИЛОЖЕНИЕ A. КРАТКИЙ СПРАВОЧНИК по QCL 118
A.4 Параметры интерпретатора
Интерпретатор /терминал/ qcl   QCL имеет следующие параметры:
Параметры запуска могут быть установлены только в командной строке.
-h, --справка, отображающая это сообщение
-V, --версия, отображающая информацию о версии
-i, --интерактивный принудительный интерактивный режим
-x, --exec<команды> выполняет "команды" при запуске
-q, -- сообщение о пропуске при запуске
-- color интерфейс color xterm
--texmacs интерфейс  TeXmacs (экспериментальный)
-n, --no-default-включить, не читать по умолчанию.qcl при запуске
-o, --logfile укажите файл журнала
-b, --bits=n: задайте количество кубитов (32).
Динамические параметры Можно задать в командной строке или с помощью команды set
(см. выше). Значения по умолчанию указаны в квадратных скобках.
-s, --seed=<начальное значение> задает случайное начальное значение (системное время).
-I, --include-path=<путь> QCL включает путь (/usr/local/lib/qcl)
--библиотека=<y|n> игнорировать переопределения существующих символов (n)
-d, --dump-file=<файл> отправить вывод команды dump в файл (нет)
-p, --plot-file=<файл> Postscript-файл, созданный командой plot (нет)
-f, --dump-format=x,d,b вывод базовых векторов в шестнадцатеричном, десятичном или двоичном виде (d)
-r, --show-regs=<y|n> показывать глобальные регистры в сброшенных состояниях (y)
-D, --dump-precision=<d> отображаются d цифр в сброшенных состояниях (5)
-P, --precision=<цифры> отображаются цифры для действительных и комплексных значений (6)
-Z, --trunc-нули=<y|n> усечение нулей для действительных и комплексных значений (y)
-T, --truc-состояния=<y|n> усечение нераспределенных кубитов (y)
--plot-paper=<формат> Установите формат бумаги для вывода на Postscript (b5)
--plot-size=<пиксель> Установите максимальный размер окна для X11 графиков (600)
-Q, --qureg-mask=<y|n> список регистрируется как маски вместо списков (n)
-g, --debug=<y|n> открывать отладочную оболочку при ошибке (n)
-a, --auto-dump=<max> сбрасывать состояния с максимальным значением. в режиме оболочки (8)
-l, --log==<y|n> регистрировать вызовы внешнего оператора (n)
-L, --логарифмическое состояние==<y|n> логарифмическое состояние после каждого преобразования (n)
-c, --проверка ==<y|n> проверка согласованности квантовой кучи (n)
--трассировка==<y|n> режим трассировки (очень подробный) (n)
-S, --синтаксис=<y|n> проверяйте только синтаксис, без интерпретации (n)
-E, --echo=<y|n> эхо-анализ входных данных (n)
-t, --test=<y|n> тестовая программа, игнорирующая квантовые операции (n)
-e, --shell-escape=<y|n> соблюдайте shell-escape (y)
--irq=<y|n> разрешить прерывания пользователя, если они поддерживаются (y)
Библиография
[1] Энтони А. Ааби: Введение в языки программирования (1996).
http://cs.wwc.edu/~aabyan/221_2/PLBOOK/
[2] Г. Бейкер: Qgol (1996). дипломная работа, Университет Маккуори,
http://www.ifost.org.au/~gregb/q-gol/
[3] А. Баренко и др.: Элементарные элементы для квантовых вычислений.
(1995). Phys. Rev. A 52, стр. 3457-3467
[4] Д. Бекман и др.: Эффективные сети для квантового факторинга (1996).
Phys. Rev. A 54, стр. 1034-1063
[5] П.А. Бениофф: Компьютер как физическая система: микроскопическая
квантово-механическая гамильтонова модель компьютеров, представленная
машинами Тьюринга (1980). J. Stat. Phys., 22 (5), стр. 563-591
[6] П.А. Бениофф: Модели квантовых машин Тьюринга (1997). LANL
quant-ph/9708054
[7] К.Х. Беннет: Логическая обратимость вычислений (1973). IBM J.
Res. Development. 17, 525
[8] К.Х. Беннет: Пространственно-временные компромиссы для обратимых вычислений (1989).
СИАМ Дж. Вычисление. 18, стр. 766
[9] Э. Бернштейн, У. Вазирани: Квантовая теория сложности (1997). СИАМ
J. Comput., 26 (5), стр. 1411-1473
[10] С. Блаха: Квантовые компьютеры и квантовые компьютерные языки:
Квантовый язык ассемблера и квантовый язык Си (2002).
LANL quant-ph/0201082
[11] К. Бом и Г. Якопини: Блок-схемы, машины Тьюринга и
языки только с двумя правилами формирования (1966). Взаимодействие
из ACM, Том 9, № 5, стр. 336-371
119
БИБЛИОГРАФИЯ 120
[12] М. Бойер, Г. Брассар, П. Хойер, А. Тапп: Жесткие рамки квантового
поиска (1998). Основы физики, том 46 (4-5), стр. 493-505
[13] П.О., Бойкин и др.: Об универсальных и отказоустойчивых квантовых
вычислениях (1999). LANL quant-ph/9906054
[14] Дж. Брэнсон: Квантовая физика, 130А (2001). конспекты лекций,
http://heppc16.ucsd.edu/ph130a/130a_notes/node15.html
[15] Й. Бухманн: Исследование факторов, влияющих на развитие общества (1996). Спектр дер
Wissenschaft 9/96, стр. 80-88
[16] С.Л. Браунштейн: Квантовые вычисления: учебное пособие (1995).
http://www.informatics.bangor.ac.uk /~schmuel/comp/comp.html
[17] Округ Колумбия Кэссиди: Выставка, посвященная Вернеру Гейзенбергу (1998). Американский
Физический институт
http://www.aip.org/history/heisenberg/p09_text.htm
[18] И.Л. Чжуан и др.: Квантовые вычисления ЯМР: реализация
алгоритма Шора (2001). Nature 414, стр. 883-887
[19] Дж.И. Сирак, П. Золлер: Квантовые вычисления с холодными захваченными ионами
(1995). Физика, статья 74, стр. 4091
[20] Р. Клив, А.Экерт, К. Маккиавелло, М. Моска:
Пересмотр квантовых алгоритмов (1998). Proc. R. Soc., Лондон, A 454, стр. 339-354
[21] Б.Дж. Коупленд: Диссертация Черча-Тьюринга (1996). Стэнфорд
Энциклопедия философии ISSN, стр. 1095-5054
[22] Д. Копперсмит: Приближенное преобразование Фурье, полезное для
квантового разложения на множители (1994). Отчет IBM Research № RC19642
[23] О.Дж. Даль, Э.В. Дейкстра, К.А.Р. Хоар: Структурированное программирование
(1972). Издательство Academic Press, Лондон, Великобритания
[24] Д. Дойч, "Квантовая теория, принцип Черча-Тьюринга и
универсальный квантовый компьютер" (1985). Сборник научных трудов, Лондон, A 400, стр. 97-117

[25] Д. Дойч: Квантовые вычислительные сети (1989). Сборник научных трудов,
Лондон, A 439, стр. 553-558
БИБЛИОГРАФИЯ 121
[26] Д. Дойч и Р. Джозса: Быстрое решение задач с помощью квантового
компьютера (1992). Сборник статей. Soc. Лондон, Сер. A, том 439, стр.
553-558
[27] Э.В. Дейкстра: Структурированное программирование (1969). Разработка программного обеспечения
Методы, Бакстон Дж. Н. и Рэнделл Б., ред. Брюссель, Бельгия,
Научный комитет НАТО.
[28] Д.П. Дивинченцо: Двухбитовые вентили универсальны для квантовых
вычислений (1995). Phys. Rev. A, 51(2), стр. 1015-1022
[29] А. Эйнштейн, Б. Подольский, Н. Розен: Можно ли считать квантово-механическое
описание физической реальности завершенным? (1935). Физический
Обзор 47, стр. 777-780
[30] А. Экерт, Р. Джозса: Квантовый алгоритм Шора для разложения чисел на множители
(1996). Ред. Современная физика 68 (3), стр. 733-753
[31] Р.П. Фейнман: Квантово-механические компьютеры (1985). Новости оптики
, 11, стр. 11-20
[32] Лов К. Гровер: Быстрый квантово-механический алгоритм поиска в базе
данных (1996). Материалы 28-го ежегодного симпозиума ACM по
Теории вычислений
[33] Дж. Груска,: Основы вычислительной техники (1998). парень. 12: “Границы возможного" -
Квантовые вычисления
[34] Г.Х. Харди, Э.М. Райт: Введение в теорию чисел.
Оксфорд (1938). Великобритания: Оксфордский университет. Нажмите

[35] А. Герман: Словарь - справочник по физике от начала и до конца (1978). Aulis-Verlag
Deubner & Co KG
[36] Р.У. Кейс: Миниатюризация электроники и ее пределы (1988). IBM
J. Res. Разработка. 32(1), стр. 24-28
[37] Д. Келпински, К. Монро и Д.Дж. Уайнленд: Архитектура
крупномасштабного квантового компьютера с ионной ловушкой (2002). Nature 417, стр. 709-711
[38] У. Куммер и Р. Траусмут: Квантовая теория (1988). Скриптум цур
Общая информация 131.869
[39] А. Лейч: “Скриптум для изучения", "Алгоритмы, рекурсии и
Теория сложных систем” (1994). Венский технический университет
СПИСОК ЛИТЕРАТУРЫ 122
[40] М. Агравал, Н. Каял, Н. Саксена: ПРОСТЫЕ числа в P (2002). препринт,
http://www.cse.iitk.ac.in/users/manindra/primality.ps
[41] З. Меглицки: Введение в квантовые вычисления (M743) (2002).
http://beige.ucs.indiana.edu/B679/M743.html
[42] Ф.Д. Мурнаган: Унитарные группы и группы вращения (1962). Спартанский
Книги, Вашингтон
[43] М.А. Нильсен и И.Л. Чжуан: Квантовые вычисления и квантовая механика.
Информация (2000). Издательство Кембриджского университета
[44] Б. Омер: Моделирование квантовых компьютеров (1996).
http://www.itp.tuwien.ac.at /~oemer/papers.html
[45] Б. Омер: Процедурный формализм для квантовых вычислений (1998).
магистерская диссертация, Венский технический университет
[46] Б. Омер: Квантовое программирование в QCL (2000). магистерская диссертация,
Венский технический университет
[47] Б. Омер: Процедурное квантовое программирование (2002). Прок от 5-го
Международная конференция CASYS 2001, Д. М. Дюбуа (ред.), Конференция AIP
Материалы 627, с. 276-285
[48] Б. Омер: Классические концепции квантового программирования (2003).
принято к публикации в сборнике материалов конференции QS2002, ЛАНЛ
quant-ph/0211100
[49] Б. Омер: домашняя страница QCL (2003).
http://www.itp.tuwien.ac.at /~oemer/qcl.html
[50] Э.Л. Пост: Конечные комбинаторные процессы - Формулировка 1 (1936).
Журнал символической логики, 1, стр. 103-105
[51] Х. Патнэм: Взгляд философа на квантовую механику (1965). Р.
Холодный (ред.), За гранью определенности: Эссе в современном
Наука и философия, Энглвуд-Клиффс, Нью-Джерси: Прентис-холл,
стр. 130-158.
[52] М. Рек, А. Цайлингер, Х.Дж. Бернштейн, П. Бертани: Экспериментальная
реализация любого дискретного унитарного оператора (1994). Phys. Rev. Lett.,
73 (1), стр. 58-61
БИБЛИОГРАФИЯ 123
[53] М.А. Роу и др.: Перенос квантовых состояний и разделение ионов
в двойной радиочастотной ионной ловушке (2002). Квантовая информация и вычисления, 2,
стр. 257-271
[54] П.У. Шор.: Алгоритмы квантовых вычислений: дискретные логарифмы
и факторинг (1994). Материалы 35-го ежегодного симпозиума по основам
Компьютерные науки, издательство IEEE Press, Лос-Аламитос, Калифорния
[55] Р. Соловей и В. Штрассен: Быстрый тест на простоту методом Монте-Карло
(1977). SIAM Journal on Computing, 1977, стр. 84-85
[56] К. Свозил: Квантовая алгоритмическая теория информации (1996). Journal of
Universal Computer Science, 2, стр. 311-346
[57] Т. Тоффоли: Двунепрерывное расширение обратимых комбинаторных функций
(1981). Математика. Система. Теория 14, стр. 13-23
[58] А. М. Тьюринг: "О вычислимых числах", с приложением к
"Entscheidungsproblem" (1936). Сборник трудов Лондонского математического
Общество, серия 2. том 42, стр. 230-265, http://www.abelard.org/turpap2/tp2-ie.asp

[59] А. М. Тьюринг: Интеллектуальная техника (1948). Национальный физический
Лабораторный отчет. В книге Мельцера Б., Мичи Д. (ред.) 1969. Машина
Intelligence 5. Edinburgh: Издательство Эдинбургского университета., 7
[60] Б. Ванхой: Структурированное программирование, управляющие структуры, if-else
Операторы, псевдокод (1998). APCS-C++, урок 8, ICT
http://www.mvhs.fuhsd.org/bob_vanhoy/pdfs/lesson08.pdf
[61] Дж. Уоллес: Квантовые компьютерные симуляторы (2001). Часть 4-го раздела.
 Конференция CASYS 2000, Д. М. Дюбуа (ред.), Международная
Журнал вычислительных систем опережающего действия, том 10, 2001, стр.
230-245
[62] Дж. Уоллес: Квантовые компьютерные симуляторы (2002). онлайн-опрос,
http://www.dcs.ex.ac.uk/~jwallace/simtable.htm
[63] П. Зулиани: Квантовое программирование (2001). Докторская диссертация,
Оксфордский университет,
Список рисунков
1.1 Программа ;, управляющая машиной M = (S, O, T, ;, ;) . . . . 17
1.2 Представление состояния кубита сферой Блоха |;; . . . . . . . . 21
1.3 Обозначения схем для общих элементов . . . . . . . . . . . . . . . . 37
2.1 Простой вероятностный квантовый алгоритм . . . . . . . . . . . . 52
2.2 Определение четности битовой строки определенной длины 4 . . . . . . . . . . . . . . . . . 53
2.3 Гибридная квантовая архитектура . . . . . . . . . . . . . . . . . . . 57
2.4 Классический компьютер с квантовым оракулом . . . . . . . . . . . . . 58
2.5 Основные структуры управления . . . . . . . . . . . . . . . . . . . . . . 63
2.6 Регистровый оператор U (s) . . . . . . . . . . . . . . . . . . . . . . 71
2.7 Квантовое преобразование Фурье для 4-кубитного регистра . . . . . . . . 79
2.8 Рекурсивное фазовое преобразование . . . . . . . . . . . . . . . . . 80
2.9 Тестовое состояние с 5 кубитами . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.10 Оператор приращения . . . . . . . . . . . . . . . . . . . . . . . . 86
2.11 Оператор условного приращения . . . . . . . . . . . . . . . . . 95
2.12 График вызовов подпрограмм QCL . . . . . . . . . . . . . . . . . . 96
2.13 Квантовый мультиплексор . . . . . . . . . . . . . . . . . . . . . . 102
2.14 Двойное логарифмическое фазовое преобразование . . . . . . . . . . . . . . . . . . . . . 103
2.15 4-кубитный тест на первичность XNF . . . . . . . . . . . . . . . . . . . . 106
124
Список таблиц
1.1 Система счисления Дирака . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Классические и квантовые вычислительные модели . . . . . . . . . . 34
1.3 Регистровая запись . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1 Концепции классического и квантового программирования . . . . . . . . . . 49
2.2 Эквивалентные команды TM и CQTM . . . . . . . . . . . . . 55
2.3 Скалярные арифметические типы и литералы в QCL . . . . . . . . . . . 60
2.4 Квантовые типы данных в QCL . . . . . . . . . . . . . . . . . . . 68
2.5 Регистровые выражения в QCL . . . . . . . . . . . . . . . . . . . 69
2.6 Иерархия подпрограмм . . . . . . . . . . . . . . . . . . . . . 75