Александр Александрович Разборов VI Летняя школа «СОВРЕМЕННАЯ МАТЕМАТИКА» (Дубна, 25 июля 2006 года)
Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время:
- Классические и квантовые схемы.
- Алгоритм Шора быстрого разложения чисел на множители: основные идеи.
- Квантовые оракулы и задача о скрытой подгруппе.
- Алгоритм квантового поиска Гровера: основные идеи.