Тот факт, что репертуар универсального квантового компьютера содержит среды, воспроизведение которых является труднорешаемым в классическом смысле, говорит о том, что новые классы чисто математических вычислений тоже должны стать легкорешаемыми на этом компьютере, потому что законы физики, как сказал Галилей, выражаются на языке математики, а воспроизведение среды эквивалентно вычислению определенных математических функций. Действительно, в настоящее время обнаружено множество математических задач, которые можно было бы эффективно решить с помощью квантовых вычислений, тогда как для всех известных классических методов они являются труднорешаемыми. Наиболее впечатляющей из этих задач является задача разложения на множители больших чисел. В 1994 году Питер Шор, работавший в Bell Laboratories, открыл метод, известный как алгоритм Шора. (Пока американское издание этой книги готовилось к печати, были открыты другие впечатляющие квантовые алгоритмы, включая алгоритм Гровера для очень быстрого поиска в длинных списках.)
Алгоритм Шора чрезвычайно прост и довольствуется гораздо более скромной аппаратурой, чем та, которая понадобилась бы для универсального квантового компьютера. А потому вероятно, что квантовое устройство для разложения на множители будет построено задолго до того, как станет технологически осуществимым весь спектр квантовых вычислений. Эта перспектива имеет грандиозное значение для криптографии (науки о секретной передаче информации и установлении ее подлинности). Реальные сети связи могут быть глобальными и иметь огромные, постоянно изменяющиеся наборы участников с непредсказуемыми схемами связи. Непрактично требовать, чтобы каждая пара участников заранее физически обменивалась секретными шифровальными ключами, которые позволили бы им позднее общаться, не боясь, что их подслушают. Криптография с открытым ключом – это любой метод отправки секретной информации, при котором ни отправитель, ни получатель не обменивались до этого никакой секретной информацией. Самый надежный из известных методов криптографии с открытым ключом основан на труднорешаемости задачи разложения на множители больших чисел. Этот метод известен как криптосистема RSA, которая получила свое название по первым буквам фамилий Рональда Ривеста, Ади Шамира и Леонарда Адельмана, впервые предложивших ее в 1978 году. Она полагается на математическую процедуру, посредством которой можно закодировать сообщение, используя в качестве ключа огромное (скажем, 250-значное) число. Получатель может свободно обнародовать этот ключ для использования всеми отправителями, потому что любое сообщение, зашифрованное с его помощью, можно расшифровать, только зная сомножители этого числа. Таким образом, я могу выбрать два 125-значных простых числа и хранить их в секрете, но перемножить их и сообщить всем их 250-значное произведение. Кто угодно может послать мне сообщение, используя это число как ключ, но только я смогу прочитать эти сообщения, потому что только мне известны секретные множители.
Как я уже сказал, не существует практической возможности разложения на множители 250-значного числа с использованием классических средств. Но квантовое устройство разложения на множители, работающее по алгоритму Шора, могло бы это сделать, выполнив всего несколько тысяч арифметических операций, что, возможно, было бы минутным делом. Таким образом, любой человек, имеющий доступ к такой машине, смог бы легко прочитать любое перехваченное сообщение, зашифрованное с помощью криптосистемы RSA.
Криптографам не помогло бы использование более длинных чисел в качестве ключей, потому что ресурсы, необходимые для работы алгоритма Шора, очень медленно увеличиваются с ростом раскладываемого на множители числа. В квантовой теории вычислений разложение на множители – очень легкорешаемая задача. Считается, что при данном уровне декогеренции все же снова появится некий практический предел размера числа, которое можно разложить на множители, но неизвестен нижний предел технологически достижимой скорости декогеренции. Поэтому мы должны сделать вывод, что однажды в будущем, во время, которое сейчас невозможно предсказать, криптосистема RSA с любой заданной длиной ключа может стать ненадежной. В определенном смысле это делает ее ненадежной даже сегодня. Ведь люди или организации, которые сейчас перехватывают сообщения, закодированные в системе RSA, и дождутся того времени, когда смогут купить квантовое устройство разложения на множители с достаточно низкой декогеренцией, сумеют расшифровать эти сообщения. Возможно, это произойдет только через века, возможно, всего через несколько десятилетий, а может, и еще раньше – кто знает? Но вероятность того, что это случится еще не скоро, – это все, что теперь осталось от бывшей абсолютной надежности системы RSA.
Когда квантовое устройство разложения на множители раскладывает 250-значное число, количество интерферирующих вселенных будет порядка 10500, т. е. десять в степени 500. Это ошеломляюще огромное число – причина того, почему алгоритм Шора делает разложение на множители легкорешаемой задачей. Я сказал, что этот алгоритм требует выполнения всего нескольких тысяч арифметических операций. Безусловно, я имел в виду несколько тысяч операций в каждой вселенной, которая вносит вклад в ответ. Все эти вычисления выполняются параллельно в различных вселенных и делятся своими результатами через интерференцию.
Возможно, вам интересно, как мы сможем убедить своих партнеров из 10500 или около того вселенных начать работать над нашей задачей разложения на множители. Разве у них нет своих собственных задач, чтобы задействовать компьютеры? Нет – и нам не нужно их убеждать. Алгоритм Шора изначально действует только в наборе вселенных, идентичных друг другу, и вызывает в них отличия только в пределах устройства разложения на множители. Поэтому мы, указавшие число, которое нужно разложить на множители, и ждущие ответа, идентичны во всех интерферирующих вселенных. Несомненно, существует много других вселенных, в которых мы задали другие числа или вообще не построили устройства разложения на множители. Но эти вселенные отличаются от нашей слишком большим количеством переменных – или, точнее, переменными, которые не настроены для правильного взаимодействия посредством запрограммированного алгоритма Шора, – и потому они не интерферируют с нашей Вселенной.
Рассуждения, приведенные в главе 2, будучи применены к любому явлению интерференции, разрушают классическую идею о единственности Вселенной. Логически возможность сложных квантовых вычислений ничего не добавляет к вопросу, на который уже нельзя ответить иначе. Но эта возможность оказывает дополнительное психологическое влияние. Алгоритм Шора очень сильно повышает убедительность этих рассуждений. Для тех, кто все еще склонен считать, что существует лишь одна Вселенная, я предлагаю следующий вызов: объясните, как работает алгоритм Шора. Я имею в виду не предсказание, каковы будут результаты его работы, поскольку для этого достаточно решить несколько непротиворечивых уравнений. Я прошу вас дать объяснение. Когда алгоритм Шора разлагает на множители число, задействовав примерно в 10500 больше вычислительных ресурсов, чем те, что можно увидеть воочию, – где же это число раскладывается на множители?
Во всей видимой Вселенной существует всего около 1080 атомов – число ничтожно малое по сравнению с 10500. Таким образом, если бы видимая Вселенная была пространством физической реальности, физическая реальность даже отдаленно не содержала бы ресурсов, достаточных для разложения на множители такого большого числа. Кто же тогда разложил его на множители? Как и где выполнялись вычисления?
Я говорил о традиционных типах математических задач, которые квантовые компьютеры смогли бы выполнить быстрее существующих машин. Но для квантовых компьютеров открыт и дополнительный класс новых задач, которые ни один классический компьютер не способен решить вообще. По странному совпадению, одна из первых найденных задач такого типа также была связана с криптографией с открытым ключом. На этот раз она состояла не во «взломе» существующей системы, а в реализации новой абсолютно надежной системы квантовой криптографии. В 1989 году в компании IBM Research в Йорктаун-Хайтс, штат Нью-Йорк, в кабинете теоретика Чарльза Беннетта был построен первый рабочий квантовый компьютер. Это был специализированный квантовый компьютер, состоящий из двух квантовых криптографических устройств, спроектированных Беннеттом и Жиллем Брассаром из Университета Монреаля. Этот компьютер стал первой машиной, выполнившей нетривиальные вычисления, которые не смогла бы выполнить ни одна машина Тьюринга.
