Эта странная математика. На краю бесконечности и за ним - [33]

Недетерминированные машины Тьюринга существуют, как мы уже выяснили, только в нашем воображении. Другое дело – квантовый компьютер, потенциально тоже чрезвычайно мощное устройство, которое уже начали создавать. Как ясно из названия, в основе принципа его работы лежит ряд очень странных явлений из области квантовой механики. А оперирует он не обычными битами (от англ. binary digit – “двоичное число”), а квантовыми, так называемыми кубитами (от англ. quantum bit – “квантовый бит”). Кубит, который может представлять собой просто электрон с неизвестным спином, имеет в контексте квантовых эффектов две характеристики, отсутствующие у обычного бита в традиционном компьютере. Во-первых, он может находиться в суперпозиции состояний: одновременно представлять собой и 0, и 1, а становиться тем или другим только тогда, когда за ним наблюдают. Это же явление можно истолковать и по-другому: квантовый компьютер, вместе со всей остальной вселенной, расщепляется на две копии самого себя, в одной из которых бит 1, а в другой – бит 0, и только при измерении кубита он, вместе с окружающей его вселенной, “схлопывается” в конкретное значение. Второе любопытное свойство, лежащее в основе работы квантовых компьютеров, – запутанность. Два запутанных кубита, даже будучи разделенными в пространстве, так связаны друг с другом явлением, которое окрестили “жутким дальнодействием”, что измерение одного из них мгновенно влияет на измерение второго.

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

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

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

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