Фесенко, Андрiй В’ячеславовичКiстаєв, Матвiй Андрiйович2024-09-262024-09-262024Кiстаєв, M. A. Застосування алгоритму QAOA для розв’язання задачi SVP : дипломна робота ... бакалавра. : 113 Прикладна математика / Кiстаєв Матвiй Андрiйович. - Київ, 2024. - 53 с.https://ela.kpi.ua/handle/123456789/69293Нараз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.53 c.ukпостквантова криптографiязадача svpквантовi варiацiйнi алгоритмиалгоритм qaoa post-quantum cryptographyshortest vector problemvariational quantum algorithmsqaoaBachelor Thesis510.52