Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
(П.17)
В обозначениях здесь явно учтено, что, как следует из выражений (П.16) и (П.17), fn-1 является функцией 2m, a wn-1 функцией 2т + 1.
Таким образом, в результате действия фильтров Добешьи h(m) и #(т) дискретные функции /п(ш) на каждом шаге перехода к более низкому уровню разрешения расщепляются на две «зеркальные» функции /n_i(2m) и wn-i(2m + l). Линейное пространство квадратично суммируемых функций Z2([0,iV — 1]), в котором определены /п(ш), расщепляется на два замкнутых подпространства с единым ортонорми-рованным базисом с удвоенной размерностью /2([0,2iV — 1]).
Совокупность операций, осуществляемых парами фильтров, получило название банка квадратурных зеркальных фильтров (quadrature mirror filters — QMF). Число значений m, при которых h(m) = 0, называется длиной фильтра S.
Рассмотрим в качестве примера унитарное преобразование Добешьи (D4) для случая, когда длина фильтров S = N = 4, L = 2, ш = 0,1,2,3. Введем для удобства обозначения: /п(ш) = /п,т5
fn-i(2m) = fn—i,2m и wn-i(2m + 1) = w„_i,2to+i- Для системы урав-
110
Глава 2
нений (П.16), (П.17) получим
/п—i,2m = ^ ^ h{m 2m)/n?ri
ш' mod4
(П.18)
Wn-I,2m+1 = X] (—i)"1/i(2m + 1 — m')fn
(П.19)
m' mod4
В матричной форме преобразование Добешьи имеет вид [2.56, 2.57]:
( fn---1,0 ^ /Ло fti h2 h% 0 0 0 0 ^ fn, o\
Wn-1,1 /ii -Л0 h3 -h2 0 0 0 0 fn,l
fn-1,2 0 0 h0 hi h2 Ы 0 0 fn,2
™n-l,3 0 0 h! -ho h3 -h2 0 0 fn,3
/п---1,4 0 0 0 0 ho hi h2 h3 fn, 0
1,5 0 0 0 0 h! ---ho h3 -h2 fn,l
fn---1,6 h2 Лз 0 0 0 0 h0 hi fn,2
Vtfn-1,7/ \Лз -h2 0 0 0 0 hi -h0) \fn, 3/
матричные элементы /i(m ) = h>m имеют четыре значения
, (П.20)
h0 —
л/З
hX =
1 + л/3
/12 =
3 + л/3 4 л/2 ’
Л3 =
3 — л/3
V2 •
(П.21)
Соответствующее квантовое преобразование может быть произведено с помощью двух однокубитовых операторов поворота У($) (см. далее гл. 4) вокруг оси у на угол $ и двухкубитовой операции S2, определяющей циклическую перестановку состояний в квантовом регистре из двух кубитов |ж(ь#1,ж25#з) ^ 1жз9жъ^2)5 которая осуществляется с помощью однокубитовой операции NOT, двухкубитовой операции CNOT и одной трехкубитовой операции Тоффоли [2.30, 2.56]: Полное число элементарных операций, если учесть, что операция Тоффоли может быть выполнена посредством пяти духкубитовых операций [2.1], равно девяти:
------------ 52------------= (/4 0 ?(7тг/6) • S2 • (/4 0 Г(5тг/3))|<=. (П.22)
ЧУ(5я-/3)Н ЩТя/Ыг
Приложение П.2. Квантовое вейвлет-преобразование 111
П.2.4. Вейвлет-преобразование Хаара
Простейшим преобразованием является преобразование Хаара (А.Нааг), недостатком которого является то, что хотя его базисные функции удовлетворяют условию компактности, но не удовлетворяет условию плавности и потому недостаточно хорошо локализованы на шкале к. Однако это преобразование полезно в том отношении, что оно позволяет наглядно продемонстрировать особенности и преимущества вейвлет-преобразования, а также указать принципы построения соответствующих квантовых схем. Выберем отцовскую функцию масштабирования в виде (р(х) = 1 в интервале [0, 1) и равной нулю в остальной области, тогда дочерняя функция масштабирования будет отлична от нуля, если
О ^ т2~п ^х^(т + 1)2~п <С N - 1, (П.23)
откуда следует, что параметры тип лежат в конечных интервалах:
О ^ ш <С (N - l)2n <С N - 1, -L <С п <С 0. (П.24)
Из (П.8) получим
h(m) = y/^j2{Smfi + <W), (П.25)
то есть длина фильтров Хаара S = 2. Пользуясь далее (П.15), найдем
(га+1)2~п
fn(m) = 2”/2 j f(x) dx = y/lj2(fn+1(2m) + fn+1(2m + 1)),
m2“n
(П.26)
ГДе (2т+1)2“(гг + 1)
Ли-1 (2т) = 2(”+1)/2 J f(x)dx,
2т2-(гг+1) (2т+2)2“(гг+1)
(П.27)
fn+1 (2т + 1) = 2<ге+1>/2 J f(x) dx.
(2m+l)2-(n+1)
112
Глава 2
С помощью (П.12) для вейвлет-преобразование Хаара получим
wn(m) = y/lj2(fn+1(2m) - /„+1(2m + 1)). (П.28)
Соответственно, дочерняя вейвлет-функция фп(х,т) принимает вид
, , ч j _2П/2 т2~п ^ х < (т + l/2)m2_n, /тт ч
фп(х,т) = < (П.29)
^ ' j _2П/2 (ш + 1/2)2_п ^ ж < (ш + l)2_n, V '
что соответствует материнской функции 'ф(х), являющейся давно известной функцией Хаара (А. Нааг) [2.58], которая соответствует М — О и отлична от нуля для х — [0,1):