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

Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями.

О сложности вычислений и квантовых компьютерах рассказывает Александр Ханиевич Шень — кандидат физико-математических наук, научный сотрудник Института проблем передачи информации РАН (Москва) и LIF CNRS — Лаборатории информатики Национального центра научных исследований Франции (Марсель). Лекция была прочитана 23 апреля 2009 года в Москве, в ФИАНе.

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

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

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

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

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

Даже если слово «квантовый» не пугает вас, квантовые компьютеры все еще остаются скорее причудливыми концепциями научной фантастики, нежели реальностью. Однако последние достижения в этой области предполагают, что эти безумно быстрые компьютеры могут появиться раньше, чем мы думаем. Соблазном квантовых компьютеров является их способность решать почти неразрешимые проблемы — настолько сложные проблемы, что для их решения современным компьютерам потребовались бы десятилетия. В теории квантовый компьютер сможет решить эти вопросы, пока вы пьете утренний кофе.

Что такое квантовый компьютер и насколько он похож на человеческий мозг? Существуют ли атомы сознания и может ли оно (сознание) рассматриваться как коллективный квантовый эффект? О математических моделях мышления, сознания и даже депрессии, сегодня после полуночи, доктор физико-математических наук Игорь Волович и наш гость из Швеции, профессор, директор Международного центра математического моделирования Андрей Хренников.