Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

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

Профессор Уинфрид Хенсингер ( слева ) и Себастьян Вайдт работают над прототипом квантового компьютера.

Заманчиво приравнять квантовые компьютеры к недетерминированным машинам Тьюринга, но, увы, это разные вещи. Да, их вычислительные возможности одинаковы, в этом смысле недетерминированные машины Тьюринга не превосходят детерминированные: на ДМТ можно смоделировать как первые, так и вторые. А вот по эффективности квантовым компьютерам вряд ли удастся догнать НМТ, что неудивительно, поскольку НМТ – исключительно гипотетические устройства. Маловероятно, например (хоть это пока и не доказано), что они смогут решать NP -полные задачи за полиномиальное время. Впрочем, одну задачу, которую раньше считали не имеющей такого решения (что предполагало бы ложность равенства “ P = NP ”), все же удалось с помощью квантовых компьютеров решить за полиномиальное время – это разложение больших чисел на простые множители. В 1994 году американский математик Питер Шор разработал для этого квантовый алгоритм, учитывающий особые свойства такой задачи. К сожалению, аналогичный метод не может быть применен для решения других задач, например NP -полных. Если и можно разработать для квантовых компьютеров полиномиальный алгоритм решения NP -полной задачи, он опять-таки должен задействовать ее специфические особенности.

Как и любая другая молодая и перспективная технология, квантовые компьютеры – это и множество надежд, и немало проблем. Среди последних – вероятность взлома шифров, которые до сих пор считались высокозащищенными, в основном потому, что, несмотря на все предпринятые усилия, за последние несколько десятилетий никому не удалось разработать полиномиальный метод их дешифровки. Современные методы криптографической защиты основаны на алгоритме RSA, названном так по первым буквам фамилий его изобретателей Рона Ривеста, Ади Шамира и Леонарда Адлемана [22] От англ. Ron Rivest, Adi Shamir, Leonard Adleman. . Алгоритм позволяет очень быстро зашифровать данные и используется ежедневно, ежесекундно при обмене данными в интернете. А вот расшифровка тем же алгоритмом без специальной информации – ключа – происходит гораздо медленнее и требует экспоненциального времени. Именно этой асимметрией скорости и необходимостью обладать дополнительной информацией объясняется эффективность RSA. Работает алгоритм следующим образом: у каждого пользователя есть два ключа – открытый и секретный. С помощью открытого, общедоступного ключа информация шифруется, а секретный ключ, предназначенный для расшифровки, известен только его владельцу. Отправить защищенное сообщение просто – достаточно с помощью открытого ключа применить алгоритм. Но прочитать сообщение сможет только его адресат, имеющий секретный ключ. Теоретически секретный ключ возможно разгадать, зная открытый, но для этого придется разлагать на множители огромные числа, состоящие из сотен знаков. Если ключи достаточно большие, то для расшифровки сообщений, которые мы постоянно отправляем при совершении банковских и других конфиденциальных операций, понадобится задействовать все компьютеры мира, причем работать им нужно будет гораздо больше времени, чем текущий возраст Вселенной. Есть, однако, опасения, что с приходом квантовых компьютеров ситуация может круто измениться.

В 2001 году с помощью алгоритма Шора, который позволяет осуществлять разложение чисел на множители за полиномиальное время, и 7-кубитного квантового компьютера число 15 было разложено на множители 3 и 5. Десятилетие спустя тем же методом было разложено число 21. Оба достижения кажутся смехотворно скромными, учитывая, что то же без труда сделает любой школьник, знающий таблицу умножения. Но вот в 2014 году с помощью другого алгоритма и квантовой вычислительной системы были разложены на простые множители уже гораздо более внушительные числа, 56 153 – самое большое [23] Уже 291 311. – Прим. науч. ред . . Даже этот результат может показаться не очень впечатляющим на фоне проблемы разложения на множители гигантских чисел, состоящих из сотен знаков. Однако с ростом числа кубитов в квантовых компьютерах успешная дешифровка всех шифров RSA рано или поздно станет возможной. Когда это произойдет, сегодняшние способы обмена данными в интернете перестанут быть безопасными – и банковская индустрия, а вместе с ней и все другие системы, требующие защиты передаваемых данных, будут повергнуты в хаос. Вероятно, удастся разработать новую систему криптографической защиты на основе NP -трудных задач – таких, которые не менее трудны для решения, чем NP -полные, но не обязательно относятся к классу NP . Наиболее сложные из NP -полных задач решить очень непросто, но для более типичных случаев обычно можно подобрать подходящий алгоритм. Криптографическую защиту на основе таких задач будет довольно легко взломать, хотя небольшая вероятность того, что шифр окажется крайне сложным, все же есть. Для надежной защиты нужен алгоритм, почти всегда дающий крайне сложный шифр, требующий экспоненциального времени для взлома. Пока такой метод не разработан, хотя в принципе это возможно. Если квантовые компьютеры окажутся неспособными решать NP -полные (а значит, и NP -трудные) задачи, то разработка такого криптографического метода даст нам возможность снова почувствовать себя в безопасности, хотя бы на какое-то время.

Большинство ученых, занимающихся вычислительными системами, полагают, что P ≠ NP . Это мнение подкреплено десятилетиями исследований, в результате которых ни для одной из более чем 3000 известных NP -полных задач не было найдено ни единого алгоритма, позволяющего решить ее за полиномиальное время. И все же аргумент, основанный на отрицательном опыте, не слишком убедителен, особенно в свете неожиданного доказательства Великой теоремы Ферма – очень просто сформулированной задачи, для решения которой потребовались огромные усилия и самые передовые методы. Чисто философские аргументы в пользу того, что P ≠ NP , также не очень убедительны. Скотт Ааронсон, математик, специалист в области теории вычислительных систем, преподающий в Массачусетском технологическом институте, заявил: “Если окажется, что P = NP , то мир станет совершенно не таким, каким мы его обычно считаем. Не будет больше никакой особой ценности в «творческих скачках», исчезнет принципиальная разница между решением задачи и признанием правильности найденного решения”. Тем не менее и в математике, и в других науках с завидной частотой происходят события, полностью переворачивающие наши представления об окружающем мире. Если действительно окажется, что P = NP , то, прежде всего, вряд ли это открытие будет иметь большое практическое значение – ведь доказательство, скорее всего, будет неконструктивным. Другими словами, даже если будет доказано, что для решения NP -полных задач существуют полиномиальные алгоритмы, ни одного конкретного алгоритма в доказательстве приведено не будет. Так что по крайней мере в ближайшем будущем нашим защищенным данным ничто не угрожает – хотя не совсем ясно, как долго это продлится, ведь математики уже всерьез занялись поиском такого алгоритма.