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

Страницы:
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 

\qw) = jqf ,qf ,...^).

Регістр \qt) описує положення слова у текстово­му масиві, а регістр |qw) описує положення слова у словнику. Введемо додатковий кубіт | /), який буде відображати наявність слова із заданим номером в заданій позиції текстового масиву. Тобто, якщо дане слово присутнє в заданій позиції, то значення цього кубіта рівне 11), в іншому випадку рівне 10). Тоді весь текстовий масив можна буде записати у вигляді такої системи кубітів

qr) = \qi 4 ,...,4nt) ® k ,qf ,...,qnww> ®\f). (1)

Для запису в квантову пам'ять тексту довжиною Nt, який містить словник розміром Nw, достатньо n't + nw +1 = log2(2 Nt Nw) кубітів. Така експонен-ційна економія квантової пам'яті у порівнянні із класичною пам'яттю можлива внаслідок реалізації квантового паралелізму. Наприклад, якщо слов­ник містить 215 слів, а текстовий масив 1040 слів, що приблизно відповідає обсягу світової класичної лі­тератури, то для запису такої інформації необхідно лише 15+40+1=56 кубітів. Для запису всієї відомої текстової інформації потрібно буде лише декілька сотень кубітів.

Запис тексту в квантову пам'ять розглянемо феноменологічно за допомогою квантового ора­кула. В теорії квантових обчислень показано, що на основі однокубітних та двокубітних квантових унітарних вентилів можна побудувати еквівалентні алгоритми класичної машини Тюрінга. Під ораку­лом будемо розуміти деяке формалізоване унітарне перетворення, за допомогою якого реалізуються наперед задані обчислення. Елементи текстового масиву визначаються квантовими станами скла­деного регістру кубітів (1). Суперпозиція цих ста­нів утворює вектор в комплексному Гільбертовому просторі. Цей вектор є квантовим еквівалентам відображенням текстових даних. Розглянемо по­слідовність квантового запису тексту. Кубіт \f) візьмемо в початковому стані |0), а регістри |qt),

\qw) в початкових станах |0)®{п') та \0)<s{nw) відпо­відно. Застосуємо однокубітні унітарні перетво­рення Адамара до регістрів |qt)®|qw)® | f):

|¥) = (nt) ® (nw) ® I (qt) ®\qw) ® j f)).

В результаті отримаємо

к>=-

1

* Е 10®lj®\0).

С=0, у=0

(2)

Суперпозиція |\|/) містить базисні ортогональні стани, кожен з яких відповідає одному положенню визначеного слова у тексті. В процесі вимірювання відбувається редукція суперпозиції до одного базо­вого стану, який відповідає одному слову в деякому положенні. Отже, та кількість памяті, яка в класич­ному випадку необхідна для запису одного слова, у квантовому випадку є достатньою для запису ці­лого текстового масиву. Нехай наявність заданого слова у певному місці тексту описується функцією fq (qt,qw), де індекс qt описує положення слова у тексті, а індекс qw описує положення цього слова у словнику. У випадку наявності заданого слова у заданому місці тексту функція набуває значення 1, інакше 0. Процес запису текста у квантову пам'ять опишемо унітарним перетворенням UF, яке визна­чається квантовим оракулом

Uf :|qt)®|qw)®| f -•|qt) ®\qw) ®| f © fq (qt,qw))'

де © означає сумування за модулем 2. Враховуючи, що кубіт \f) є в початковому стані |0), отримаємо

Uf :\qt)®|qw)® |0)-\qt)®|qw)® |fq(qt,qw)) . (3)

4. Пошук заданого ключового слова у квантовій базі даних

Завдання полягає в пошуку деякого ключово­го слова wk , яке може бути закодоване у вигляді квантового стану

|qk) = |q*,qk,...,q^) .

Використаємо вентиль Тоффолі для знаходжен­ня квантових станів, в яких закодовані ключові теги. Введемо в систему кубітів (1) додатковий ку-біт — анцилу |z), отримаємо

qr) = |qt)®\qw)®\fq(qt,qw)}®|z) . (4)

Подіємо на кубіт 11) в стані 11) оператором Ада-мара

1

\z)=H 1)(0>­

1

(5)

Допоміжний кубіт |z) буде керуватись за допо­могою nw+7-мірного елемента Тоффолі Tnw+1, в якому керуючими кубітами виступають nw кубітів регістру \qw) та кубіт \f (qt,qw)). Значення кубіта z) в квантовому стані може змінитись під впли­вом вентиля Тоффолі у випадку, коли всі кубіти ре­гістру \qw) та кубіт f (qt,qw)) будуть рівні одиниці. Щоб перевести значення кубітів у значення |1) для квантових станів, які описують ключове слово розглянемо унітарний оператор, який є тензорним добутком однокубітних операторів

( nw

ST = I®(nt) ®| ® S I ® I,

[i=1

(6)

де S

1;

11, qf

[ *, qk = 0;

Оператор ST переводить квантові базисні стани регістру |qr) у стани, в яких значення регістру |qw) рівні 1, якщо співпадають кодування слова в тексті та ключового слова |qw) = |qk), тобто

S^qr) = \qt)®nw ®|f(qt,qw))®|z),

якщо \qw) = \qk).

Розглянемо оператор

Ut = (St ) (I®(nt) ®Tnw+1) (St ). (7) Подіємо цим оператором на систему регістрів кубітів |qr). Перша справа група операторів виді­лених дужками переводить регістр |qw) у значен­ня nw для станів, які відповідають шуканим ключовим словам, друга група операторів реалізує інверсію керованого кубіта |z) для шуканих ста­нів, третя група повертає змінені першою групою стани у стан перед застосуванням оператора Ut . В результаті дії оператора Ut отримаємо

1

x=2n

Е  \х)®\f(x)>®|z)

x=1

. \x)®lf(x)>- Е \x)®lf(x)> ®lz), (8)

\x) = \qt) ®\qw),

де Xk—множина станів суперпозиції, які відповідають кодуванню шуканих ключових слів. Допоміжний керований кубіт | z) не змінив свого значення під дією оператора Ut і знаходиться у стані (5), в якому він знаходився перед дією оператора Ut , тому його можна винести за дужки та вилучити із подальшого розгляду. Це зумовлено тим, що кубіт \z) був пере­ведений в новий базисний стан (5) за допомогою оператора Адамара. Інверсія стану в цьому базисі є рівнозначна інверсії знаку амплітуди підсистеми квантових станів, в яких закодовані ключові слова. Роль цього кубіта полягала у тому, щоб під дією вен­тиля Тофолі він змінював свій знак на протилежний у квантових станах, які відповідають умові пошуку.

Страницы:
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 самых важных уроков библии

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

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

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

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