Квантовые вычисления: математика и теория для начинающих

0. Обзор курса по квантовым вычислениям [0]

Этот материал представляет собой математическое введение в квантовые вычисления. Он охватывает основы, необходимые для понимания квантовых алгоритмов. [0]

0.1. Структура курса [8]

1. Первый раздел: Основная математика для понимания курса. [9]
   1. Введение в комплексные числа. [9]
   2. Основы линейной алгебры. [9]
2. Второй раздел: Изучение кубита и его математического представления. [9]
   1. Определение кубита. [9]
   2. Операции с одним кубитом и их свойства. [10]
3. Третий раздел: Математическое представление нескольких кубитов. [11]
   1. Операции над несколькими кубитами. [11]
   2. Исследование квантовой запутанности и фазового отката. [12]
4. Четвертый раздел: Анализ квантовых алгоритмов. [13]
   1. Демонстрация революционной технологии квантовых компьютеров. [14]

1. Основы математики: Комплексные числа [15]

1.1. Мнимые числа [15]

1. Необходимо рассмотреть квадратные корни чисел. [15]
2. Уравнение $x^2=4$ дает $x=\pm 2$. [16]
3. Уравнение $x^2=-4$ требует введения мнимых чисел. [17]
4. Определим $i$ как $\sqrt{-1}$. [18]
   1. Тогда $\sqrt{-4}$ можно записать как $\pm 2i$. [18]
5. Мнимое число содержит множитель $\sqrt{-1}$. [19]

1.2. Комплексные числа [20]

1. Комплексное число — это сумма действительного и мнимого числа. [21]
2. Стандартный вид: $a+iB$. [22]
   1. $A$ — действительная часть. [22]
   2. $B$ — мнимая часть. [22]
3. В следующем уроке будет показано представление для моделирования квантовых состояний. [23]

1.3. Операции с комплексными числами [24]

1. Сложение и вычитание: складываем/вычитаем действительные и мнимые части. [24]
2. Умножение: необходимо помнить, что $i^2=-1$. [25]
3. Комплексное сопряжение (обозначается $\ast$): меняет знак мнимой части. [26]
4. Свойство: умножение числа на его сопряженное всегда дает действительное число. [29]
   1. Пример: $(2+3i)(2-3i)$ должно дать действительное число. [30]
5. Графическое представление: комплексное число как вектор на плоскости. [31]
   1. Действительная ось — горизонтальная, мнимая ось — вертикальная. [31]
   2. Например, $-2+3i$ заканчивается в точке $(-2,3)$. [32]

1.4. Модуль и формы комплексных чисел [33]

1. Модуль — это расстояние от начала координат. [33]
   1. Обозначается вертикальными линиями $|a+iB|$. [33]
   2. Вычисляется по теореме Пифагора: $\sqrt{a^2+b^2}$. [34]
2. Полярная форма: представление через модуль ($r$) и угол ($\theta$). [36]
   1. Форма: $r(\cos \theta +i\sin \theta )$. [37]
   2. Угол $\theta =\arctan (B/A)$. [38]
3. Экспоненциальная форма: $r{e}^{i\theta }$. [40]
4. В квантовых вычислениях почти всегда используется экспоненциальная форма. [42]
   1. Изменение $\theta$ соответствует вращению вокруг круга. [43]
   2. Умножение двух комплексных чисел с модулем 1 вращает по единичной окружности. [43]
   3. Это свойство полезно для представления квантовых состояний. [44]

2. Матрицы и их свойства [45]

2.1. Определение и базовые операции с матрицами [45]

1. Матрица — это двумерное расположение чисел. [45]
2. Размерность: $M\times N$ (строки $M$, столбцы $N$). [47]
   1. Приведенный пример — матрица $2\times 3$. [47]
3. Сложение и вычитание: складываются/вычитаются соответствующие элементы. [49]
   1. Матрицы должны иметь одинаковые строки и столбцы для сложения/вычитания. [51]
4. Умножение на скаляр: каждый элемент умножается на скаляр. [53]
5. Умножение матриц: требует скалярного произведения. [55]
   1. Элемент $(1,1)$ новой матрицы — скалярное произведение первой строки левой и первого столбца правой матрицы. [55]
   2. Процесс продолжается для всех элементов. [57]
