Файл: Дойч. Структура Реальности.doc

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

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

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

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

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

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

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

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

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

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

Экспериментальные и теоретические исследования в области кван­тового вычисления набирают темп во всем мире. Предлагают даже бо­лее обещающие новые технологии реализации квантовых компьютеров и постоянно открывают и анализируют новые типы квантового вы­числения с различными преимуществами перед классическим вычис­лением. Я нахожу все эти разработки весьма захватывающими и счи­таю, что некоторые из них принесут технологические плоды. Но для этой книги данный вопрос несущественен. С фундаментальной точки зрения не имеет значения, насколько полезным оказывается кванто­вое вычисление, как не имеет значения и то, построим ли мы первый универсальный квантовый компьютер на следующей неделе, через ве­ка или не построим его никогда. В любом случае, квантовая теория вычисления должна быть неотъемлемой частью мировоззрения любого человека, ищущего фундаментального понимания реальности. То, что квантовые компьютеры говорят нам о связи законов физики, универ­сальности и, на первый взгляд, несвязанных направлений объяснения в структуре реальности, мы можем обнаружить —и уже обнаружива­ем, —изучая их теоретически.

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

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

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

Легко/труднообрабатываемый(Правило быстрых приближен­ных расчетов) —вычислительная задача считается легкообрабатывае­мой, если ресурсы, необходимые для ее выполнения, не увеличиваются экспоненциально с ростом количества разрядов вводимого числа.

Хаос —неустойчивость движения большинства классических сис­тем. Небольшая разница между двумя начальными состояниями по­рождает экспоненциально растущие отклонения двух результирующих траекторий. Однако реальность подчиняется не классической, а кванто­вой физике. Непредсказуемость, вызванная хаосом, в общем случае пе­рекрывается квантовой неопределенностью, вызванной тем, что иден­тичные вселенные становятся различными.

Универсальный квантовый компьютер —компьютер, способ­ный выполнить любое вычисление, которое способен выполнить любой другой квантовый компьютер, и передать любую конечную физически возможную среду в виртуальной реальности.

Квантовая криптография —любая форма криптографии, кото­рую можно реализовать на квантовых компьютерах, но невозможно на классических.

Специализированный квантовый компьютер —квантовый компьютер, например, квантовое криптографическое устройство или квантовое устройство разложения на множители, который не является универсальным квантовым компьютером.

Декогерентность—когда различные отрасли квантового вычис­ления в различных вселенных по-разному воздействуют на окружаю­щую среду, интерференция уменьшается, а вычисление может не по­лучиться. Декогерентность —это главное препятствие практической реализации более мощных квантовых компьютеров.

Резюме.

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