Золотой билет

В 1982 году лауреат Нобелевской премии по физике Ричард Фейнман обратил внимание на тот факт, что простого способа смоделировать работу квантовой системы на цифровом компьютере не существует. Из проблемы родилась идея: а что, если вычислительные устройства, основанные на принципах квантовой механики, будут работать намного эффективнее обычных компьютеров?

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

Квантовый видеорекордер

Том живет в Бостоне и, конечно, болеет за «Ред Сокс». Днем его любимая команда принимала Нью-Йоркских «Янкиз»; Том был на работе и специально не читал бейсбольные новости. Вернувшись домой, он заказал пиццу, включил телевизор и начал смотреть игру, которая к тому моменту уже давно закончилась. На исходе девятого иннинга у хозяев были заняты вторая и третья база, два игрока были в ауте и один в рандауне. Отбивающий Брайан Хаммер побежал к «дому». Том напряженно замер в надежде, что его команда получит очко, – и вдруг одернул себя: эфир-то не прямой! Очко уже либо заработано, либо нет, только Тому пока об этом не известно. Для него исход по-прежнему не определен: не победа и не поражение, а что-то между ними. Результат игры он узнает чуть позже.

Реальность для Тома определяется тем, что он видит. Он смотрит последний иннинг – а значит, в его мире еще никто не победил. Матч продолжается; и пока не закончится последний розыгрыш, он так и будет находиться в промежуточном состоянии между победой «Ред Сокс» и их поражением.

Сьюзен – ярый фанат «Янкиз». Она тоже записала игру и теперь, как и Том, смотрит ее в оффлайн-режиме и гадает, заработает ли Хаммер победное очко. Для Сьюзен, как и для Тома, результат игры еще не определен; он случаен – ровно до того момента, пока Сьюзен не услышала финальный свисток.

Том и Сьюзен одновременно наблюдают разные случайные события, находясь в 200 милях друг от друга. И все же результат они увидят совершенно одинаковый. И для Тома, и для Сьюзен Хаммер либо заработает победное очко, либо не заработает. Не может быть такого, чтобы в мире Тома Хаммер заработал очко, а в мире Сьюзен – нет. Исход игры никто из зрителей пока не знает, однако оба уверены, что в конце увидят на табло один и тот же счет. Результаты событий, отражаемых на экранах телевизоров Тома и Сьюзен, каким-то загадочным образом связаны друг с другом.

Вы спросите, причем здесь квантовые вычисления? В классических цифровых компьютерах основной логической единицей является бит, или двоичная цифра (от англ. bit – binary digit). Каждый бит может принимать ровно два значения, например – истина и ложь, или победа и поражение. Базовый элемент квантовых компьютеров – это кубит, или квантовый бит (от англ. qubit – quantum bit). В отличие от бита, который всегда принимает одно из двух пограничных значений, кубит может находиться в некотором промежуточном состоянии, называемом суперпозицией.

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

Квантовые биты могут быть определенным образом связаны, или запутаны, – например, так, что при каждом измерении они будут приходить в одно и то же состояние. Нечто подобное происходит и при просмотре записанных на телевизор бейсбольных игр.

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

Состояние бейсбольного матча «ходит» вдоль одной оси: это просто вероятность того или иного исхода.

Рис. 9.1. Бостонская команда

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

Состояния кубита образуют окружность с центром в точке пересечения осей «Истина» и «Ложь».

Рис. 9.2. Кубиты

В данном случае звездочка перемещается по двумерной траектории. На рис. 9.2 ее текущие координаты – 0,55 по «Истине» и 0,84 по «Лжи». Координаты вполне могут быть и отрицательными: к примеру, смайлик находится в точке (-0,71; -0,71). Квантовые компьютеры вращают и переворачивают эти окружности и таким образом управляют состояниями кубитов.

Одному кубиту соответствует окружность на плоскости. Двум кубитам требуется четырехмерная окружность; нарисовать ее здесь или даже просто представить в уме было бы довольно затруднительно. В системе из тридцати кубитов размерность пространства будет более триллиона.

Все это наводит на мысль использовать квантовые компьютеры для решения NP-задач. Допустим, нам нужно найти клику размера 50 среди 20000 жителей Королевства. Имея около 500 кубитов, мы сможем воспроизвести сразу все группы размера 50, которые будут обрабатываться параллельно; чтобы отметить клику, квантовый компьютер выполнит определенную последовательность вращений и переворотов.

В результате система придет в квантовое состояние, представляющее собой совокупность приблизительно из 3 × 10¹⁵⁰ (т. е. 3 и 150 нулей) групп, часть которых отмечены как клики. Если мы научимся эффективно «вытаскивать» из квантовых состояний информацию о кликах, то получим быстрый квантовый алгоритм для поиска клики, а также для всех остальных NP-полных задач. Считывая квантовое состояние системы (т. е., в некотором роде, наблюдая за окончанием игры), мы видим лишь один исход, в данном случае – одну группу жителей; маловероятно, что именно эта группа окажется кликой.

Нам нужно научиться как-то выделять искомые клики, чтобы при считывании квантового состояния они попадались нам с большей вероятностью. Сделать это можно при помощи квантовых манипуляций с кубитами. Правда, при грубом подходе манипуляций потребуется столько же, сколько и групп, т. е. примерно 3 × 10¹⁵⁰, и все преимущества квантовых вычислений будут сведены на нет. В 1996 году сотрудник Лабораторий Белла в Нью-Джерси Лов Гровер разработал «умный» квантовый алгоритм, который мог обнаружить клику в Королевстве «всего» за 2 × 10⁷⁵ квантовых шагов. Однако даже при скорости триллион операций в секунду на это ушло бы в пять раз больше времени, чем живет наша вселенная.

