Структура реальности. Наука параллельных вселенных

Тот факт, что репертуар универсального квантового компьютера содержит среды, воспроизведение которых является труднорешаемым в классическом смысле, говорит о том, что новые классы чисто математических вычислений тоже должны стать легкорешаемыми на этом компьютере, потому что законы физики, как сказал Галилей, выражаются на языке математики, а воспроизведение среды эквивалентно вычислению определенных математических функций. Действительно, в настоящее время обнаружено множество математических задач, которые можно было бы эффективно решить с помощью квантовых вычислений, тогда как для всех известных классических методов они являются труднорешаемыми. Наиболее впечатляющей из этих задач является задача разложения на множители больших чисел. В 1994 году Питер Шор, работавший в Bell Laboratories, открыл метод, известный как алгоритм Шора. (Пока американское издание этой книги готовилось к печати, были открыты другие впечатляющие квантовые алгоритмы, включая алгоритм Гровера для очень быстрого поиска в длинных списках.)

Алгоритм Шора чрезвычайно прост и довольствуется гораздо более скромной аппаратурой, чем та, которая понадобилась бы для универсального квантового компьютера. А потому вероятно, что квантовое устройство для разложения на множители будет построено задолго до того, как станет технологически осуществимым весь спектр квантовых вычислений. Эта перспектива имеет грандиозное значение для криптографии (науки о секретной передаче информации и установлении ее подлинности). Реальные сети связи могут быть глобальными и иметь огромные, постоянно изменяющиеся наборы участников с непредсказуемыми схемами связи. Непрактично требовать, чтобы каждая пара участников заранее физически обменивалась секретными шифровальными ключами, которые позволили бы им позднее общаться, не боясь, что их подслушают. Криптография с открытым ключом – это любой метод отправки секретной информации, при котором ни отправитель, ни получатель не обменивались до этого никакой секретной информацией. Самый надежный из известных методов криптографии с открытым ключом основан на труднорешаемости задачи разложения на множители больших чисел. Этот метод известен как криптосистема RSA, которая получила свое название по первым буквам фамилий Рональда Ривеста, Ади Шамира и Леонарда Адельмана, впервые предложивших ее в 1978 году. Она полагается на математическую процедуру, посредством которой можно закодировать сообщение, используя в качестве ключа огромное (скажем, 250-значное) число. Получатель может свободно обнародовать этот ключ для использования всеми отправителями, потому что любое сообщение, зашифрованное с его помощью, можно расшифровать, только зная сомножители этого числа. Таким образом, я могу выбрать два 125-значных простых числа и хранить их в секрете, но перемножить их и сообщить всем их 250-значное произведение. Кто угодно может послать мне сообщение, используя это число как ключ, но только я смогу прочитать эти сообщения, потому что только мне известны секретные множители.

Как я уже сказал, не существует практической возможности разложения на множители 250-значного числа с использованием классических средств. Но квантовое устройство разложения на множители, работающее по алгоритму Шора, могло бы это сделать, выполнив всего несколько тысяч арифметических операций, что, возможно, было бы минутным делом. Таким образом, любой человек, имеющий доступ к такой машине, смог бы легко прочитать любое перехваченное сообщение, зашифрованное с помощью криптосистемы RSA.

Криптографам не помогло бы использование более длинных чисел в качестве ключей, потому что ресурсы, необходимые для работы алгоритма Шора, очень медленно увеличиваются с ростом раскладываемого на множители числа. В квантовой теории вычислений разложение на множители – очень легкорешаемая задача. Считается, что при данном уровне декогеренции все же снова появится некий практический предел размера числа, которое можно разложить на множители, но неизвестен нижний предел технологически достижимой скорости декогеренции. Поэтому мы должны сделать вывод, что однажды в будущем, во время, которое сейчас невозможно предсказать, криптосистема RSA с любой заданной длиной ключа может стать ненадежной. В определенном смысле это делает ее ненадежной даже сегодня. Ведь люди или организации, которые сейчас перехватывают сообщения, закодированные в системе RSA, и дождутся того времени, когда смогут купить квантовое устройство разложения на множители с достаточно низкой декогеренцией, сумеют расшифровать эти сообщения. Возможно, это произойдет только через века, возможно, всего через несколько десятилетий, а может, и еще раньше – кто знает? Но вероятность того, что это случится еще не скоро, – это все, что теперь осталось от бывшей абсолютной надежности системы RSA.