Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время: Классические и квантовые схемы; Алгоритм Шора быстрого разложения чисел на множители: основные идеи; Квантовые оракулы и задача о скрытой подгруппе; Алгоритм квантового поиска Гровера.

Вы узнаете: Какие технологии называются квантовыми и почему. В чем преимущество квантовых технологий перед классическими. Что может и что не может квантовый компьютер. Как физики делают квантовый компьютер. Когда он будет создан.

Физик Алексей Федоров о будущем гибридной криптографии, предпосылках возникновения квантового компьютера и задаче факторизации.

Какие условия должны соблюдаться при применении технологии квантовой криптографии? Каковы коммерческие перспективы этой технологии? Каким образом обеспечивается безопасность информации при использовании данного метода ее передачи? О принципе квантового распределения ключа, коммерческой составляющей квантовых технологий и информационной безопасности рассказывает доктор физико-математических наук Сергей Кулик.

Отрывок из книги математиков Андрея Райгородского и Нелли Литвак, посвященный истории онлайн-рекламы, нобелевскому лауреату Уильяму Викри и стоимости одного клика.

Физики из Массачусетского технологического института и Инсбрукского университета создали квантовый компьютер, допускающий масштабирование при выполнении алгоритма Шора. Алгоритм Питера Шора — это квантовый алгоритм разложения чисел на простые множители, то есть факторизации. Суть алгоритма заключается в сведении задачи факторизации к поиску периода функции.

Квантовый мир очень далек от нашего, поэтому его законы часто кажутся нам странными и контринтуитивными. Однако важные новости из квантовой физики приходят буквально каждый день, так что иметь о них правильное представление сейчас необходимо — иначе работа физиков в наших глазах превращается из науки в магию и обрастает мифами. На наши вопросы о том, что это значит, отвечал сотрудник РКЦ, заведующий лабораторией сверхпроводящих материалов Национального исследовательского технологического университета «МИСиС» и профессор Технологического института Карлсруэ Алексей Устинов.

В 1936 году советский инженер и учёный Владимир Лукьянов создал вычислительную машину, все математические операции в которой выполняла текущая вода. Гидравлический интегратор Лукьянова — первая в мире вычислительная машина для решения дифференциальных уравнений в частных производных — на протяжении полувека был единственным средством вычислений, связанных с широким кругом задач математической физики.

Электронно-цифровые подписи мы используем повсеместно. Это действительно один из самых простых, универсальных и надежных способов гарантировать наше авторство на какой-либо цифровой контент в цифровом мире. Однако, как было показано Питером Шором, квантовые компьютеры дают ускорение в решении ряда математических задач, в частности в решении задачи факторизации. Таким образом, квантовый компьютер может стать угрозой для инфраструктуры электронно-цифровых подписей. Физик Алексей Федоров о квантовых технологиях, принципе блокчейна и электронно-цифровых подписях.

План лекций: Доказуемость и недоказуемость (почему некоторые утверждения нельзя ни доказать, ни опровергнуть?); Вычислимые функции (почему некоторые функции нельзя вычислить на компьютере?); Сложность алгоритмов; Формальные языки и исчисления.