Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
2~п 2°
2~‘
2 2 23
О 2 4 6 8 т
Рис. П.2.1. Разбиение х — к плоскости при вейвлет-преобразовании для значений 0 ^ т < N = 23 = 8, — 3 ^ п ^ 0.
Существует много типов вейвлетов с различным характером локализации. Наиболее интересные из них удовлетворяют условию компактности (compact support), то есть они равны нулю вне некоторого конечного интервала длины. Алгоритм построения полной совокупности произвольных типов базисных вейвлетов был развит в теории многоуровневого разрешения (multiresolution analysis) [2.50, 2.51]. Приведем далее основные положения этой теории, опуская доказательства.
П.2.2. Построение ортонормированного вейвлет-базиса
Рассмотрим последовательность линейных подпространств Vn натянутых на совокупность вспомогательных квадратично интегрируе-
1
+
Приложение П.2. Квантовое вейвлет-преобразование 107
мых функций, соответствующих отдельным 2п-м уровням разрешения [2.51, 2.54]. Базисом для подпространства Vn с масштабом, определяемым параметром п, является полная ортонормированная совокупность таких функций, задаваемых выражением
(рп(х,т) = 2п/2(р(2пх — т) (П.5)
и условием ортонормированности
N
j <pn{x,m)<pn(x,m')dx — $тт' • (п.б)
О
Они называются функциями масштабирования (scaling functions). Далее будет удобно рассматривать функции ipn(x,m) как периодические на множестве целых чисел ш, то есть в зависимости от т mod N.
В теории многоуровневого разрешения предполагается, что функциональное подпространство более низкого уровня разрешения Vn вложено в подпространство с более высоким уровнем: Vn С Vn+\. При этом каждая «отцовская» функция масштабирования (р(х) = (ро(х,0), определенная в Vo, выражается через функцию (pi(x,m), определенную в подпространстве Vi посредством линейного соотношения:
(р(х) = V2 ^ h(m)ip(2x — ш), (П.7)
mmodiV
где вид импульсного отклика h(m) зависит от вида функции (р(х):
1
(р(х)(р(2х — т) dx = h(m). (П.8)
о
Для дочерних функций масштабирования получим уравнения
(pn-i(x, т) = (р(2п~1х — т) = ^ h(mf — 2т)(рп(х, т!). (П.9)
т' modTV
В отличие от функций масштабирования вейвлеты являются ортогональными базисными функциями другого функционального подпространства Wn, которое представляет собой ортогональное дополнение к Vn в подпространстве V^+i: Fn+i = Vn 0 Wn. Поскольку
108
Глава 2
Wn С V^+i, то материнский вейвлет ф(х) может быть выражен через функцию масштабирования ipi(x,m) [2.54, 2.55] с помощью выражения, аналогичного (П.7):
^(ж) = XI #(шМ2ж - т)> (п.10)
mmodN
где
g(m) = ( — l)mh(l — т). (П.11)
И, соответственно, получим
V’n-ifх,т) — X g(m' - 2т)<рп(х,т') -
т' modTV
= X (—l)m h(2m + 1 — т')(рп(х, т!).
(П.12)
т' modTV
Пары импульсных откликов h(m) и g(m), называемых фильтрами До-бешьи (I. Daubechies), обладают свойствами:
h(m)h(m — 2к) = (П.13)
mmodiV
а также удовлетворяют условию
X h(2m) = J] h{2m + 1) = л/Щ (П.14)
mmodN mmodN
П.2.3. Дискретное вейвлет-преобразование
Для дискретизации функции f(x) далее воспользуемся итерационным алгоритмом Добешьи (I. Daubechies) и Меллата (S.Mallat) [2.54, 2.55], основанным на теории многоуровневого разрешения.
Производя преобразование масштабирования функции f(x) с помощью функций у?та(ж,ш), получим ее дискретное представление как функцию дискретной переменной т для каждого заданного уровня разрешения (параметр п):
N
fn(m) = J ip„(x,m)f(x)dx, (П.15)
Приложение П.2. Квантовое вейвлет-преобразование 109
а учитывая (П.9), найдем уравнение, связывающее амплитуды разного уровня разрешения /n_i(2m) и /п(ш):
N
fn-i{2m) = J <pn-1(x,m)f(x) dx = ^ h(m'-2m)fn(m'). (П.16)
q т' mod TV
Амплитуду fn (ш) будем рассматривать теперь как амплитуду состояния ш-го кубита для n-го разрешения в квантовом регистре из L = = log2 N кубитов.
Аналогичным образом, учитывая (П.12), найдем выражение для связи дискретных вейвлет-преобразований разного уровня разрешения
N
w„-1{2m + 1) = J •фп-1(х,т)/(х) dx = ^ g(m'-2m)fn(m') =
q m'modN
= Е (-l)m'h(l + 2m-m')fn(m').
т' mod TV
