Цифровой журнал «Компьютерра» № 62

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

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

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

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

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

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

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

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