Компьютерра PDA N104 (26.03.2011-01.04.2011) - [12]

.

С помощью марионеток американские военные смогут добиваться ложного единодушия в сетевых дискуссиях, дружного вопля "распни Его!". Психологические операции во все времена похожи и проходят по ведомству информационных технологий, хотя Добролюбов и создал некогда виртуальную личность Якова Хама, от лица которого в "Свистке" печатались благонамеренные вирши.

Анатолий Вассерман: Квантовое планирование

Автор: Анатолий Вассерман

Опубликовано 29 марта 2011 года

"Компьюлента" сообщает: "Молекулы фуллерена были использованы для создания квантовых точек". Сделан ещё один заметный шаг по направлению к созданию работоспособной квантовой вычислительной системы.

Не слишком углубляясь в технические подробности (их при желании можно выгуглить в любой потребной дозе), отмечу: квантовые вычисления теоретически могут идти одновременно по всем возможным веткам задачи, невзирая на общее число этих веток. Таким образом, время решения задачи определяется скоростью прохождения по одной ветке. Конечно, для надлежащего представления задачи в виде, допускающем квантовое распараллеливание, зачастую требуются далеко не тривиальные усилия математиков в целом и алгоритмистов в частности. Но пока принято считать, что такие усилия всегда осуществимы в разумный срок.

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

Один из известнейших примеров NP-задач - современные методы криптографии: если задан конкретный ключ, можно довольно быстро зашифровать и/или расшифровать текст, но по конкретному набору образцов зашифрованного текста невозможно быстро вычислить ключ, а можно лишь подобрать его (что при достаточной длине ключа требует астрономического времени). Квантовый компьютер позволит быстро дешифровать любой закодированный материал. Отсюда интерес к нему многих серьёзных структур.

Меня же квантовый компьютер интересует скорее в связи с обычной полиномиальной задачей. Ещё в "Компьютерре" №1996/20 я опубликовал статью "Коммунизм и компьютер", где перевёл с математического языка на человеческий некоторые труды выдающегося советского математика Виктора Михайловича Глушкова (в журнале я ухитрился назвать его Владимиром). Из них следует: число действий, необходимое для балансировки плана производства, пропорционально числу названий предметов, чьё производство планируется, примерно в степени 2.5, а для оптимизации плана - в степени 3.5, и способов дальнейшего уменьшения этого показателя математика не видит.

В середине 1970-х, когда Глушков обнародовал первые свои труды на эту тему, общее число названий предметов, производимых в СССР, перевалило за 20 миллионов. Отсюда следовало: весь мировой вычислительный парк 1996-го года мог справиться с балансировкой общесоветского плана на 1976-й год лет за десять, а с оптимизацией - за добрый миллиард лет. С общемировой же экономикой образца 1996-го и подавно не было шансов управиться. Между тем хозяйственная обстановка меняется едва ли не ежеминутно (даже в отсутствие катаклизмов, вроде недавнего землетрясения в Японии), и в идеале надо так же ежеминутно принимать решения, учитывающие эти перемены. Правда, с тех пор всемирная вычислительная мощность выросла на несколько порядков, но и разнообразие производства многократно выросло. Так что математически идеальное планирование сегодня остаётся столь же недостижимым, как и полтора десятилетия назад.

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

В то же время классический рынок благодаря децентрализации принятия решений чаще всего выбирает локальный экстремум, отстающий от глобального всего в пару раз. Поэтому планирование экономики из единого центра приводит к ухудшению состояния экономики в целом примерно на порядок, хотя и позволяет на любом заранее выбранном направлении добиться более чем впечатляющих результатов (но, увы, чаще всего ценой заметного отставания на многих иных направлениях). Исходя из этих и многих других сходных соображений, я тогда решительно поддержал рыночную экономику, да и по сей день остаюсь в целом её приверженцем. Просто потому, что в среднем она работает лучше.

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