Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 76

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Умова рівності регістрів ключового тега та регістру кодування слова враховується в операторі ST .

Наступним кроком алгоритму є переведення додаткового кубіта \f) у початковий базисний стан j 0} та вилучення його із подальшого розгляду. Це можна зробити за допомогою унітарного опера­тора U-1, який є оберненим до оператора UF (3). В результаті отримаємо

k) f-1 = uf1 W) T

42^л

х <tXk

\x) = \qt) 8\qw).

Отже, в результаті дії складеного оператора UFFUTUF отримаємо суперпозицію базисних рів-ноймовірнісних станів (2), в якій стани, що коду­ють наявні ключові слова, мають від'ємну ампліту­ду.

5. Підсилення амплітуд заданих квантових станів

Для того щоб при вимірюванні виявити квантові стани, в яких закодовані ключові слова, необхідно підсилити амплітуди шуканих станів. Таке підси­лення амплітуд станів, які мають задані властивос­ті, можна здійснити за допомогою оператора інвер­сії відносно середнього, який використовується в алгоритмі Гровера для пошуку в неструктурованій квантовій базі даних [1,2,3]. Оператор інверсії роз­глянемо у вигляді

(9)

де |¥с) = H -| 0)8

=2" -1

X 10

i=0

В геометричній інтерпретації оператор UG здій­снює в Гільбертовому просторі дзеркальне відо­браження деякого вектора відносно осі, яка визна­чається вектором |yc). Оператор інверсії можна представити сукупністю однокубітних операторів Адамара та операторів інверсії стану кубіта віднос­но базисного вектора 10)

UG = H8" (2|0)(0| -1)8"H8".

Оператор UG також називають оператором ін­версії відносно середнього [1, 2, 3, 6], оскільки пе­ретворення UG можна зообразити

Ug :XaV)^X(2А~ai)|0 ,

ii

де А — середнє значення амплітуд aV. Оператор UG можна зообразити унітарною матрицею, елементи якої визначаються правилом

,i * J

1,i = j.

Підсилення амплітуд станів із інверсними зна­ками амплітуд відбувається внаслідок дії оператора інверсії UG аналогічно до механізму, описаного в алгоритмі Гровера [1, 2, 3]. Враховуючи визначен­ня операторів (3), (6), (7), (9), розглянемо ітерацію алгоритму Гровера у загальному вигляді складено­го оператора

UgU-UtUf

(10)

Можна показати, що внаслідок реалізації ітера­ції UI можна підсилити амплітуди заданих станів в 3 рази. Якщо шукане ключове слово зустрічається в текстовому масиві лише один раз, то аналогічно до алгоритму Гровера [1,2,3] оптимальна кількість ітерацій UI буде

k„ , N = 2"+"w,

U 4

де N — кількість квантових станів рівна N = NtNw. Отже, складість алгоритму в даному випадку буде O(-JN) . Якщо кількість шуканих ключових тегів рівна /, тоді згідно із [1,2,3,6] кількість необхідних ітерацій буде рівна

-N

4/

Однак наперед невідомо, яка кількість входжень ключового слова в текстовому масиві. В такому ви­падку можна провести серію реалізацій алгоритму Гровера із кількостями ітерацій UI, які утворюють прогресію

kU = 1,2,4,8,...U ,

де /U — деяке максимальне значення кількості ітерацій UI. Тобто спочатку реалізується алгоритм з однією ітерацією, потім із двома і т.д. Якщо в цій серії реалізацій алгоритму при вимірюванні вияв­лено шукані квантові стани, тоді можна прийняти рішення про наявність шуканого ключового слова в аналізованому текстовому масиві, а також оцінити кількість появи цього слова в текстовому масиві. Можна показати, що складність алгоритму в такому випадку є також . В класичному алгоритмі

