WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 33 | 34 || 36 | 37 |   ...   | 58 |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме.

Pages:     | 1 |   ...   | 33 | 34 || 36 | 37 |   ...   | 58 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.