Вероятностные и квантовые алгоритмы

Лектор - профессор Алексеев Валерий Борисович.

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

Объявления

Вопросы к экзамену на январь 2022 года

Программа курса

• Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

• Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

• Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

• Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

• Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

• Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

• Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

• Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

• Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

• Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

• Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

• Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

• Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

• Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

• Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

• Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

• Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

• Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

Литература

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291. discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.