складність пошуку в неструктурованому текстовому масиві буде O(Nt). Враховуючи те, що N = NtNw, можна побачити, що не для всіх випадків кванто­вий алгоритм дасть поліноміальне прискорення обчислень. Наприклад, коли Nt ~ Nw, складність пошуку класичного та квантового алгоритму буде співмірною. Поліноміальне прискорення алгоритму буде спостерігатись для випадку, коли розмір тек­стового масиву суттєво перевищує розмір словника, тобто Nt >> Nw .

Висновки

В роботі розглянута модель запису текстових масивів у квантову пам'ять. Запропонований кван­товий алгоритм пошуку ключових слів у текстових масивах. Реалізація цього алгоритму здійснюється на основі квантових логічних елементів, зокрема,з використанням вентиля Тоффолі. Ітерація Гро-вера використовується для підсилення амплітуд квантових станів із заданими властивостями. Пока­зано, що реалізація квантового алгоритму пошуку ключових слів у текстових масивах за деяких умов дає можливість експоненційно скоротити об'єм необхідної пам'яті та поліноміально зменшити час виконання алгоритму у порівнянні із класичними алгоритмами внаслідок реалізації квантового пара­лелізму. Ефективність квантового алгоритму зрос­тає у випадку великих розмірів текстових масивів, які суттєво перевищують розмір словника, та у ви­падках багатократної появи ключових слів в аналі­зованому текстовому масиві.

Список літератури. 1. Grover, L.K. Quantum Mechanics helps in searching for a needle in haystack/ L.K.Grover // Phys.Rev. Lett. 79(2):325—328, 1997. 2. Za/ka, C. Grover's quantum searching algorithm is optimal./ C. Zalka. // Phys. Rev. A., 60(4):2746—2751, 1999. 3. Lavor, C., Manssur, L.R.U., Portuga/, R. Grover's Algorithm: Quantum Database Search [Електронний ресурс] // C.Lavor, L.R.U. Manssur, R. Portugal // arXiv:quant-ph/0301079v1 (2003). 4. Pav/y-shenko, B. Quantum Algorithm of Evolutionary Analysis of 1D Cellular Automata [Електронний ресурс] // B. Pavly-shenko // arXiv:1001.4870v1 (2010). 5. Крохмальський, Т. Квантові комп'ютери: основи й алгоритми (короткий огляд) [Текст]/ Т.Крохмальський // Журнал фізичних досліджень. — 2004. — Т. 8. — № 4. — С. 1-15. 6. Китаев, А.

Классические и квантовые вычисления [Текст] / А. Ки­таев, А. Шень, М. Вялий М.: МЦНМО, ЧеРо, 1999.

— 192 с.

Надійшла до редколегії 26.09.2011

УДК 004.652: 519.765:519.767:004.93

Квантовый алгоритм поиска ключевых слов в тексто­вых массивах данных / Б.М. Павлышенко // // Бионика интеллекта: науч.-техн. журнал. — 2011. — № 3 (77). —

С. 157-161.

Предложена модель квантовой записи массива тек­стовых данных. Проанализирован поиск ключевых слов в квантовой базе данных текстовых массивов используя елементы алгоритма Гровера. Показана эффективность квантового алгоритма в случаэ больших размеров тек­стовых массивов, которые существенно превышают раз­мер словаря и в случае многократного появления ключе­вых слов в анализированном массиве.

Библиогр.: 6 назв.

УДК 004.652: 519.765:519.767:004.93

The Quantum Algorithm of Key Words Search in Text Arrays / B.M. Pavlyshenko // // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 157-161.

The model of text array quantum writing has been suggested. The search of key words in quantum database of text arrays with the use of Grover's algorithm elements has been analyzed. The effectiveness of quantum algorithm in case of large text arrays when their size exceeds essentially the dictionary size and in cases when key words appear repeateadly in the analyzed text array is shown.

ОБ АВТОРАХ

Алексенко Виктория Сергеевна 74

Аксак Наталия Георгиевна 94

Бабий Андрей Степанович 89

