Застосування алгоритму QAOA для розв’язання задачi SVP

Скорочена інформація про документ
dc.contributor.advisorФесенко, Андрiй В’ячеславович
dc.contributor.authorКiстаєв, Матвiй Андрiйович
dc.date.accessioned2024-09-26T09:59:43Z
dc.date.available2024-09-26T09:59:43Z
dc.date.issued2024
dc.description.abstractНаразi вже оголошено першi 3 переможцi конкурсу постквантових асиметричних криптографiчних алгоритмiв NIST та опублiковано попереднi версiї вiдповiдних державних стандартiв постквантових цифрового пiдпису та iнкапсуляцiї ключа. Стiйкiсть цих криптосистем-переможцiв ґрунтується на складностi певних задач на решiтках. Задача SVP є базовою задачею, яка визначає верхню межу складностi для бiльшостi задач на решiтках, що використовуються в постквантовiй криптографiї. В той же час, поки сучасний рiвень розвитку технологiй не дозволяє створити завадостiйкий масштабований квантовий комп’ютер, який змiг би ефективно застосовувати повноцiннi квантовi алгоритми для задач практичних розмiрiв. В таких умовах активно вiдбувається дослiдження та розробка квантових алгоритмiв, якi дозволяли б застосовувати наявнi NISQ-комп’ютери для розв’язання практичних задач. Одним iз основних напрямкiв побудови таких алгоритмiв стали варiацiйнi квантовi алгоритми, найбiльш сучасним та унiверсальним iз яких наразi є QAOA. Застосування таких алгоритмiв вимагає зведення дослiджуваної задачi до задачi пошуку основного стану гамiльтонiану. Метою роботи є дослiдження складностi застосування алгоритму QAOA до задачi SVP, а також можливих шляхiв покращення цiєї складностi. Предметом дослiдження є процес застосування алгоритму QAOA до задачi SVP та його складнiсть. У роботi побудовано та доведено оцiнки складностi алгоритму QAOA для наявного зведення. Також запропоноване новий метод зведення, для якого побудовано аналогiчнi оцiнки складностi. Виконано порiвняльний аналiз двох описаних методiв зведення для практично значимих екземплярiв задачi SVP.
dc.description.abstractotherThe first 3 winners of the NIST Post-Quantum Cryptographic Algorithms competition have already been announced, and public draft versions of the corresponding USA federal standards for post-quantum digital signature and key encapsulation have been published. The security of the corresponding cryptosystems is based on the complexity of certain lattice problems. The Shortest Vector Problem (SVP) serves as a fundamental problem that defines the upper bound of complexity for most lattice problems used in post-quantum cryptography. At the same time, current technological development has not yet enabled the creation of a fault-tolerant scalable quantum computer capable of effectively applying full-fledged quantum algorithms to practical-sized problems. In such conditions, research and development of quantum algorithms are actively underway to enable existing NISQ computers to tackle practical problems. One of the main directions in building such algorithms has been Variational Quantum Algorithms, with QAOA being the most advanced and versatile one today. Applying such algorithms requires reducing the studied problem to the problem of finding the ground state of a Hamiltonian. The purpose of this work is to study the complexity of applying the QAOA to the SVP and possible ways to improve this complexity. The subject of the research is the application of the QAOA to the SVP and its complexity. The work constructs and proves quantum complexity bounds for the QAOA for the existing reduction. Additionally, a new reduction method is proposed, for which similar complexity bounds are constructed. A comparison of the two described reduction methods is performed for practically significant instances of the SVP problem.
dc.format.extent53 c.
dc.identifier.citationКiстаєв, M. A. Застосування алгоритму QAOA для розв’язання задачi SVP : дипломна робота ... бакалавра. : 113 Прикладна математика / Кiстаєв Матвiй Андрiйович. - Київ, 2024. - 53 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/69293
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectпостквантова криптографiя
dc.subjectзадача svp
dc.subjectквантовi варiацiйнi алгоритми
dc.subjectалгоритм qaoa post-quantum cryptography
dc.subjectshortest vector problem
dc.subjectvariational quantum algorithms
dc.subjectqaoa
dc.subject.udc510.52
dc.titleЗастосування алгоритму QAOA для розв’язання задачi SVP
dc.typeBachelor Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Kistaiev_bakalavr.pdf
Розмір:
788.43 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Бакалаврські роботи (ММЗІ)
Бакалаврські роботи