Уже доказано, что при решении 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 появилась двухстраничная реклама.

Рис. 9.3. Реклама IBM. Публикуется с разрешения IBM

Что же это за волшебный процесс, которым так хвалится журнал? К гуляшу и кубитам он прямого отношения не имеет, хотя квантовый бит действительно умеет исчезать из одного места и появляться в другом, прямо как в сказке. В рекламе речь идет об открытии, сделанном в 1993 году Чарльзом Беннетом и его коллегами по IBM, среди которых был и Жиль Брассард. Вместе с квантовой криптографией ученые подарили миру и квантовую телепортацию.

Допустим, у Артура есть кубит, который нужно переправить Гарриет. Как это сделать лучше всего?

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

Рис. 9.4. Кубит

Альтернативный вариант – отправить Гарриет параметры кубита (-0,55 по «Истине» и 0,84 по «Лжи»), чтобы она могла воссоздать его у себя. Правда, эти параметры должны быть Артуру заранее известны: в противном случае получить он их никак не сможет, поскольку любое измерение разрушит квантовое состояние кубита.

Беннет с коллегами разработали метод, при помощи которого Артур сможет спокойно передать Гарриет свой кубит. Для этого лишь нужно будет выполнить некоторые предварительные действия, а именно – сцепить пару кубитов.

На рис. 9.5 кубиты с сердечками надлежащим образом запутаны. Один из них находится у Артура, другой – у Гарриет. Если Артур измерит состояние своего кубита, он с одинаковой вероятностью увидит либо ноль, либо единицу. Но если он увидит ноль, то и Гарриет увидит ноль, а если он увидит единицу, то и Гарриет тоже увидит единицу (прямо как с бейсбольными играми).

Рис. 9.5. Сцепленные кубиты

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

Полученные биты Артур отсылает Гарриет. Один из них несет информацию о том, нужно ли Гарриет вращать кубит, другой – нужно ли его переворачивать. Гарриет выполняет необходимые действия, и… та-дам! Ее кубит приходит в то же состояние, в котором изначально находился кубит Артура. Ловкость рук – и никакого мошенничества! Верится с трудом, однако схема работает.

А что же стало с кубитами Артура? После измерения их квантовые состояния разрушились. По-другому и быть не могло – иначе у кубита Артура образовался бы клон, а это противоречит квантовым законам.

Пока Артур проводит квантовые манипуляции и измеряет состояния своих кубитов, с кубитом Гарриет не происходит ровно ничего, хотя он и сцеплен с кубитом Артура. Если бы Артур мог влиять на состояние кубита Гарриет, это означало бы, что он умеет передавать информацию мгновенно, быстрее скорости света, однако по законам физики это невозможно.

Кубит Гарриет является, по сути, двойником кубита Артура, только расположен он в пространстве немного по-другому. Благодаря двум полученным от Артура битам Гарриет сумеет привести его в искомое положение. Эти маленькие биты волшебным образом помогут ей воссоздать исходный кубит, хотя она так и не узнает, какие именно манипуляции проводил с кубитами Артур.

Рис. 9.6. Кубит

Вы спросите, как все это связано с гуляшом и с чудесными транспортерами из сериала «Звездный путь»? Давайте посмотрим, как можно организовать транспортер, выполняющий квантовую телепортацию. Допустим, я хочу телепортироваться из Чикаго в Токио и обращаюсь в специализированную компанию. Они создают запутанную квантовую систему из внушительного числа кубитов. Часть кубитов, соблюдая все возможные меры предосторожности, доставляют в Чикаго, остальные – в Токио. В Чикаго меня вместе с кубитами помещают в специальную камеру; описать мое состояние нужно очень точно, поэтому кубитов должно быть достаточно много. Нас вращают в многомерном пространстве, измеряют, и в результате мы все превращаемся в обычные нули и единички. Полученную кучу битов передают в токийский филиал, где с ними в такой же камере производят необходимые вращения. Потом камеру открывают, и я выхожу. Вот это да!

Использованные кубиты – отработанный материал. Если я решу вернуться, или нужно будет телепортировать кого-то еще, понадобится новая система запутанных кубитов. Кстати, с самолетами дело обстоит примерно так же: на обратном пути невозможно повторно воспользоваться израсходованным топливом.

Впрочем, это еще не самое страшное. Главная проблема – сохранить все зависимости между кубитами. Чтобы описать меня, требуется порядка миллиона миллиардов триллионов сцепленных кубитов: примерно столько атомов содержится в человеческом теле. И это еще довольно оптимистичная оценка, поскольку на деле кубитов, вероятно, понадобится намного больше. Ведь достаточно потерять каких-нибудь две-три связи (которые охотно разрушаются при малейшем взаимодействии с окружающей средой) – и из камеры вывалится порядком изуродованная, а то и вовсе неживая версия меня. Поэтому – только после вас. Я уж лучше по старинке, на самолете. Встретимся на месте!

Квантовое будущее

Ряд ученых полагают, что теорию вычислений пора переводить на квантовый уровень. Пусть кванты и не позволят нам решать NP-полные задачи, однако с их помощью можно будет эмулировать физические системы, а это значительно приблизит нас к пониманию сущности материи, космоса и даже человеческого мозга. Мир увидит такие научные открытия, которые сейчас не в состоянии даже вообразить!

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

Что же может послужить очередным толчком в развитии вычислений? Какие еще грандиозные вычислительные задачи требуют нашего внимания? Читайте дальше – и вы все узнаете.