Лэнс Фотноу - Золотой билет
Уже доказано, что при решении NP-полных задач на квантовом компьютере алгоритм Гровера в общем случае дает наилучший результат, поэтому квантовые алгоритмы вряд ли позволят приравнять классы P и NP. Если физики когда-нибудь и построят полноценные квантовые компьютеры, самые трудные проблемы все равно окажутся им не по зубам.
Это, конечно, не означает, что от квантовых компьютеров не будет никакого толку. С их помощью мы сможем эффективно эмулировать нетривиальный жизненный цикл различных наносистем и постепенно приоткроем завесу над тайнами вселенной. А еще квантовые компьютеры помогут нам решить некоторые NP-задачи, с которыми обычные компьютеры за разумное время не справляются.
В 1994 году другой сотрудник Лабораторий Белла, Питер Шор, придумал, как на квантовом компьютере можно быстро выполнять факторизацию, т. е. раскладывать число на простые множители (к примеру, для числа 16461679220973794359 тут же выяснилось бы, что 16461679220973794359 = 5754853343 × 2860486313). При наличии мощного квантового компьютера алгоритм Шора спокойно работал бы с числами из сотен и даже тысяч знаков. Для поиска делителей алгоритм строит алгебраические конструкции, с которыми квантовые компьютеры справились бы очень легко. Современным машинам такая задача не под силу, а вот квантовые могли бы эффективно факторизовывать сколь угодно большие числа. К сожалению, хорошие алгебраические конструкции для NP-полных задач пока не придумали, поэтому для них алгоритм Шора работать не будет.
Разумеется, прежде чем реализовывать какой-нибудь квантовый алгоритм, нужно создать полноценный квантовый компьютер. Для решения особо трудоемких задач, перед которыми пасуют даже самые мощные современные машины, понадобятся системы из десятков тысяч запутанных кубитов; связи между кубитами должны сохраняться в течение нескольких секунд, пока с ними проводятся квантовые преобразования. К сожалению, эти связи очень хрупкие и легко обрываются. Малейшее взаимодействие с внешней средой способно вызывать у кубитов состояние считывания, разрушить отдельные связи и исказить весь процесс вычисления.
Создать абсолютно – или хотя бы относительно – устойчивую систему даже из двух запутанных кубитов физикам пока не удалось. Ученые-кибернетики разработали специальные методы квантовой коррекции ошибок, которые позволяют строить алгоритмы, способные корректно работать с довольно приличным количеством связей. А вот как поддерживать все эти многочисленные связи в системе хотя бы из двух десятков кубитов, мы пока не знаем. Не исключено, что большие запутанные квантовые системы просто обязаны разрушаться через некоторое время, подчиняясь законам природы; с другой стороны, проблема может носить и чисто технический характер. Будем надеяться, физики с этим когда-нибудь разберутся.
Существуют и другие способы организовать вычисления при помощи квантовых явлений: это адиабатические процессы и квантовый отжиг. Впрочем, они тоже обладают целым рядом технических и мощностных ограничений. Канадская компания D-Wave заявила о создании адиабатических компьютеров, однако ученые пока не уверены, что они работают лучше обычных.
Если мы даже и построим мощные квантовые компьютеры, они все равно будут довольно узко специализированы. Для разложения чисел на множители и эмуляции физических систем они, конечно, подойдут; с их помощью можно будет взламывать шифры и разгадывать тайны вселенной, однако они не дадут нам ключ к решению NP-полных задач и не заставят Excel работать быстрее.
Квантовая криптография
Большинство рассмотренных в предыдущей главе алгоритмов шифрования базируются на предположении, что задача факторизации является вычислительно трудной. Если же под рукой у вас имеется квантовый компьютер, то любой из этих шифров взламывается алгоритмом Шора, раскладывающим числа на множители. Конечно, пока это только фантазия, которая, однако, имеет все шансы превратиться в реальность. Для защиты от квантовых криптографических атак можно было бы попытаться разработать новые протоколы шифрования, основанные на особо трудоемких задачах, не укладывающихся в «любимые» квантовыми компьютерами алгебраические структуры. Однако ученые придумали другой способ: шифрование при помощи квантовой механики.
Возможность копировать данные воспринимается нами как должное. Функции копирования и вставки сейчас есть почти в каждой программе. Мы можем сохранить один и тот же файл в разных папках и на разных машинах, можем создать резервную копию данных на жестком диске или в облаке. Иногда все эти многочисленные экземпляры нам даже мешают – очень трудно, к примеру, удалить свои персональные данные и электронный адрес так, чтобы о них больше не осталось ни единого упоминания.
А вот квантовые биты копированию не поддаются. Ведь чтобы скопировать кубит, его нужно хотя бы частично измерить, т. е. выполнить наблюдение, которое сразу превратит его в обычный бит с двумя значениями. Предположим, Джордж отсылает Гарри кубит информации, а Эрик его перехватывает. Если Эрик попытается скопировать или прочитать кубит, тот сразу же примет вид обычного бита. Безопасность обеспечена, вот только для организации переписки этого явно недостаточно: ведь когда Гарри начнет читать сообщение, он тоже увидит лишь обычный бит.
В 1979 году в Пуэрто-Рико проходила важнейшая международная конференция по проблемам теоретической информатики – IEEE Symposium on Foundations of Computer Science. Среди участников был Жиль Брассард из Монреальского университета. Когда он после очередного заседания плескался в океане, его разыскал Чарльз Беннет. Знакомство вылилось в плодотворное сотрудничество; вместе ученые придумали, как при помощи квантовых битов можно создавать системы шифрования с доказуемой криптостойкостью. Допустим, Джордж отсылает Гарри длинную последовательность кубитов, содержащую секретный ключ для шифрования дальнейшей переписки. Любой злоумышленник, перехвативший это сообщение, разрушит все кубиты, как только попытается их прочитать или скопировать. Беннет и Брассард разработали метод, позволяющий при помощи дополнительного обмена информацией по квантовым и классическим каналам либо успешно передать секретный ключ, либо установить, что сообщение было скомпрометировано (в этом случае можно попытаться еще раз).
Впрочем, у нового протокола имелись некоторые ограничения. При передаче данных возникали ошибки; из-за этого число кубитов приходилось увеличивать, и в результате злоумышленники получали шанс похитить часть данных, оставшись незамеченными. В целях борьбы с подобными проблемами исходный вариант протокола неоднократно дорабатывался и усложнялся.
В отличие от случая с квантовыми вычислениями, в протоколе Беннета–Брассарда квантовая запутанность не применяется. Вероятно, поэтому квантовые криптосистемы средней мощности уже реализованы. В Лос-Аламос, к примеру, сообщения успешно отправлялись по оптоволоконному кабелю почти на 150 километров, а между Канарскими островами – по воздушному каналу примерно на 140 километров. Не исключено, что когда-нибудь квантовые технологии позволят нам пересылать не поддающиеся взлому сообщения даже через спутник.
Почему бы нам всем уже сейчас не перейти на квантовое шифрование? Дело в том, что на текущий момент квантовые криптосистемы находятся на стадии тестирования; они дорого стоят, часто ошибаются, да и скорость передачи данных у них не велика. Слабое место в них – не сами шифры: главную опасность представляют «дыры» в реализации. Вероятность разработать здесь «дырявый» протокол ничуть не меньше (а может, даже больше), чем в случае с обычными криптосистемами. Кроме того, неясно, как обеспечить передачу данных через интернет, где информация по пути к адресату многократно перекидывается от одного сервера к другому. Впрочем, пока современные системы шифрования могут спать спокойно: вряд ли в ближайшем будущем появятся квантовые или еще какие-нибудь хитрые компьютеры, способные эффективно разложить число на множители.
Квантовая телепортация
В 1996 году компания IBM анонсировала новое направление исследований. На форзаце февральского номера журнала Scientific American появилась двухстраничная реклама.
«Она годами делилась рецептами с другом из Осаки. Она познакомила его с сотней способов применения паприки. В ответ он раскрыл ей тайну своего восхитительного сукияки. Однажды Сейджи получил от Маргит письмо: „Никуда не уходи. Я сейчас телепортирую тебе гуляш“. Конечно, Маргит несколько поторопилась, но мы уже над этим работаем. Специалисты IBM создали ряд технологий, при помощи которых можно обратить некий объект в пыль, а затем в целости и сохранности воссоздать его в другом месте. И это вовсе не сказка: сделанное открытие затронет все сферы человеческой деятельности, от разработки компьютеров до освоения космоса. Умные ребята – вот только голубцы готовить не умеют. Пока».
