Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
ф(х) = {* °^ж<1/2, (П30)
v ' ' 1 1/2 <; х < 0.
Из (П.28) мы видим, что при вейвлет-преобразовании Хаара происходит дискретизация преобразуемой непрерывной функции и расщепление на две части, относящиеся к подпространству более высокого уровня разрешения Vn+i.
Квантовое однокубитовое (L = 1, N = 2, т = 0,1, п = 0,-1) вейвлет-преобразование Хаара QWTHi осуществляется с помощью одного оператора Адамара Н, преобразующего исходные состояния кубита с амплитудами /i(m)
\Ф) = /о(0)|0) + /0(1)|1> = (П.31)
к состоянию, в котором два состояния кубита имеют амплиту-ды /_1 (0) и w-i(0):
QWTHi ¦ № = нщ = я (*(«) = т (*<;>! А<|>) = (п 32)
^i((°o))=/-i(0)|0)+w-i(0)|1)-
Для двухкубитового преобразования (L = 2, т mod 4 = 0,1,2,3, п = 0,-1,-2) потребуется более сложная квантовая схема. Двухку-битовые состояния |0л0#), |0л1#)5\^а^в) и \1а^в) будем использовать
Приложение П.2. Квантовое вейвлет-преобразование 113
в качестве базисных. Квантовая схема и матрица преобразования принимают вид [2.56]:
qwth2 =
(1 1 1 1 \
л/2 -у/2 О О
1 1-1-1
V 0 0 л/2 — л/2 У
(П.ЗЗ)
где
СН =
н
А о о о \ О лДТ2 о л/Щ 0 0 10 Vo 072 О -0727
(П.34)
— контролируемый оператор Адамара. Последовательность операций в квантовой схеме производится как обычно слева направо, а результирующая матрица умножается на преобразуемые состояния слева. Двух-кубитовая операция Хаара осуществляется тремя однокубитовыми операциями и одной двухкубитовой операцией, то есть всего четырьмя элементарными операциями.
Например, состояние
IV») = /™(0)|0л0> + /„(1)|01) + /„(2)110) + /„(3)|11)
преобразуется следующим образом:
(П.35)
QWTH2 -\ф) = ±
1
у/2
1
\0
1
-у/2
1
0
1
о
-1
72
1 \
0 -1
--Л)
/1/2(/„(0) + /„( 1) + /«(2) + /п(3))\ лД72(/„(о) - /„(1))
1/2(/и(0) + /„(1) — /и(2) — /и(3)) хД72(/п(2) - Ш) )
(Ш)\
/п(1)
/п(2)
V/»(3)/
IVn—l (0) fn-l(l)
\wn-l(l)/
(П.36)
114
Глава 2
то есть для двухкубитового регистра при заданном уровне разрешения мы получаем две вейвлет-амплитуды
ti>„_i(0) = x/V2(/n(0) - /и(1)), = \Д72(/„(2) - /„(3)).
(П.37)
Число элементарных квантовых операций, необходимых для реализации вейвлет-преобразования для всего диапазона уровней разрешения, определяется длиной используемых на операции расщепления фильтров S и числом кубитов L в квантовом регистре и оказывается порядка SL2 [2.30], тогда как быстрое классическое вейвлет-преобразование потребовало бы порядка L2l операций [2.59]. Если S', как в случае преобразования Хаара, порядка единицы, то квантовые вейвлет-преобразования имеют ту же сложность, что и квантовые фурье-преобразования. Однако преимущество квантовых вейвлет-преобразований появляется в случае, когда достаточно ограничиться определенным диапазоном разрешения \п\ « I, и потребуется всего \n\SL операций [2.60].
П.2.5. Квантовое вейвлет-преобразование как альтернатива фурье-преобразованию в алгоритме факторизации Шора
Алгоритм факторизации Шора основан на нахождении периода г определенным образом сформированных амплитуд состояния квантового регистра. Для этих целей используется квантовое дискретное фурье-преобразование, которое для регистра из L кубитов строится из L операторов Адамара Н и L(L — 1)/2 операторов контролируемого изменения фазы то есть требует L(L + 1)/2 элементарных операций (см. раздел 2.2.6).
Представим квазипериодическую дискретную функцию, характеризующуюся конечным числом равных по амплитуде отсчетов, отстоящих на расстояниях г друг от друга (х = j>), в виде:
f(x) = \frjN • 6xjr, j = 0,1,... [N/r — 1]. (П.38)
Амплитуда фурье-преобразования такой функции (2.55)
N/r-1 _ ...
f(k) = (Vi/N) ? ехр((П.39)
3=0
Приложение П.2. Квантовое вейвлет-преобразование 115
имеет конечное число равновероятных дискретных отсчетов на одномерной шкале при к = vN/r, v = 0,1,... , г — 1. Существенным недостатком дискретного фурье-преобразования, как уже отмечалось выше, является то, что при его выполнении имеют место значительные вычислительные затраты, особенно при учете амплитуд с большими значениями к, которые обычно по разным причинам не достаточно четко известны или имеют сильно отличающуюся временную цену, связанную с выполнением операций контролируемого изменения фазы. Если искомый период г значительно больше расстояния 2~ь между кубитами регистра, что соответствует сравнительно малым значениям параметра к, то вычислительные затраты, учитывающие при фурье-преобразовании в равной мере все амплитуды, оказываются излишне большими.