6. Условие умножения: число столбцов первой матрицы должно быть равно числу строк второй. [59]

2.2. Векторы и преобразования [61]

1. Столбцовый вектор: матрица $n\times 1$. [61]
2. Состояние квантовых вычислений представляется столбцовым вектором. [63]
3. Умножение матрицы на столбец дает новый столбец. [64]
4. Матрица действует как преобразование на векторе. [65]
   1. В квантовых вычислениях матрицы применяются к квантовому состоянию. [67]

2.3. Специальные матрицы и сопряжение [68]

1. Единичная матрица ($I$): нули, кроме единиц на главной диагонали. [68]
   1. Умножение любой матрицы на $I$ возвращает исходную матрицу. [70]
2. Обратная матрица ($A^{-1}$): при умножении на $A$ дает $I$. [72]
   1. Графически: применение $A$, затем $A^{-1}$ возвращает вектор в исходную точку. [74]
3. Комплексное сопряжение матрицы ($A^{\ast }$): меняет знак мнимых компонентов всех элементов. [76]
4. Транспонирование ($A^T$): строки меняются местами со столбцами. [80]
5. Сопряженное транспонирование (Даггер, $A^{†}$): комплексное сопряжение и транспонирование. [82]
6. Унитарные матрицы ($U$): $U{U}^{†}=I$. [84]
   1. Геометрически: длина вектора сохраняется при действии унитарной матрицы. [86]
7. Эрмитовы матрицы ($H$): $H=H^{†}$. [89]

2.4. Собственные векторы и собственные значения [91]

1. Если преобразование растягивает или сжимает вектор, не меняя направления, это собственное преобразование. [91]
2. Собственный вектор — вектор, который остается в том же направлении. [92]
3. Собственное значение ($\lambda$) — скаляр, на который растягивается вектор. [92]
4. Пример: матрица $\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right)$ на вектор $\left(\begin{array}{c}0\\ 3\end{array}\right)$ дает $\left(\begin{array}{c}0\\ 6\end{array}\right)$. [94]
   1. Собственное значение равно 2, собственный вектор $\left(\begin{array}{c}0\\ 3\end{array}\right)$. [96]

3. Математика Кубитов и Суперпозиция [97]

3.1. Кубиты против Битов [97]

1. Классические компьютеры используют нули и единицы (биты). [97]
2. Квантовые компьютеры используют кубиты (могут быть 0 и 1 одновременно). [98]
3. Кубит может быть любой квантовой частицей с двумя состояниями (например, поляризация фотона). [101]
4. В квантовых вычислениях 0 и 1 определяются как столбцовые векторы: [102]
   1. $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$
   2. $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$
5. Скобки $⟨\cdot |\cdot ⟩$ — это нотация Дирака (кет). [103]

3.2. Суперпозиция и измерение [104]

1. Суперпозиция: квантовая частица находится в двух состояниях одновременно. [104]
   1. Кубит в суперпозиции одновременно является 0 и 1. [106]
2. Математическое представление кубита ($\psi$): столбец из двух элементов. [108]
   1. Верхний элемент: вклад в состояние $|0⟩$. [109]
   2. Нижний элемент: вклад в состояние $|1⟩$. [109]
3. Измерение изменяет состояние системы до измеренного. [114]
   1. При измерении кубита получаем либо 0, либо 1. [119]
   2. Состояние коллапсирует до измеренного значения. [117]
4. Амплитуды определяют вероятность измерения. [123]
   1. Вероятность измерения $|0⟩$ — модуль квадрата амплитуды состояния $|0⟩$. [124]
   2. Пример: если $\psi =\left(\begin{array}{c}\sqrt{0.75}\\ \sqrt{0.25}\end{array}\right)$, шанс измерить 0 — 75%. [124]
5. Валидность состояния: вероятности 0 и 1 должны суммироваться в 1. [127]
6. Нотация Дирака: $\alpha |0⟩+\beta |1⟩$. [131]
   1. Кеты $|\cdot ⟩$ обозначают, что это квантовые состояния. [136]
   2. Эта нотация удобнее для систем с большим числом кубитов. [139]

