Аналіз алгоритмів квантових обчислень на прикладі задачі неструктурованого пошуку
Автор: Овчаренко Ілля Андрійович
Кваліфікаційний рівень: магістр (ОНП)
Спеціальність: Комп'ютерні науки (освітньо-наукова програма)
Інститут: Інститут комп'ютерних наук та інформаційних технологій
Форма навчання: денна
Навчальний рік: 2023-2024 н.р.
Мова захисту: українська
Анотація: Овчаренко І. А., Кособуцький П. С. (керівник). Аналіз алгоритмів квантових обчислень на прикладі задачі неструктурованого пошуку. Магістерська кваліфікаційна робота. – Національний університет “Львівська політехніка”, Львів, 2024. серію експериментів для оцінки ефективності алгоритму на різних наборах даних. Для реалізації алгоритму Гровера було використано мову програмування Python та бібліотеку Qiskit, що дозволяє розробляти та тестувати квантові алгоритми на симуляторах та реальних квантових процесорах IBM. Алгоритм був протестований на різних масивах даних для оцінки його продуктивності та порівняння з класичним лінійним пошуком. Висновки роботи включають оцінку ефективності алгоритму Гровера та аналіз можливого практичного застосування алгоритму. Алгоритм Гровера має потенціал для значного прискорення процесу пошуку у великих масивах даних, особливо в контексті зростання потужностей та зменшення помилок сучасних квантових процесорів. Водночас, робота вказує на необхідність подальших досліджень щодо оптимізації квантових алгоритмів та вдосконалення апаратних платформ для квантових обчислень. Практичне значення дослідження полягає в можливості використати алгоритми квантового пошуку для реальних задач у великих базах даних та інших галузях, де необхідно швидко знаходити специфічні елементи. Квантові алгоритми, такі як алгоритм Гровера, можуть значно підвищити ефективність і швидкодію систем обробки даних. Напрямом для подальшого дослідження є вдосконаленні квантових алгоритмів, оптимізації квантових схем та зменшенні рівня помилок при виконанні квантових обчислень[4]. Робота демонструє перспективи використання квантових алгоритмів у задачах, що потребують значних обчислювальних ресурсів, та підкреслює важливість подальшого розвитку квантових технологій для досягнення нових висот у швидкодії та ефективності обчислень. Хоча квантові комп’ютери все ще перебувають на стадії розвитку, подібні системи мають значний потенціал для вирішення завдань, які є обчислювально складними для класичних комп’ютерів. Алгоритм Гровера може стати важливим інструментом у майбутніх системах обробки даних. Ключові слова – квантові обчислення, алгоритм Гровера, неструктурований пошук, кубіти, квантові гейти, квантові схеми, квантовий комп’ютер, Qiskit, IBM Quantum. Перелік використаних джерел. 6 1. Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219). 2. Mittal, R. Lecture 11: Unstructured search. 3. Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press. 4. Devitt, S. J., Munro, W. J., & Nemoto, K. (2013). Quantum error correction for beginners. Reports on Progress in Physics, 76(7), 076001. У даній магістерській кваліфікаційній роботі проведено дослідження алгоритму Гровера[1] для задачі неструктурованого пошуку[2]. Мета роботи полягає в аналізі ефективності квантового алгоритму пошуку та його реалізації за допомогою сучасних квантових процесорів або їх симуляторів. Задача неструктурованого пошуку, яка полягає у знаходженні елемента в невідсортованому масиві, є однією з основних проблем в інформатиці. Класичний алгоритм лінійного пошуку, хоча і є простим у реалізації, мають лінійну асимптотичну швидкість. Натомість квантовий алгоритм Гровера, який використовує принципи квантових обчислень, дозволяє виконати цей пошук за квадратичний час, що значно прискорює процес. Об’єктом дослідження є процес пошуку елементів у невідсортованих масивах даних. Предметом дослідження виступає алгоритм Гровера як метод квантового обчислення для вирішення задачі неструктурованого пошуку. Метою дослідження є аналіз ефективності алгоритму Гровера у порівнянні з класичними методами пошуку, а також його реалізація з використанням сучасних інструментів програмування для квантових обчислень. У роботі розглянуто теоретичні основи квантових обчислень, зокрема принципи роботи кубітів, квантових гейтів та квантових схем[3]. Проведено детальний математичний опис алгоритму Гровера, включаючи оракул, оператор дифузора та принципи його роботи. Оцінено апаратні обмеження сучасних квантових комп’ютерів, такі як кількість кубітів та ймовірність помилок під час виконання квантових обчислень. Здійснено аналіз альтернативних методів вирішення задачі пошуку на класичних та квантових комп’ютерах. У результаті дослідження було розроблено алгоритм пошуку індексу елемента в масиві за його значенням. Основою став алгоритму Гровера. Для отримання значення елемента масиву в квантовій схемі була запропонована власна версія реалізації оракула, як частини алгоритму пошуку. Було проведено серію експериментів, які показали значне прискорення пошуку при використанні квантового алгоритму в порівнянні з класичним лінійним пошуком. Проведено