Реклама
Книги по философии
Дэвид Дойч
Структура реальности
(страница 47)
Известны интерференционные явления, включающие огромные количества частиц, например, суперпроводимость или супертекучесть, но кажется, что ни одно из них невозможно использовать для выполнения хоть сколь-нибудь интересных вычислений. Во время написания книги в лаборатории можно было без труда выполнить только однобитовые квантовые вычисления. Однако, экспериментаторы уверены, что в течение нескольких последующих лет будут созданы двух- и более битовые квантовые логические элементы (квантовые эквиваленты классических логических элементов). Это основные составляющие квантовых компьютеров. Некоторые физики, особенно Рольф Ландауер из Исследовательского Центра IBM, настроены пессимистично относительно перспектив будущих достижений. Они полагают, что декогерентность никогда не будет сведена до того уровня, где можно будет выполнить больше, чем несколько последовательных этапов квантового вычисления. Большинство исследователей из этой области настроены гораздо более оптимистично (хотя возможно, это связано с тем, что над квантовым вычислением решаются работать только очень большие оптимисты!). Уже были построены некоторые специализированные квантовые компьютеры (смотри ниже), и лично я думаю, что появление более сложных квантовых компьютеров -- скорее дело нескольких лет, чем десятилетий. Что касается универсального квантового компьютера, то я считаю, что его создание -- это тоже только дело времени, хотя мне не хотелось бы предсказывать, сколько времени на это уйдет: десятилетия или века.
Тот факт, что репертуар универсального квантового компьютера содержит среды, передача которых является труднообрабатываемой для классического вычисления, говорит о том, что новые классы чисто математических вычислений тоже должны стать легкообрабатываемыми на этом компьютере. Как сказал Галилео, законы физики выражаются на языке математики, а передача среды эквивалентна оценке определенных математических функций. Действительно, в настоящее время обнаружено множество математических задач, которые можно было бы эффективно решить с помощью квантового вычисления, так как для всех известных классических методов они являются труднообрабатываемыми. Наиболее эффектной из этих задач является задача разложения на множители больших чисел. В 1994 году Питер Шор, работающий в Bell Laboratories, открыл метод, известный как алгоритм Шора. (Пока эта книга корректировалась, были открыты другие эффектные квантовые алгоритмы, включая алгоритм Гровера для очень быстрого поиска длинных списков).
Алгоритм Шора чрезвычайно прост и довольствуется гораздо более скромным аппаратным обеспечением, чем то, которое понадобилось бы для универсального квантового компьютера. А потому вероятно, что квантовое устройство для разложения на множители будет построено задолго до того, как весь диапазон квантовых вычислений станет технологически осуществимым. Эта перспектива имеет грандиозное значение для криптографии (науки, которая занимается секретной передачей информации и установлением ее подлинности). Реальные сети связи могут быть глобальными и иметь огромные, постоянно изменяющиеся наборы участников с непредсказуемыми схемами связи. Непрактично требовать, чтобы каждая пара участников заранее физически обменивалась секретными шифровальными ключами, которые позволили бы им позднее общаться, не боясь, что их подслушают. Криптография с открытым ключом -- это любой метод отправки секретной информации, при котором ни отправитель, ни получатель не делятся секретной информацией. Самый надежный из известных методов криптографии с открытым ключом основан на трудности обработки задачи разложения на множители больших чисел. Этот метод известен как криптосистема RSA, которая получила свое название в честь Рональда Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адельмана (Adelman), которые впервые предложили ее в 1978 году. Этот метод обусловлен математической процедурой, посредством которой сообщение можно закодировать, используя в качестве ключа огромное (скажем, 250-значное) число. Получатель может свободно обнародовать этот ключ, потому что любое сообщение, зашифрованное с его помощью, можно расшифровать, только зная множители этого числа. Таким образом, я могу выбрать два 125-значных простых числа и хранить их в секрете, но перемножив, сообщить всем их 250-значное произведение. Кто угодно может послать мне сообщение, использовав это число как код, но только я смогу прочитать эти сообщения, потому что только мне известны секретные множители.
Как я уже сказал, не существует практической возможности разложения на множители 250-значного числа с использованием классических средств. Но квантовое устройство разложения на множители, работающее по алгоритму Шора, могло бы это сделать, выполнив всего несколько тысяч арифметических операций, что, возможно, было бы минутным делом. Таким образом, любой человек, имеющий доступ к такой машине, смог бы легко прочитать любое перехваченное сообщение, зашифрованное с помощью криптосистемы RSA.
Шифровальщикам не помогло бы даже использование больших чисел в качестве ключей, потому что ресурсы, необходимые для работы алгоритма Шора, очень медленно увеличиваются с увеличением раскладываемого на множители числа. В квантовой теории вычисления разложение на множители -- очень легко обрабатываемая задача. Считается, что при данном уровне декогерентности снова появится практическое ограничение величины числа, которое можно разложить на множители, но неизвестен нижний предел технологически достижимой степени декогерентности. Поэтому, мы должны сделать вывод, что однажды в будущем, во время, которое сейчас невозможно предсказать, криптосистема RSA с любой данной длиной ключа может стать несекретной. В определенном смысле это делает ее несекретной даже сегодня. Любой человек или организация, которые сейчас записывают сообщения, закодированные в системе RSA, и ждут того времени, когда смогут купить квантовое устройство разложения на множители с достаточно низкой декогерентностью, смогут расшифровать эти сообщения. Возможно, это произойдет только через века, возможно всего через несколько десятилетий, а может, и еще раньше -- кто знает? Но вероятность, что это произойдет еще не скоро, -- это все, что теперь осталось от бывшей абсолютной секретности системы RSA.
Когда квантовое устройство разложения на множители раскладывает на множители 250-значное число, количество интерферирующих вселенных будет порядка 10500, т.е. десять в степени 500. Это ошеломляюще огромное число -- причина того, почему алгоритм Шора делает разложение на множители легкообрабатываемым. Я сказал, что этот алгоритм требует выполнения всего нескольких тысяч арифметических операций. Безусловно, я имел в виду несколько тысяч операций в каждой вселенной, которая вносит вклад в ответ. Все эти вычисления выполняются в различных параллельных вселенных и делятся своими результатами через интерференцию.
Возможно, вам интересно, как мы сможем убедить своих двойников из 10000 вселенных начать работать над нашей задачей разложения на множители. Разве у них нет своих собственных задач, чтобы задействовать компьютеры? Нам не нужно их убеждать. Алгоритм Шора изначально действует только в наборе вселенных, идентичных друг другу, и вызывает в них отличия только в пределах устройства разложения на множители. Поэтому мы, точно определившие число, которое нужно разложить на множители, и ждущие ответа, идентичны во всех интерферирующих вселенных. Несомненно, существует много других вселенных, в которых мы запрограммировали другое число или вообще не построили устройство разложения на множители. Но эти вселенные отличаются от нашей слишком большим количеством переменных -- или точнее, переменными, которые программирование алгоритма Шора не привело к нужному взаимодействию, -- и потому они не интерферируют с нашей вселенной.
Доказательство, приведенное в главе 2, применительно к любому явлению интерференции, разрушает классическую идею существования только одной вселенной. Логически возможность комплексных квантовых вычислений ничего не дает в том случае, на который уже нельзя ответить. Но эта возможность оказывает психологическое влияние. Алгоритм Шора расширяет это доказательство. Для тех, кто все еще склонен считать, что существует только одна вселенная, я предлагаю следующую задачу: объясните принцип действия алгоритма Шора. Я не имею в виду, предскажите, что он будет работать, поскольку для этого достаточно решить несколько непротиворечивых уравнений. Я прошу вас дать объяснение. Когда алгоритм Шора разложил на множители число, задействовав примерно 10500 вычислительных ресурсов, которые можно увидеть, где это число раскладывалось на множители?
Во всей видимой вселенной существует всего около 1080 атомов, число ничтожно малое по сравнению с 10500. Таким образом, если бы видимая вселенная была мерой физической реальности, физическая реальность даже отдаленно не содержала бы ресурсов, достаточных для разложения на множители такого большого числа. Кто же тогда разложил его т множители? Как и где выполнялось вычисление?
Я говорил о традиционных типах математических задач, которые квантовые компьютеры смогли бы выполнить быстрее существующих. Но для квантовых компьютеров открыт и дополнительный класс новых задач, которые не способен решить ни один классический компьютер. По странному совпадению, одной из первых таких задач обнаружили задачу, также связанную с криптографией с открытым ключом. На этот раз дело не в разрушении существующей системы, а в реализации новой абсолютно секретной системы квантовой криптографии. В 1989 году в Нью-Йорке, в Исследовательском Центре IBM, в офисе теоретика Чарльза Беннетта был построен первый рабочий квантовый компьютер. Это был специализированный квантовый компьютер, состоящий из двух квантовых криптографических устройств, спроектированных Беннеттом и Жилем Брассаром из Монреальского Университета. Этот компьютер стал первой машиной, выполнившей небанальные вычисления, которые не смогла бы выполнить ни одна машина Тьюринга.