3.3. Блоховская сфера и фаза [140]

1. Кубит можно графически представить на сфере Блоха. [140]
   1. $|0⟩$ — Северный полюс, $|1⟩$ — Южный полюс. [141]
2. Чем выше кубит, тем выше вероятность измерения $|0⟩$. [144]
3. Фаза: вращение кубита вокруг сферы. [147]
4. Пример: состояние $\frac{1}{\sqrt{2}}|0⟩+\frac{\sqrt{3}}{2}|1⟩$ находится ниже экватора. [150]
   1. Вероятность $|0⟩$ равна $1/4$, вероятность $|1⟩$ равна $3/4$. [151]

4. Однокубитные Врата (Операции) [152]

4.1. Врата X, Y, Z [152]

1. В квантовых компьютерах используются врата для изменения состояний кубитов. [153]
2. Врата X: переворачивает $|0⟩$ в $|1⟩$ и наоборот. [155]
   1. Вращает кубит на $180^{\circ }$ ($\pi$ радиан) вокруг оси X. [160]
3. Врата Y: вращает кубит на $\pi$ радиан вокруг оси Y. [163]
4. Врата Z: вращает кубит на $\pi$ радиан вокруг оси Z. [164]
5. Эти три враты являются своими собственными обратными (применение дважды возвращает в исходное положение). [165]
6. Матрицы для этих врат: игнорировать комплексные числа во вратах Y пока. [167]

4.2. Применение врат к кубитам [170]

1. Применение врат: умножение матрицы ворот на столбцовый вектор кубита. [170]
2. Интерпретация матрицы ворот: [173]
   1. Первый столбец: куда переходит состояние $|0⟩$. [173]
   2. Второй столбец: куда переходит состояние $|1⟩$. [173]
3. Линейность: врата действуют на каждое состояние суперпозиции индивидуально. [175]
4. Врата Z: меняет $\alpha |0⟩+\beta |1⟩$ на $\alpha |0⟩-\beta |1⟩$. [179]
   1. Врата Z не влияют на вероятности измерения. [181]
5. Фаза: вращение вокруг оси Z называется фазой. [183]
   1. Фаза важна для мощности квантовых компьютеров. [185]
   2. Фаза математически представляется комплексными числами в экспоненциальной форме. [188]

5. Фаза и Врата, зависящие от Фазы [188]

5.1. Фаза на сфере Блоха [188]

1. Вращение вокруг оси Z соответствует изменению фазы. [193]
2. Множитель $-1$ можно представить как $e^{i\pi }$ (угол $\pi$ радиан). [194]
3. Множитель $i$ можно представить как $e^{i\pi /2}$ (угол $\pi /2$ радиан). [198]
4. Глобальная фаза: умножение всего кубита на комплексное число (физически неважно). [200]
5. Относительная фаза: умножение только амплитуды состояния $|1⟩$ на комплексное число. [201]
   1. Относительная фаза вращает кубит вокруг оси Z. [205]
6. Относительная фаза критически важна для вычислений. [203]
7. Фаза не влияет на вероятность измерения. [206]

5.2. Специальные состояния и Врата [208]

1. Состояния на экваторе (равная вероятность 0 или 1): [212]
   1. Плюс-состояние $|+⟩$: $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$. [216]
   2. Минус-состояние $|-⟩$: $|+⟩$ с относительной фазой $-1$. [218]
   3. I-состояние $|i⟩$: относительная фаза $i$. [219]
   4. Минус I-состояние $|-i⟩$: относительная фаза $-i$. [219]
2. Врата Адамара ($H$): матрица $\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$. [221]
   1. Преобразует $|0⟩$ в $|+⟩$, а $|1⟩$ в $|-⟩$. [222]
   2. $H$ является своим собственным обратным ($H^2=I$). [224]
   3. Врата Адамара показывают важность фазы. [226]
3. Врата S и T: добавляют относительную фазу. [231]
   1. Врата S: добавляет фазу $\pi /2$ ($e^{i\pi /2}$). [232]
   2. Врата T: добавляет фазу $\pi /4$ ($e^{i\pi /4}$). [233]
