Лэнс Фотноу - Золотой билет
Новый этап в развитии криптографии, начало которому в семидесятых годах положили Диффи и Хеллман, привел нас к криптографическим протоколам, базирующимся на практической неразрешимости некоторых задач. Чемпионы по кроссвордам, великие шахматисты и талантливые математики уже не способны были разгадывать шифры силой своего интеллекта.
Впрочем, игра в кошки-мышки по-прежнему продолжается. Современные мошенники уже не взламывают сами шифры, а ищут уязвимые места в системе. В протоколе, которым пользуются Элис и Боб, числа могут оказаться недостаточно случайными. В операционной системе или браузере могут найтись дефекты, позволяющие хакеру проникнуть в компьютер. Злоумышленники могут обмануть Элис и заставить ее сообщить секретный ключ. А придумав ненадежный пароль, Элис сама поставит себя под удар.
Помимо зашифрованного текста, хакеры анализируют самую разнообразную информацию – к примеру, время шифрования, которое для разных сообщений может отличаться. Еще вариант – вывести из строя часть системы, как в случае с расплавленной в микроволновке смарт-картой, и надеяться, что сбои приведут к потере конфиденциальности.
Никакой, пусть даже самый стойкий шифр не гарантирует стойкость всей системы; не исключено, что абсолютно надежный протокол мы так и не создадим.
Глава 9. Его величество квант
В 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 × 10150 (т. е. 3 и 150 нулей) групп, часть которых отмечены как клики. Если мы научимся эффективно «вытаскивать» из квантовых состояний информацию о кликах, то получим быстрый квантовый алгоритм для поиска клики, а также для всех остальных NP-полных задач. Считывая квантовое состояние системы (т. е., в некотором роде, наблюдая за окончанием игры), мы видим лишь один исход, в данном случае – одну группу жителей; маловероятно, что именно эта группа окажется кликой.
Нам нужно научиться как-то выделять искомые клики, чтобы при считывании квантового состояния они попадались нам с большей вероятностью. Сделать это можно при помощи квантовых манипуляций с кубитами. Правда, при грубом подходе манипуляций потребуется столько же, сколько и групп, т. е. примерно 3 × 10150, и все преимущества квантовых вычислений будут сведены на нет. В 1996 году сотрудник Лабораторий Белла в Нью-Джерси Лов Гровер разработал «умный» квантовый алгоритм, который мог обнаружить клику в Королевстве «всего» за 2 × 1075 квантовых шагов. Однако даже при скорости триллион операций в секунду на это ушло бы в пять раз больше времени, чем живет наша вселенная.
Уже доказано, что при решении NP-полных задач на квантовом компьютере алгоритм Гровера в общем случае дает наилучший результат, поэтому квантовые алгоритмы вряд ли позволят приравнять классы P и NP. Если физики когда-нибудь и построят полноценные квантовые компьютеры, самые трудные проблемы все равно окажутся им не по зубам.
