Дэвид Дойч - Структура реальности. Наука параллельных вселенных

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

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

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

Когда квантовое устройство разложения на множители раскладывает 250-значное число, количество интерферирующих вселенных будет порядка 10500, т. е. десять в степени 500. Это ошеломляюще огромное число – причина того, почему алгоритм Шора делает разложение на множители легкорешаемой задачей. Я сказал, что этот алгоритм требует выполнения всего нескольких тысяч арифметических операций. Безусловно, я имел в виду несколько тысяч операций в каждой вселенной, которая вносит вклад в ответ. Все эти вычисления выполняются параллельно в различных вселенных и делятся своими результатами через интерференцию.