4. Обратные враты: $S^{†}$ и $T^{†}$ являются обратными к $S$ и $T$. [234]

6. Многокубитные Системы и Схемы [238]

6.1. Тензорное произведение и многокубитные состояния [238]

1. Несколько кубитов представляются через тензорное произведение ($\otimes$). [238]
2. Два кубита в состоянии $|0⟩$ представляются как $|0⟩\otimes |0⟩$. [239]
3. Суперпозиция двух кубитов дает четыре состояния: $|00⟩,|01⟩,|10⟩,|11⟩$. [241]
4. Измерение работает так же: вероятность — модуль квадрата коэффициента. [245]
5. Добавление кубита: тензорное произведение с новым состоянием. [248]
6. Квантовая схема: диаграмма для отображения последовательности операций. [251]
   1. Вертикально — кубиты, слева — начальные состояния. [253]
   2. Квадраты — квантовые врата, стрелки — измерения. [255]
   3. Горизонтально — порядок применения (слева направо). [257]

6.2. Многокубитные Врата [267]

1. CNOT (Controlled-X): действует на два кубита (управляющий и целевой). [268]
   1. Применяет врата X к целевому кубиту, только если управляющий кубит равен $|1⟩$. [272]
2. Врата Тоффоли: имеет два управляющих кубита. [275]
3. Управляемые версии однокубитных врат (Y, Z, S, T, H) существуют. [279]
   1. Они применяют врата, если управляющий кубит равен $|1⟩$. [279]
4. Измерение одного кубита в многокубитной системе: [282]
   1. Суммируются вероятности всех состояний, где этот кубит равен $|1⟩$. [282]
5. Коллапс после измерения: [285]
   1. Если измеряется $|1⟩$, удаляются все состояния, где этот кубит не $|1⟩$. [287]
   2. Состояние нормализуется константой $A$. [289]

6.3. Запутанность и Фазовый Откат [302]

1. Запутанность: состояние нельзя факторизовать в тензор отдельных кубитов. [303]
   1. Пример: $\frac{1}{\sqrt{2}}(|00⟩+|11⟩)$ — запутанное состояние. [309]
2. Максимально запутанные состояния (Состояния Белла): измерение одного кубита определяет состояние других. [308]
3. Частично запутанные состояния: измерение одного кубита влияет на вероятности/фазу других. [311]
4. Фазовый откат (Phase Kickback): [313]
   1. Если целевой кубит $|V⟩$ является собственным вектором управляемых врат $U$, то: [317]
   2. Фаза $e^{i\theta }$ применяется к управляющему кубиту. [323]
   3. Это происходит, если $|V⟩$ — собственный вектор $U$. [325]

6. Квантовые Протоколы и Обратимость [326]

6.1. Суперплотное кодирование [326]

1. Протокол позволяет отправить два бита классической информации, используя один кубит. [327]
2. Требуется предварительная запутанность двух кубитов (Алиса и Боб берут по одному). [329]
3. Алиса применяет операции к своему кубиту в зависимости от отправляемых 2 бит: [334]
   1. 00: ничего не делает. [335]
   2. 01: применяет врата X. [336]
   3. 10: применяет врата Z. [337]
   4. 11: применяет врата X и Z. [338]
4. Боб применяет CNOT (первый кубит — управление), затем Адамар к первому кубиту. [341]
5. Измерение кубитов дает Бобу исходные два бита Алисы. [344]

6.2. Обратимые Классические Операции [347]

1. Классические операции: AND, OR, NOT, XOR. [348]
2. NOT: простейшая, меняет 0 на 1 и 1 на 0. [350]
3. AND: возвращает 1, только если оба входа равны 1. [353]
4. OR: возвращает 1, если хотя бы один вход равен 1. [356]
5. XOR (исключающее ИЛИ): возвращает 1, если входы различны. [358]
6. Обратимая функция: если по выходу $F(x)$ можно определить вход $x$. [362]
   1. OR необратима (выход 1 соответствует трем разным входам). [363]
