Единственное нетривиальное использование квантовых свойств для вычислений, которое мы уже рассмотрели, — это решение универсальной переборной задачи алгоритмом Гровера, изложенным в лекции 8. К сожалению, при этом достигается лишь полиномиальное ускорение. Поэтому никаких серьезных следствий для теории сложности вычислений (типа $$\BQP\supset \BPP$$ ) алгоритм Гровера не дает. В настоящее время нет доказательства того, что квантовые вычисления превосходят по скорости классические вероятностные. Но есть косвенные свидетельства в пользу такого утверждения. Первое из них — пример задачи с оракулом (т.е. процедурой типа "
Задача о скрытой
Задача о скрытой подгруппе в $$(\ZZ_2)^k$$.
Мы рассмотрим сформулированную выше задачу в случае $$G=(\ZZ_2)^k$$. Элементы этой группы
можно представлять строками длины $$k$$ из нулей и единиц; групповая операция — побитовое сложение по модулю 2.
Легко доказать, что нельзя быстро найти "скрытую
Утверждение 12.1. Пусть $$n\ge k$$. Для любого классического вероятностного алгоритма, делающего не более $$2^{k/2}$$ обращений к оракулу, существует
Доказательство. Для одной и той же подгруппы $$D$$ существует несколько различных оракулов $$f$$. Мы будем считать, что один из них выбирается случайно и равновероятно. (Если алгоритм ошибается с вероятностью $$>\slashfrac{1}{3}$$ при случайном оракуле, то он также будет ошибаться с вероятностью $$>\slashfrac{1}{3}$$ при каком-нибудь конкретном оракуле.) Случайный оракул обладает следующим свойством: если очередной ответ $$y_j$$ не совпадает ни с одним из предыдущих ответов $$y_1,\dots,y_{j-1}$$, то он равномерно распределен на множестве $$\cb^n\backslash\{y_1,\dots,y_{j-1}\}$$. Таким образом, случайный оракул эквивалентен устройству с памятью, которое на вопрос $$x_j$$ выдает наименьшее число $$s_j\le j$$, такое что $$x_j-x_{s_j}\in D$$. Классическую машину можно изменить таким образом, что она сама будет производить случайный выбор $$y_j\double\in\cb^n\backslash\{y_1,\dots,y_{j-1}\}$$, когда $$s_j=j$$.
Пусть число вопросов к оракулу равно $$l\le 2^{k/2}$$. Без уменьшения общности все вопросы различны. В случае $$D=\{0\}$$ все ответы также различны, то есть $$s_j=j$$ для всех $$j$$. Теперь рассмотрим случай $$D\double=\{0,z\}$$, где $$z$$ выбирается случайно с равномерным распределением на множестве всех ненулевых элементов группы $$(\ZZ_2)^k$$. Тогда, независимо от используемого алгоритма, $$s_j=j$$ c вероятностью $$\ge 1-\slashfrac{(j-1)}{(2^k-1)}$$. С вероятностью $$\ge1-\slashfrac{l(l-1)}{(2(2^k-1))}>\slashfrac{1}{2}$$ это имеет место для всех $$j=1,\dots,l$$. Напомним, что у нас есть два случайных параметра: $$z$$ и $$r$$. Мы можем зафиксировать $$z$$ таким образом, чтобы вероятность получения ответов $$s_j=j$$ (для всех $$j$$ ) по-прежнему была больше $$\slashfrac{1}{2}$$. Посмотрим, что будет делать классическая машина в этом случае. Если она выдает ответ " $$D=\{0\}$$ " с вероятностью $$\ge\slashfrac{2}{3}$$, положим $$D=\{0,z\}$$ — тогда выдаваемый ответ будет неверным с вероятностью $$>(\slashfrac{2}{3})\cdot(\slashfrac{1}{2})=\slashfrac{1}{3}$$. Если же вероятность ответа " $$D=\{0\}$$ " меньше $$\slashfrac{2}{3}$$, положим $$D=\{0\}$$.
Теперь определим квантовый аналог описанного выше устройства. Соответствующий квантовый оракул — это унитарный оператор$$\begin{equation}\label{кв-оракул} U\colon \ket{x,y}\,\mapsto\,\ket{x,\,y\oplus f(x)}. \end{equation}$$
( $$\oplus$$ обозначает побитовое сложение). Заметим, что квантовый оракул допускает
Пусть $$Е=G/D$$, а $$E^*$$ — группа характеров на $$E$$, т.е. гомоморфизмов $$E\to U(1)$$. В случае $$G=(\ZZ_2)^k$$ группу $$E^*$$ можно охарактеризовать следующим образом:$$E^*= \{h \in(\ZZ_2)^k: \forall\, z\in(\ZZ_2)^k\: (h\cdot z=0) \},$$
где $$h\cdot z$$ обозначает
Начнем с того, что приготовим состояние $$\ket{\xi}=2^{-k/2}\sum_{x\in G}\ket{x}=H^{\otimes k}\ket{0^k}$$ в одном квантовом регистре. Во второй регистр поместим состояние $$\ket{0^n}$$ и применим оператор $$U$$. Затем выбросим второй регистр, т.е. не будем его больше использовать. Получится смешанное состояние$$\rho \,=\, \Tr_2\Bigl(U(\ket{\xi}\bra{\xi}\otimes\ket{0^n}\bra{0^n})U^\dagger \Bigr)\,=\, 2^{-k}\,\sum_{x,y:x-y\in D}\ket{x}\bra{y}.$$ Теперь применим оператор $$H^{\otimes k}$$:$$\gamma \,=\, H^{\otimes k}\rho H^{\otimes k} \,=\, 2^{-2k} \sum_{a,b}\sum_{x,y:x-y\in D} (-1)^{a\cdot x-b\cdot y}\ket{a}\bra{b}.$$ Легко видеть, что величина $$\sum\limits_{x,y:x-y\in D}(-1)^{a\cdot x-b\cdot y}$$ отлична от нуля только в том случае, когда $$a=b\in E^*$$. Таким образом,$$\gamma = \frac{1}{|E^*|} \sum_{a\in Е^*} \ket{a}\bra{a}.$$ Это в точности матрица плотности для случайного равномерно распределенного элемента группы $$E^*$$. Теперь осталось воспользоваться следующей леммой, которую мы сформулируем в виде задачи.
Задача 12.1. Пусть $$h_1,\dots,h_l$$ — независимые случайные равномерно распределенные элементы абелевой группы $$X$$. Докажите, что они порождают всю группу $$X$$ c вероятностью $$\ge 1-\slashfrac{|X|}{2^l}$$.
Таким образом, достаточно $$2k$$ случайных элементов, чтобы породить всю группу $$E^*$$ с вероятностью ошибки $$\le 2^{-k}$$. (Такая маленькая вероятность ошибки получается без особых затрат по сравнению с $$\slashfrac{1}{3}$$. Чтобы сделать ее еще меньше, эффективнее всего воспользоваться стандартной процедурой: повторить все вычисление несколько раз и выбрать наиболее часто встречающийся ответ).
Подведем итог: для нахождения "скрытой подгруппы" $$D$$ требуется $$O(k)$$ обращений к квантовому оракулу. В целом алгоритм имеет сложность $$O(k^3)$$.
Второе свидетельство в пользу гипотезы $$\BQP\supset\BPP$$ — быстрые квантовые алгоритмы разложения числа на простые множители и вычисления
Факторизация числа. Дано натуральное число $$y$$. Требуется найти его разложение на простые множители$$y=p_1^{\alpha_1}p_2^{\alpha_2}\cdot\ldots\cdot p_k^{\alpha_k}.$$
Эта задача считается сложной настолько, что на предположении о трудности ее решения основываются практические алгоритмы криптографии. С теоретической точки зрения положение несколько хуже: неизвестно ни сведение к задаче факторизации задач из класса
Мы будем строить быстрый квантовый алгоритм не для решения задачи факторизации, а для решения другой задачи Нахождение периода, к которой задача факторизации сводится с помощью классического вероятностного алгоритма.
Нахождение периода. Имеется число $$q$$, записывающееся не более чем $$n$$ двоичными цифрами ( $$1\leq q < 2^n$$ ) и число $$a$$ такое, что $$a<q$$, $$(a,q)=1$$ ( $$(a,q)$$ обозначает наибольший общий
Другими словами, период — это порядок числа $$a$$ в мультипликативной группе
Ниже мы построим квантовый алгоритм для решения задачи о нахождении периода числа. Но начнем с того, что опишем классическое вероятностное сведение задачи факторизации к задаче вычисления периода. Читателю также предлагается вспомнить вероятностный тест простоты числа, изложенный в первой части (см. лекцию 3).
Итак, предположим, что мы умеем решать задачу нахождения периода. Ясно, что
Вход: число $$y$$.
Шаг 1. Проверяем
Шаг 2. Проверяем, извлекается ли из $$y$$ нацело корень $$k$$ -й степени при $$k=2,\dots,\log_2y$$. Если $$y=m^r$$, то ответ " $$m$$ ", иначе переходим к шагу 3.
Шаг 3. Выбираем случайное $$a$$ среди чисел от $$1$$ до $$y$$, вычисляем $$r=\per_y(a)$$ (используя имеющийся по предположению алгоритм нахождения периода) и, если $$r$$ — нечетное, то ответ " $$y$$ — простое". В противном случае находим $$d=(a^{r/2}-1,y)$$ (скажем,
Шаг 4. Если $$d>1$$, то ответ " $$d$$ ", в противном случае ответ " $$y$$ — простое".
Докажем, что вероятность получить
Если $$r=\per_y(a)$$ — четное, то $$(a^{r/2}+1)(a^{r/2}-1)\equiv0\pmod y$$. Так что в этом случае процедура выдаст ответ " $$y$$ — простое" только тогда, когда $$a^{r/2}\equiv-1\pmod y$$.
Запишем разложение $$y$$ на простые множители $$y=\prod_{j=1}^{k}p_j^{\alpha_j}$$ и введем обозначения$$a_j\equiv a\pmod{p_j^{\alpha_j}}, \quad r_j=\per_{(p_j^{\alpha_j})} a_j= 2^{s_j}r'_j, \text{ где } r'_j\ \text{--- нечетноe}.$$
Докажем, что процедура выдает ответ " $$y$$ — простое" тогда и только тогда, когда $$s_1=s_2=\ldots=s_k$$. Действительно, если $$s_1=s_2=\ldots\double=s_k=0$$, то $$r$$ нечетно (поскольку $$r$$ — наименьшее общее кратное всех $$r_j$$ ). Если $$s_1=s_2=\ldots=s_k\geq1$$, то $$a_j^{r_j/2}\equiv-1\pmod{p_j^{\alpha_j}}$$ (используем цикличность $$(\ZZ/p_j^{\alpha_j}\ZZ)^*$$ ), а, значит, и $$a^{r/2}\equiv-1\pmod{y}$$ (используем китайскую теорему об остатках). Наоборот, если не все $$s_j$$ равны, то при некотором $$m$$ получим $$a_m^{r/2}\equiv1\pmod{p_m^{\alpha_m}}$$, т.е. $$a^{r/2}\not\equiv-1\pmod{y}$$.
По китайской теореме об остатках случайный равномерный выбор $$a$$ есть то же самое, что независимый случайный равномерный выбор всех $$a_j$$. Оценим для некоторого $$s$$ вероятность события $$s_1=s$$ при независимом выборе $$a_1$$. Пусть $$p_1^{\alpha_1}-1=2^tq$$, где $$q$$ — нечетное, $$g$$ — образующая (циклической) группы $$(\ZZ/p_1^{\alpha_1}\ZZ)^*$$. Тогда$$|\{a_1: s_1=s\}| = |\{g^{2^{t-s}m}: m\ \text{--- нечетное}\}| = \left\{\begin{array}{@{\hskip2pt}cl} q, \text{если } s=0,\\ (2^s-2^{s-1})q, \text{если } s>0, \end{array}\right.$$
поэтому вероятность $$s_1=s$$ не больше $$\slashfrac{1}{2}$$. Отсюда следует искомая оценка вероятности успеха всей процедуры нахождения
Рассмотрим оператор умножения
Поскольку для умножения
Перестановка, которую задает оператор $$U_a$$, разбивается на циклы. Цикл, содержащий $$a$$, содержит и $$1$$ (после $$\per_q(a)-1$$ итераций мы попадаем из $$a$$ в $$1$$ ). Алгоритм, о котором пойдет речь, начинает с состояния $$\ket1$$ и применяет к нему оператор $$U_a$$ по многу раз. Но за пределы орбиты $$a$$ (цикла перестановки, которому принадлежит $$a$$ ) мы такими преобразованиями не выйдем. Поэтому рассмотрим ограничение оператора $$U_a$$ на подпространство, порожденное орбитой $$a$$.
Легко проверить, что написанные векторы действительно собственные. Достаточно заметить, что умножение на $$a$$ приводит к сдвигу индексов в сумме. Если заменить переменную суммирования, чтобы устранить этот сдвиг, получим множитель $$e^{2\pi\ii\cdot k/t}$$.
Если бы мы могли измерять
Пусть у нас есть машина $$M$$, которая при каждом запуске выдает нам число $$k/t$$, где $$t$$ — искомый период, а $$k$$ — равномерно распределенное на множестве $$\{0,\dots,t-1\}$$ случайное число. Мы предполагаем, что $$k/t$$ представлено в виде несократимой дроби $$k'/t'$$ (если бы машина выдавала число в виде $$k/t$$, то вообще не было бы проблем).
Получив несколько дробей такого вида $$k_1'/t_1',\,k_2'/t_2',\dots,k_l'/t_l'$$, можно с большой вероятностью найти число $$t$$, приводя эти дроби к общему знаменателю.
Лемма. Если получено $$l$$ дробей, то вероятность того, что наименьшее общее кратное их знаменателей отлично от $$t$$, меньше $$3\cdot2^{-l}$$.
Доказательство. Дроби $$k_1'/t_1',\dots,k_l'/t_l'$$ получаются сокращением дробей $$k_1/t,\dots,k_l/t$$ (т.е. $$k_j'/t_j'=k_j/t$$ ), где $$k_1,\dots,k_l$$ — независимо распределенные случайные числа. Достаточно, чтобы эти числа были в совокупности взаимно просты, тогда наименьшее общее кратное $$t_1',\dots,t_l'$$ будет равно $$t$$.
Вероятность того, что $$k_1,\dots,k_l$$ имеют общий простой
Теперь будем строить машину $$M$$. Она должна содержать схему, измеряющую
Задача 12.2. Используя оператор $$U$$, реализуйте оператор $$\Lambda(U_b)$$ для любого $$b$$, взаимно простого с $$q$$.
Обозначим $$\calL_{a,k}=\CC(\ket{\xi_{a,k}})$$ (подпространство, порожденное $$\ket{\xi_{a,k}}$$ ), тогда искомая схема должна реализовывать измеряющий оператор $$W=\sum\limits_{k=0}^{t-1}V_{a,k}\otimes\Pi_{\calL_{a,k}}$$ с операторами $$V_{a,k}$$ вида $$\ket{0}\mapsto\sum_{y,z}c_{y,z}\ket{y,z}$$, где $$y$$ — некоторая несократимая дробь, а $$z$$ — мусор. При этом для
Построение такой измеряющей схемы довольно сложное, поэтому вначале объясним, как из нее строится машина $$M$$. Возьмем состояние $$\ket1$$ в качестве начального. Прямое вычисление (читателю рекомендуется его проделать) показывает, что$$\ket1= \frac{1}{\sqrt{t}}\sum_{k=0}^{t-1}\ket{\xi_k}.$$
Это равенство гарантирует равномерное распределение
Вероятности всех $$\ket{\xi_k}$$ равны: $$\PP(\ket{1},\calL_k)=\left| \langle \xi_k|1\rangle \right|^2=\slashfrac1t$$, а указанное выше свойство
Условно работу машины $$M$$ можно представить в виде такого процесса:
(Cлучайный выбор $$k$$ происходит сам по себе, без применения какого бы то ни было оператора. Просто формула полной вероятности устроена так, как будто до начала измерения генерируется случайное $$k$$, которое затем остается постоянным. Разумеется, формула условной вероятности верна только тогда, когда оператор $$W$$ является измеряющим для заданных подпространств $$\calL_{a,k}$$ ).
Теперь будем строить оператор, измеряющий
В лекции 11 был введен оператор $$\Xi(U_a)\double=(H\otimes I)\Lambda(U_a)(H\otimes I)$$, измеряющий
Нам потребуется еще оператор $$\Xi(\ii U_a)$$. Его также нетрудно реализовать. Реализация, изображенная на рисунке, использует оператор $$K\double=\begin{pmatrix} 10\\0\ii\end{pmatrix}$$ из стандартного базиса. Обведенный фрагмент реализует оператор $$\Lambda(\ii U_a)$$. Действительно, $$K$$ умножает на $$\ii$$ только $$\ket1$$, но как раз в этом случае применяется оператор $$U_a$$ (по определению оператора $$\Lambda(U_a)$$ ). Для оператора $$\Xi(\ii U_a)$$
Сложность реализации операторов $$\Xi(U_a)$$ и $$\Xi(\ii U_a)$$ зависит от сложности реализации оператора $$\Lambda(U_a)$$, которая ненамного выше сложности реализации оператора $$U_a$$ (см. задачу 12.2).
Мы будем локализовывать значение $$\ph_k$$, оценивая
У нас есть квантовый регистр $$A$$, в котором находится $$\ket{\xi_{a,k}}$$. (На самом деле там вначале был$$\ket1=\frac{1}{\sqrt{t}}\sum_{k=0}^{t-1}\ket{\xi_k},$$ но мы рассматриваем $$\ket{\xi_{a,k}}$$ по отдельности; это корректно в силу вида измеряющего оператора). Заведем большое количество ( $$s$$ штук) вспомогательных регистров длиной в 1 бит. Каждый из этих регистров будет использоваться для применения оператора $$\Xi(U_a)$$.
Как было доказано в лекции 11,
Далее с битами, в которых записаны результаты "экспериментов", будут уже производиться классические действия. Поскольку
Если монета брошена $$s$$ раз, то доля выпавших единиц $$(\sum y_r)/s$$ примерно равна $$\PP(1\big| k)$$. С какой точностью верна такая оценка? Из теории вероятностей известно, что$$\Prob\left[\left|\frac{\sum\nolimits_{r=1}^{s}y_r}{s}-\PP(1\big|k)\right| >\delta\right]<2e^{-c\delta^{2}s},$$ где $$c>0$$ — некоторая константа. Это показывает, что при любом фиксированном $$\delta$$ можно добиться вероятности ошибки $$\eps$$ за $$O(\log(1/\eps))$$ испытаний.
Итак, мы научились находить с некоторой точностью $$\delta$$ синус и косинус от $$\ph_k$$. Теперь подберем $$\delta$$ таким, чтобы значение $$\ph_k$$ можно было установить по значениям синуса и косинуса с точностью $$1/8$$. На этом второй этап завершен.
Для увеличения точности мы будем использовать, наряду с $$\Lambda(U_a)$$, операторы $$\Lambda((U_a)^{2^j})$$ для всех $$j\le 2n$$. Числа мы можем быстро возводить в степень, а операторы, вообще говоря, — нет. Но оператор умножения на число $$U_a$$ обладает следующим замечательным свойством:$$(U_a)^p = U_{a^p\bmod q}.$$ Следовательно, $$\Lambda((U_a)^{2^j})=\Lambda(U_b)$$, где $$b\equiv a^{2^j}\pmod q$$. Нужные нам значения параметра $$b$$ можно вычислить при помощи схемы полиномиального размера, а затем использовать результат задачи 12.2.
Вход: $$a$$ и $$q$$
Ответ: $$t$$ (с вероятностью ошибки $$<3\cdot 2^{-l}+4nle^{-cs}$$, где $$c={\rm const}$$ )
Вернемся к схеме упоминаемой ранее. Мы находили собственное число $$\lambda_k=e^{2\pi\ii\ph_k}$$ для некоторого собственного вектора $$\ket{\xi_{a,k}}$$. Этот же вектор останется собственным и для любой степени оператора $$U_a$$, поэтому можно на одном и том же квантовом регистре искать собственное число для $$U_a^2=U_{a^2}$$, оно равно $$\lambda_k=e^{2\pi\ii2\ph_k}$$ ; для $$U_a^4=U_{a^4}$$ оно равно $$\lambda_k\double=e^{2\pi\ii4\ph_k}$$ ;...
Другими словами, мы можем с точностью $$1/8$$ определить значения $$\ph_k, 2\ph_k, \dots, 2^{2n}\ph_k$$ по модулю 1. Но это позволяет определить $$\ph_k$$ с точностью $$1/2^{2n+1}$$ за полиномиальное время .
Идея доказательства. Множество возможных значений $$\ph_k$$ удобно представлять в виде окружности единичной длины. Зная $$\ph_k$$ с точностью $$1/8$$, мы выделяем дугу в $$1/4$$ от всей окружности. Знание $$2\ph_k$$ с точностью $$1/8$$ позволяет выделить две дуги длиной $$1/8$$ каждая, причем только одна из них имеет непустое пересечение с предыдущей дугой.
Обсудим два естественно возникающих вопроса по поводу изложенного алгоритма.
— Можно ли находить собственные числа других операторов так же, как в алгоритме вычисления периода? Да, например, можно находить
Точность определения собственных чисел произвольного оператора невелика, полиномиально зависит от размера схемы. Если можно эффективно вычислять степени оператора (как и было в рассмотренном алгоритме), то точность можно сделать экспоненциальной.
— Какие собственные числа мы находим?
Мы находим значение случайно выбранного собственного числа. Распределением по множеству всех собственных чисел можно управлять, выбирая начальное состояние (в алгоритме вычисления периода — $$\ket1$$ ). Если взять в качестве начального состояние, задаваемое диагональной матрицей плотности$$\rho=\frac{1}{t}\sum\limits_{a}^{} \ket{a}\bra{a} =\frac{1}{t}\sum\limits_{k}^{} \ket{\xi_k}\bra{\xi_k},$$
где $$\ket{\xi_k}$$ пробегает множество
Задача 12.3. Постройте квантовую схему размера $$\poly(n\log(\slashfrac1\delta))$$, реализующую преобразование Фурье на группе $$\ZZ_k$$ при любом $$k\le 2^n$$ с точностью $$\delta$$. (Определение см. в задаче 8.4. Указание: воспользуйтесь результатом задачи 11.2).
Задача о скрытой подгруппе в $$\ZZ^k$$.
Алгоритмы, открытые Саймоном и Шором, обобщаются на довольно широкий класс задач, связанных с абелевыми группами. Самой общей из них является задача о скрытой
"Скрытая
Задача о вычислении периода является частным случаем задачи о скрытой
Известная задача вычисления
Опишем квантовый алгоритм решения задачи о скрытой
Если породить $$l=n+3$$ случайных равномерно распределенных характера $$(\phi_1^{(1)},\dots,\phi_k^{(1)})$$ $$,\dots$$, $$(\phi_1^{(l)},\dots,\phi_k^{(l)})$$, то они порождают всю группу $$E^*$$ с вероятностью $$\ge 1-\slashfrac{1}{2^{l-n}}=1-\slashfrac{1}{8}$$ (см. задачу 12.1). Каждую из величин $$\phi_j^{(r)}$$ достаточно знать с точностью $$\delta$$ и вероятностью ошибки $$\le\eps$$, где$$\begin{equation}\label{deltaeps} \delta\le\frac{1}{2^{2n+1}},\qquad\quad \eps\le\frac{1}{5kl}. \end{equation}$$ Последнее условие гарантирует, что суммарная вероятность ошибки будет не больше, чем $$\slashfrac{1}{8}+\slashfrac{1}{5}<\slashfrac{1}{3}$$.
Выберем достаточно большое число $$M=2^m$$ (конкретная оценка получается из анализа алгоритма). Мы будем работать с целыми числами в диапазоне от $$0$$ до $$M-1$$.
Приготовим в одном квантовом регистре длины $$km$$ состояние$$\ket{\xi}=M^{-k/2}\sum_{g\in\Delta} \ket{g},\ \text{где}\ \Delta=\{0,\dots,M-1\}^k.$$ В другой регистр поместим $$\ket{0^n}$$. Применим квантовый оракул (12.2) и выбросим второй регистр. Получится смешанное состояние$$\rho=\Tr_{[km+1,\dots,km+n]}\Bigl(U\bigl(\ket{\xi}\bra{\xi}\otimes\ket{0^n}\bra{0^n} \bigr)U^\dagger \Bigr)= M^{-k}\mkern-6mu \sum_{g,h\in\Delta:g-h\in D}\mkern-3mu \ket{g}\bra{h}.$$
Теперь мы собираемся измерить собственные значения операторов сдвига по модулю $$M$$:$$V_j\colon \Bigl(g_1,\dots,g_j,\dots,g_k\Bigr) \,\mapsto\, \Bigl(g_1,\dots,(g_j+1)\bmod M,\dots,g_k\Bigr)$$
(меняется только $$j$$ -ая компонента). Эти операторы коммутируют, поэтому у них есть общий базис из
Вероятность того, что реализуется данный набор $$s_1,\dots,s_k$$, равна$$\begin{equation*}
\PP(\rho,\,\calL_{s_1,\dots,s_k}) =
\bra{\xi_{s_1,\dots,s_k}}\,\rho\,\ket{\xi_{s_1,\dots,s_k}}\, =\\
=\ M^{-2k} \sum_{g,h\in\ZZ^k}\chi_D(g-h)\,\chi_\Delta(g)\chi_\Delta(h)\,
\exp\Bigl(2\pi i\sum_{j=1}^{k}\frac{(g_j-h_j)s_j}{M}\Bigr),
\end{equation*}$$
где $$\chi_A(\cdot)$$ обозначает характеристическую функцию множества $$A$$. Фурьеобраз от произведения равен
При заданных значениях $$\phi_1,\dots,\phi_k$$ функция $$p_{\phi_1,\dots,\phi_k}(s_1,\dots,s_k)$$ является вероятностным распределением, относительно которого$$\Pr\Bigl[|s_j/M-\phi_j|>\beta\Bigr] \,\le\, \frac{1}{M\beta}$$ ( $$\beta$$ — любое). Мы измеряем величины $$s_j/M$$ (как уже говорилось, измерение одной из них не меняет значения другой); при этом нас устроит точность $$\beta$$ и вероятность ошибки $$\le\slashfrac{1}{M\beta}$$. Тем самым мы получаем значения $$\phi_1,\dots,\phi_k$$ с точностью $$\delta=2\beta$$ и вероятностью ошибки $$\le\eps=\slashfrac{2}{M\beta}$$. Теперь осталось подобрать числа $$M$$ и $$\beta$$, чтобы удовлетворить неравенствам 12.3.
Tребуется $$O(n)$$ обращений к оракулу, каждый вопрос имеет длину $$O(k(n+\log k))$$. Размер квантовой схемы оценивается как $$O(kn^3)\poly(\log k,\log n)$$.
Замечание. Для измерения собственных чисел операторов $$V_j$$ можно воспользоваться квантовым преобразованием Фурье на группе $$\ZZ_M$$ при $$M=2^m$$ (см. задачу 8.4). Это позволяет несколько уменьшить размер схемы (на логарифмический множитель), однако приходится использовать нестандартные элементы.
Единственное нетривиальное использование квантовых свойств для вычислений, которое мы уже рассмотрели, — это решение универсальной переборной задачи алгоритмом Гровера, изложенным в лекции 8. К сожалению, при этом достигается лишь полиномиальное ускорение. Поэтому никаких серьезных следствий для теории сложности вычислений (типа $$\BQP\supset \BPP$$ ) алгоритм Гровера не дает. В настоящее время нет доказательства того, что квантовые вычисления превосходят по скорости классические вероятностные. Но есть косвенные свидетельства в пользу такого утверждения. Первое из них — пример задачи с оракулом (т.е. процедурой типа "
Задача о скрытой
Задача о скрытой подгруппе в $$(\ZZ_2)^k$$.
Мы рассмотрим сформулированную выше задачу в случае $$G=(\ZZ_2)^k$$. Элементы этой группы
можно представлять строками длины $$k$$ из нулей и единиц; групповая операция — побитовое сложение по модулю 2.
Легко доказать, что нельзя быстро найти "скрытую
Утверждение 12.1. Пусть $$n\ge k$$. Для любого классического вероятностного алгоритма, делающего не более $$2^{k/2}$$ обращений к оракулу, существует
Доказательство. Для одной и той же подгруппы $$D$$ существует несколько различных оракулов $$f$$. Мы будем считать, что один из них выбирается случайно и равновероятно. (Если алгоритм ошибается с вероятностью $$>\slashfrac{1}{3}$$ при случайном оракуле, то он также будет ошибаться с вероятностью $$>\slashfrac{1}{3}$$ при каком-нибудь конкретном оракуле.) Случайный оракул обладает следующим свойством: если очередной ответ $$y_j$$ не совпадает ни с одним из предыдущих ответов $$y_1,\dots,y_{j-1}$$, то он равномерно распределен на множестве $$\cb^n\backslash\{y_1,\dots,y_{j-1}\}$$. Таким образом, случайный оракул эквивалентен устройству с памятью, которое на вопрос $$x_j$$ выдает наименьшее число $$s_j\le j$$, такое что $$x_j-x_{s_j}\in D$$. Классическую машину можно изменить таким образом, что она сама будет производить случайный выбор $$y_j\double\in\cb^n\backslash\{y_1,\dots,y_{j-1}\}$$, когда $$s_j=j$$.
Пусть число вопросов к оракулу равно $$l\le 2^{k/2}$$. Без уменьшения общности все вопросы различны. В случае $$D=\{0\}$$ все ответы также различны, то есть $$s_j=j$$ для всех $$j$$. Теперь рассмотрим случай $$D\double=\{0,z\}$$, где $$z$$ выбирается случайно с равномерным распределением на множестве всех ненулевых элементов группы $$(\ZZ_2)^k$$. Тогда, независимо от используемого алгоритма, $$s_j=j$$ c вероятностью $$\ge 1-\slashfrac{(j-1)}{(2^k-1)}$$. С вероятностью $$\ge1-\slashfrac{l(l-1)}{(2(2^k-1))}>\slashfrac{1}{2}$$ это имеет место для всех $$j=1,\dots,l$$. Напомним, что у нас есть два случайных параметра: $$z$$ и $$r$$. Мы можем зафиксировать $$z$$ таким образом, чтобы вероятность получения ответов $$s_j=j$$ (для всех $$j$$ ) по-прежнему была больше $$\slashfrac{1}{2}$$. Посмотрим, что будет делать классическая машина в этом случае. Если она выдает ответ " $$D=\{0\}$$ " с вероятностью $$\ge\slashfrac{2}{3}$$, положим $$D=\{0,z\}$$ — тогда выдаваемый ответ будет неверным с вероятностью $$>(\slashfrac{2}{3})\cdot(\slashfrac{1}{2})=\slashfrac{1}{3}$$. Если же вероятность ответа " $$D=\{0\}$$ " меньше $$\slashfrac{2}{3}$$, положим $$D=\{0\}$$.
Теперь определим квантовый аналог описанного выше устройства. Соответствующий квантовый оракул — это унитарный оператор$$\begin{equation}\label{кв-оракул} U\colon \ket{x,y}\,\mapsto\,\ket{x,\,y\oplus f(x)}. \end{equation}$$
( $$\oplus$$ обозначает побитовое сложение). Заметим, что квантовый оракул допускает
Пусть $$Е=G/D$$, а $$E^*$$ — группа характеров на $$E$$, т.е. гомоморфизмов $$E\to U(1)$$. В случае $$G=(\ZZ_2)^k$$ группу $$E^*$$ можно охарактеризовать следующим образом:$$E^*= \{h \in(\ZZ_2)^k: \forall\, z\in(\ZZ_2)^k\: (h\cdot z=0) \},$$
где $$h\cdot z$$ обозначает
Начнем с того, что приготовим состояние $$\ket{\xi}=2^{-k/2}\sum_{x\in G}\ket{x}=H^{\otimes k}\ket{0^k}$$ в одном квантовом регистре. Во второй регистр поместим состояние $$\ket{0^n}$$ и применим оператор $$U$$. Затем выбросим второй регистр, т.е. не будем его больше использовать. Получится смешанное состояние$$\rho \,=\, \Tr_2\Bigl(U(\ket{\xi}\bra{\xi}\otimes\ket{0^n}\bra{0^n})U^\dagger \Bigr)\,=\, 2^{-k}\,\sum_{x,y:x-y\in D}\ket{x}\bra{y}.$$ Теперь применим оператор $$H^{\otimes k}$$:$$\gamma \,=\, H^{\otimes k}\rho H^{\otimes k} \,=\, 2^{-2k} \sum_{a,b}\sum_{x,y:x-y\in D} (-1)^{a\cdot x-b\cdot y}\ket{a}\bra{b}.$$ Легко видеть, что величина $$\sum\limits_{x,y:x-y\in D}(-1)^{a\cdot x-b\cdot y}$$ отлична от нуля только в том случае, когда $$a=b\in E^*$$. Таким образом,$$\gamma = \frac{1}{|E^*|} \sum_{a\in Е^*} \ket{a}\bra{a}.$$ Это в точности матрица плотности для случайного равномерно распределенного элемента группы $$E^*$$. Теперь осталось воспользоваться следующей леммой, которую мы сформулируем в виде задачи.
Задача 12.1. Пусть $$h_1,\dots,h_l$$ — независимые случайные равномерно распределенные элементы абелевой группы $$X$$. Докажите, что они порождают всю группу $$X$$ c вероятностью $$\ge 1-\slashfrac{|X|}{2^l}$$.
Таким образом, достаточно $$2k$$ случайных элементов, чтобы породить всю группу $$E^*$$ с вероятностью ошибки $$\le 2^{-k}$$. (Такая маленькая вероятность ошибки получается без особых затрат по сравнению с $$\slashfrac{1}{3}$$. Чтобы сделать ее еще меньше, эффективнее всего воспользоваться стандартной процедурой: повторить все вычисление несколько раз и выбрать наиболее часто встречающийся ответ).
Подведем итог: для нахождения "скрытой подгруппы" $$D$$ требуется $$O(k)$$ обращений к квантовому оракулу. В целом алгоритм имеет сложность $$O(k^3)$$.
Второе свидетельство в пользу гипотезы $$\BQP\supset\BPP$$ — быстрые квантовые алгоритмы разложения числа на простые множители и вычисления
Факторизация числа. Дано натуральное число $$y$$. Требуется найти его разложение на простые множители$$y=p_1^{\alpha_1}p_2^{\alpha_2}\cdot\ldots\cdot p_k^{\alpha_k}.$$
Эта задача считается сложной настолько, что на предположении о трудности ее решения основываются практические алгоритмы криптографии. С теоретической точки зрения положение несколько хуже: неизвестно ни сведение к задаче факторизации задач из класса
Мы будем строить быстрый квантовый алгоритм не для решения задачи факторизации, а для решения другой задачи Нахождение периода, к которой задача факторизации сводится с помощью классического вероятностного алгоритма.
Нахождение периода. Имеется число $$q$$, записывающееся не более чем $$n$$ двоичными цифрами ( $$1\leq q < 2^n$$ ) и число $$a$$ такое, что $$a<q$$, $$(a,q)=1$$ ( $$(a,q)$$ обозначает наибольший общий
Другими словами, период — это порядок числа $$a$$ в мультипликативной группе
Ниже мы построим квантовый алгоритм для решения задачи о нахождении периода числа. Но начнем с того, что опишем классическое вероятностное сведение задачи факторизации к задаче вычисления периода. Читателю также предлагается вспомнить вероятностный тест простоты числа, изложенный в первой части (см. лекцию 3).
Итак, предположим, что мы умеем решать задачу нахождения периода. Ясно, что
Вход: число $$y$$.
Шаг 1. Проверяем
Шаг 2. Проверяем, извлекается ли из $$y$$ нацело корень $$k$$ -й степени при $$k=2,\dots,\log_2y$$. Если $$y=m^r$$, то ответ " $$m$$ ", иначе переходим к шагу 3.
Шаг 3. Выбираем случайное $$a$$ среди чисел от $$1$$ до $$y$$, вычисляем $$r=\per_y(a)$$ (используя имеющийся по предположению алгоритм нахождения периода) и, если $$r$$ — нечетное, то ответ " $$y$$ — простое". В противном случае находим $$d=(a^{r/2}-1,y)$$ (скажем,
Шаг 4. Если $$d>1$$, то ответ " $$d$$ ", в противном случае ответ " $$y$$ — простое".
Докажем, что вероятность получить
Если $$r=\per_y(a)$$ — четное, то $$(a^{r/2}+1)(a^{r/2}-1)\equiv0\pmod y$$. Так что в этом случае процедура выдаст ответ " $$y$$ — простое" только тогда, когда $$a^{r/2}\equiv-1\pmod y$$.
Запишем разложение $$y$$ на простые множители $$y=\prod_{j=1}^{k}p_j^{\alpha_j}$$ и введем обозначения$$a_j\equiv a\pmod{p_j^{\alpha_j}}, \quad r_j=\per_{(p_j^{\alpha_j})} a_j= 2^{s_j}r'_j, \text{ где } r'_j\ \text{--- нечетноe}.$$
Докажем, что процедура выдает ответ " $$y$$ — простое" тогда и только тогда, когда $$s_1=s_2=\ldots=s_k$$. Действительно, если $$s_1=s_2=\ldots\double=s_k=0$$, то $$r$$ нечетно (поскольку $$r$$ — наименьшее общее кратное всех $$r_j$$ ). Если $$s_1=s_2=\ldots=s_k\geq1$$, то $$a_j^{r_j/2}\equiv-1\pmod{p_j^{\alpha_j}}$$ (используем цикличность $$(\ZZ/p_j^{\alpha_j}\ZZ)^*$$ ), а, значит, и $$a^{r/2}\equiv-1\pmod{y}$$ (используем китайскую теорему об остатках). Наоборот, если не все $$s_j$$ равны, то при некотором $$m$$ получим $$a_m^{r/2}\equiv1\pmod{p_m^{\alpha_m}}$$, т.е. $$a^{r/2}\not\equiv-1\pmod{y}$$.
По китайской теореме об остатках случайный равномерный выбор $$a$$ есть то же самое, что независимый случайный равномерный выбор всех $$a_j$$. Оценим для некоторого $$s$$ вероятность события $$s_1=s$$ при независимом выборе $$a_1$$. Пусть $$p_1^{\alpha_1}-1=2^tq$$, где $$q$$ — нечетное, $$g$$ — образующая (циклической) группы $$(\ZZ/p_1^{\alpha_1}\ZZ)^*$$. Тогда$$|\{a_1: s_1=s\}| = |\{g^{2^{t-s}m}: m\ \text{--- нечетное}\}| = \left\{\begin{array}{@{\hskip2pt}cl} q, \text{если } s=0,\\ (2^s-2^{s-1})q, \text{если } s>0, \end{array}\right.$$
поэтому вероятность $$s_1=s$$ не больше $$\slashfrac{1}{2}$$. Отсюда следует искомая оценка вероятности успеха всей процедуры нахождения
Рассмотрим оператор умножения
Поскольку для умножения
Перестановка, которую задает оператор $$U_a$$, разбивается на циклы. Цикл, содержащий $$a$$, содержит и $$1$$ (после $$\per_q(a)-1$$ итераций мы попадаем из $$a$$ в $$1$$ ). Алгоритм, о котором пойдет речь, начинает с состояния $$\ket1$$ и применяет к нему оператор $$U_a$$ по многу раз. Но за пределы орбиты $$a$$ (цикла перестановки, которому принадлежит $$a$$ ) мы такими преобразованиями не выйдем. Поэтому рассмотрим ограничение оператора $$U_a$$ на подпространство, порожденное орбитой $$a$$.
Легко проверить, что написанные векторы действительно собственные. Достаточно заметить, что умножение на $$a$$ приводит к сдвигу индексов в сумме. Если заменить переменную суммирования, чтобы устранить этот сдвиг, получим множитель $$e^{2\pi\ii\cdot k/t}$$.
Если бы мы могли измерять
Пусть у нас есть машина $$M$$, которая при каждом запуске выдает нам число $$k/t$$, где $$t$$ — искомый период, а $$k$$ — равномерно распределенное на множестве $$\{0,\dots,t-1\}$$ случайное число. Мы предполагаем, что $$k/t$$ представлено в виде несократимой дроби $$k'/t'$$ (если бы машина выдавала число в виде $$k/t$$, то вообще не было бы проблем).
Получив несколько дробей такого вида $$k_1'/t_1',\,k_2'/t_2',\dots,k_l'/t_l'$$, можно с большой вероятностью найти число $$t$$, приводя эти дроби к общему знаменателю.
Лемма. Если получено $$l$$ дробей, то вероятность того, что наименьшее общее кратное их знаменателей отлично от $$t$$, меньше $$3\cdot2^{-l}$$.
Доказательство. Дроби $$k_1'/t_1',\dots,k_l'/t_l'$$ получаются сокращением дробей $$k_1/t,\dots,k_l/t$$ (т.е. $$k_j'/t_j'=k_j/t$$ ), где $$k_1,\dots,k_l$$ — независимо распределенные случайные числа. Достаточно, чтобы эти числа были в совокупности взаимно просты, тогда наименьшее общее кратное $$t_1',\dots,t_l'$$ будет равно $$t$$.
Вероятность того, что $$k_1,\dots,k_l$$ имеют общий простой
Теперь будем строить машину $$M$$. Она должна содержать схему, измеряющую
Задача 12.2. Используя оператор $$U$$, реализуйте оператор $$\Lambda(U_b)$$ для любого $$b$$, взаимно простого с $$q$$.
Обозначим $$\calL_{a,k}=\CC(\ket{\xi_{a,k}})$$ (подпространство, порожденное $$\ket{\xi_{a,k}}$$ ), тогда искомая схема должна реализовывать измеряющий оператор $$W=\sum\limits_{k=0}^{t-1}V_{a,k}\otimes\Pi_{\calL_{a,k}}$$ с операторами $$V_{a,k}$$ вида $$\ket{0}\mapsto\sum_{y,z}c_{y,z}\ket{y,z}$$, где $$y$$ — некоторая несократимая дробь, а $$z$$ — мусор. При этом для
Построение такой измеряющей схемы довольно сложное, поэтому вначале объясним, как из нее строится машина $$M$$. Возьмем состояние $$\ket1$$ в качестве начального. Прямое вычисление (читателю рекомендуется его проделать) показывает, что$$\ket1= \frac{1}{\sqrt{t}}\sum_{k=0}^{t-1}\ket{\xi_k}.$$
Это равенство гарантирует равномерное распределение
Вероятности всех $$\ket{\xi_k}$$ равны: $$\PP(\ket{1},\calL_k)=\left| \langle \xi_k|1\rangle \right|^2=\slashfrac1t$$, а указанное выше свойство
Условно работу машины $$M$$ можно представить в виде такого процесса:
(Cлучайный выбор $$k$$ происходит сам по себе, без применения какого бы то ни было оператора. Просто формула полной вероятности устроена так, как будто до начала измерения генерируется случайное $$k$$, которое затем остается постоянным. Разумеется, формула условной вероятности верна только тогда, когда оператор $$W$$ является измеряющим для заданных подпространств $$\calL_{a,k}$$ ).
Теперь будем строить оператор, измеряющий
В лекции 11 был введен оператор $$\Xi(U_a)\double=(H\otimes I)\Lambda(U_a)(H\otimes I)$$, измеряющий
Нам потребуется еще оператор $$\Xi(\ii U_a)$$. Его также нетрудно реализовать. Реализация, изображенная на рисунке, использует оператор $$K\double=\begin{pmatrix} 10\\0\ii\end{pmatrix}$$ из стандартного базиса. Обведенный фрагмент реализует оператор $$\Lambda(\ii U_a)$$. Действительно, $$K$$ умножает на $$\ii$$ только $$\ket1$$, но как раз в этом случае применяется оператор $$U_a$$ (по определению оператора $$\Lambda(U_a)$$ ). Для оператора $$\Xi(\ii U_a)$$
Сложность реализации операторов $$\Xi(U_a)$$ и $$\Xi(\ii U_a)$$ зависит от сложности реализации оператора $$\Lambda(U_a)$$, которая ненамного выше сложности реализации оператора $$U_a$$ (см. задачу 12.2).
Мы будем локализовывать значение $$\ph_k$$, оценивая
У нас есть квантовый регистр $$A$$, в котором находится $$\ket{\xi_{a,k}}$$. (На самом деле там вначале был$$\ket1=\frac{1}{\sqrt{t}}\sum_{k=0}^{t-1}\ket{\xi_k},$$ но мы рассматриваем $$\ket{\xi_{a,k}}$$ по отдельности; это корректно в силу вида измеряющего оператора). Заведем большое количество ( $$s$$ штук) вспомогательных регистров длиной в 1 бит. Каждый из этих регистров будет использоваться для применения оператора $$\Xi(U_a)$$.
Как было доказано в лекции 11,
Далее с битами, в которых записаны результаты "экспериментов", будут уже производиться классические действия. Поскольку
Если монета брошена $$s$$ раз, то доля выпавших единиц $$(\sum y_r)/s$$ примерно равна $$\PP(1\big| k)$$. С какой точностью верна такая оценка? Из теории вероятностей известно, что$$\Prob\left[\left|\frac{\sum\nolimits_{r=1}^{s}y_r}{s}-\PP(1\big|k)\right| >\delta\right]<2e^{-c\delta^{2}s},$$ где $$c>0$$ — некоторая константа. Это показывает, что при любом фиксированном $$\delta$$ можно добиться вероятности ошибки $$\eps$$ за $$O(\log(1/\eps))$$ испытаний.
Итак, мы научились находить с некоторой точностью $$\delta$$ синус и косинус от $$\ph_k$$. Теперь подберем $$\delta$$ таким, чтобы значение $$\ph_k$$ можно было установить по значениям синуса и косинуса с точностью $$1/8$$. На этом второй этап завершен.
Для увеличения точности мы будем использовать, наряду с $$\Lambda(U_a)$$, операторы $$\Lambda((U_a)^{2^j})$$ для всех $$j\le 2n$$. Числа мы можем быстро возводить в степень, а операторы, вообще говоря, — нет. Но оператор умножения на число $$U_a$$ обладает следующим замечательным свойством:$$(U_a)^p = U_{a^p\bmod q}.$$ Следовательно, $$\Lambda((U_a)^{2^j})=\Lambda(U_b)$$, где $$b\equiv a^{2^j}\pmod q$$. Нужные нам значения параметра $$b$$ можно вычислить при помощи схемы полиномиального размера, а затем использовать результат задачи 12.2.
Вход: $$a$$ и $$q$$
Ответ: $$t$$ (с вероятностью ошибки $$<3\cdot 2^{-l}+4nle^{-cs}$$, где $$c={\rm const}$$ )
Вернемся к схеме упоминаемой ранее. Мы находили собственное число $$\lambda_k=e^{2\pi\ii\ph_k}$$ для некоторого собственного вектора $$\ket{\xi_{a,k}}$$. Этот же вектор останется собственным и для любой степени оператора $$U_a$$, поэтому можно на одном и том же квантовом регистре искать собственное число для $$U_a^2=U_{a^2}$$, оно равно $$\lambda_k=e^{2\pi\ii2\ph_k}$$ ; для $$U_a^4=U_{a^4}$$ оно равно $$\lambda_k\double=e^{2\pi\ii4\ph_k}$$ ;...
Другими словами, мы можем с точностью $$1/8$$ определить значения $$\ph_k, 2\ph_k, \dots, 2^{2n}\ph_k$$ по модулю 1. Но это позволяет определить $$\ph_k$$ с точностью $$1/2^{2n+1}$$ за полиномиальное время .
Идея доказательства. Множество возможных значений $$\ph_k$$ удобно представлять в виде окружности единичной длины. Зная $$\ph_k$$ с точностью $$1/8$$, мы выделяем дугу в $$1/4$$ от всей окружности. Знание $$2\ph_k$$ с точностью $$1/8$$ позволяет выделить две дуги длиной $$1/8$$ каждая, причем только одна из них имеет непустое пересечение с предыдущей дугой.
Обсудим два естественно возникающих вопроса по поводу изложенного алгоритма.
— Можно ли находить собственные числа других операторов так же, как в алгоритме вычисления периода? Да, например, можно находить
Точность определения собственных чисел произвольного оператора невелика, полиномиально зависит от размера схемы. Если можно эффективно вычислять степени оператора (как и было в рассмотренном алгоритме), то точность можно сделать экспоненциальной.
— Какие собственные числа мы находим?
Мы находим значение случайно выбранного собственного числа. Распределением по множеству всех собственных чисел можно управлять, выбирая начальное состояние (в алгоритме вычисления периода — $$\ket1$$ ). Если взять в качестве начального состояние, задаваемое диагональной матрицей плотности$$\rho=\frac{1}{t}\sum\limits_{a}^{} \ket{a}\bra{a} =\frac{1}{t}\sum\limits_{k}^{} \ket{\xi_k}\bra{\xi_k},$$
где $$\ket{\xi_k}$$ пробегает множество
Задача 12.3. Постройте квантовую схему размера $$\poly(n\log(\slashfrac1\delta))$$, реализующую преобразование Фурье на группе $$\ZZ_k$$ при любом $$k\le 2^n$$ с точностью $$\delta$$. (Определение см. в задаче 8.4. Указание: воспользуйтесь результатом задачи 11.2).
Задача о скрытой подгруппе в $$\ZZ^k$$.
Алгоритмы, открытые Саймоном и Шором, обобщаются на довольно широкий класс задач, связанных с абелевыми группами. Самой общей из них является задача о скрытой
"Скрытая
Задача о вычислении периода является частным случаем задачи о скрытой
Известная задача вычисления
Опишем квантовый алгоритм решения задачи о скрытой
Если породить $$l=n+3$$ случайных равномерно распределенных характера $$(\phi_1^{(1)},\dots,\phi_k^{(1)})$$ $$,\dots$$, $$(\phi_1^{(l)},\dots,\phi_k^{(l)})$$, то они порождают всю группу $$E^*$$ с вероятностью $$\ge 1-\slashfrac{1}{2^{l-n}}=1-\slashfrac{1}{8}$$ (см. задачу 12.1). Каждую из величин $$\phi_j^{(r)}$$ достаточно знать с точностью $$\delta$$ и вероятностью ошибки $$\le\eps$$, где$$\begin{equation}\label{deltaeps} \delta\le\frac{1}{2^{2n+1}},\qquad\quad \eps\le\frac{1}{5kl}. \end{equation}$$ Последнее условие гарантирует, что суммарная вероятность ошибки будет не больше, чем $$\slashfrac{1}{8}+\slashfrac{1}{5}<\slashfrac{1}{3}$$.
Выберем достаточно большое число $$M=2^m$$ (конкретная оценка получается из анализа алгоритма). Мы будем работать с целыми числами в диапазоне от $$0$$ до $$M-1$$.
Приготовим в одном квантовом регистре длины $$km$$ состояние$$\ket{\xi}=M^{-k/2}\sum_{g\in\Delta} \ket{g},\ \text{где}\ \Delta=\{0,\dots,M-1\}^k.$$ В другой регистр поместим $$\ket{0^n}$$. Применим квантовый оракул (12.2) и выбросим второй регистр. Получится смешанное состояние$$\rho=\Tr_{[km+1,\dots,km+n]}\Bigl(U\bigl(\ket{\xi}\bra{\xi}\otimes\ket{0^n}\bra{0^n} \bigr)U^\dagger \Bigr)= M^{-k}\mkern-6mu \sum_{g,h\in\Delta:g-h\in D}\mkern-3mu \ket{g}\bra{h}.$$
Теперь мы собираемся измерить собственные значения операторов сдвига по модулю $$M$$:$$V_j\colon \Bigl(g_1,\dots,g_j,\dots,g_k\Bigr) \,\mapsto\, \Bigl(g_1,\dots,(g_j+1)\bmod M,\dots,g_k\Bigr)$$
(меняется только $$j$$ -ая компонента). Эти операторы коммутируют, поэтому у них есть общий базис из
Вероятность того, что реализуется данный набор $$s_1,\dots,s_k$$, равна$$\begin{equation*}
\PP(\rho,\,\calL_{s_1,\dots,s_k}) =
\bra{\xi_{s_1,\dots,s_k}}\,\rho\,\ket{\xi_{s_1,\dots,s_k}}\, =\\
=\ M^{-2k} \sum_{g,h\in\ZZ^k}\chi_D(g-h)\,\chi_\Delta(g)\chi_\Delta(h)\,
\exp\Bigl(2\pi i\sum_{j=1}^{k}\frac{(g_j-h_j)s_j}{M}\Bigr),
\end{equation*}$$
где $$\chi_A(\cdot)$$ обозначает характеристическую функцию множества $$A$$. Фурьеобраз от произведения равен
При заданных значениях $$\phi_1,\dots,\phi_k$$ функция $$p_{\phi_1,\dots,\phi_k}(s_1,\dots,s_k)$$ является вероятностным распределением, относительно которого$$\Pr\Bigl[|s_j/M-\phi_j|>\beta\Bigr] \,\le\, \frac{1}{M\beta}$$ ( $$\beta$$ — любое). Мы измеряем величины $$s_j/M$$ (как уже говорилось, измерение одной из них не меняет значения другой); при этом нас устроит точность $$\beta$$ и вероятность ошибки $$\le\slashfrac{1}{M\beta}$$. Тем самым мы получаем значения $$\phi_1,\dots,\phi_k$$ с точностью $$\delta=2\beta$$ и вероятностью ошибки $$\le\eps=\slashfrac{2}{M\beta}$$. Теперь осталось подобрать числа $$M$$ и $$\beta$$, чтобы удовлетворить неравенствам 12.3.
Tребуется $$O(n)$$ обращений к оракулу, каждый вопрос имеет длину $$O(k(n+\log k))$$. Размер квантовой схемы оценивается как $$O(kn^3)\poly(\log k,\log n)$$.
Замечание. Для измерения собственных чисел операторов $$V_j$$ можно воспользоваться квантовым преобразованием Фурье на группе $$\ZZ_M$$ при $$M=2^m$$ (см. задачу 8.4). Это позволяет несколько уменьшить размер схемы (на логарифмический множитель), однако приходится использовать нестандартные элементы.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.