Застосування алгоритму QAOA для розв’язання задачi SVP
Вантажиться...
Дата
2024
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Нараз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.
Опис
Ключові слова
постквантова криптографiя, задача svp, квантовi варiацiйнi алгоритми, алгоритм qaoa post-quantum cryptography, shortest vector problem, variational quantum algorithms, qaoa
Бібліографічний опис
Кiстаєв, M. A. Застосування алгоритму QAOA для розв’язання задачi SVP : дипломна робота ... бакалавра. : 113 Прикладна математика / Кiстаєв Матвiй Андрiйович. - Київ, 2024. - 53 с.