При обсуждении квантовой реализации классических вычислений, мы ввели несколько стандартных трансформаций, действующих на пространстве кубитов. Эти квантовые элементы RAND, RОR, NОТ и СNОТ представляют трансформации специального вида - все они просто переставляют базисные вектора. Чтобы добиться полной мощности квантового компьютера, необходимо сделать следующий шаг и ввести более общие операции в пространстве 1- и 2-кубита.
Первая трансформация, которую мы введем, называется трансформацией Адамара. Она действует в пространстве 1-кубита и определена следующим образом:
$$H|0\rangle = \frac{1}{\sqrt2}|0\rangle+\frac{1}{\sqrt2}|1\rangle,\\ H|1\rangle=\frac{1}{\sqrt2}|0\rangle-\frac{1}{\sqrt2}|1\rangle$$Второе стандартное семейство квантовых элементов - это трансформации поворотов $$R_{\alpha}$$ в пространстве 1 -кубита:
$$R_{\alpha}|0\rangle=\cos \alpha |0\rangle - \sin \alpha |1\rangle,\\ R_{\alpha}|0\rangle = \sin \alpha |0\rangle+\cos \alpha |1\rangle$$Трансформация Адамара и семейство поворотов образуют ортогональную группу О(2) - каждая ортогональная трансформация в пространстве 1 -кубита является либо поворотом, либо произведением поворота и трансформации Адамара.
Последней стандартной квантовой трансформацией является семейство управляемых поворотов $$СК_{\аlpha}$$. Это семейство действует в пространстве 2-кубита и определено следующим образом:
$$CR_{\alpha}|xy\rangle=\begin{cases} |xy\rangle\text{если} х=0,\\ |x\rangle R_{\alpha}|y\rangle \text{если} x=1 \end{cases}$$Поворот применяется ко второму квантовому биту, но это поворот, управляемый значением первого квантового бита. Если первый бит имеет значение 1, поворот применяется, если 0- не применяется.
В стандартном базисе 2-кубит пространства $$\{ |00 \rangle , |01 \rangle , |10 \rangle , |11 \rangle \}$$ матрица этой трансформации имеет вид:
$$CR_{\alpha}= \begin{pmatrix}1000\\0100 \\00\cos \alpha \sin \alpha \\ 00-\sin \alpha \cos \alpha\end{pmatrix}$$Перейдем к определению квантового преобразования Фурье (КПФ).
В классическом ДПФ входом является вектор измерений $$(F_0,F_1,\dots,f_{n-1})$$, выходом - вектор коэффициентов Фурье $$(a_0,a_1,\dots,a_{n/2-1}, b_0, b_1,\dots b_{M/2-1}) $$. КПФ делает аналогичную вещь, - только входом и выходом являются п-кубиты:
$$\sum_{k=0}^{2^n-1}f_k|k_{n-1}\dotsk_{1k0} \rangle \to \sum_{p=0}^{2^{n-1}-1}a_p|p_0p_1\dotsp_{n-2} \rangle|0 \rangle+\sum_{p=0}^{2^{n-1}-1}b_p|p_0p_1\dotsp_{n-2} \rangle|1 \rangle$$Здесь $$k_{n_1}\dots k_1k_0$$ - бинарное представление целого k. Справа от стрелки удобнее писать биты р в обратном порядке: $$р = р_{n_2}2^{n-2} + \dots + 2р_1 + р_0$$, представленных как $$|р_{0р1} \dots p_{n-2} \rangle$$. Так как $$а_р$$ коэффициенты пишутся первыми в последовательности преобразования Фурье, то значение ведущего бита для них равно 0, а для коэффициентов $$b_p -1$$.
Цель этой главы представить реализацию КПФ, используя стандартные 1-кубит и 2-кубит операции.
Эта реализация построена на идеях БПФ. Также как БПФ, КПФ является рекурсивным алгоритмом. Это означает, что мы будем использовать КПФ для (n - 1)-кубита при построении КПФ для n-кубитов.
Перечислим вначале 6 шагов реализации КПФ, а затем обсудим каждый шаг в деталях. Замечательное свойство КПФ в том, что оно не требует никакой дополнительной памяти.
Шаг 1. Применить КПФ к первым n - 1 битам входа из n кубитов.
Шаг 2. Применить трансформацию Адамара к последнему биту входа.
Шаг З. Применить СNOТ к последнему биту, управляемую предпоследним битом.
Шаг 4. Применить к предпоследнему биту последовательность поворотов, управляемых предыдущими битами.
Шаг 5. Применить СNОТ к предпоследнему биту, управляемую последним битом.
Шаг 6. Применить СNOТ к первым n - 2 битам, управляемую предпоследним битом.
Начнем со входа, заданного п-кубитом:
$$\sum_{k=0}^{2^n-1}f_k|k_{n-1}\dots k_{1k0} \rangle$$Далее, следуя идеям БПФ, расщепим последовательность f на две последовательности g и h, соответствующие для g четным значениям k, для h -нечетным. После этих изменений в нотации наш входной кубит записывается так:
Выполним Шаг 1 нашей процедуры, применяя КПФ к левым n -1 битам. Результат этой операции таков:
На Шаге 2 применим трансформацию Адамара:
$$H|0 \rangle=\frac{1}{\sqrt2}|0 \rangle+\frac{1}{\sqrt2}|1 \rangle\\ H|1 \rangle=\frac{1}{\sqrt2}|0 \rangle-\frac{1}{\sqrt2}|1 \rangle $$к последнему биту. В результате получим:
$$ \sum_{p=0}^{2^{n-2}-1}\frac{a_p^g}{\sqrt2}|p_o\dots p_{n-3}\rangle|00\rangle+\frac{a_p^g}{\sqrt2} |p_0\dots p_{n-3}\rangle|01\rangle +\frac{b_p^g}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle+\frac{b_p^g}{\sqrt2}|p_0 \dots p_{n-3}\rangle|01\rangle\\ +\frac{a_p^h}{\sqrt2}|p_0 \dots p_{n-3}\rangle|00\rangle-\frac{a_p^h}{\sqrt2}|p_0 \dots p_{n-3}\rangle|01\rangle+\frac{b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle-\frac{b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|11\rangle\\ =\sum_{p=0}^{2^{n-2}-1}\frac{a_p^g+a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|00\rangle +\frac{a_p^g-a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|01\rangle +\frac{b_p^g+b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle +\frac{b_p^g-b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|11\rangle $$На Шаге 3 выполняется операция СNОТ на последнем бите, управляемая предпоследним битом:$$|xy\rangle\to|xy\oplus x\rangle$$, что дает:
$$\sum_{p=0}^{2^{n-2}-1}\frac{a_p^g+a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|00\rangle +\frac{a_p^g-a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|01\rangle +\frac{b_p^g+b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|11\rangle +\frac{b_p^g-b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle $$Шаг 4 более изощренный. Мы выполняем последовательность поворотов предпоследнего бита:
$$|0\rangle \to \cos \alpha |0\rangle -\sin \alpha |1\rangle ,\\ |1\rangle \to \sin \alpha |0\rangle +\cos |alpha |1\rangle $$Первый поворот на угол $$\pi/2^n+1}$$. Затем для каждого из первых n - 2 битов $$p_0\dotsp_{n-3}$$ выполняем поворот предпоследнего бита на угол $$\pi/2^{n-j}$$ управляемое битом $$р_j$$ . Поворот выполняется только тогда, когда $$р_j$$ равно 1, в противном случае ничего не делается. В качестве альтернативы управляемый поворот можно интерпретировать как поворот предпоследнего бита на угол $$p_j\pi/2^{n-j}$$.
Комбинируя эти повороты вместе, получаем поворот на угол
$$\alpha==(1+2p_0+2^2p_1+\dots+2^{n-2}p_{n-3})\frac{\pi}{2^{n+1}}=\frac{(2p+1)\pi}{2^{n+1}}$$Далее в записи введем сокращение, заменяя $$|p_0\dotsp_{n-3}\rangle $$ на $$|р\rangle$$. Результатом работы Шага 4 является:
$$\sum_{p=0}{2^{n-2}-1}\frac{a_p^g+a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |00\rangle -\frac{a_p^g+a_p^h}{\qsrt2} \sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |10\rangle +\frac{a_p^g-a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |01\rangle -\frac{a_p^g-a_p^h}{\qsrt2} \sin\left(\frac{(2p+1}\pi}{2^{n+1}}\right)|p\rangle |11\rangle\\ +\frac{b_p^g+b_p^h}{\sqrt2} \sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle 01\rangle +\frac{b_p^g+b_p^h}{\qsrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |11\rangle+\frac{b_p^g-b_p^h}{\sqrt2} \sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |00\rangle +\frac{b_p^g-b_p^h}{\qsrt2} \cos\left(\frac{(2p+1}\pi}{2^{n+1}}\right)|p\rangle |10\rangle\\ =\sum_{p=0}^{2^{n-2}-1} \left(\frac{a_p^g+a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) +\frac{b_p^g-b_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |00\rangle + \left(\frac{a_p^g-a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) +\frac{b_p^g+b_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |01\rangle\\ +\left(\frac{b_p^g-b_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) -\frac{a_p^g+a_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |10\rangle+\left(\frac{b_p^g+b_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) -\frac{a_p^g-a_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |11\rangle$$На шаге 5 применяется СNОТ к предпоследнему биту, управляемое последним битом:
$$|xy\rangle \to |x \oplus yy\rangle $$что дает:
$$\sum_{p=0}^{2^{n-2}-1}\left(\frac{a_p^g+a_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) + \frac{b_p^g-b_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |00\rangle + \left(\frac{a_p^g-a_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) + \frac{b_p^g+b_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |11\rangle \\ +\left(\frac{b_p^g-b_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) - \frac{a_p^g+a_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |10\rangle +\left(\frac{b_p^g+b_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) - \frac{a_p^g-a_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |01\rangle $$Наш завершающий шаг состоит из применения управляемого отрицания СNОТ к каждому из первых n - 2 битов, все управляемые предпоследним битом. При записи финального результата разделяем его на две части. Тогда, когда предпоследний бит равен нулю, сохраняем р как суммируемую переменную. Когда же предпоследний бит равен единице, заменяем р новой переменной r. Биты r берутся с отрицанием, результат отрицания будем обозначать как $$|\bar r\rangle =|\bar r_0 \bar r_1 \dots \bar r_{n-3}\rangle $$. В результате получаем следующее выражение:
Вспоминая формулы БПФ, мы обнаруживаем, что первые два коэффициента-это$$а_р$$ и $$b_р$$ для $$0 \le р < 2^{n-2}$$, в то время как последние два коэффициента - это $$а_р$$ и $$b_р$$ для $$2^{n-2} \le р < 2^{n-1}$$, $$р = 2^{n-1} - 1 - r$$. Предыдущее выражение упрощается и имеет вид:
$$ \sum_{p=0}^{2^{n-2}-1}(a_p|p\rangle|00\rangle + b_p|p\rangle|01\rangle) +\sum_{\substack{p=2^{n-2}\\p =2^{n-1}-1-r}}^{2^{n-1}-1}(a_p|\bar r\rangle|10\rangle+b_p|\bar r\rangle|11\rangle)$$Когда $$2^{n-2} \le р < 2^{n-1}$$, $$р = 2^{n-1} - 1 - r$$, то оно записывается как целое из n - 1 бит в бинарной форме, ведущий бит р равен 1, а остальные n - 2 бита являются отрицанием битов $$r, |р\rangle = |\bar r\rangle|1\rangle$$, так что две части суммы можно скомбинировать, рассматривая р теперь как целое из n - 1 битов,
Мы видим, что в результате последовательности шагов 1-б в точности получено квантовое преобразование Фурье входа из n-кубита.
Упражнение. Покажите, что сложность квантового преобразования Фурье для п-кубита (число используемых стандартных квантовых элементов) равна $$n^2$$.
Мы видим, что КПФ имеет квадратичную сложность (как функция от числа битов), в то время как БПФ имеет экспоненциальную сложность.
При обсуждении квантовой реализации классических вычислений, мы ввели несколько стандартных трансформаций, действующих на пространстве кубитов. Эти квантовые элементы RAND, RОR, NОТ и СNОТ представляют трансформации специального вида - все они просто переставляют базисные вектора. Чтобы добиться полной мощности квантового компьютера, необходимо сделать следующий шаг и ввести более общие операции в пространстве 1- и 2-кубита.
Первая трансформация, которую мы введем, называется трансформацией Адамара. Она действует в пространстве 1-кубита и определена следующим образом:
$$H|0\rangle = \frac{1}{\sqrt2}|0\rangle+\frac{1}{\sqrt2}|1\rangle,\\ H|1\rangle=\frac{1}{\sqrt2}|0\rangle-\frac{1}{\sqrt2}|1\rangle$$Второе стандартное семейство квантовых элементов - это трансформации поворотов $$R_{\alpha}$$ в пространстве 1 -кубита:
$$R_{\alpha}|0\rangle=\cos \alpha |0\rangle - \sin \alpha |1\rangle,\\ R_{\alpha}|0\rangle = \sin \alpha |0\rangle+\cos \alpha |1\rangle$$Трансформация Адамара и семейство поворотов образуют ортогональную группу О(2) - каждая ортогональная трансформация в пространстве 1 -кубита является либо поворотом, либо произведением поворота и трансформации Адамара.
Последней стандартной квантовой трансформацией является семейство управляемых поворотов $$СК_{\аlpha}$$. Это семейство действует в пространстве 2-кубита и определено следующим образом:
$$CR_{\alpha}|xy\rangle=\begin{cases} |xy\rangle\text{если} х=0,\\ |x\rangle R_{\alpha}|y\rangle \text{если} x=1 \end{cases}$$Поворот применяется ко второму квантовому биту, но это поворот, управляемый значением первого квантового бита. Если первый бит имеет значение 1, поворот применяется, если 0- не применяется.
В стандартном базисе 2-кубит пространства $$\{ |00 \rangle , |01 \rangle , |10 \rangle , |11 \rangle \}$$ матрица этой трансформации имеет вид:
$$CR_{\alpha}= \begin{pmatrix}1000\\0100 \\00\cos \alpha \sin \alpha \\ 00-\sin \alpha \cos \alpha\end{pmatrix}$$Перейдем к определению квантового преобразования Фурье (КПФ).
В классическом ДПФ входом является вектор измерений $$(F_0,F_1,\dots,f_{n-1})$$, выходом - вектор коэффициентов Фурье $$(a_0,a_1,\dots,a_{n/2-1}, b_0, b_1,\dots b_{M/2-1}) $$. КПФ делает аналогичную вещь, - только входом и выходом являются п-кубиты:
$$\sum_{k=0}^{2^n-1}f_k|k_{n-1}\dotsk_{1k0} \rangle \to \sum_{p=0}^{2^{n-1}-1}a_p|p_0p_1\dotsp_{n-2} \rangle|0 \rangle+\sum_{p=0}^{2^{n-1}-1}b_p|p_0p_1\dotsp_{n-2} \rangle|1 \rangle$$Здесь $$k_{n_1}\dots k_1k_0$$ - бинарное представление целого k. Справа от стрелки удобнее писать биты р в обратном порядке: $$р = р_{n_2}2^{n-2} + \dots + 2р_1 + р_0$$, представленных как $$|р_{0р1} \dots p_{n-2} \rangle$$. Так как $$а_р$$ коэффициенты пишутся первыми в последовательности преобразования Фурье, то значение ведущего бита для них равно 0, а для коэффициентов $$b_p -1$$.
Цель этой главы представить реализацию КПФ, используя стандартные 1-кубит и 2-кубит операции.
Эта реализация построена на идеях БПФ. Также как БПФ, КПФ является рекурсивным алгоритмом. Это означает, что мы будем использовать КПФ для (n - 1)-кубита при построении КПФ для n-кубитов.
Перечислим вначале 6 шагов реализации КПФ, а затем обсудим каждый шаг в деталях. Замечательное свойство КПФ в том, что оно не требует никакой дополнительной памяти.
Шаг 1. Применить КПФ к первым n - 1 битам входа из n кубитов.
Шаг 2. Применить трансформацию Адамара к последнему биту входа.
Шаг З. Применить СNOТ к последнему биту, управляемую предпоследним битом.
Шаг 4. Применить к предпоследнему биту последовательность поворотов, управляемых предыдущими битами.
Шаг 5. Применить СNОТ к предпоследнему биту, управляемую последним битом.
Шаг 6. Применить СNOТ к первым n - 2 битам, управляемую предпоследним битом.
Начнем со входа, заданного п-кубитом:
$$\sum_{k=0}^{2^n-1}f_k|k_{n-1}\dots k_{1k0} \rangle$$Далее, следуя идеям БПФ, расщепим последовательность f на две последовательности g и h, соответствующие для g четным значениям k, для h -нечетным. После этих изменений в нотации наш входной кубит записывается так:
Выполним Шаг 1 нашей процедуры, применяя КПФ к левым n -1 битам. Результат этой операции таков:
На Шаге 2 применим трансформацию Адамара:
$$H|0 \rangle=\frac{1}{\sqrt2}|0 \rangle+\frac{1}{\sqrt2}|1 \rangle\\ H|1 \rangle=\frac{1}{\sqrt2}|0 \rangle-\frac{1}{\sqrt2}|1 \rangle $$к последнему биту. В результате получим:
$$ \sum_{p=0}^{2^{n-2}-1}\frac{a_p^g}{\sqrt2}|p_o\dots p_{n-3}\rangle|00\rangle+\frac{a_p^g}{\sqrt2} |p_0\dots p_{n-3}\rangle|01\rangle +\frac{b_p^g}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle+\frac{b_p^g}{\sqrt2}|p_0 \dots p_{n-3}\rangle|01\rangle\\ +\frac{a_p^h}{\sqrt2}|p_0 \dots p_{n-3}\rangle|00\rangle-\frac{a_p^h}{\sqrt2}|p_0 \dots p_{n-3}\rangle|01\rangle+\frac{b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle-\frac{b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|11\rangle\\ =\sum_{p=0}^{2^{n-2}-1}\frac{a_p^g+a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|00\rangle +\frac{a_p^g-a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|01\rangle +\frac{b_p^g+b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle +\frac{b_p^g-b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|11\rangle $$На Шаге 3 выполняется операция СNОТ на последнем бите, управляемая предпоследним битом:$$|xy\rangle\to|xy\oplus x\rangle$$, что дает:
$$\sum_{p=0}^{2^{n-2}-1}\frac{a_p^g+a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|00\rangle +\frac{a_p^g-a_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|01\rangle +\frac{b_p^g+b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|11\rangle +\frac{b_p^g-b_p^h}{\sqrt2}|p_0\dots p_{n-3}\rangle|10\rangle $$Шаг 4 более изощренный. Мы выполняем последовательность поворотов предпоследнего бита:
$$|0\rangle \to \cos \alpha |0\rangle -\sin \alpha |1\rangle ,\\ |1\rangle \to \sin \alpha |0\rangle +\cos |alpha |1\rangle $$Первый поворот на угол $$\pi/2^n+1}$$. Затем для каждого из первых n - 2 битов $$p_0\dotsp_{n-3}$$ выполняем поворот предпоследнего бита на угол $$\pi/2^{n-j}$$ управляемое битом $$р_j$$ . Поворот выполняется только тогда, когда $$р_j$$ равно 1, в противном случае ничего не делается. В качестве альтернативы управляемый поворот можно интерпретировать как поворот предпоследнего бита на угол $$p_j\pi/2^{n-j}$$.
Комбинируя эти повороты вместе, получаем поворот на угол
$$\alpha==(1+2p_0+2^2p_1+\dots+2^{n-2}p_{n-3})\frac{\pi}{2^{n+1}}=\frac{(2p+1)\pi}{2^{n+1}}$$Далее в записи введем сокращение, заменяя $$|p_0\dotsp_{n-3}\rangle $$ на $$|р\rangle$$. Результатом работы Шага 4 является:
$$\sum_{p=0}{2^{n-2}-1}\frac{a_p^g+a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |00\rangle -\frac{a_p^g+a_p^h}{\qsrt2} \sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |10\rangle +\frac{a_p^g-a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |01\rangle -\frac{a_p^g-a_p^h}{\qsrt2} \sin\left(\frac{(2p+1}\pi}{2^{n+1}}\right)|p\rangle |11\rangle\\ +\frac{b_p^g+b_p^h}{\sqrt2} \sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle 01\rangle +\frac{b_p^g+b_p^h}{\qsrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |11\rangle+\frac{b_p^g-b_p^h}{\sqrt2} \sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)|p\rangle |00\rangle +\frac{b_p^g-b_p^h}{\qsrt2} \cos\left(\frac{(2p+1}\pi}{2^{n+1}}\right)|p\rangle |10\rangle\\ =\sum_{p=0}^{2^{n-2}-1} \left(\frac{a_p^g+a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) +\frac{b_p^g-b_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |00\rangle + \left(\frac{a_p^g-a_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) +\frac{b_p^g+b_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |01\rangle\\ +\left(\frac{b_p^g-b_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) -\frac{a_p^g+a_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |10\rangle+\left(\frac{b_p^g+b_p^h}{\sqrt2} \cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right) -\frac{a_p^g-a_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right) \right)|p\rangle |11\rangle$$На шаге 5 применяется СNОТ к предпоследнему биту, управляемое последним битом:
$$|xy\rangle \to |x \oplus yy\rangle $$что дает:
$$\sum_{p=0}^{2^{n-2}-1}\left(\frac{a_p^g+a_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) + \frac{b_p^g-b_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |00\rangle + \left(\frac{a_p^g-a_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) + \frac{b_p^g+b_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |11\rangle \\ +\left(\frac{b_p^g-b_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) - \frac{a_p^g+a_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |10\rangle +\left(\frac{b_p^g+b_p^h}{\sqrt2} \cos \left( \frac{(2p+1)\pi}{2^{n+1}}\right) - \frac{a_p^g-a_p^h}{\sqrt2} \sin \left( \frac{(2p+1)\pi}{2^{n+1}}\right)\right)|p\rangle |01\rangle $$Наш завершающий шаг состоит из применения управляемого отрицания СNОТ к каждому из первых n - 2 битов, все управляемые предпоследним битом. При записи финального результата разделяем его на две части. Тогда, когда предпоследний бит равен нулю, сохраняем р как суммируемую переменную. Когда же предпоследний бит равен единице, заменяем р новой переменной r. Биты r берутся с отрицанием, результат отрицания будем обозначать как $$|\bar r\rangle =|\bar r_0 \bar r_1 \dots \bar r_{n-3}\rangle $$. В результате получаем следующее выражение:
Вспоминая формулы БПФ, мы обнаруживаем, что первые два коэффициента-это$$а_р$$ и $$b_р$$ для $$0 \le р < 2^{n-2}$$, в то время как последние два коэффициента - это $$а_р$$ и $$b_р$$ для $$2^{n-2} \le р < 2^{n-1}$$, $$р = 2^{n-1} - 1 - r$$. Предыдущее выражение упрощается и имеет вид:
$$ \sum_{p=0}^{2^{n-2}-1}(a_p|p\rangle|00\rangle + b_p|p\rangle|01\rangle) +\sum_{\substack{p=2^{n-2}\\p =2^{n-1}-1-r}}^{2^{n-1}-1}(a_p|\bar r\rangle|10\rangle+b_p|\bar r\rangle|11\rangle)$$Когда $$2^{n-2} \le р < 2^{n-1}$$, $$р = 2^{n-1} - 1 - r$$, то оно записывается как целое из n - 1 бит в бинарной форме, ведущий бит р равен 1, а остальные n - 2 бита являются отрицанием битов $$r, |р\rangle = |\bar r\rangle|1\rangle$$, так что две части суммы можно скомбинировать, рассматривая р теперь как целое из n - 1 битов,
Мы видим, что в результате последовательности шагов 1-б в точности получено квантовое преобразование Фурье входа из n-кубита.
Упражнение. Покажите, что сложность квантового преобразования Фурье для п-кубита (число используемых стандартных квантовых элементов) равна $$n^2$$.
Мы видим, что КПФ имеет квадратичную сложность (как функция от числа битов), в то время как БПФ имеет экспоненциальную сложность.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.