Барыло Екатерина Васильевна 107

Беспалов Юрий Гаврилович 54

Бенаддия Абдельлатиф 112 Бондаренко Михаил Федорович       3, 14,

30, 150

Бондаренко Tатьяна Петровна 54

Голян Наталья Викторовна 46

Городнянский Илья Дмитриевич 54 Гороховатский Владимир Алексеевич 85

Гофман Евгений Александрович 126

Губаренко Евгений Витальевич 60

Гурина Анна Владимировна 70

Джулгам Саад 98

Ерохин Андрей Леонидович 89

Жолткевич Григорий Николаевич 54

Зайцев Сергей Алексеевич 131

студентка факультета компьютерньгх наук Харьковского национального университета радиоэлектроники

канд. техн. наук, старший научный сотрудник, доцент кафедры ЭВМ Харьковского национального университета радиоэлектроники

преподаватель кафедры информатики и информационных технологий в деяльности ОВС Харьковского национального университета внутренних дел

аспирант секции информатики кафедры компьютерных наук Сумского государственного университета

старший научный сотрудник лаборатории моделирования адаптационных механизмов биологического факультета Харьковского национального университета им. В. Н. Каразина

аспирант кафедры ЭВМ Харьковского национального университета радиоэлектроники

член-корреспондент НАН Украины, д-р техн. наук, профессор, ректор Харьковского национального университета радиоэлектроники

д-р биолог. наук, профессор, зав. отделом Института криобиологии и криомедицины Национальной академии наук Украины

ассистент кафедры программного обеспечения ЭВМ Харьковского национального университета радиоэлектроники

студент биологического факультета Харьковского национального университета им. В. Н. Каразина

д-р техн. наук, заведующий кафедрой информационных технологий Харьковского института банковского дела Университета банковского дела Национального Банка Украины

аспирант кафедры программных средств Запорожского национального технического университета

аспирант кафедры системотехники Харьковского национального университета радиоэлектроники

студентка кафедры системотехники Харьковского национального университета радиоэлектроники

аспирант кафедры компьютерных наук Сумского государственного университета

д-р техн. наук, профессор, начальник факультета психологии, менеджмента, социальных и информационных технологий Харьковского национального университета внутренних дел

канд. физ.-мат. наук, д-р техн. наук, декан механико-математического факультета Харьковского национального университета им. В. Н. Каразина

аспирант кафедры программных средств Запорожского национального технического университета

Зарецкая Ирина Тимофеевна 54

Зацеркляный Николай Милентиевич 89

Kалиновская Екатерина Михайловна 54

Калита Надежда Ивановна 70

Карреро Яфрейзи 54

Коноплянко Зеновий Дмитриевич 150

Кораблев Николай Михайлович 102

Кузьменко Сергей Викторович 65

Мальков Юрий Анатольевич 136

Мартыненко Сергей Сергеевич 98

Михаль Олег Филиппович           112, 119

Мохамад Али 119

Носов Kонстантин Валентинович 54

Олейник Андрей Александрович 126

Павлишенко Богдан Михайлович 157

Петров Эдуард Георгиевич 60

Писклакова Валентина Петровна 78

Писклакова Ольга Александровна    74, 78

канд. физ.-мат. наук, доцент механико-математического факультета Харьковского национального университета им. В. Н. Каразина.

д-р техн. наук, профессор кафедры информатики и информационных технологий в деятельности ОВС Харьковского национального университета внутренних дел

заместитель заведующего отделом рептилий Харьковского зоопарка

канд. техн. наук, доцент кафедры системотехники Харьковского национального университета радиоэлектроники

бакалавр гуманитарных наук (BA), математика, Fine Arts minor, College of Mount Saint Vincent, Riverdale, New York; магистр ландшафтной архитектуры (MLA, Master of Landscape Architecture), The Bernard and Anne Spitzer School of Architecture, CUNY City College of New York, New York

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа