Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень
Проведено аналіз семантичних образів у масивах текстових об'єктів із використанням елементів квантового алгоритму Гровера. Показано, що реалізація квантових алгоритмів для деякого класу задач такого аналізу дає можливість експоненційно зменшити об'єм необхідної пам'яті та поліноміальн...
Gespeichert in:
| Veröffentlicht in: | Математичні машини і системи |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/83797 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень / Б.М. Павлишенко // Мат. машини і системи. — 2013. — № 1. — С. 34-43. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860243780313022464 |
|---|---|
| author | Павлишенко, Б.М. |
| author_facet | Павлишенко, Б.М. |
| citation_txt | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень / Б.М. Павлишенко // Мат. машини і системи. — 2013. — № 1. — С. 34-43. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Проведено аналіз семантичних образів у масивах текстових об'єктів із використанням елементів квантового алгоритму Гровера. Показано, що реалізація квантових алгоритмів для деякого класу задач такого аналізу дає можливість експоненційно зменшити об'єм необхідної пам'яті та поліноміально зменшити час виконання алгоритму у порівнянні із класичними алгоритмами внаслідок реалізації квантового паралелізму.
Проведен анализ семантических образов в массивах текстовых объектов с использованием элементов квантового алгоритма Гровера. Показано, что реализация квантовых алгоритмов для некоторого класса задач такого анализа дает возможность экспоненциально уменьшить объем требуемой памяти и полиномиально уменьшить время выполнения алгоритма по сравнению с классическими алгоритмами в результате реализации квантового параллелизма.
The analysis of semantic patterns in the text objects arrays using Grover algorithms elements has been performed. It is shown that implementation of quantum algorithms for some classes of problems gives the ability to decrease required memory exponentially and decrease the time of algorithm performance polynomial in comparison with the classical algorithms due to quantum parallelism.
|
| first_indexed | 2025-12-07T18:33:43Z |
| format | Article |
| fulltext |
34 © Павлишенко Б.М., 2013
ISSN 1028-9763. Математичні машини і системи, 2013, № 1
УДК 519.765:004.89
Б.М. ПАВЛИШЕНКО
АНАЛІЗ СЕМАНТИЧНИХ ОБРАЗІВ У МАСИВАХ ТЕКСТОВИХ ОБ’ЄКТІВ ЗА
ДОПОМОГОЮ КВАНТОВИХ ОБЧИСЛЕНЬ
Анотація. Проведено аналіз семантичних образів у масивах текстових об’єктів із використан-
ням елементів квантового алгоритму Гровера. Показано, що реалізація квантових алгоритмів для
деякого класу задач такого аналізу дає можливість експоненційно зменшити об’єм необхідної
пам’яті та поліноміально зменшити час виконання алгоритму у порівнянні із класичними алгори-
тмами внаслідок реалізації квантового паралелізму.
Ключові слова: квантові обчислення, алгоритм Гровера, аналіз текстів, семантичі поля.
Аннотация. Проведен анализ семантических образов в массивах текстовых объектов с использо-
ванием элементов квантового алгоритма Гровера. Показано, что реализация квантовых алгорит-
мов для некоторого класса задач такого анализа дает возможность экспоненциально уменьшить
объем требуемой памяти и полиномиально уменьшить время выполнения алгоритма по сравнению
с классическими алгоритмами в результате реализации квантового параллелизма.
Ключевые слова: квантовые вычисления, алгоритм Гровера, анализ текстов, семантические поля.
Abstract. The analysis of semantic patterns in the text objects arrays using Grover algorithms elements
has been performed. It is shown that implementation of quantum algorithms for some classes of problems
gives the ability to decrease required memory exponentially and decrease the time of algorithm perfor-
mance polynomial in comparison with the classical algorithms due to quantum parallelism.
Keywords: quantum calculations, Grover’s quantum algorithm, texts analysis, semantic fields.
1. Вступ
Пошук нових алгоритмів аналізу слабоструктурованих даних, зокрема, текстового типу, є
одним із актуальних напрямів сучасних інформаційних технологій. Якісно нові підходи до
такого аналізу можливі при використанні квантових обчислень, теорія яких активно розви-
вається останнім часом [1, 2]. В інтелектуальному аналізі текстових масивів можна виділи-
ти деякий клас задач, на якому можна показати ефективність реалізації квантових алгори-
тмів. Вони дають можливість суттєво пришвидшити розв’язок внаслідок реалізації кванто-
вого паралелізму та заплутаності квантових станів. Одним із відомих квантових алгорит-
мів є алгоритм Гровера для пошуку даних у неструктурованій базі даних [3, 4]. У порів-
нянні із класичним алгоритмом, в якому пошук здійснюється за час )(NO , алгоритм Гро-
вера дає квадратичне прискорення розв’язку, що є актуальним при великих значеннях N .
Особливістю квантового алгоритму Гровера є те, що він являється ймовірнісним алгорит-
мом, тобто дає правильний розв’язок із заданою ймовірністю, яка може бути збільшена
шляхом повторного використання алгоритму. Алгоритм Гровера може бути складовою ча-
стиною інших квантових алгоритмів, зокрема, в роботі [5] він використовується для ево-
люційного аналізу кліткових автоматів. У сучасних алгоритмах аналізу текстів часто вико-
ристовують модель векторного простору. Основна ідея цієї моделі полягає у представленні
кожного текстового документа у вигляді вектора у деякому векторному просторі [6–8].
Вважають, що точки, які є близькі між собою у цьому просторі, відображають семантично
близькі документи і навпаки – семантично близькі документи відображаються близькими
точками у фазовому просторі. В основі використання векторної моделі лежить статистична
гіпотеза, яка полягає в тому, що статистичні характеристики використання слів
відображають ті поняття, які відображаються у цих текстах [6].
ISSN 1028-9763. Математичні машини і системи, 2013, № 1 35
2. Постановка задачі
Розглянемо деякі моделі задач, які виявляють ефективність квантових обчислень. Нехай
існує відображення масиву текстових документів, в якому тексти представлені у вигляді
частотних спектрів лексем словникового складу або у вигляді характеристик лексемних
об’єднань. Такими об’єднаннями можуть бути, наприклад, семантичні поля. Сукупність
частот семантичних полів текстового об’єкта можна розглядати як семантичний образ,
який характеризує текстовий об’єкт. Нехай завдання полягає у виявленні існування текс-
тових об’єктів із заданими властивостями. Розглянемо семантичну векторну модель маси-
ву текстових об’єктів. Проаналізуємо базові елементи квантових обчислень, які можуть
бути використані в алгоритмах аналізу текстів. Створимо модель квантового запису маси-
ву семантичного вектора текстового об’єкта. Розглянемо пошук заданих семантичних об-
разів у квантовій базі даних текстових об’єктів, використовуючи елементи алгоритму Гро-
вера. Проаналізуємо ефективність квантового алгоритму пошуку семантичних образів тек-
стових об’єктів у порівнянні з класичними алгоритмами.
3. Семантична векторна модель текстових об’єктів
Під текстовими об’єктами будемо розглядати текстові документи у вигляді сукупності ло-
гічно пов’язаних лексем, об’єднаних у масиві речень. Розглянемо представлення текстових
об’єктів у вигляді векторів семантичного простору. В основі такого представлення лежить
статистична семантична гіпотеза [6], яка припускає, що статистичні характеристики вжи-
вання лексем можуть бути використані для визначення змісту сказаного. Якщо деякі час-
тини тексту мають подібні вектори в частотних матрицях, тоді ці частини мають подібні
значення. Сукупність текстових об’єктів опишемо такою множиною:
{ }tj N...,2,1j|tT == , (1)
де tN – кількість об’єктів. Упорядкований за алфавітом словник текстового об’єкта jt роз-
глянемо як мультимножину t
jW над множиною словника W :
{ }wjii
wt
ij
t
j N...,2,1i,tw|)w(nW =∈= , (2)
де wt
ijn – кількість входжень лексеми iw із словника W у множину лексем текстового до-
кумента jt . Введемо множину семантичних полів:
{ }sk NksS ...,2,1| == . (3)
Під семантичним полем розуміють множину лексем, об’єднаних деяким спільним
поняттям [9, 10]. Прикладом семантичних полів можуть бути поле руху, поле комунікації,
поле сприйняття та ін. Відображення лексемного складу словника W на множину семан-
тичних полів S (3) задамо таблицею, яка визначається експертним лексикографічним
аналізом. Лексемний склад семантичного поля ks визначимо як
=→= w
U
kii
s
k NiswwW
ws
...,2,1,| . (4)
Множину образів відображення wsU розглянемо як мультимножину над множиною
семантичних полів S :
{ }sk
s
kf NksnS ...,2,1|)( == , (5)
36 ISSN 1028-9763. Математичні машини і системи, 2013, № 1
де s
kn – кількість лексем словника W , які відносять до семантичного поля ks . Введемо
мультимножину образів відображення wsU семантичних полів для окремого текстового
об’єкта jt :
{ }sk
st
kj
t
j N...,2,1k|)s(nS == , (6)
де st
kjn – кількість лексем семантичного поля ks в лексемному складі документа jt .
Аналогічно до [8] введемо оператор відображення семантичного складу t
jS текстового
об’єкта jt на множину квантитативних ознак:
ts
st
kjksd N...2,1j,N,...2,1k,ps:U ==→ . (7)
Величина st
kjp визначає структурну частоту лексем семантичного поля ks у тексто-
вому документі jd . Сукупність значень st
kjp утворюють матрицю ознака-об’єкт, у якій оз-
наками виступають частоти семантичних полів в об’єктах:
( ) ds N,N
1j,1k
st
kjsd pM
==
= . (8)
Вектор
( )st
jN
st
j2
st
j1
s
j s
p,...,p,pV = (9)
відображає текстовий об’єкт jt в sN -мірному просторі текстових об’єктів. Використання
векторного представлення (9) дає можливість пошуку подібних об’єктів у векторному
просторі з базисом, утвореним частотними характеристиками семантичних полів. Цей ба-
зис має суттево меншу розмірність у порівнянні з базисом, утвореним частотними харак-
теристиками лексем словника текстових масивів. Це дає можливість зменшити кількість
необхідних обчислень в алгоритмах аналізу текстів.
Складові семантичного вектора (9) є дійсними величинами, які можуть набувати
значень у проміжку [0,1]. Однак можна знайти відображення цього вектора на множину
бінарних значень:
sb
j
s
j VV → ,
де ( )stb
jN
stb
j2
stb
j1
sb
j s
p,...,p,pV = , { }1,0p stb
ij ∈ . (10)
У найпростішому випадку відображення (10) може здійснюватись так:
≥
<
=
,)(,1
,)(,0
th
st
i
st
ij
th
st
i
st
ijstb
ij
pp
pp
p (11)
де th
st
i )p( – деякі порогові значення частот семантичних полів, вибрані експерименталь-
ним шляхом. У загальному випадку, якщо потрібно враховувати різні значення частот,
можна використати декілька двійкових розрядів для кодування. Наприклад, якщо збільши-
ти розмір бінарного вектора sb
jV у два рази, тоді можна буде кодувати кожну частоту дво-
ма двійковими розрядами, що буде відповідати чотирьом інтервалам значень частот.
ISSN 1028-9763. Математичні машини і системи, 2013, № 1 37
4. Базові елементи квантових обчислень
Розглянемо базові квантові принципи реалізації квантових алгоритмів [1, 2]. Основною ві-
дмінністю квантового біта – кубіта від класичного біта є те, що кубіт, крім станів 0 і 1 ,
може також знаходитись у суперпозиції цих станів:
10 ba +=ψ . (12)
Стани 0 і 1 є базисними векторами, які можна представити у матричному вигля-
ді:
=
0
1
0
=
1
0
1 . (13)
Регістр із n кубітів nxxx ,..., 21 утворює суперпозицію із nN 2= станів, яку можна
записати так:
∑
−
=
=
1
0
N
i
i iaψ . (14)
Ортонормований базис { }12,...1,0 −n
називають обчислювальним базисом.
Розглянемо однокубітні квантові вентилі. Розрахунки у квантових алгоритмах здій-
снюють за допомогою унітарних перетворень, які можна розглядати як повороти комплек-
сного векторного простору. Розглянемо базові операції над кубітами. Оператор тотожного
перетворення не змінює значення кубітів і має вигляд
=
10
01
I . (15)
Операцію заперечення використовують для реалізації інверсії значень кубітів і ви-
значають так:
0110 +=X . (16)
У спінорному зображенні оператор заперечення має вигляд матриці:
=
01
10
X . (17)
Одним із важливих елементів є «контрольоване НЕ», яке здійснюється над двома
кубітами і змінює значення другого кубіта на протилежне, якщо значення першого кубіта
рівне 1. Цей логічний елемент може бути визначений як
XIUCNOT ⊗+⊗= 1100 , (18)
а матриця оператора унітарного перетворення «контрольоване НЕ» має вигляд
=
0100
1000
0010
0001
CNOTU . (19)
Дію вентиля «контрольоване НЕ» можна зобразити так:
38 ISSN 1028-9763. Математичні машини і системи, 2013, № 1
baabaUCNOT ⊕→ ,,: , (20)
де ⊕ означає сумування за модулем 2. Ще одним важливим логічним елементом є вентиль
Тоффолі, який діє на три кубіти і змінює значення третього кубіта на протилежне, якщо
значення першого та другого кубітів рівне 1. Від логічного елемента «контрольоване НЕ»
вентиль Тоффолі відрізняється наявністю ще одного додаткового керуючого кубіта. Цей
вентиль можна визначити так:
CNOTUIIT ⊗+⊗⊗= 1100 . (21)
Перетворення Тоффолі можна зообразити в такому вигляді:
abcbacbaT ⊕→ ,,,,: . (22)
Вентиль Тоффолі є універсальним квантовим логічним елементом, на основі якого
можна побудувати оборотну квантову машину Тюрінга. В подальших дослідженнях буде-
мо використовувати вентиль Тоффолі з n керуючими кубітами. В такому вентилі відбува-
ється інверсія керованого кубіта при умові, що n керуючих кубітів мають значення 1 .
5. Представлення семантичного вектора текстового об’єкта у квантовій пам’яті
Нехай існує деякий масив текстових об’єктів (1). Множину семантичних полів розглянемо
у вигляді (3). Кожне семантичне поле можна закодувати його номером i за допомогою ві-
дображення
iS:U is → . (23)
Для простоти розгляду будемо вважати, що розмір множини масиву текстових
об’єктів рівний )nt(
t 2N = , а розмір множини семантичних полів рівний )ns(
w 2N = . Тоді,
для кодування положення об’єкта в масиві, потрібно nt двійкових елементів, а для коду-
вання семантичного образу потрібно ns двійкових елементів. Нехай квантовий регістр
складається із двох частин qt і qs :
.q,...,q,qqs,q,...,q,qqt,qsqt s
ns
s
1
s
1
t
nt
t
1
t
1 ==⊗ (24)
Регістр qt описує положення текстового об’єкта у масиві, а регістр qs описує
семантичний образ, який складається із набору семантичних полів. Введемо додатковий
кубіт f , який буде відображати наявність семантичного поля із заданим номером у зада-
ному текстовому об’єкті. Якщо дане поле є присутнє в заданому текстовому об’єкті, тобто,
якщо його бінарна частота stb
ijp (11) рівна 1, то значення цього кубіта рівне 1 , в іншому
випадку рівне 0 . Тоді весь масив текстових об’єктів можна буде записати у вигляді такої
системи кубітів:
fq,...,q,qq,...,q,qqr s
ns
s
1
s
1
t
nt
t
1
t
1 ⊗⊗= . (25)
Для запису в квантову пам’ять масиву текстових об’єктів розміром tN , який міс-
тить набір семантичних полів розміром sN , достатньо )NN2(log1nsnt st2 ⋅⋅=++ кубітів.
Така експоненційна економія квантової пам’яті у порівнянні із класичною пам’яттю мож-
лива внаслідок реалізації квантового паралелізму. Наприклад, якщо набір семантичних по-
ISSN 1028-9763. Математичні машини і системи, 2013, № 1 39
лів містить 25 елементів, а масив текстових об’єктів – 1015 елементів, то для запису такої
інформації необхідно лише 5+15+1=21 кубітів.
Запис масиву текстових об’єктів у квантову пам’ять розглянемо феноменологічно за
допомогою квантового оракула. В теорії квантових обчислень показано, що на основі од-
нокубітних та двокубітних квантових унітарних вентилів можна побудувати еквівалентні
алгоритми класичної машини Тюрінга. Під оракулом будемо розуміти деяке формалізова-
не унітарне перетворення, за допомогою якого реалізуються наперед задані обчислення.
Елементи масиву текстових об’єктів визначаються квантовими станами складеного регіст-
ру кубітів (25). Суперпозиція цих станів утворює вектор у комплексному Гільбертовому
просторі. Цей вектор є квантовим еквівалентним відображенням текстових об’єктів. Розг-
лянемо послідовність квантового запису масиву текстових об’єктів. Кубіт f візьмемо в
початковому стані 0 , а регістри qt , qs – в початкових станах
)(
0
nt⊗
та
)ns(
0
⊗
відпо-
відно. Застосуємо однокубітні унітарні перетворення Адамара до регістрів
fqsqt ⊗⊗ :
( )fqsqtIHH )nw()nt( ⊗⊗⊗⊗= ⊗⊗ψ . (26)
В результаті отримаємо
0ji
2
1 st N,N
0j,0i
nsnt
⊗⊗= ∑
==
+
ψ . (27)
Суперпозиція ψ містить базисні ортогональні стани, кожен з яких відповідає од-
ному запису семантичного вектора текстового об’єкта. У процесі вимірювання відбуваєть-
ся редукція суперпозиції до одного базового стану, який відповідає одному текстовому
об’єкту. Отже, та кількість памяті, яка в класичному випадку необхідна для запису семан-
тичного вектора одного текстового об’єкта, в квантовому випадку є достатня для запису
цілого масиву текстового об’єкта. Нехай наявність заданого семантичного вектора тексто-
вого об’єкта описується функцією )qs,qt(fq , де індекс qt описує текстовий об’єкт, а ін-
декс qs описує спектр семантичних полів текстового об’єкта. У випадку наявності задано-
го спектра семантичних полів у заданому текстовому об’єкті функція набуває значення 1,
інакше 0. Процес запису текста у квантову пам’ять опишемо унітарним перетворенням
FU , яке визначається квантовим оракулом:
)qs,qt(ffqsqtfqsqt:U qF ⊕⊗⊗→⊗⊗ , (28)
де ⊕ означає сумування за модулем 2. Враховуючи, що кубіт f є в початковому стані
0 , отримаємо
)qs,qt(fqsqt0qsqt:U qF ⊗⊗→⊗⊗ . (29)
6. Пошук заданих семантичних образів текстових об’єктів у квантовій базі даних
Завдання полягає в пошуку деякого ключового семантичного образу, який може бути за-
кодований у вигляді квантового стану:
k
ns
k
1
k
1 q,...,q,qqk = . (30)
40 ISSN 1028-9763. Математичні машини і системи, 2013, № 1
Використаємо вентиль Тоффолі для знаходження квантових станів, в яких закодо-
вані ключові семантичні образи. Введемо в систему кубітів (25) додатковий кубіт – анцилу
z , отримаємо
z)qs,qt(fqsqtqr q ⊗⊗⊗= . (31)
Подіємо на кубіт z у стані 1 оператором Адамара:
( )10
2
1
1 −== Hz . (32)
Допоміжний кубіт z буде керуватись за допомогою 1ns + -мірного елемента Тоф-
фолі 1nsT + , в якому керуючими кубітами виступають ns кубітів регістру qs та кубіт
)qs,qt(f . Значення кубіта z у квантовому стані може змінитись під впливом вентиля
Тоффолі у випадку, коли всі кубіти регістру qs та кубіт )qs,qt(f будуть рівні одиниці.
Щоб перевести значення кубітів у значення 1 для квантових станів, які описують ключо-
вий семантичний образ qk , розглянемо унітарний оператор, який є тензорним добутком
однокубітних операторів:
IISIS q
i
ns
1i
)nt(q
T ⊗⊗
⊗⊗=
=
⊗
, (33)
де
, 1,
, 0.
k
iq
i k
i
I q
S
X q
==
=
Оператор q
TS переводить квантові базисні стани регістру qr в стани, в яких зна-
чення регістру qs рівні 1, якщо співпадають кодування семантичного вектора текстового
об’єкта в тексті та ключового семантичного образа qkqs = , тобто
z)qs,qt(f1,...1,1qtqrS
nsT ⊗⊗⊗= , якщо qkqs = . (34)
Розглянемо оператор
)S()TI()S(U q
T1ns
)nt(q
TT ⋅⊗⋅= +
⊗ . (35)
Подіємо цим оператором на систему регістрів кубітів qr . Перша справа група опе-
раторів, виділених дужками, переводить регістр qs у значення nw
1,...1,1 для станів, які
відповідають шуканим ключовим семантичним образам, друга група операторів реалізує
інверсію керованого кубіта z для шуканих станів семантичних образів, третя група пове-
ртає змінені першою групою стани у стан перед застосуванням оператора TU . В результаті
дії оператора TU отримаємо
,qsqtx,z)x(fx)x(fx
2
1
z)x(fx
2
1
U
kk
nsnt
XxXx
nsnt
2x
1x
nsntTT
⊗=⊗
⊗−⊗×
×=
⊗⊗=
∑∑
∑
∈∉
+
=
=
+
+
ψ
(36)
ISSN 1028-9763. Математичні машини і системи, 2013, № 1 41
де kX – множина станів суперпозиції, які відповідають кодуванню шуканих ключових се-
мантичних образів. Допоміжний керований кубіт z не змінив свого значення під дією
оператора TU і знаходиться у стані (32), в якому він знаходився перед дією оператора TU ,
тому його можна винести за дужки та вилучити із подальшого розгляду. Це зумовлено
тим, що кубіт z був переведений в новий базисний стан (32) за допомогою оператора
Адамара. Інверсія стану у цьому базисі є рівнозначна інверсії знаку амплітуди підсистеми
квантових станів, в яких закодовані ключові слова. Роль цього кубіта полягала в тому, щоб
під дією вентиля Тофолі він змінював свій знак на протилежний у квантових станах, які
відповідають умові пошуку. Умова рівності регістрів семантичного вектора текстового
об’єкта та регістру ключового семантичного образу враховується в операторі q
TS .
Наступним кроком алгоритму є переведення додаткового кубіта f в початковий
базисний стан 0 та вилучення його із подальшого розгляду. Це можна зробити за допо-
могою унітарного оператора 1−
FU , який є оберненим до оператора FU (29). В результаті
отримаємо
.qsqtx,xx
2
1
U
kk
1
XxXx
nwntT
1
FF
⊗=
−== ∑∑
∈∉
+
−
− ψψ (37)
Отже, в результаті дії складеного оператора FTF UUU 1− отримаємо суперпозицію ба-
зисних рівноймовірнісних станів (27), в якій стани, що кодують наявні ключові семантичні
образи, мають від’ємну амплітуду.
Для того, щоб при вимірюванні виявити квантові стани, в яких закодовані ключові
семантичні образи, необхідно підсилити амплітуди цих станів. Таке підсилення амплітуд
станів, які мають задані властивості, можна здійснити за допомогою оператора інверсії ві-
дносно середнього, який використовується в алгоритмі Гровера для пошуку в неструкту-
рованій квантовій базі даних [3, 4]. Оператор інверсії розглянемо у вигляді
IU ccG −= ψψ2 , (38)
де ∑
−=
=
⊗⊗ ==
12
02
1
0
ni
i
n
nn
c iHψ . (39)
У геометричній інтерпретації оператор GU здійснює в Гільбертовому просторі дзе-
ркальне відображення деякого вектора відносно осі, яка визначається вектором cψ . Опе-
ратор інверсії можна представити сукупністю однокубітних операторів Адамара та опера-
торів інверсії стану кубіта відносно базисного вектора 0 :
nnn
G HIHU ⊗⊗⊗ −= )002( . (40)
Підсилення амплітуд станів з інверсними знаками амплітуд відбувається внаслідок
дії оператора інверсії GU аналогічно до механізму, описаного в алгоритмі Гровера [3,4].
Враховуючи визначення операторів (28), (35), (38), розглянемо ітерацію алгоритму Грове-
ра у загальному вигляді складеного оператора:
FTFGI UUUUU 1−= . (41)
42 ISSN 1028-9763. Математичні машини і системи, 2013, № 1
Можна показати, що внаслідок реалізації ітерації IU можна підсилити амплітуди
заданих станів у 3 рази. Якщо шуканий ключовий семантичний образ зустрічається в ма-
сиві текстових об’єктів лише один раз, то, аналогічно алгоритму Гровера [3, 4], оптималь-
на кількість ітерацій IU буде
,2N,N
4
k nsnt
U
+=≈ π
(42)
де N – кількість квантових станів рівна st NNN = . Отже, складність алгоритму в даному
випадку буде )( NO . Якщо кількість шуканих об’єктів із ключовим семантичним образом
є рівною l , тоді, згідно із [3, 4], кількість необхідних ітерацій буде рівна
l
N
kU 4
π≈ . (43)
Однак наперед невідомо, скільки текстових об’єктів відповідають ключовому сема-
нтичному образу. В такому випадку можна провести серію реалізацій алгоритму Гровера з
кількостями ітерацій IU , які утворюють прогресію
UU lk ,...8,4,2,1= , (44)
де Ul – деяке максимальне значення кількості ітерацій IU . Тобто спочатку реалізується
алгоритм з однією ітерацією, потім з двома і т.д. Якщо в цій серії реалізацій алгоритму при
вимірюванні виявлено шукані квантові стани, тоді можна прийняти рішення про наявність
шуканого семантичного образу у текстових об’єктах аналізованого масиву, а також оціни-
ти кількість текстових об’єктів із заданим семантичним образом у цьому масиві. Можна
показати, що складність алгоритму в такому випадку є також )( NO . У класичному алго-
ритмі складність пошуку семантичних образів у неструктурованому масиві текстових
об’єктів буде )N(O .
7. Висновки
У роботі розглянута модель квантового представлення семантичних векторів масиву текс-
тових об’єктів, яка дає можливість експоненційно зменшити об’єм необхідної квантової
пам’яті у порівнянні із класичним записом. Запропоновано квантовий алгоритм пошуку
ключових семантичних образів у масивах текстових об’єктів. Реалізація цього алгоритму
здійснюється на основі квантових логічних елементів, зокрема, з використанням вентиля
Тоффолі. Ітерація Гровера використовується для підсилення амплітуд квантових станів,
які описують семантичні вектори текстових об’єктів. Показано, що реалізація квантових
алгоритмів аналізу семантичних образів текстових об’єктів для деякого класу задач дає
можливість поліноміально зменшити час виконання алгоритму у порівнянні із класичними
алгоритмами внаслідок реалізації квантового паралелізму.
СПИСОК ЛІТЕРАТУРИ
1. Крохмальський Т. Квантові комп’ютери: основи й алгоритми (короткий огляд) / Т. Крохмальсь-
кий // Журнал фізичних досліджень. – 2004. – Т. 8, № 4. – С. 1 – 15.
2. Китаев А. Классические и квантовые вычисления / Китаев А., Шень А., Вялый М. – М.:
МЦНМО, ЧеРо, 1999. – 192 с.
3. Grover L.K. Quantum Mechanics helps in searching for a needle in haystack / L.K. Grover // Phys.Rev.
Lett. – 1997. – N 79 (2). – Р. 325 – 328.
ISSN 1028-9763. Математичні машини і системи, 2013, № 1 43
4. Zalka C. Grover’s quantum searching algorithm is optimal / C. Zalka // Phys. Rev. A. – 1999. –
N 60 (4). – P. 2746 – 2751.
5. Павлишенко Б.М. Квантовий алгоритм еволюційного аналізу одновимірних кліткових автоматів
/ Б.М. Павлишенко // Журнал фізичних досліджень. – 2011. – Т. 15, № 3. – С. 1 – 6.
6. Pantel P. From Frequency to Meaning: Vector Space Models of Semantics / P. Pantel, P.D. Turney //
Journal of Artificial Intelligence Research. – 2010. – Vol. 37. – Р. 141 – 188.
7. Павлишенко Б.М. Сингулярна декомпозиція матриці семантичних ознак в алгоритмі ієрархічної
кластеризації текстових масивів / Б.М. Павлишенко // Математичні машини і системи. – 2012. –
№ 1. – С. 69 – 76.
8. Павлишенко Б.М. Використання концепції семантичного поля у векторній моделі текстових
документів / Б.М. Павлишенко // Східно-Європейський журнал передових технологій. – 2011. –
№ 6/2 (54). – С. 7 – 11.
9. Вердиева З.Н. Семантические поля в современном английском языке / Вердиева З.Н. – М.: Выс-
шая школа, 1986. – 120 с.
10. Левицкий В.В. Экспериментальные методы в семасиологии / В.В. Левицкий, И.А. Стернин. –
Воронеж: Изд-во ВГУ, 1989. – 192 с.
Стаття надійшла до редакції 30.05.2012
|
| id | nasplib_isofts_kiev_ua-123456789-83797 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:33:43Z |
| publishDate | 2013 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Павлишенко, Б.М. 2015-06-24T06:38:02Z 2015-06-24T06:38:02Z 2013 Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень / Б.М. Павлишенко // Мат. машини і системи. — 2013. — № 1. — С. 34-43. — Бібліогр.: 10 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83797 519.765:004.89 Проведено аналіз семантичних образів у масивах текстових об'єктів із використанням елементів квантового алгоритму Гровера. Показано, що реалізація квантових алгоритмів для деякого класу задач такого аналізу дає можливість експоненційно зменшити об'єм необхідної пам'яті та поліноміально зменшити час виконання алгоритму у порівнянні із класичними алгоритмами внаслідок реалізації квантового паралелізму. Проведен анализ семантических образов в массивах текстовых объектов с использованием элементов квантового алгоритма Гровера. Показано, что реализация квантовых алгоритмов для некоторого класса задач такого анализа дает возможность экспоненциально уменьшить объем требуемой памяти и полиномиально уменьшить время выполнения алгоритма по сравнению с классическими алгоритмами в результате реализации квантового параллелизма. The analysis of semantic patterns in the text objects arrays using Grover algorithms elements has been performed. It is shown that implementation of quantum algorithms for some classes of problems gives the ability to decrease required memory exponentially and decrease the time of algorithm performance polynomial in comparison with the classical algorithms due to quantum parallelism. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень Анализ семантических образов в массивах текстовых объектов с помощью квантовых вычислений The analysis of semantic images in the text objects arrays by quantum calculations Article published earlier |
| spellingShingle | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень Павлишенко, Б.М. Обчислювальні системи |
| title | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень |
| title_alt | Анализ семантических образов в массивах текстовых объектов с помощью квантовых вычислений The analysis of semantic images in the text objects arrays by quantum calculations |
| title_full | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень |
| title_fullStr | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень |
| title_full_unstemmed | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень |
| title_short | Аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень |
| title_sort | аналіз семантичних образів у масивах текстових об'єктів за допомогою квантових обчислень |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83797 |
| work_keys_str_mv | AT pavlišenkobm analízsemantičnihobrazívumasivahtekstovihobêktívzadopomogoûkvantovihobčislenʹ AT pavlišenkobm analizsemantičeskihobrazovvmassivahtekstovyhobʺektovspomoŝʹûkvantovyhvyčislenii AT pavlišenkobm theanalysisofsemanticimagesinthetextobjectsarraysbyquantumcalculations |