Математики, шпионы и хакеры. Кодирование и криптография

От бита к кубиту

Какая, однако, связь между суперпозицией состояний частиц и вычислениями, не говоря уже о криптографии? До 1984 г. никто даже не думал о связи между этими двумя областями. Примерно в то же время британский физик Дэвид Дойч выступил с революционной идеей: а что было бы, если бы компьютеры подчинялись законам квантовой механики, а не классической физики? Как повлиял бы принцип суперпозиции состояний частиц на вычисления?

Напомним, что обычные компьютеры обрабатывают минимальные единицы информации, называемые битами, допускающими два взаимоисключающих значения: 0 и 1. Квантовый компьютер, с другой стороны, в качестве минимальной единицы информации мог бы работать с частицей, находящейся в двух возможных состояниях. Например, спин электрона может быть направлен либо вверх, либо вниз. Такая частица будет иметь фантастическое свойство: представлять значение 0 (спин вниз) или значение 1 (спин вверх). По принципу суперпозиции состояний она может представлять оба значения одновременно. Эта новая единица информации получила название кубит (сокращение от «квантовый бит»), и работа с такими единицами открывает двери в мир супермощных компьютеров.

Обычный компьютер выполняет вычисления последовательно. Возьмем в качестве примера цифровую информацию, содержащуюся в 32 битах. С таким количеством битов мы можем закодировать числа от 0 до 4292967295. Обычный компьютер, чтобы найти определенное число из этой группы, должен будет перебирать бит за битом. Однако квантовый компьютер может выполнить задачу гораздо быстрее.

Чтобы проиллюстрировать это, представим, что в специальном контейнере находятся 32 электрона в суперпозиции состояний. Применяя достаточно сильные электрические импульсы, мы можем изменить спин электрона сверху вниз. Тогда эти 32 электрона — кубиты нашего квантового компьютера — будут представлять все возможные комбинации спина вверх (1) и спина вниз (0) одновременно. В результате поиск нужного числа выполняется за один раз, так как находит все возможные варианты. Если мы увеличим количество кубитов до, например, 250, количество одновременных операций, которые могут быть выполнены, составит примерно 10⁷⁵ — чуть больше, чем предполагаемое число атомов в нашей Вселенной.

Работы Дойча доказали, что квантовые компьютеры теоретически возможны.

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

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

* * *

Конец криптографии?

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

Эта операция чрезвычайно трудоемкая, и пока не существует математической лазейки для ее решения. Может ли квантовой компьютер взять на себя задачу разложения числа на простые числа, которые использует шифр RSA? Американский ученый Питер Шор в 1994 г. дал на этот вопрос утвердительный ответ. Шор разработал алгоритм для квантового компьютера, способный разложить большие числа на множители за намного меньшее время, чем самый мощный обычный компьютер.

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

Одной из основ квантовой механики является принцип неопределенности, открытый Вернером Гейзенбергом в 1927 г. Хотя его точная формулировка очень сложна, сам Гейзенберг обобщил его следующим образом: «Мы в принципе не можем знать настоящее во всех подробностях». Более точно: невозможно определить с любой степенью точности те или иные свойства частицы в любой момент времени. Возьмем, например, частицы света (фотоны). Одной из их основных характеристик является поляризация — технический термин, связанный с колебаниями электромагнитных волн. [Хотя фотоны поляризованы во всех направлениях, в нашем примере мы будем считать, что они имеют поляризацию четырех типов: вертикальную

, горизонтальную , по диагонали слева направо вниз , по диагонали слева направо вверх . Принцип Гейзенберга утверждает, что для определения поляризации фотона нужно пропустить его через фильтр, или «щель», которая, в свою очередь, может быть горизонтальной, вертикальной и диагональной: слева направо вниз или слева направо вверх. Фотоны, поляризованные горизонтально, пройдут горизонтальный фильтр без изменений, а поляризованные вертикально этот фильтр не пройдут. Что касается фотонов, которые поляризованы по диагонали, то половина из них пройдет через этот фильтр, поменяв поляризацию с диагональной на горизонтальную, а другая половина этот фильтр не пройдет. Это будет происходить случайным образом. Более того, после того как фотон пройдет фильтр, невозможно будет с уверенностью сказать, какова была его первоначальная поляризация.

Если мы пропустим ряд фотонов с различной поляризацией через горизонтальный фильтр, то увидим, что половина фотонов, поляризованных по диагонали, пройдет через фильтр, поменяв поляризацию на горизонтальную.

Какова связь между поляризацией фотонов и криптографией? Очень существенная, как мы увидим ниже. Для начала представим себе исследователя, который хочет определить поляризацию ряда фотонов. Для этого он выбирает фильтр с фиксированной ориентацией, например, горизонтальный. Предположим, что фотон прошел через фильтр. Какой вывод может сделать наш исследователь? Конечно, он может сказать, что исходная поляризация фотона не была вертикальной. А может он сделать другие предположения? Нет. Казалось бы, можно подумать, что более вероятно, что этот фотон был поляризован по горизонтали, а не по диагонали, потому что половина фотонов, поляризованных по диагонали, не проходит через фильтр.