Пошук академічних текстів

Інформація × Реєстраційний номер 2124U002560, Матеріали видань та локальних репозитаріїв Категорія Бакалаврська робота Назва роботи Застосування алгоритму QAOA для розв’язання задачi SVP Автор Кiстаєв Матвiй Андрiйович Дата публікації 01-01-2024 Постачальник інформації Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» Першоджерело 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. Додано в НРАТ 2025-01-29 Закрити