Введение в квантовые алгоритмы
Задача разложения на элементарные операции. Эффективные алгоритмы синтеза логических операций.
Алгоритмы быстрой арифметики на квантовых вычислителях.
Алгоритм Гровера поиска в неупорядоченной базе данных и его оптимальность. Квантовый алгоритм усиления амплитуды.
Квантовые блуждания и квадратичное ускорение сходимости марковских цепей. Задача о сваренных деревьях.
Квантовое преобразование Фурье. Квантовый алгоритм оценки фазы. Квантовое цифро-аналоговое и аналого-цифровое преобразования.
Задачи поиска скрытой подгруппы. Алгоритм Саймона. Aлгоритмы Шора решения задач дискретного логарифмирования и нахождения периода.
Симуляция квантовой динамики спиновых цепочек. Разложение Сузуки-Троттера. Адиабатические вычисления и их универсальность.
Вариационные квантовые алгоритмы (VQA). Алгоритм приближенной квантовой оптимизации (QAOA).
Вычисления на одном чистом кубите (DQC1). Тест Адамара, swap-тест. Оценка высокотемпературных корреляторов.
Алгоритм Харроу–Хассидима–Ллойда (HHL) решения линейных систем уравнений. Квантовое машинное обучение.
Квантовая обработка сигнала (QSP). Блочные кодирования, кубитизация, разложения в линейные комбинации унитарных операций (LCU).
Квантовое преобразование сингулярных значений (QSVT). Приготовление основного состояния локального гамильтониана.
Сведение задач оптимизации к декодированию (DQI).
Эффективная обработка больших данных на квантовых процессорах (QOS).
E. O. Kiktenko, A. A. Popov, A. K. Fedorov, “Bidirectional imperfect quantum teleportation with a single Bell state”, Phys. Rev. A, 93 (2016)
I. A. Luchnikov, E. O. Kiktenko, M. A. Gavreev, H. Ouerdane, S. N. Filippov, A. K. Fedorov, “Probing non-Markovian quantum dynamics with data-driven analysis: Beyond “black-box” machine-learning models”, Phys. Rev. Research, 4 (2022)
Страница спецкурса: https://www.mathnet.ru/conf2803
Квантовые вычисления представляют собой обобщённую модель обработки информации, обладающую фундаментальными преимуществами по сравнению с классическими вычислениями. Область квантовых алгоритмов занимается математическим исследованием этих преимуществ и возможностей их применения при решении конкретных вычислительных задач.
В 1994 году Питер Шор разработал эффективный алгоритм для решения задачи разложения больших чисел на множители, таким образом показав, что построение полноценных квантовых вычислитетей поставит под угрозу стойкость современных криптографических систем. С тех пор были разработаны методы решения многих важных задач из различных областей: вычислительной теории чисел, криптологии, квантовой химии, квантовой многочастичной физики и физики высоких энергий, логистики — в этих исследованиях использовались продвинутые результаты линейной алгебры, теории операторов, теории аппроксимаций, теории представлений, теории вычислительной сложности. В целом, была проведена огромная работа по разработке, доказательству корректности, систематике и унификации квантовых алгоритмов.
Цель нашего курса — взглянуть на главные квантовые алгоритмы, сформировать общее понимание принципов их построения, познакомиться с используемыми ими математическими теориями и научиться оценивать их потенциал в приложениях. Курс начнётся с обсуждения ранних результатов в области квантовых алгоритмов — включая алгоритмы Гровера и Шора, — после чего мы последовательно проследим за развитием этих идей и взглянем на современные достижения, такие как методы квантового преобразования сингулярных значений и вариационные алгоритмы.