7. Сделать классический вентиль обратимым: добавить дополнительный бит $C$. [365]
   1. Возвращать $X$ и $C\oplus F(X)$. [365]
   2. Пример: обратимый OR возвращает $X$ и $C\oplus (X_1\vee X_2)$. [367]
8. Квантовые операции (кроме измерения) должны быть обратимыми (унитарными). [371]

7. Применение Функций и Фазовый Оракул [374]

7.1. Квантовое применение функций [374]

1. Квантовые функции должны быть унитарными (обратимыми). [377]
2. Квантовая функция $f$ кодируется в унитарной матрице $U_f$. [384]
3. Стандартное применение: вход $X,Y$ преобразуется в $X,Y\oplus f(X)$. [379]
   1. Если $Y=0$, выход становится $X,f(X)$. [381]
4. Фазовый оракул: функция применяется к состоянию $|x⟩|-⟩$. [399]
   1. Выход: $-1^{f(x)}|x⟩|-⟩$. [398]
   2. Если $f(x)=0$, состояние $\frac{1}{\sqrt{2}}(|x0⟩-|x1⟩)$. [392]
   3. Если $f(x)=1$, состояние $\frac{1}{\sqrt{2}}(|x0⟩-|x1⟩)$ с фазой $-1$. [393]

7.2. Теорема о запрете клонирования [401]

1. Невозможно скопировать кубит в неизвестном состоянии $\alpha |0⟩+\beta |1⟩$. [401]
2. Копирование возможно, только если известны амплитуды $\alpha$ и $\beta$. [403]

