Структура реальности

Дойч Дэвид

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

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

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

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

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

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

Рассуждения, приведенные в главе 2, будучи применены к любому явлению интерференции, разрушают классическую идею о единственности Вселенной. Логически возможность сложных квантовых вычислений ничего не добавляет к вопросу, на который уже нельзя ответить иначе. Но эта возможность оказывает дополнительное психологическое влияние. Алгоритм Шора очень сильно повышает убедительность этих рассуждений. Для тех, кто все еще склонен считать, что существует лишь одна Вселенная, я предлагаю следующий вызов: объясните, как работает алгоритм Шора. Я имею в виду не предсказание, каковы будут результаты его работы, поскольку для этого достаточно решить несколько непротиворечивых уравнений. Я прошу вас дать объяснение. Когда алгоритм Шора разлагает на множители число, задействовав примерно в 10500 больше вычислительных ресурсов, чем те, что можно увидеть воочию, – где же это число раскладывается на множители?

Во всей видимой Вселенной существует всего около 1080 атомов – число ничтожно малое по сравнению с 10500. Таким образом, если бы видимая Вселенная была пространством физической реальности, физическая реальность даже отдаленно не содержала бы ресурсов, достаточных для разложения на множители такого большого числа. Кто же тогда разложил его на множители? Как и где выполнялись вычисления?

Я говорил о традиционных типах математических задач, которые квантовые компьютеры смогли бы выполнить быстрее существующих машин. Но для квантовых компьютеров открыт и дополнительный класс новых задач,

которые ни один классический компьютер не способен решить вообще. По странному совпадению, одна из первых найденных задач такого типа также была связана с криптографией с открытым ключом. На этот раз она состояла не во «взломе» существующей системы, а в реализации новой абсолютно надежной системы квантовой криптографии. В 1989 году в компании IBM Research в Йорктаун-Хайтс, штат Нью-Йорк, в кабинете теоретика Чарльза Беннетта был построен первый рабочий квантовый компьютер. Это был специализированный квантовый компьютер, состоящий из двух квантовых криптографических устройств, спроектированных Беннеттом и Жиллем Брассаром из Университета Монреаля. Этот компьютер стал первой машиной, выполнившей нетривиальные вычисления, которые не смогла бы выполнить ни одна машина Тьюринга.

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

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

42

За время, прошедшее с момента написания книги, дальность квантовой криптографической связи выросла до нескольких сотен километров за счет повышения качества источников, приемников и передающих сред. Также активно ведутся исследования, направленные на создание квантовых повторителей, которые позволят ретранслировать сигнал без потери ключевого для квантовой криптографии свойства – возможности обнаружить прослушивание канала связи на любом участке. – Прим. ред.

Терминология

Квантовые вычисления – вычисления, которые требуют квантово-механических процессов, особенно интерференции. Другими словами, вычисления, которые осуществляются в сотрудничестве с параллельными вселенными.

Экспоненциальные вычисления – вычисления, требования которых к ресурсам (например, необходимому времени) увеличиваются примерно в одинаковое число раз при добавлении к вводимому числа каждого дополнительного разряда.