Пока мы описали работу квантового компьютера. Теперь пора определить, когда эта работа приводит к решению интересующей нас задачи. Определение будет похоже на определение вероятностного вычисления.
Пусть есть функция $$F\colon\cb^n\to\cb^m$$. Рассмотрим квантовую схему, работающую с $$N$$ битами: $$U=U_L\cdot\ldots\cdot U_2U_1\colon{} \BB^{\otimes N}\to\BB^{\otimes N}$$. Неформально говоря, эта схема вычисляет $$F$$, если после применения $$U$$ к начальному состоянию $$\ket{x,0^{N-n}}$$, мы, "посмотрев" на первые $$m$$ битов, с большой вероятностью "увидим" $$F(x)$$. (Остальные q-биты могут содержать произвольный мусор.)
Нужно только оговорить, что такое эта вероятность. Слова "посмотрев" и "увидим" в точном смысле означают, что производится измерение значений соответствующих q-битов. В результате измерения могут получаться разные ответы, каждому соответствует своя вероятность. Ниже (раздел 9) этот вопрос рассматривается подробно. Для того, чтобы дать определение квантового вычисления функции $$F$$, достаточно (не вдаваясь в обсуждение физических объяснений этого факта) принять следующее: вероятность получения базисного состояния, $$x$$ при измерении состояния $$\ket\psi=\sum_x c_x\ket{x}$$ равна $$\PP(\ket\psi, x)=|c_x|^2.$$
Нас интересует вероятность того, что компьютер закончит работу в состоянии вида $$(F(x),z)$$, где $$z$$ — любое.
Определение 8.1. Схема $$U=U_L\cdot\ldots\cdot U_2U_1$$ вычисляет $$F$$, если для любого $$x$$ выполнено$$\sum_{z}^{} \bigl| \langle F(x),z|\,U\,|x,0^{N-n}\rangle\bigr|^2 \ge 1-\varepsilon,$$ где $$\varepsilon$$ — некоторое фиксированное число, меньшее $$1/2$$. (Обратите внимание, что $$F(x)$$ и $$x$$ состоят из разного количества битов, хотя суммарная длина $$(F(x),z)$$ и $$(x,0^{N-n})$$ одинакова и равна $$N$$.)
Как и для вероятностных вычислений, выбор $$\varepsilon$$ несущественен, поскольку можно запустить несколько экземпляров схемы независимо и выбрать тот результат, который получается чаще всего. Из оценки, приведенной в лекции 3, следует, что для уменьшения вероятности неудачи в $$N$$ раз нужно взять $$O(\log N)$$ экземпляров схемы $$U$$. Выбор самого частого результата реализуется классической схемой, использующей функцию голосования $$\MAJ(x_1,\dots,x_n)$$ (она равна 1, когда более половины ее аргументов равны 1, и равна 0 в противном случае). Функция $$\MAJ(x_1,\dots,x_n)$$ реализуется в полном базисе схемой размера $$O(n\log n)$$, так что потеря эффективности при уменьшении вероятности неудачи в $$N$$ раз задается множителем $$O(m\log N\log\log N)$$.
Задача 8.1. Докажите, что приведенное рассуждение является корректным в квантовом случае: функция $$\MAJ_\oplus$$ реализована в виде обратимой схемы, на вход которой подаются выходные q-биты $$n$$ копий схемы $$U$$.
Итак, мы имеем определение квантового вычисления. Теперь можно заняться сравнением эффективности классического и квантового вычисления. Во введении упоминались три основных примера, для которых квантовое вычисление оказывается, по-видимому, эффективнее классического. Мы начнем с того из них, в котором квантовое вычисление заведомо эффективнее (хотя ускорение лишь "полиномиальное").
Дадим определение универсальной переборной задачи в классической и квантовой постановке.
Пусть имеется устройство (см. рисунок), которое по входам $$x$$ и $$y$$ определяет значение некоторого предиката $$\calA(x,y)$$. Нас интересует предикат $$F(x)\double=\exists\, y\:\calA(x,y)$$. Это похоже на определение класса
Оказывается, что на квантовом компьютере можно вычислить значение предиката $$F(x)$$ и даже найти $$y$$, на котором выполнено $$\calA(x,y)$$, за время $$O(\sqrt{N})$$. Получены также и нижние оценки, показывающие, что в этой постановке квантовые устройства дают лишь полиномиальное ускорение по сравнению с классическими.
В квантовой постановке задача выглядит так. Вход $$x$$ по-прежнему классический, но сам "
Нужно вычислить значение $$F(x)$$ и найти "ответ" $$y$$ (при котором выполнен $$\calA(x,y)$$ ).
Результаты, о которых уже упоминалось, формулируются так (см.[31, 48]): существуют две константы $$C_1$$ и $$C_2$$ такие, что есть схема размера $$\leq C_1\sqrt{N}$$, решающая задачу для любого предиката $$\calA(x,y)$$ ; а для любой схемы размера $$\leq C_2\sqrt{N}$$ существует предикат $$\calA(x,y)$$, при котором задача не решается на этой схеме (т.е. схема дает неправильный ответ с вероятностью $$>1/3$$ ).
Мы разберем упрощенную постановку: считаем, что "ответ" существует и единствен, обозначим его через $$y_0$$ ; нужно найти $$y_0$$. Схема, которую мы для этого построим, будет примером "прямого" квантового вычисления; она будет описана в терминах преобразований
Рассмотрим два оператора:
$$U=I-2\ket{y_0}\bra{y_0}$$
и$$V=I-2\ket{\xi}\bra{\xi}, \quad\mathrm{где}\ \ket{\xi}=\frac{1}{\sqrt{N}}\sum_{y}^{}\ket{y}.$$
Оператор $$V$$ в
Оператор $$U$$ нам задан (это оракул). Построим квантовую схему, вычисляющую $$V$$. Действовать будем так: переведем $$\ket{\xi}$$ в $$\ket{0^n}$$ некоторым оператором $$W$$, затем применим оператор $$Y=I-2\ket{0^n}\bra{0^n}$$, после чего применим $$W^{-1}$$.
Построить оператор $$W$$, который переводит $$\ket{\xi}$$ в $$\ket{0^n}$$, просто. Это $$W=H^{\otimes n}$$, где оператор $$H$$ — из стандартного базиса (см. лекцию 7). Действительно, $$\ket\xi=\frac{1}{\sqrt{2^n}}\left(\ket0+\ket1\right)^{\otimes n}, \text{ а } H\colon \frac{1}{\sqrt2}\left(\ket0+\ket1\right)\mapsto\ket0$$.
Теперь построим реализацию оператора $$Y$$. Используем обратимую классическую схему, реализующую оператор $$Z\colon\cb^{n+1}\to\cb^{n+1}$$,$$\begin{align*} Z\ket{a_0,\dots,a_n}\ =\ \ket{a_0\oplus f(a_1,a_2,\dots,a_n),a_1,\dots,a_n}; \\ f(a_1,\dots,a_n)\ =\ \left\{ \begin{array}{rl} 1,\ \mbox{если}\ a_1=\ldots=a_n=0,\\ 0,\ \mbox{если}\ \exists\, j: a_j\ne0. \end{array} \right. \end{align*}$$ (С точностью до перестановки аргументов, $$Z=\widehat{f_{\oplus}}$$.) Поскольку $$f$$ имеет малую схемную сложность (в классическом смысле), по лемме для вычисления $$Z$$ существует небольшая схема (в которой берутся "напрокат" дополнительные q-биты).
Схема, реализующая оператор $$V$$, изображена на рис. рис. 8.1.. Центральная часть, включающая в себя $$Z$$, $$\sz$$ и $$Z$$, реализует оператор $$Y$$. В схеме используется оператор $$\sz=K^2$$ ( $$K$$ из стандартного базиса).
(рис 8.1) Заметим, что $$W^2$$ и $$Z^2$$ действуют тождественно на векторах с нулевыми значениями q-битов, взятых напрокат. Поэтому решающую роль играет оператор $$\sz$$, действующий на вспомогательный q-бит, который также не меняется после всего вычисления.
Пусть вас не смущает то, что $$\sz$$ действует только на "управляемый" q-бит, а меняется в результате весь вектор. Вообще, различие между "чтением" и "записью" в квантовом случае неабсолютно и зависит от выбора базиса. Приведем соответствующий пример.
Напишем матрицу $$\Lambda(\sx)\colon{} \ket{a,b}\mapsto \ket{a,a\oplus b}$$ в базисе $$\frac{1}{\sqrt2}\left(\ket0\pm\ket1\right)$$ для каждого из q-бит. Другими словами, запишем матрицу для оператора $$X=\left(H\otimes H\right)\, \Lambda(\sx)\, \left(H\otimes H\right)$$. Схема для этого оператора изображена на рис. рис. 8.2. Используя равенство $$\Lambda(\sx)\ket{c,d}\double=\ket{c,c\oplus d}$$, найдем действие $$X$$ на базисном векторе:$$\begin{align*} X\ket{a,b}=\frac{1}{2}\left(H\otimes H\right) \Lambda(\sx)\sum\limits_{c,d}^{}(-1)^{ac+bd}\ket{c,d}=\\ =\frac{1}{2}\left(H\otimes H\right) \sum\limits_{c,d}^{}(-1)^{ac+bd}\ket{c,c\oplus d}=\\ =\frac{1}{4} \sum\limits_{a',b',c,d}^{}(-1)^{a'c+b'(c+d)} (-1)^{ac+bd}\ket{a',b'}=\\ =\frac{1}{4}\sum_{a',b'}^{} 2\delta_{b,b'}\cdot2\delta_{a,(a'+b')} \ket{a',b'}=\ket{a\oplus b,b}. \end{align*}$$ Итак, в базисе$$\frac{1}{\sqrt2}\left(\ket0\pm\ket1\right)$$ управляющий и управляемый биты поменялись местами. Какой бит "управляющий", или какой "читается", зависит от выбора базиса. Разумеется, такое положение дел противоречит нашей классической интуиции. Трудно представить, как при переходе к другому базису квантовый принтер вдруг становится квантовым сканнером.
(рис 8.2) Задача 8.2. Что будет, если изменить базис только в одном бите? Например, как будет выглядеть матрица оператора, схема которого изображена на рисунке? Попробуйте также поменять базис в другом бите.
Вернемся к построению схемы для универсальной переборной задачи. Оракул $$U=I-2\ket{y_0}\bra{y_0}$$ нам задан, и мы реализовали оператор $$V=I-2\ket{\xi}\bra{\xi}$$. Из вектора $$\ket{0^n}$$ можно получить вектор $$\ket\xi$$ применением оператора $$W$$ ( $$W^2=I$$ ). Теперь с помощью операторов $$U$$ и $$V$$ построим из вектора $$\ket{\xi}$$ искомый вектор $$\ket{y_0}$$. Для этого будем поочередно действовать операторами $$V,U$$:$$\dots V\,U\,V\,U\,\ket\xi=(VU)^s\ket\xi.$$
Что при этом получается? Геометрически оба оператора есть отражения относительно
Композиция двух отражений относительно двух прямых есть поворот на удвоенный угол между этими прямыми. Угол легко вычислить, $$\displaystyle \langle \xi| y_0\rangle =\frac{1}{\sqrt{N}}=\sin\frac{\varphi}{2}$$, т.е. эти прямые почти перпендикулярны. Поэтому можно написать $$VU=-R$$, где $$R$$ — поворот на малый угол $$\varphi$$. Но тогда $$(VU)^s=(-1)^sR^s$$, где $$R^s$$ — поворот на угол $$s\varphi$$. Знак нас не интересует (фазовые множители не меняют вероятностей). При больших $$N$$ имеем $$\varphi\approx\slashfrac{2}{\sqrt{N}}$$. Тогда после $$s\approx\slashfrac{\pi}{4}\sqrt{N}$$ итераций исходный вектор повернется на угол $$s\varphi\approx\slashfrac{\pi}{2}$$ и станет близок к искомому вектору. Это и означает, что система окажется в состоянии $$\ket{y_0}$$ с вероятностью, близкой к единице.
Если решается переборная задача в общей постановке (т.е. ответов может быть несколько, а может не быть вообще), требуются дополнительные технические ухищрения. Число шагов для поворота от исходного вектора к какому-нибудь вектору из подпространства, порожденного векторами ответов, обратно пропорционально корню из числа решений.
Второй из примеров, упомянутых во введении, — моделирование квантовомеханических систем. Это нечетко поставленная задача, так как большую роль в ней играет выбор конкретной системы и выделение существенных "степеней" свободы. С математической точки зрения, более корректно говорить о моделировании квантовых схем.
Квантовые схемы имеют конструктивное описание, если указать точность, с которой известны матричные элементы операторов, входящих в схему. Пусть есть описание квантовой схемы $$Z$$, размера $$\leq L$$ и точности $$\delta$$. Элементами этой схемы могут быть любые унитарные операторы на $$r=O(\log L)$$ q-битах (так чтобы полная длина описания схемы не превышала $$\poly(L,\log(1/\delta))\$$,). Обозначим оператор, реализуемый этой схемой, через $$Op(Z)$$.
Из результатов задач 7.1 и 7.11 следует, что можно построить универсальную квантовую схему $$U$$ размера $$\poly(L, \log 1/\delta)$$, которая моделирует работу произвольной квантовой схемы следующим образом. Если задано описание некоторой схемы $$Op(Z)$$ размера $$L$$ и ее вход $$\ket\xi$$, то$$\Bigl\| U(\ket{Z}\otimes\ket\xi)-\ket{Z}\otimes Op(Z)\ket\xi\Bigr\|= O(L\delta).$$
До сих пор мы рассматривали неоднородные вычисления (вычислялись
Замечание 8.1. Можно определить квантовую
Определение 8.2. Функция $$F\colon\cb^*\to\cb^*$$ принадлежит классу $$\BQP$$, если есть квантовый алгоритм ее вычисления, работающий за время $$O(n^d)$$ для некоторой константы $$d$$.
Как соотносится класс BQP{} с сложностными классами, введенными ранее?
Задача 8.3. Докажите, что$$\BPP\subseteq \BQP\subseteq \PPP \subseteq \PSPACE.$$ Класс $$\PPP$$ состоит из предикатов вида$$Q(x)=\Bigl(\, |\{y:R_0(x,y)\}| < |\{y:R_1(x,y)\}| \,\Bigr),$$ где $$R_0,R_1\in\P$$, и учитываются только $$y$$ с длиной меньше некоторого полинома $$q(x)$$.
Это почти все, что известно о соотношениях между BQP и другими сложностными классами. Косвенное свидетельство в пользу строгого включения $$\BPP\subset\BQP$$ дает существование эффективных квантовых алгоритмов для некоторых теоретико-числовых задач, традиционно считаемых трудными (см. раздел 12).
Заметим также, что в последнее время появились интересные результаты о квантовых аналогах некоторых более сильных сложностных классов (не описанных в части I).
Задача 8.4. Постройте квантовые схемы полиномиального размера в базисе из операторов на двух q-битах, которые выполняют следующие действия:
Пока мы описали работу квантового компьютера. Теперь пора определить, когда эта работа приводит к решению интересующей нас задачи. Определение будет похоже на определение вероятностного вычисления.
Пусть есть функция $$F\colon\cb^n\to\cb^m$$. Рассмотрим квантовую схему, работающую с $$N$$ битами: $$U=U_L\cdot\ldots\cdot U_2U_1\colon{} \BB^{\otimes N}\to\BB^{\otimes N}$$. Неформально говоря, эта схема вычисляет $$F$$, если после применения $$U$$ к начальному состоянию $$\ket{x,0^{N-n}}$$, мы, "посмотрев" на первые $$m$$ битов, с большой вероятностью "увидим" $$F(x)$$. (Остальные q-биты могут содержать произвольный мусор.)
Нужно только оговорить, что такое эта вероятность. Слова "посмотрев" и "увидим" в точном смысле означают, что производится измерение значений соответствующих q-битов. В результате измерения могут получаться разные ответы, каждому соответствует своя вероятность. Ниже (раздел 9) этот вопрос рассматривается подробно. Для того, чтобы дать определение квантового вычисления функции $$F$$, достаточно (не вдаваясь в обсуждение физических объяснений этого факта) принять следующее: вероятность получения базисного состояния, $$x$$ при измерении состояния $$\ket\psi=\sum_x c_x\ket{x}$$ равна $$\PP(\ket\psi, x)=|c_x|^2.$$
Нас интересует вероятность того, что компьютер закончит работу в состоянии вида $$(F(x),z)$$, где $$z$$ — любое.
Определение 8.1. Схема $$U=U_L\cdot\ldots\cdot U_2U_1$$ вычисляет $$F$$, если для любого $$x$$ выполнено$$\sum_{z}^{} \bigl| \langle F(x),z|\,U\,|x,0^{N-n}\rangle\bigr|^2 \ge 1-\varepsilon,$$ где $$\varepsilon$$ — некоторое фиксированное число, меньшее $$1/2$$. (Обратите внимание, что $$F(x)$$ и $$x$$ состоят из разного количества битов, хотя суммарная длина $$(F(x),z)$$ и $$(x,0^{N-n})$$ одинакова и равна $$N$$.)
Как и для вероятностных вычислений, выбор $$\varepsilon$$ несущественен, поскольку можно запустить несколько экземпляров схемы независимо и выбрать тот результат, который получается чаще всего. Из оценки, приведенной в лекции 3, следует, что для уменьшения вероятности неудачи в $$N$$ раз нужно взять $$O(\log N)$$ экземпляров схемы $$U$$. Выбор самого частого результата реализуется классической схемой, использующей функцию голосования $$\MAJ(x_1,\dots,x_n)$$ (она равна 1, когда более половины ее аргументов равны 1, и равна 0 в противном случае). Функция $$\MAJ(x_1,\dots,x_n)$$ реализуется в полном базисе схемой размера $$O(n\log n)$$, так что потеря эффективности при уменьшении вероятности неудачи в $$N$$ раз задается множителем $$O(m\log N\log\log N)$$.
Задача 8.1. Докажите, что приведенное рассуждение является корректным в квантовом случае: функция $$\MAJ_\oplus$$ реализована в виде обратимой схемы, на вход которой подаются выходные q-биты $$n$$ копий схемы $$U$$.
Итак, мы имеем определение квантового вычисления. Теперь можно заняться сравнением эффективности классического и квантового вычисления. Во введении упоминались три основных примера, для которых квантовое вычисление оказывается, по-видимому, эффективнее классического. Мы начнем с того из них, в котором квантовое вычисление заведомо эффективнее (хотя ускорение лишь "полиномиальное").
Дадим определение универсальной переборной задачи в классической и квантовой постановке.
Пусть имеется устройство (см. рисунок), которое по входам $$x$$ и $$y$$ определяет значение некоторого предиката $$\calA(x,y)$$. Нас интересует предикат $$F(x)\double=\exists\, y\:\calA(x,y)$$. Это похоже на определение класса
Оказывается, что на квантовом компьютере можно вычислить значение предиката $$F(x)$$ и даже найти $$y$$, на котором выполнено $$\calA(x,y)$$, за время $$O(\sqrt{N})$$. Получены также и нижние оценки, показывающие, что в этой постановке квантовые устройства дают лишь полиномиальное ускорение по сравнению с классическими.
В квантовой постановке задача выглядит так. Вход $$x$$ по-прежнему классический, но сам "
Нужно вычислить значение $$F(x)$$ и найти "ответ" $$y$$ (при котором выполнен $$\calA(x,y)$$ ).
Результаты, о которых уже упоминалось, формулируются так (см.[31, 48]): существуют две константы $$C_1$$ и $$C_2$$ такие, что есть схема размера $$\leq C_1\sqrt{N}$$, решающая задачу для любого предиката $$\calA(x,y)$$ ; а для любой схемы размера $$\leq C_2\sqrt{N}$$ существует предикат $$\calA(x,y)$$, при котором задача не решается на этой схеме (т.е. схема дает неправильный ответ с вероятностью $$>1/3$$ ).
Мы разберем упрощенную постановку: считаем, что "ответ" существует и единствен, обозначим его через $$y_0$$ ; нужно найти $$y_0$$. Схема, которую мы для этого построим, будет примером "прямого" квантового вычисления; она будет описана в терминах преобразований
Рассмотрим два оператора:
$$U=I-2\ket{y_0}\bra{y_0}$$
и$$V=I-2\ket{\xi}\bra{\xi}, \quad\mathrm{где}\ \ket{\xi}=\frac{1}{\sqrt{N}}\sum_{y}^{}\ket{y}.$$
Оператор $$V$$ в
Оператор $$U$$ нам задан (это оракул). Построим квантовую схему, вычисляющую $$V$$. Действовать будем так: переведем $$\ket{\xi}$$ в $$\ket{0^n}$$ некоторым оператором $$W$$, затем применим оператор $$Y=I-2\ket{0^n}\bra{0^n}$$, после чего применим $$W^{-1}$$.
Построить оператор $$W$$, который переводит $$\ket{\xi}$$ в $$\ket{0^n}$$, просто. Это $$W=H^{\otimes n}$$, где оператор $$H$$ — из стандартного базиса (см. лекцию 7). Действительно, $$\ket\xi=\frac{1}{\sqrt{2^n}}\left(\ket0+\ket1\right)^{\otimes n}, \text{ а } H\colon \frac{1}{\sqrt2}\left(\ket0+\ket1\right)\mapsto\ket0$$.
Теперь построим реализацию оператора $$Y$$. Используем обратимую классическую схему, реализующую оператор $$Z\colon\cb^{n+1}\to\cb^{n+1}$$,$$\begin{align*} Z\ket{a_0,\dots,a_n}\ =\ \ket{a_0\oplus f(a_1,a_2,\dots,a_n),a_1,\dots,a_n}; \\ f(a_1,\dots,a_n)\ =\ \left\{ \begin{array}{rl} 1,\ \mbox{если}\ a_1=\ldots=a_n=0,\\ 0,\ \mbox{если}\ \exists\, j: a_j\ne0. \end{array} \right. \end{align*}$$ (С точностью до перестановки аргументов, $$Z=\widehat{f_{\oplus}}$$.) Поскольку $$f$$ имеет малую схемную сложность (в классическом смысле), по лемме для вычисления $$Z$$ существует небольшая схема (в которой берутся "напрокат" дополнительные q-биты).
Схема, реализующая оператор $$V$$, изображена на рис. рис. 8.1.. Центральная часть, включающая в себя $$Z$$, $$\sz$$ и $$Z$$, реализует оператор $$Y$$. В схеме используется оператор $$\sz=K^2$$ ( $$K$$ из стандартного базиса).
(рис 8.1) Заметим, что $$W^2$$ и $$Z^2$$ действуют тождественно на векторах с нулевыми значениями q-битов, взятых напрокат. Поэтому решающую роль играет оператор $$\sz$$, действующий на вспомогательный q-бит, который также не меняется после всего вычисления.
Пусть вас не смущает то, что $$\sz$$ действует только на "управляемый" q-бит, а меняется в результате весь вектор. Вообще, различие между "чтением" и "записью" в квантовом случае неабсолютно и зависит от выбора базиса. Приведем соответствующий пример.
Напишем матрицу $$\Lambda(\sx)\colon{} \ket{a,b}\mapsto \ket{a,a\oplus b}$$ в базисе $$\frac{1}{\sqrt2}\left(\ket0\pm\ket1\right)$$ для каждого из q-бит. Другими словами, запишем матрицу для оператора $$X=\left(H\otimes H\right)\, \Lambda(\sx)\, \left(H\otimes H\right)$$. Схема для этого оператора изображена на рис. рис. 8.2. Используя равенство $$\Lambda(\sx)\ket{c,d}\double=\ket{c,c\oplus d}$$, найдем действие $$X$$ на базисном векторе:$$\begin{align*} X\ket{a,b}=\frac{1}{2}\left(H\otimes H\right) \Lambda(\sx)\sum\limits_{c,d}^{}(-1)^{ac+bd}\ket{c,d}=\\ =\frac{1}{2}\left(H\otimes H\right) \sum\limits_{c,d}^{}(-1)^{ac+bd}\ket{c,c\oplus d}=\\ =\frac{1}{4} \sum\limits_{a',b',c,d}^{}(-1)^{a'c+b'(c+d)} (-1)^{ac+bd}\ket{a',b'}=\\ =\frac{1}{4}\sum_{a',b'}^{} 2\delta_{b,b'}\cdot2\delta_{a,(a'+b')} \ket{a',b'}=\ket{a\oplus b,b}. \end{align*}$$ Итак, в базисе$$\frac{1}{\sqrt2}\left(\ket0\pm\ket1\right)$$ управляющий и управляемый биты поменялись местами. Какой бит "управляющий", или какой "читается", зависит от выбора базиса. Разумеется, такое положение дел противоречит нашей классической интуиции. Трудно представить, как при переходе к другому базису квантовый принтер вдруг становится квантовым сканнером.
(рис 8.2) Задача 8.2. Что будет, если изменить базис только в одном бите? Например, как будет выглядеть матрица оператора, схема которого изображена на рисунке? Попробуйте также поменять базис в другом бите.
Вернемся к построению схемы для универсальной переборной задачи. Оракул $$U=I-2\ket{y_0}\bra{y_0}$$ нам задан, и мы реализовали оператор $$V=I-2\ket{\xi}\bra{\xi}$$. Из вектора $$\ket{0^n}$$ можно получить вектор $$\ket\xi$$ применением оператора $$W$$ ( $$W^2=I$$ ). Теперь с помощью операторов $$U$$ и $$V$$ построим из вектора $$\ket{\xi}$$ искомый вектор $$\ket{y_0}$$. Для этого будем поочередно действовать операторами $$V,U$$:$$\dots V\,U\,V\,U\,\ket\xi=(VU)^s\ket\xi.$$
Что при этом получается? Геометрически оба оператора есть отражения относительно
Композиция двух отражений относительно двух прямых есть поворот на удвоенный угол между этими прямыми. Угол легко вычислить, $$\displaystyle \langle \xi| y_0\rangle =\frac{1}{\sqrt{N}}=\sin\frac{\varphi}{2}$$, т.е. эти прямые почти перпендикулярны. Поэтому можно написать $$VU=-R$$, где $$R$$ — поворот на малый угол $$\varphi$$. Но тогда $$(VU)^s=(-1)^sR^s$$, где $$R^s$$ — поворот на угол $$s\varphi$$. Знак нас не интересует (фазовые множители не меняют вероятностей). При больших $$N$$ имеем $$\varphi\approx\slashfrac{2}{\sqrt{N}}$$. Тогда после $$s\approx\slashfrac{\pi}{4}\sqrt{N}$$ итераций исходный вектор повернется на угол $$s\varphi\approx\slashfrac{\pi}{2}$$ и станет близок к искомому вектору. Это и означает, что система окажется в состоянии $$\ket{y_0}$$ с вероятностью, близкой к единице.
Если решается переборная задача в общей постановке (т.е. ответов может быть несколько, а может не быть вообще), требуются дополнительные технические ухищрения. Число шагов для поворота от исходного вектора к какому-нибудь вектору из подпространства, порожденного векторами ответов, обратно пропорционально корню из числа решений.
Второй из примеров, упомянутых во введении, — моделирование квантовомеханических систем. Это нечетко поставленная задача, так как большую роль в ней играет выбор конкретной системы и выделение существенных "степеней" свободы. С математической точки зрения, более корректно говорить о моделировании квантовых схем.
Квантовые схемы имеют конструктивное описание, если указать точность, с которой известны матричные элементы операторов, входящих в схему. Пусть есть описание квантовой схемы $$Z$$, размера $$\leq L$$ и точности $$\delta$$. Элементами этой схемы могут быть любые унитарные операторы на $$r=O(\log L)$$ q-битах (так чтобы полная длина описания схемы не превышала $$\poly(L,\log(1/\delta))\$$,). Обозначим оператор, реализуемый этой схемой, через $$Op(Z)$$.
Из результатов задач 7.1 и 7.11 следует, что можно построить универсальную квантовую схему $$U$$ размера $$\poly(L, \log 1/\delta)$$, которая моделирует работу произвольной квантовой схемы следующим образом. Если задано описание некоторой схемы $$Op(Z)$$ размера $$L$$ и ее вход $$\ket\xi$$, то$$\Bigl\| U(\ket{Z}\otimes\ket\xi)-\ket{Z}\otimes Op(Z)\ket\xi\Bigr\|= O(L\delta).$$
До сих пор мы рассматривали неоднородные вычисления (вычислялись
Замечание 8.1. Можно определить квантовую
Определение 8.2. Функция $$F\colon\cb^*\to\cb^*$$ принадлежит классу $$\BQP$$, если есть квантовый алгоритм ее вычисления, работающий за время $$O(n^d)$$ для некоторой константы $$d$$.
Как соотносится класс BQP{} с сложностными классами, введенными ранее?
Задача 8.3. Докажите, что$$\BPP\subseteq \BQP\subseteq \PPP \subseteq \PSPACE.$$ Класс $$\PPP$$ состоит из предикатов вида$$Q(x)=\Bigl(\, |\{y:R_0(x,y)\}| < |\{y:R_1(x,y)\}| \,\Bigr),$$ где $$R_0,R_1\in\P$$, и учитываются только $$y$$ с длиной меньше некоторого полинома $$q(x)$$.
Это почти все, что известно о соотношениях между BQP и другими сложностными классами. Косвенное свидетельство в пользу строгого включения $$\BPP\subset\BQP$$ дает существование эффективных квантовых алгоритмов для некоторых теоретико-числовых задач, традиционно считаемых трудными (см. раздел 12).
Заметим также, что в последнее время появились интересные результаты о квантовых аналогах некоторых более сильных сложностных классов (не описанных в части I).
Задача 8.4. Постройте квантовые схемы полиномиального размера в базисе из операторов на двух q-битах, которые выполняют следующие действия:
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.