8. Алгоритм Дойча (Deutsch's Algorithm) [405]

8.1. Постановка задачи [405]

1. Задача: дана функция $f:\{0,1\}\to \{0,1\}$. [406]
2. Определить, является ли $f$ постоянной (всегда один и тот же выход) или сбалансированной (половина входов дают 0, половина — 1). [410]
3. Классический компьютер требует двух запросов ($f(0)$ и $f(1)$). [418]
4. Алгоритм Дойча решает задачу за один запрос. [421]

8.2. Схема алгоритма Дойча [422]

1. Начало: кубиты в состоянии $|00⟩$. [424]
2. Шаг 1: применяем Адамар к обоим кубитам: $|+⟩|-⟩$. [425]
3. Шаг 2: применяем фазовый оракул $U_f$. [428]
   1. Состояние переходит в $\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ с фазой $-1^{f(0)}$ и $\frac{1}{\sqrt{2}}(|1⟩-|0⟩)$ с фазой $-1^{f(1)}$. [430]
4. Результат после оракула: [433]
   1. Если $f(0)=f(1)$ (постоянная): состояние $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$ (состояние $|+⟩$). [434]
   2. Если $f(0)\ne f(1)$ (сбалансированная): состояние $\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ (состояние $|-⟩$). [438]
5. Шаг 3: применяем Адамар к первому кубиту. [441]
   1. Постоянная функция $\to$ состояние $|0⟩$. [442]
   2. Сбалансированная функция $\to$ состояние $|1⟩$. [442]
6. Измерение: $|0⟩$ означает постоянную, $|1⟩$ означает сбалансированную. [444]

9. Алгоритм Дойча-Йожи (Deutsch-Jozsa Algorithm) [447]

9.1. Обобщение задачи [447]

1. Алгоритм решает ту же задачу, но для функции $f$, принимающей любое число битов ($n$ бит). [447]
2. Постоянная функция: всегда возвращает одно и то же значение. [449]
3. Сбалансированная функция: возвращает 0 для половины входов и 1 для другой половины. [451]
4. Классическое решение: в худшем случае требуется $2^{n-1}+1$ запросов. [454]
5. Квантовое решение: требуется только один запрос функции. [459]

9.2. Схема алгоритма Дойча-Йожи [460]

1. Шаг 1: $N$ кубитов в $|0{⟩}^{\otimes N}$, затем применяем $N$ врат Адамара. [461]
2. Важная идентичность: применение $N$ Адамаров к $|0{⟩}^{\otimes N}$ дает равную суперпозицию всех $2^N$ битовых строк $X$. [474]
3. Шаг 2: применяем оракул $U_f$ (фазовый оракул, так как целевой кубит в $|-⟩$). [479]
   1. Состояние принимает вид: $\frac{1}{\sqrt{2^N}}{\sum }_X(-1{)}^{f(X)}|X⟩$. [482]
4. Шаг 3: применяем Адамар к каждому из $N$ кубитов. [484]
   1. Важная идентичность: Адамар на произвольной строке $X$ дает $\frac{1}{\sqrt{2^N}}{\sum }_Z(-1{)}^{X\cdot Z}|Z⟩$. [496]
5. Шаг 4: измеряем кубиты. [512]

9.3. Анализ результата [499]

1. Амплитуда нулевого состояния $|0{⟩}^{\otimes N}$: [500]
   1. Если $f(X)$ постоянна (равна $c$): амплитуда равна $\pm 1$. [507]
   2. Если $f(X)$ сбалансирована: амплитуда равна 0. [511]
2. Измерение: [512]
   1. Измерение $|0{⟩}^{\otimes N}$ $\to$ функция постоянная. [514]
   2. Измерение любого другого состояния $\to$ функция сбалансированная. [515]

10. Алгоритм Бернштейна-Вазирани (Bernstein-Vazirani) [520]

10.1. Постановка задачи и классическое решение [520]

1. Задача: дана функция $f(X)=X\cdot S(\mathrm{mod}2)$, где $S$ — секретная строка длины $n$. [521]
2. Цель: найти секретную строку $S$. [522]
3. Классический подход: требуется $n$ запросов, используя базисные векторы (один 1 в $X$). [523]
4. Квантовый подход: требуется один запрос функции. [526]

10.2. Схема алгоритма Бернштейна-Вазирани [527]

1. Схема похожа на алгоритм Дойча, но целевой кубит инициализируется в $|-⟩$. [527]
2. Шаг 1: Инициализация в $|X⟩|-⟩$, где $|X⟩=|0{⟩}^{\otimes n}$. [529]
3. Шаг 2: Применение оракула $U_f$ (фазовый оракул). [531]
   1. Состояние: $\frac{1}{\sqrt{2^n}}{\sum }_X(-1{)}^{X\cdot S}|X⟩$. [534]
4. Шаг 3: Применение Адамара ко всем $n$ кубитам. [535]
   1. Применяется идентичность Адамара к $|X⟩$. [536]
   2. Результирующая амплитуда для состояния $|Z⟩$ зависит от $S\oplus Z$. [540]
5. Шаг 4: Измерение кубитов. [541]
6. Результат: вероятность измерения состояния $|S⟩$ равна единице. [547]
   1. Измерение дает секретную строку $S$ за один запрос. [549]

11. Квантовое Преобразование Фурье (QFT) [553]

11.1. Интуиция QFT [553]

1. QFT используется во многих алгоритмах, включая алгоритм Шора. [553]
2. Преобразование: кодирует числа в фазе кубитов в равномерной суперпозиции. [556]
3. Если $N$ — число кубитов, последний кубит имеет $2^N$ фазовых опций. [560]
4. Кодирование числа $J$: [563]
   1. Правый кубит вращается на $\frac{J}{2^N}\cdot 2\pi$ радиан. [564]
   2. Следующий кубит вращается на $2\times$ предыдущий угол. [565]
5. Если $|J⟩$ — двоичное представление числа, QFT дает состояние, закодированное фазами. [566]

11.2. Схема QFT и Математика [568]

1. Схема QFT включает управляемые врата R и врата перестановки (swap). [569]
2. Управляемые врата R ($R_k$): применяют фазу $e^{2\pi i/2^k}$ к $|1⟩$. [571]
3. Врата перестановки (swap): меняет местами состояния двух кубитов. [575]
4. Пример с тремя битами ($J=j_2 j_1 j_0$): [577]
   1. Последовательное применение Адамара и управляемых врат $R_k$ кодирует $J$ в фазу. [580]
   2. В конце применяется перестановка для упорядочивания фаз. [590]
5. Общая формула QFT: [594]

$$\text{QFT}|J⟩=\frac{1}{\sqrt{2^n}}\sum _{K=0}^{2^n-1}{e}^{2\pi i\frac{JK}{2^n}}|K⟩$$

1. Обратное QFT отменяет преобразование, возвращая исходное состояние $|J⟩$. [595]

12. Оценка Квантовой Фазы (QPE) [597]

12.1. Цель QPE [597]

1. Алгоритм QPE находит собственное значение ($\lambda =e^{i\theta }$) собственного вектора ($V$) матрицы $U$. [597]
2. QPE находит $e^{i\theta }$ с заданной точностью. [599]
3. Алгоритм является ключевой частью алгоритма Шора. [600]
4. Схема QPE использует два регистра: [601]
   1. Первый регистр ($M$ нулей): хранит оценку фазы. [602]
   2. Второй регистр ($N$ кубитов): собственный вектор $V$. [602]

12.2. Схема QPE и Фазовый Откат [603]

1. Шаг 1: Инициализация в $|0{⟩}^{\otimes M}|V⟩$. [607]
2. Шаг 2: Применение Адамара ко всем кубитам первого регистра. [607]
3. Шаг 3: Применение управляемых врат $U^{2^k}$ к $V$. [608]
   1. При $k$-м кубите применяется $U^{2^k}$. [603]
   2. Фазовый откат добавляет фазу $e^{i{2}^k\theta }$ к $k$-му кубиту. [609]
4. Результат: первый регистр содержит состояние, пропорциональное $|J⟩$, где $J$ — двоичное представление $\theta /2\pi$. [613]
5. Шаг 4: Применение обратного QFT к первому регистру. [605]
6. Шаг 5: Измерение первого регистра дает $J$ с точностью до $M$ бит. [624]
   1. $\theta$ находится как $2\pi J$. [625]

13. Алгоритм Шора (Shor's Algorithm) [626]

13.1. Задача и Теория Чисел [626]

1. Задача: найти простые множители большого числа $N=PQ$. [627]
2. Алгоритм использует как классические, так и квантовые шаги. [631]
3. Классический шаг 1: Выбрать $A$ такое, что $\text{НОД}(A,N)=1$. [632]
4. Теория чисел: сведение задачи к нахождению периода $R$ модулярного возведения в степень. [634]
   1. $A^R\equiv 1(\mathrm{mod}N)$. [640]
5. Квантовый шаг: использование QPE для нахождения периода $R$. [644]
   1. Если $R$ найден, множители $P$ и $Q$ находятся через $\text{НОД}(A^{R/2}\pm 1,N)$. [643]

13.2. Квантовое нахождение периода $R$ [645]

1. Требуется унитарный гейт $U$, преобразующий $|x⟩\to |xA(\mathrm{mod}N)⟩$. [645]
2. Состояние $|1⟩$ является собственным вектором $U$ с собственным значением $e^{2\pi iS/R}$. [653]
3. Конструкция состояния: создается суперпозиция всех $|U^S⟩$ состояний. [655]
   1. Состояние $\frac{1}{\sqrt{R}}{\sum }_{S=0}^{R-1}|U^S⟩$ является собственным вектором. [660]
4. Применение QPE: используется для оценки собственного значения $e^{2\pi iS/R}$. [662]
5. Результат QPE: получаем десятичное число $J\approx S/R$. [666]

13.3. Нахождение $R$ и Факторизация [667]

1. Оценка $S$ и $R$: используется метод непрерывных дробей для аппроксимации $J$. [667]
2. Выбирается аппроксимация, где знаменатель (кандидат на $R$) меньше $N$. [673]
3. Факторизация: используя найденное $R$: [675]
   1. Вычисляем $\text{НОД}(A^{R/2}-1,N)$ и $\text{НОД}(A^{R/2}+1,N)$. [679]
4. Пример $N=15$ ($P=3, Q=5$): [681]
   1. Выбираем $A=7$. [683]
   2. Квантовая часть находит период $R=4$. [685]
   3. $\text{НОД}(7^{4/2}-1,15)=\text{НОД}(48,15)=3$. [687]
   4. $\text{НОД}(7^{4/2}+1,15)=\text{НОД}(50,15)=5$. [688]
   5. Множители найдены: 3 и 5. [689]