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

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

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

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

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

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

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

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

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

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

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

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

Более того, даже если ограничиться классической цифровой техникой, пока не видно заметных отступлений от закона Мура об экспоненциальном росте производительности каждого отдельного процессора. Число же их пока растёт также экспоненциально. То есть даже обычная вычислительная мощность того и гляди окажется достаточной для всемирного Госплана.

Увы, есть в статье и третья глава. За год до Канторовича ту же премию по экономике получил Фридрих Август фон Хайек. Он, в частности, показал: все сведения, необходимые для составления плана, не могут быть собраны в едином управляющем центре хотя бы потому, что значительная часть этих сведений формируется в процессе производства, а то и потребления произведённого. Более того, из его трудов следует: в принципе невозможен лучший, нежели деньги, носитель информации, необходимой для принятия хозяйственных решений. Так что рыночная экономика даже при наличии квантовых компьютеров будет по суммарным показателям опережать плановую.

Это, конечно, не значит, что надо вовсе отказаться от плана. Если перед обществом встаёт задача, требующая напряжения всех его сил, централизация управления незаменима. Даже в оплоте современной рыночной идеологии США, для полёта человека на Луну, централизовали управление космическими исследованиями куда сильнее, чем это когда-либо удавалось в СССР. Сейчас с нелёгкой руки Ханны Арендт такую концентрацию усилий принято именовать тоталитаризмом и считать безоговорочно вредной. Тогда, очевидно, и великий тренер фигуристов Станислав Алексеевич Жук - страшный и предосудительный тоталитарист.

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

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