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